June 20 Information

Can anyone find the sequence with this rule:

Find the number of ways to arrange the numbers 1 to n so that a and a+1 (or n and 1) will never occur in positions b and b+1 (or n and 1.)

For n=2, there are none. (This makes it clear that f(2) = 0.

For n=3, we have 2,1,3; 1,3,2; and 3,2,1. So f(3) must be 3.

For n=4, we have:

• 1,4,3,2
• 2,1,4,3
• 3,2,1,4
• 4,3,2,1

So f(4) must be 4.

For n=5, there's:

• 1,3,2,5,4
• 1,3,5,2,4
• 1,4,2,5,3
• 1,4,3,5,2
• 1,5,2,4,3
• 1,5,3,2,4
• 1,5,4,3,2
• All the above with each value 1 to 4 being replaced by one more and 5 being replaced by 1.

This means f(5) must be 35.

Anyone know the sequence to at least f(11)?? Georgia guy ( talk) 19:06, 20 June 2021 (UTC) reply

(You missed 1,3,5,4,2.) Working with Z_n = {0,1,...,n−1} (the integers modulo n), each valid arrangement is a permutation π such that π(i+1) ≠ π(i)+1. This is OEIS:  A167760. There is a link there to a table up to f₄₄₉. Clearly, f_n is always a multiple of n, so we can also look at the sequence a_n = f_n/n. This is OEIS:  A000757.  -- Lambiam 21:01, 20 June 2021 (UTC) reply