Alternating permutation

In combinatorial mathematics, an alternating permutation of the set {1, 2, 3, ..., n} is an arrangement of those numbers into an order c₁, ..., c_n such that no element c_i is between c_i - 1 and c_i + 1 for any value of i and c₁< c₂. In other words, c_i < c_i+ 1 if i is odd and c_i > c_i+ 1 if i is even. For example, the five alternating permutations of {1, 2, 3, 4} are:

• 1, 3, 2, 4       because       1 < 3 > 2 < 4
• 1, 4, 2, 3       because       1 < 4 > 2 < 3
• 2, 3, 1, 4       because       2 < 3 > 1 < 4
• 2, 4, 1, 3       because       2 < 4 > 1 < 3
• 3, 4, 1, 2       because       3 < 4 > 1 < 2

This type of permutation was first studied by Désiré André in the 19th century.