International Mathematics Competition
for University Students
2015

IMC2015: Day 2, Problem 8

8. Consider all $26^{26}$ words of length 26 in the Latin alphabet. Define the weight of a word as $1/(k+1)$, where $k$ is the number of letters not used in this word. Prove that the sum of the weights of all words is $3^{75}$.

Proposed by Fedor Petrov, St. Petersburg State University

Solution 1. Let $n=26$, then $3^{75}=(n+1)^{n-1}$. We use the following well-known

Lemma. If $f(x)$ is a polynomial of degree at most $n$, then its $(n+1)$-st finite difference vanishes: $\Delta^{n+1}f(x):=\sum_{i=0}^{n+1} (-1)^i \binom{n+1}{i} f(x+i)\equiv 0$.

Proof. If $\Delta$ is the operator which maps $f(x)$ to $f(x+1)-f(x)$, then $\Delta^{n+1}$ is indeed $(n+1)$-st power of $\Delta$ and the claim follows from the observation that $\Delta$ decreases the power of a polynomial.

In other words, $f(x)=\sum_{i=1}^{n+1} (-1)^{i+1}\binom{n+1}{i} f(x+i)$. Applying this for $f(x)=(n-x)^n$, substituting $x=-1$ and denoting $i=j+1$ we get $$ (n+1)^n=\sum_{j=0}^n (-1)^j \binom{n+1}{j+1} (n-j)^n=(n+1) \sum_{j=0}^n \binom{n}{j}\cdot \frac{(-1)^j}{j+1}\cdot (n-j)^n. $$ The $j$-th summand $\binom{n}{j}\cdot \frac{(-1)^j}{j+1}\cdot (n-j)^n$ may be interpreted as follows: choose $j$ letters, consider all $(n-j)^n$ words without those letters and sum up $\frac{(-1)^j}{j+1}$ over all those words. Now we change the order of summation, counting at first by words. For any fixed word $W$ with $k$ absent letters we get $\sum_{j=0}^k \binom{k}{j}\cdot \frac{(-1)^j}{j+1}=\frac1{k+1}\cdot \sum_{j=0}^k (-1)^j\cdot \binom{k+1}{j+1}=\frac1{k+1}$, since the alternating sum of binomial coefficients $\sum_{j=-1}^k (-1)^j\cdot \binom{k+1}{j+1}$ vanishes. That is, after changing order of summation we get exactly initial sum, and it equals $(n+1)^{n-1}$.

Solution 2 (based on students' papers). Define by $W$ the set of all $26$-strings of Latin letters, and let $W^*$ be the set of all $25$-strings of the alphabet $\{A,B,\ldots,Z,*\}$. For any string in $W$ or $W^*$, denote by $\ell(w)$ the number of different Latin letters (excluding stars) in $w$. According the definition, the weight of any word $w\in W$ is $\frac{1}{27-\ell(w)}$.

Define a map $\varphi:W\to W^*$ in the following way. Suppose that $w\in W$ is an arbitrary $26$-string and $x$ is its first letter. Remove the leading $x$ from $w$ and replace all other occurences of $x$ by the character $*$. Let $\varphi(w)\in W^*$ be the resulting $25$-string. Notice that the number of different Latin letters decreases by $1$, so we have $\ell(\varphi(w))=\ell(w)-1$.

The map $\varphi$ is not injective. For every $u\in W^*$, as $u$ contains $\ell(u)$ different characters, there are $26-\ell(u)$ different Latin letters that are not used in $u$, there are $26-\ell(u)$ possible pre-images of $u$. The pre-images of $u$ contain $\ell(u)+1$ Latin letters, so their weights are equal to $\frac{1}{26-\ell(u)}$. Hence, the total weight of the pre-images of $u$ is equal to $1$.

Therefore, the total weight of the words in $W$ is equal to the number of strings in $W^*$, which is $|W^*|=27^{25}$.