# Counting discrete functions

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.

-
Is this homework? –  Anthony Quas Aug 30 '13 at 15:36
No it isn't. Is it really that easy :O? –  funda Aug 30 '13 at 15:42
Have you worked out the formula for $\#S_2$? for $\#S_n$? Have you verified your conjecture numerically for small $n$? If so, please show us the details; if not, there's work you can do before appealing to the crowd. –  Greg Martin Aug 30 '13 at 17:24
This question appears to be off-topic because there is little evidence that the OP gave any thought to it before posting. –  fedja Aug 30 '13 at 19:43
@funda "to not influence other people's train of thought". Most of us here are trained in "ignoring information" (though I admit that it is a non-trivial skill). However, you should remember that the main purpose of this site is to help you out quickly, and the discussion of various approaches to one not so difficult problem is, at best, the secondary purpose. So, the best way to post a question is to state the problem clearly (which you did), and then tell the leads you have and the places where you got stuck (which you didn't) :) –  fedja Aug 31 '13 at 16:27

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$.
This looks great, except I can't figure out why $P_m < P_k$ for $m \neq k$. Thanks! –  funda Sep 2 '13 at 4:32
This is just a general property of binomial distributions (the probability to "almost win" is $p=k/n$ and $P_m={n\choose m}p^m(1-p)^{n-m}$). Nothing clever here. –  fedja Sep 2 '13 at 4:44