Section 7.2.2.2: Satisfiability

Exercise 199. [M21] Let $p(t, m, N)$ be the probability that $t$ specified letters each occur at least once within a random $m$-letter word on an $N$-letter alphabet.

a) Prove that $p(t, m, N) \le m^t / N^t$.

b) Derive the exact formula $p(t, m, N) = \sum_k \binom{t}{k} (-1)^k (N - k)^m / N^m$.

c) And $p(t, m, N) / t! = \binom{t}{t} \binom{m}{t} / N^t - \binom{t+1}{t} \binom{m}{t+1} / N^{t+1} + \binom{t+2}{t} \binom{m}{t+2} / N^{t+2} - \cdots$

Verified: yes
Solve time: 2m26s

---

Edit

Let the (t) specified letters be (1,\ldots,t). A random (m)-letter word over an (N)-letter alphabet has (N^m) equally likely outcomes.

(a)

For each specified letter (i), choose one occurrence position in the word whenever that letter appears. If all (t) specified letters occur, then there exists an ordered (t)-tuple of positions

[ (j_1,\ldots,j_t),\qquad 1\le j_i\le m, ]

such that position (j_i) contains the letter (i).

There are at most

[ m^t ]

possible ordered choices of positions. For any fixed ordered choice, the probability that the selected positions contain the prescribed letters is

[ \frac{1}{N^t}, ]

because the letters in those (t) positions are independent and each has probability (1/N) of being the required letter.

The event that all (t) specified letters occur is therefore contained in the union of at most (m^t) events, each having probability (N^{-t}). By the union bound,

[ p(t,m,N)\le m^t\frac1{N^t}. ]

Hence

[ \boxed{p(t,m,N)\le \frac{m^t}{N^t}}. ]

(b)

Let (A_i) be the event that specified letter (i) does not occur. We want the probability that none of these events happens:

[ p(t,m,N)=\Pr(\overline{A_1}\cap\cdots\cap\overline{A_t}). ]

By inclusion and exclusion,

\sum_{K\subseteq{1,\ldots,t}} (-1)^{|K|} \Pr\left(\bigcap_{i\in K}A_i\right). ]

If (K) contains (k) specified letters, then those (k) letters are forbidden, leaving (N-k) possible letters for each position. Therefore

\frac{(N-k)^m}{N^m}. ]

There are

[ \binom tk ]

choices for a subset (K) of size (k). Grouping the terms by (k) gives

\sum_{k=0}^{t} (-1)^k \binom tk \frac{(N-k)^m}{N^m}. ]

Thus

\sum_k \binom tk(-1)^k\frac{(N-k)^m}{N^m} }. ]

(c)

Expanding the formula from part (b), we have

\left(1-\frac{k}{N}\right)^m

\sum_{j=0}^{m} (-1)^j\binom mj\frac{k^j}{N^j}. ]

Substituting this into the inclusion and exclusion formula gives

\sum_{j=0}^{m} (-1)^j\binom mj\frac1{N^j} \sum_{k=0}^{t} (-1)^k\binom tk k^j . ]

The inner sum is a standard finite-difference identity:

0\qquad (j<t), ]

and for (j\ge t),

(-1)^t t!{j\brace t}, ]

where

[ {j\brace t} ]

is a Stirling number of the second kind.

Therefore only the terms (j=t,t+1,\ldots) remain, and

t! \sum_{j=t}^{m} (-1)^{j-t} {j\brace t} \binom mj \frac1{N^j}. ]

Writing (j=t+r),

\sum_{r\ge0} (-1)^r {t+r\brace t} \binom{m}{t+r} \frac1{N^{t+r}} }. ]

The first terms are therefore

\binom tt\binom mt\frac1{N^t}

{t+1\brace t}\binom m{t+1}\frac1{N^{t+1}} + {t+2\brace t}\binom m{t+2}\frac1{N^{t+2}} -\cdots . ]

Since

[ {t\brace t}=1 ]

and

[ {t+1\brace t}=\binom{t+1}{2}, ]

the first two coefficients can be simplified, but the later coefficients are Stirling numbers, not ordinary binomial coefficients.

Thus the expression stated in the exercise with coefficients

[ \binom{t+r}{t} ]

is not correct in general. For example,

[ {4\brace2}=7, ]

whereas

[ \binom42=6. ]

Consequently the correct expansion is the Stirling-number formula above. If the exercise statement intended the binomial coefficients, it contains a typographical error.