Counting discrete functions

Question

For $1\leq k \leq n+1$, consider the set $S_k$ of functions $f:\{1,\ldots,n\} \rightarrow \{1,\ldots,n+1\}$, with the property that $|f^{-1}\{1,\ldots,k\}| < k$. Note that $|S_1|=n^n$, and $|S_{n+1}| = (n+1)^n$. Is it true that $|S_k|$ grows with $k$?

It's not hard to come up with the formula $$ |S_k| = \sum_{j=0}^{k-1} {n \choose j} k^j (n+1-k)^{n-j}$$ and if you plot this it is at least apparent that the conjecture should be true.

Another vague observation is that, if you divide by $(n+1)^n$ and take limit as $n\rightarrow \infty$, keeping $k$ fixed, you get the expression $$ e^{-k} \sum_{j=0}^{k-1} \frac{k^j}{j!}$$ and using Taylor's integral remainder theorem you can prove the conjecture at least in the limit.

Answer 1

OK, once I went into "preaching", I feel I am obliged to post a solution too.

Let's consider $n$ i.i.d. Bernoulli variables $X_j$ such that $P(X_j=1)=\frac k{n+1}$ and $P(X_j=0)=1-\frac k{n+1}$. We want to show that the probability of the event $\sum_j X_j<k$ is increasing in $k$. Note that we can model it as $n$ games where the player has $0$ dollars to start with and plays until he either goes down to $-k$ or reaches $n+1-k$. The problem asks to show that the probability to win less than $k$ games increases as $k$ goes up from $1$ to $n$.

Let us play each game until we reach either $n-k$ or $-k$ and then take a short break to look around. Let $P_m$ be the probability that at this moment $m$ games out of $n$ are in the position $n-k$. Assume that we are playing up to $-k$ and $n+1-k$. Then if we are at $-k$ already, it is a sure loss. If we are at $n-k$, it is still uncertain. Thus, the probability we are interested in for $k$, is $$ \sum_{m<k}P_m+\sum_{m\ge k}P_m Q(m\to <k) $$ where $Q(m\to<k)$ is the probability to go from the position with $m$ "almost won" games to that with $<k$ really won games. Similarly, if we are playing up to $-(k+1)$ and $n-k$, the probability in question is $$ 1-\sum_{m>k}P_m-\sum_{m\le k}P_m Q(m\to>k) $$ Thus, the first probability is less than the second iff $$ P_k>\sum_{m\ge k}P_m Q(m\to <k)+\sum_{m\le k}P_m Q(m\to>k) $$ Note now that $P_m<P_k$ for $k\ne m$. Thus, it will suffice to show that $$ \sum_{m\ge k}Q(m\to <k)+\sum_{m\le k}Q(m\to>k)\le 1 $$ The probability to get the unexpected outcome of an almost finished game is $\frac{1}{n+1}$. Thus, this sum can be rewritten as $$ \sum_{u=0}^{n-k} P\left(\sum_{j=1}^{k+u}Y_j\ge u+1\right)+\sum_{u=0}^k P\left(\sum_{j=1}^{n-k+u}Y_j\ge u+1\right) $$ where $Y_j$ are independent Bernoulli with $P(Y_j=1)=\frac{1}{n+1}$. Thus, it will suffice to show that $$ \sigma_s=\sum_{u=0}^\infty P\left(\sum_{j=1}^{s+u}Y_j\ge u+1\right)\le \frac sn $$ However, this is an identity. I'll just prove it by induction in $s$. The base $s=0$ is obvious. Now, conditioning upon the length $\ell$ of the initial streak of $1$'s in the sequence $Y_j$, we have $$ \sigma_{s+1}=\sum_{\ell\ge 0}\left(\frac 1{n+1}\right)^\ell\frac{n}{n+1}(\ell+\sigma_s)=\frac 1n+\sigma_s $$ because when $s\ge 1$, the conditional probability $P\left(\sum_{j=1}^{s+u}Y_j\ge u+1\mid Y_1=\dots=Y_\ell=1,Y_{\ell+1}=0\right)$ equals $1$ if $u\le\ell-1$ and $P\left(\sum_{j=\ell+2}^{s+u}Y_j\ge (u-\ell)+1\right)=P\left(\sum_{j=1}^{(s-1)+(u-\ell)}Y_j\ge (u-\ell)+1\right)$ for $u\ge\ell$.