Up, Down, Up

Worked solution

**Answer: 272.** Let A(n) count such zigzags of odd length n (starting with a rise, ending with a fall). The largest number 7 must sit at a peak, an even position 2j. Everything to its left is a zigzag of odd length 2j − 1 of the same type (it starts with a rise and, because position 2j − 2 is a peak, ends with a fall), and the same holds to its right with odd length 7 − 2j. The left and right parts use any split of the other six numbers. Hence A(n) = Σ_j C(n − 1, 2j − 1) A(2j − 1) A(n − 2j), with A(1) = 1. So A(3) = 2·1·1 = 2, A(5) = 4·1·2 + 4·2·1 = 16, and A(7) = 6·1·16 + 20·2·2 + 6·16·1 = 96 + 80 + 96 = 272. These are André's tangent numbers: the coefficients of tan x = x + 2x³/3! + 16x⁵/5! + 272x⁷/7! + ...