Putnam 2024, Problem B-5

Let \( k \) and \( m \) be positive integers. For a positive integer \( n \), let \( f(n) \) be the number of integer sequences \( x_1, \ldots, x_k, y_1, \ldots, y_m, z \) satisfying \( 1 \leq x_1 \leq \cdots \leq x_k \leq z \leq n \) and \( 1 \leq y_1 \leq \cdots \leq y_m \leq z \leq n \). Show that \( f(n) \) can be expressed as a polynomial in \( n \) with nonnegative coefficients.

Solution:
For convenience, we extend the problem to allow nonnegative values for $k$ and $m$.

**First solution.** Let $R(n,k)$ denote the number of subsets of $\{1,\ldots,n\}$ of size $k$ where repetitions are allowed. The "sticks and stones" argument shows that
$$R(n,k) = \binom{n+k-1}{k},$$
there is a bijection of these subsets with linear arrangements of $k$ (unlabeled) sticks and $z-1$ (unlabeled) stones, where we recover the subset by counting the number of stones to the left of each stick.

Let $f_{k,m}(n) := \sum_{z=1}^{n} R(z,k)R(z,m)$. It is known that for any positive integer $k$, the sum of the $k$-th powers of all positive integers less than or equal to $n$ is a polynomial in $n$ (given explicitly in terms of Bernoulli numbers via Faulhaber's formula); hence $f_{k,m}(n)$ is a polynomial in $n$. We wish to show that this polynomial has nonnegative coefficients.

Using the recursion for binomial coefficients, we obtain
$$R(n,k)R(n,m) = f_{k,m}(n) - f_{k,m}(n-1)$$
$$= \sum_{z=1}^{n} (R(z,k)R(z,m) - R(z-1,k)R(z-1,m))$$
$$= \sum_{z=1}^{n} (R(z,k)R(z,m) - R(z-1,k)R(z,m))$$
$$+ R(z-1,k)R(z,m) - R(z-1,k)R(z-1,m))$$
$$= \sum_{z=1}^{n} (R(z,k-1)R(z,m) + R(z,k)R(z,m-1))$$
$$= f_{k-1,m}(n) + f_{k,m-1}(n) - f_{k-1,m-1}(n).$$

It follows from the latter equation (replacing the index $m$ by $m+1$) that
$$f_{k,m}(n) = R(n,k)R(n,m+1) + f_{k-1,m}(n) - f_{k-1,m+1}(n); \tag{3}$$
this can also be recovered by applying Abel summation (summation by parts) to $\sum_{z=1}^{n} R(z,k)R(z,m)$.

Using (3), we can evaluate $f_{k,m}$ by induction on $k$: for the first few values we obtain
$$f_{0,m}(n) = R(n,m+1)$$
$$f_{1,m}(n) = R(n,1)R(n,m+1) + R(n,m+1) - R(n,m+2)$$
$$= R(n,m+1)((m+1)n+1)/(m+2)$$
$$= R(n,m+1) \frac{R(m+1,1)R(n,1) + 1}{m+2}$$
and similarly
$$f_{2,m}(n) = R(n,m+1)(R(m+1,2)R(n,2) + R(m+1,1)R(n,1) + R(m+1,0)R(n,0))/R(m+2,2).$$

This leads us to conjecture that
$$f_{k,m}(n) = \frac{R(n,m+1)}{R(m+2,k)} \sum_{i=0}^{k} R(m+1,i)R(n,i), \tag{4}$$
which we prove by induction on $k$. The base case $k = 0$ is evident; given (4) with $k$ replaced by $k-1$, we apply (3) to obtain
$$f_{k,m}(n)$$
$$= R(n,k)R(n,m+1) + \frac{R(n,m+1)}{R(m+2,k-1)} \sum_{i=0}^{k-1} R(m+1,i)R(n,i)$$
$$- \frac{R(n,m+2)}{R(m+3,k-1)} \sum_{i=0}^{k-1} R(m+2,i)R(n,i)$$
$$= \frac{R(n,m+1)}{R(m+2,k)} \sum_{i=0}^{k} R(m+1,i)R(n,i)$$
yielding (4) as written.

Since $R(n,i) = n(n+1)\cdots(n+i-1)/i!$ clearly has positive coefficients for all $i$, the explicit formula (4) implies that $f_{k,m}(n)$ also has positive coefficients for all $k$ and $m$.

**Second solution.** (by an anonymous Putnam participant) As in the first solution, we deduce that $f_{k,m}(n)$ is a polynomial in $n$ of degree $k+m+1$ satisfying $f_{k,m}(0) = 0$ and $f_{k,m}(n) - f_{k,m}(n-1) = R(n,k)R(n,m)$. Since $f_{k,m}(n) > 0$ for $n \gg 0$, this polynomial has positive leading coefficient. To prove that it has nonnegative coefficients, it will suffice to prove the stronger assertion that the roots of $f_{k,m}(x)$ are all real and nonpositive, as then this will imply that $f_{k,m}(x) = c \prod_{j=0}^{k+m} (x + r_j)$ for some $r_j \geq 0$.

Since $R(n,m) = 0$ for $m = 0,-1,\ldots,-m+1$, we deduce that $f_{k,m}(n) = 0$ for $n = 0,-1,\ldots,-m$. Consequently, $f_{k,m}(x)$ can be written as $x(x+1)\cdots(x+m)Q(x)$ for some polynomial $Q(x)$ of degree $k$, and it will suffice to check that $Q(x)$ has $k$ distinct negative real roots.

From the equality $f_{k,m}(n) - f_{k,m}(n-1) = R(n,k)R(n,m)$, if we substitute in for $Q(x)$ and divide out common factors, we obtain
$$(x+m)Q(x) - (x-1)Q(x-1) = \frac{1}{m!}R(x,k).$$

Substituting $x = 0,-1,\ldots,-k+1$ in turn, we obtain
$$Q(-j) = -\frac{j+1}{m-j}Q(-j-1) \quad (j = 0,\ldots,k-1).$$

In particular, if any of $Q(0),\ldots,Q(-k)$ were zero, then all of them would be zero and $Q$ would have too many roots for its degree. Consequently, $Q(0),\ldots,Q(-k)$ are all nonzero and alternating in sign. By the intermediate value theorem, $Q$ has a root $r_j$ in the interval $(-j-1,-j)$ for $j = 0,\ldots,k-1$; this completes the proof.