Putnam 2025, Problem A-5

Let \( n \) be an integer with \( n \geq 2 \). For a sequence \( s = (s_1, \ldots, s_{n-1}) \) where each \( s_i = \pm 1 \), let \( f(s) \) be the number of permutations \( (a_1, \ldots, a_n) \) of \( \{1, 2, \ldots, n\} \) such that \( s_i (a_{i+1} - a_i) > 0 \) for all \( i \). For each \( n \), determine the sequences \( s \) for which \( f(s) \) is maximal.

Solution:
The sequences \( s \) for which \( f(s) \) are maximal are the alternating sequences
\[
((-1)^i : i = 1, \ldots, n - 1), \quad ((-1)^{i+1} : i = 1, \ldots, n - 1).
\]
For convenience we permit the case \( n = 1 \), where the two sequences collapse to the empty sequence.

**First solution.** For a permutation \( (a_1, \ldots, a_n) \) of \( \{1, 2, \ldots, n\} \), we refer to the unique sequence \( (s_1, \ldots, s_{n-1}) \in \{\pm 1\}^{n-1} \) satisfying \( s_i(a_{i+1} - a_i) > 0 \) for all \( i \) as the *descent pattern* of \( (a_1, \ldots, a_n) \). In this language, \( f(s) \) counts permutations with descent pattern \( s \). For \( s \in \{\pm 1\}^{n-1} \), \( j \in \{1, \ldots, n\} \), let \( f(s, j) \) be the number of permutations \( (a_1, \ldots, a_n) \) with \( a_n = j \) having descent pattern \( s \), so that
\[
f(s) = \sum_{j=1}^n f(s, j).
\]
Writing \( -s \) for the sequence \( (-s_1, \ldots, -s_{n-1}) \), we have \( f(s, j) = f(-s, n + 1 - j) \) on account of the bijection
\[
(a_1, \ldots, a_n) \mapsto (n + 1 - a_1, \ldots, n + 1 - a_n).
\]
Let \( s_+ \in \{\pm 1\}^n \) be the sequence \( s \) with 1 appended. We then have
\[
f(s_+, j) = \sum_{i=1}^{j-1} f(s, i) \quad (j = 1, \ldots, n + 1) :
\]
a permutation \( (a_1, \ldots, a_n, j) \) has descent pattern \( s_+ \) if and only if \( a_n \in \{1, \ldots, j - 1\} \) and the permutation obtained from \( (a_1, \ldots, a_n) \) by subtracting 1 from each entry greater than \( j \) has descent pattern \( s \). In particular,
\[
f(s_+, j) \leq f(s_+, j + 1) \quad (j = 1, \ldots, n).
\]
Moreover, \( f(s_+, n + 1) = f(s) > 0 \). Let \( s_{++}, s_{+-} \in \{\pm 1\}^{n+1} \) be the sequence \( s_+ \) with \( +1 \) or \( -1 \) appended, respectively. By writing
\[
f(s_{++}, j) = \sum_{i=1}^{j-1} f(s_+, i), \quad f(s_{+-}, n + 3 - j) = \sum_{i=1}^{j-1} f(s_+, n + 2 - j + i)
\]
(using sign symmetry for the second equality) and noting that \( f(s_+, i) \leq f(s_+, n + 2 - j + i) \), we deduce that
\[
f(s_{++}, j) \leq f(s_{+-}, n + 3 - j) \quad (j = 1, \ldots, n + 2);
\]
moreover, the inequality is strict for \( 1 < j < n + 2 \).

Recurring forward, we deduce that for any sequence \( s \in \{\pm 1\}^{n-1} \) and any \( j \in \{1, \ldots, n - 1\} \) such that \( s_{j-1} = s_j = 1 \), the sequence \( t \in \{\pm 1\}^{n-1} \) with
\[
t_i = \begin{cases} 
s_i & i < j \\
-s_i & i \geq j 
\end{cases}
\]
satisfies \( f(s) < f(t) \). Since there are only finitely many sequences in \( \{\pm 1\}^{n-1} \), maximal sequences exist and cannot contain two consecutive equal entries; this proves the claim.

**Remark.** One can also reinterpret the proof of the inequality \( f(s) \leq f(t) \) without recursion, by exhibiting an explicit injective map from the sequences with descent pattern \( s \) to the sequences with descent pattern \( t \).

**Second solution.** (communicated by the Putnam graders) For a sequence \( s \in \{\pm 1\}^{n-1} \), define the set \( P \) of *peaks* of \( s \) to contain those \( i \in \{1, \ldots, n\} \) such that \( s_{i-1} = 1 \) if \( i > 1 \) and \( s_i = -1 \) if \( i < n \). Define the set \( V \) of *valleys* of \( s \) as the peaks of the negated sequence \( -s \). Then
\[
f(s) = \sum_{i \in P} \binom{n - 1}{i - 1} f(s_1, \ldots, s_{i-2}) f(s_{i+1}, \ldots, s_n) = \sum_{i \in V} \binom{n - 1}{i - 1} f(s_1, \ldots, s_{i-2}) f(s_{i+1}, \ldots, s_n),
\]
so
\[
2f(s) = \sum_{i \in P \cup V} \binom{n - 1}{i - 1} f(s_1, \ldots, s_{i-2}) f(s_{i+1}, \ldots, s_n) \leq \sum_{i=1}^n \binom{n - 1}{i - 1} f(s_1, \ldots, s_{i-2}) f(s_{i+1}, \ldots, s_n).
\]
Let \( t_n \) be the alternating sequence \( (1, -1, \ldots) \) of length \( n - 1 \) and define \( E_n := f(t_{n-1}) = f(-t_{n-1}) \); note that \( 2E_n = \sum_{i=1}^{n-1} \binom{n-1}{i-1} E_{i-1} E_{n-i} \). We now induct on \( n \) (again taking \( n = 1 \) as the base case). Suppose that \( n \geq 2 \) and, for any \( s \neq \pm t_k \) of length \( k \leq n - 2 \), we have \( f(s) < E_{k+1} \). Then for \( s \) of length \( n - 1 \),
\[
2f(s) \leq \sum_{i=1}^n \binom{n - 1}{i - 1} f(s_1, \ldots, s_{i-2}) f(s_{i+1}, \ldots, s_n) \leq \sum_{i=1}^n \binom{n - 1}{i - 1} E_{i-1} E_{n-i} = 2E_n,
\]
so \( f(s) \leq E_n \). Equality only occurs if \( P \cup V = \{1, \ldots, n\} \), which happens if and only if \( s = \pm t_{n-1} \).

**Remark.** This result is a theorem of Niven, who deduced it from a formula for \( f(s) \) for arbitrary \( s \), and independently de Bruijn (Permutations with given ups and downs, *Nieuw Archief voor Wiskunde*, 3/18(1) (1970), 61–65), who used the recursive approach described in the first solution. Beware that de Bruijn uses the term *signature* for what we call the *descent pattern*, but this risks confusion with the signature in the sense of group theory. A related concept in music theory is the *Parsons code*.

The maximal values of \( f(s) \) form OEIS sequence A000111 (variously called zigzag numbers, up/down numbers, or Euler numbers).