Jump to content

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

From Wikipedia, the free encyclopedia
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]