Help plz with counting
Find the number of ways of arranging the numbers 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 in a row so that the product of any two adjacent numbers is even or a mutliple of 3
There is a simple way of counting bad configurations, so an approach would be to count these and subtract from the total.
In a bad configuration, there is a pair of adjacent numbers whose product is neither even not a multiple of 3; that means that neither number is even or a multiple of 3 and this leaves us with 1,5 and 7. So a bad configuration is a permutation of 1,…,10 in which two adjacent numbers are 1,5,7.
We can construct these by first choosing a permutation of 2,3,4,6,8,9,10, and then inserting the three unwanted numbers. Let’s represent the chosen permutation as
−_−_−_−_−_−_−_−
where each _s is one of the 7 “good” numbers, and the −s are positions where 1,5,7 can be inserted. There are two classes of insertions:
Choose one of the −s and insert 1,5,7at that position, in any order. There are 8*6=48 ways to do it.
Choose one − to insert one of 1,5,7— this can be done in 8*3=24 ways. Now, choose one of the remaining −s, and insert the remaining two numbers in each of the two possible orders — this can be done in 7*2=14ways. Altogether, this yields 24*14=336 bad permutations.
So, each of the chosen permutations yields 48+336=384 bad configurations, so the total number of bad configurations is 384*7!.
Since the total number of configurations is 10!, the number of good configurations is 10!−384*7!=(10*9*8−384)*7!=336*7! = 1,693,440 arrangements.
