Snake Permutations And Their Number

Problem

Snake Permutations And Their Number

Solution

The snakes Arnold inequired about are commonly called "up-down" to differentiate from "down-up" ones in the form $x_1\gt x_2\lt x_3\gt x_4\lt x_5\gt\ldots.$ The number of "up-down" snakes is usually denoted as $A_n$ and that of the "down-up" ones as $B_n.$

There is a $1-1$ correspondence between the up-down and down-up snakes. The correspondence is defined via the reflection function $f(a)=n+1-a.$ In particular, $A_n=B_n$ and it is often more convenient to compute $2A_n=A_n+B_n$ than just $A_n.$

The known recurrence formula $\displaystyle 2A_n=\sum_{k=1}^{n-1}{n-1\choose k-1}A_{k-1}A_{n-k}$ could be explained in the following manner:

Given a snake permutation of either kind, let the largest element (which is $n)$ occupy position $k.$ In front of it, there is a snake of $k-1$ elements which, depending on the parity of $k,$ is either up-down or down-up. Regardless, the total number of such snakes is $A_{k-1}.$ There are $\displaystyle {n-1\choose k-1}$ variants to fill the $k-1$ position. On the other hand, following $n$ in the position $k,$ there's is a down-up (because $n$ is the largest element) snake of length $n-k.$

Using the recurrence (and setting $A_1=1$ and checking the obvious $A_2=1)$ we get the sequences:

$A_1=1,A_2=1,A_3=2,A_4=5,A_5= 16,\\A_6=61,A_7=272,A_8=1385,A_9=7936,A_{10}=50521.$

Acknowledgment and References

This is problem 47 from V. Arnold's brochure Problems for children from 5 to 15.

As there was an earlier discussion on a similar problem, I made a web search that showed that the problem was well known and well studied. "Snakes" looks like a semi-official name, with "up-down" (and, to distiguish, "down-up"), "zig-zag" or "alternate" being more common. The difference between "up-down" and "down-up" is in the meaning of the first inequality, $"\lt"$ or $"\gt",$ respectively.

The problem of enumeration of snake permutations is named after D. André who worked on that in 1870-1880s; see sequence A000111 at the Online Encyclopedia of Integer Sequences.

The problem has been posted as 4755 in the Am Math Monthly by C. Davis (1956, p 596) and solved by W. J. Blundon (1957, 533-534).

It was also studied by Harold Reiter at the Canadian Crux Mathematicorum (1999, v 25, n 1, 33-46, Counting Snakes, Differentiating the Tangent Function, and Investigating the Bernoulli-Euler Triangle.

 

[an error occurred while processing this directive]

|Contact| |Front page| |Contents| |Probability|

Copyright © 1996-2018 Alexander Bogomolny
[an error occurred while processing this directive]
[an error occurred while processing this directive]