Problem 3 · Zigzag numbers
Combinatorics: up-down patterns with four distinct digits.
Integer answer, at most 4 digitsA positive integer is called a zigzag number if it satisfies the following three conditions:
- Its digits are nonzero and all different.
- It has no three consecutive digits in ascending order.
- It has no three consecutive digits in descending order.
For example, 14385 and 2917 are zigzag numbers but 2564 and 71544 are not. How many four-digit zigzag numbers are there?
Reasoned solution
Key idea: separate the choice of the set of digits from the choice of the order in which they appear.
The digits are $4$ distinct values from $\{1,\dots,9\}$: there are $\binom{9}{4}=126$ possible sets.
For a fixed set, look at the pattern of comparisons between consecutive digits ($\uparrow$ = up, $\downarrow$ = down; there are $3$ comparisons). Forbidding three increasing or decreasing consecutive digits means no two equal arrows in a row. The only valid patterns are therefore:
For $4$ fixed values $a