Snake Permutations And Their Number
Problem
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}{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.
- What Is Probability?
- Intuitive Probability
- Probability Problems
- Sample Spaces and Random Variables
- Probabilities
- Conditional Probability
- Dependent and Independent Events
- Algebra of Random Variables
- Expectation
- Probability Generating Functions
- Probability of Two Integers Being Coprime
- Random Walks
- Probabilistic Method
- Probability Paradoxes
- Symmetry Principle in Probability
- Non-transitive Dice
|Contact| |Front page| |Contents| |Probability|
Copyright © 1996-2018 Alexander Bogomolny71493613