3
$\begingroup$

For $n \ge 3,$ Let $C_n$ be the cycle graph $(1,2,\cdots n)$ [where $n$ joins back to $1.$] Also let the distance $d(a,b)$ between two nodes $a,b$ be the lesser of $a-b$ mod $n$ and $b-a$ mod $n$. Thus for $n=10$ we have $d(1,10)=1,$ and also for example $d(3,9)=4.$

I'm trying to count the number $f(n)$ of permutations of $\{1,\cdots,n\}$ for which no element is moved more than $1$ unit from where it starts. This means that of course the identity works, as well as the complete cycle $C(n)$ and its inverse. Also one may select any collection of pairwise disjoint "adjacent" 2-cycles, these being $(1,2),(2,3), \cdots (n-1,n),(n,1),$ and together these form an acceptable permutation (viewed as a product of disjoint 2-cycles).

I have fairly carefully looked at the cases $3 \le n \le 9$ and found that for these we have $f(n)=L_n+2$ where $L_n$ is the $n$th Lucas number which are those in the list $1,3,4,7,11,\cdots,$ index starting at $1.$ Thus $f(3)=4+2=6,$ not surprising as in this case all nodes are at distance $\le 1$ fom each other. The next is $f(4)=9,$ which one can check on paper. As $n$ increases, it becomes more difficult to keep track of the count.

If someone has access to software which computes the permament of a matrix, then a program could be written to check my conjecture... not much support so far only up to 9.

I've had no success relating $f(n)$ to its previous 2 values, mainly since I don't see how to relate the counts on cycles whose lengths differ by 1 or 2. Thanks for any insight.

$\endgroup$

2 Answers 2

Reset to default
3
$\begingroup$

Consider your $n$ transpositions. Label them by the least element, so you get the set $\{1,...,n\}$. How many subsets are there with no adjacent numbers? Call this $A_n$.

Such a set either contains $n$ or it doesn't. There are clearly $A_{n-1}$ of the second kind. Elements of the first kind may not contain $n-1$ nor $1$, so there are $A_{n-2}$ of them.

Therefore, $A_n=A_{n-1}+A_{n-2}$.

Plus, you have the full cycle and its inverse, so the number you want is $A_n+2$.

$\endgroup$
2
  • $\begingroup$ Note the recursion doesn't work until $n=5.$ That is, in your notation, $A_n=A_{n-1}+A_{n-2}$ doesn't hold until $n \ge 5.$ [Note that $A_2=2,A_3=4,A_4=7. $\endgroup$ Commented Aug 28, 2018 at 1:17
  • 1
    $\begingroup$ Yes, some care must be taken with the initial conditions, because the full cycle and its inverse must be considered for small $n$. But this should be easy. Let me know if you need more help. $\endgroup$ Commented Aug 28, 2018 at 17:18
1
$\begingroup$

Just like the Fibonacci numbers give the number of ways to tile an $n\times 1$ grid of squares with square and domino tiles, the Lucas numbers count the number of ways to tile an annulus divided into $n$ equal sections with rounded "square" and "domino" tiles. This tiling question is equivalent to your problem.

To prove this, condition on the "last" tile in the circle. Numbering the sectors clockwise from $1$ to $n$, the "first" tile is the one covering sector $1$, while the "last" tile is anti-clockwise adjacent to the first. Deleting the last tile, and contracting the circle to fill the gap, you get a tiling of either an $n-1$ or $n-2$ sector annulus. If the last tile does not cover square $n$, then you will have to renumber sector $n$ after the deletion, so the sectors are still numbered $1$ to $k$, where $k=n-1$ or $n-2$. A little thought shows this is a bijection from $n$-tilings to the disjoint union of $(n-1)$-tilings and $(n-2)$-tilings when $n\ge 3$, proving $$ f(n)=f(n-1)+f(n-2)\tag{$n\ge 3$} $$ Combined with the base cases $f(1)=1$, $f(2)=3$, this shows $f$ agrees with a shift of the Lucas numbers.

$\endgroup$
3
  • $\begingroup$ I'll need to digest this. But it looks good... $\endgroup$ Commented Aug 27, 2018 at 23:14
  • $\begingroup$ I don't follow why $f(2)=3.$ That's why I assumed $n \ge 3.$ Also I think one needs to ignore the two long cycles in order to do a domino argument. And do you mean to tile an annulus rather than a torus? $\endgroup$ Commented Aug 28, 2018 at 1:20
  • $\begingroup$ Yes, I made a lot of mistakes. I think their is enough info here to deduce the recursion equation $f(n)=f(n-1)+f(n-2)$, which holds for large enough $n$, but I will not try to fix this answer as there is a better one already. $\endgroup$ Commented Aug 28, 2018 at 3:41

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.