Mathematics desk
< June 19	<< May \| June \| Jul >>	June 21 >

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

June 20

New problem

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]