Wikipedia:Reference desk/Archives/Mathematics/2021 June 20

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

edit

New problem

edit

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 Zn = {0,1,...,n−1} (the integers modulo n), each valid arrangement is a permutation π such that π(i+1) ≠ π(i)+1. This is OEISA167760. There is a link there to a table up to f449. Clearly, fn is always a multiple of n, so we can also look at the sequence an = fn/n. This is OEISA000757.  --Lambiam 21:01, 20 June 2021 (UTC)[reply]