Composing words from a limited letter supply

40 Views Asked by At

A typesetter working with an $n$-letter alphabet has $k$ copies of each letter in his type case; how many $n$-letter words can he compose?

What is the number of $n$-letter words composed from an $n$-letter alphabet such that no letter appears more than $k$ times?

Denoting this number by $T_k(n)$, we have $T_1(n)=n!$ in a trivial way.

For $k=2$ we have, say, $T_2(1)=1$, $T_2(2)=4$, and $T_2(3)=24$; subsequent terms can be computed from $$ T_2(n) = \sum_{k=0}^{n/2} \frac{(n!)^2}{2^k(k!)^2\,(n-2k)!}. $$ The sequence $T_2(n)$ is OEIS A012244. Asymptotically, $$ T_2(n) = C\,(1+\sqrt 2)^n\, (n/e)^n (1+o(1)) $$ where $C=(1+1/\sqrt 2)^{1/2}$.

What happens for $k\ge 3$? It would be great to have an asymptotic formula with an explicit remainder term; that is, without assuming that $k$ is fixed.

1

There are 1 best solutions below

1
On BEST ANSWER

This problem is discussed in overwhelming detail in the following paper on arXiv: Coalescence under preimage constraints by Benjamin Otto. The relevant result is Corollary $7.8$, which implies that for fixed $k\ge 2$,

$$ T_k(n)=n!(\rho_k)^{-n}n^{-1/2}(2\pi \tau_k\rho_k \cdot e_{k-2}(\tau_k))^{-1/2}(1+o(1))\qquad \text{as }n\to\infty $$ where

  • $ e_k(x)=1+x+x^2/2!+\dots+x^k/k!,$

  • $\tau_k$ is the unique $x\in \mathbb R_{+}$ for which $e_k(x)-te_{k-1}(x)=0,$

  • $\rho_k=\tau_k/e(\tau_k)$.

I have not checked the details, but this agrees with your $k=2$ result.

I am paraphrasing their notation. They handle the more general case where the number of times each letter is allowed to appear is a set $\mathcal P$, when you are only concerned with $\mathcal P=\{0,1,\dots,k\}$. Whereas they have $e_{\mathcal P}(x)=\sum_{i\in \mathcal P}x^i/i!$, I replaced this with $e_k(x)$.