Adjacent coprime Permutations

Number Theory Level 5

How many 10-element permutations of the set $\{1,2,\dots,10\}$ have the following property? Given a specific permutation $p_1,p_2,\dots,p_{10}$ , for each element $p_i$ , $\gcd(p_i,p_{i+1})=\gcd(p_i,p_{i-1})=1$ . Note that we do not want to have a circular permutation, therefore, the relative status of the first and the last elements of a permutation is of zero importance here.

The answer is 22032.

1 solution

A Former Brilliant Member
Feb 26, 2019

I am hoping for a better solution, however, a hint on the ugly approach is included below.

There are two types structures (mutually exclusive cases) to take into account (otherwise, we are going to have two even integers next to each other).

1- The sequence structure with alternating even and odd terms, like below.

$e,o,e,o,e,o,e,o,e,o$

and

$o,e,o,e,o,e,o,e,o,e$

for the first case, we have the symmetry between the two cases, so we can count the possibilities for one and multiply the result by 2. We know that $(10,5)$ , $(3,6)$ , and $(6,9)$ cannot be adjacent. So, we use Inclusion-Exclusion Principle to calculate:

2- The sequence structure with alternating even and odd terms, expect at one point where two odds are next to each other.

$e,o,o,e,o,e,o,e,o,e$

and

$e,o,e,o,o,e,o,e,o,e$

and

$e,o,e,o,e,o,o,e,o,e$

and

$e,o,e,o,e,o,e,o,o,e$

Same as case 1 is done here and the results are added to give $22032$

Adjacent coprime Permutations

The answer is 22032.

1 solution

0 pending reports