Words of length $n$ out of an alphabet of $n$ symbols such that no symbol appears exactly $k > 0$ times

Question

I need to count the possible words of length $n$ out of an alphabet of $n$ symbols such that no symbol appears exactly $k$ times, with $k > 0$.

I already tried considering the weak compositions of $n$ in $n$ parts with the restriction of having no parts being exactly $k$, but the problem is that then I would need to find a way of counting how many ways of ordering I have for each of the compositions.

I would need the exact amount or asymptotics or at least any bounds that are tighter than $$C^w_{n}(n,\check{k})n!$$

where $C^w_{n}(n,\check{k})$ is the amount of weak compositions of $n$ in $n$ parts with no parts being equal to $k$.

Answer 1

As suggested in a comment, this can be solved using inclusion-exclusion.

There are

$$ \frac{n!}{(k!)^j(n-jk)!}(n-j)^{n-jk} $$

words in which $j$ particular symbols appear exactly $k$ times. Thus by inclusion–exclusion there are

$$ \sum_{j=0}^{\left\lfloor\frac nk\right\rfloor}(-1)^j\binom nj\frac{n!}{(k!)^j(n-jk)!}(n-j)^{n-jk} $$

words in which no symbol appears exactly $k$ times.

Answer 2

The combinatorial class of these words is given by

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \textsc{SEQ}_{=n}(\textsc{SET}_{\ne k}(\mathcal{Z})).$$

This gives the EGF

$$G(z) = \left(\exp(z)-\frac{z^k}{k!}\right)^n.$$

Extracting coefficients we find

$$n! [z^n] G(z) = n! [z^n] \sum_{j=0}^n {n\choose j} \exp((n-j)z) (-1)^j \frac{z^{kj}}{(k!)^j} \\ = n! [z^n] \sum_{j=0}^{\lfloor n/k \rfloor} {n\choose j} \exp((n-j)z) (-1)^j \frac{z^{kj}}{(k!)^j} \\ = n! \sum_{j=0}^{\lfloor n/k \rfloor} {n\choose j} [z^{n-kj}] \exp((n-j)z) (-1)^j \frac{1}{(k!)^j} \\ = n! \sum_{j=0}^{\lfloor n/k \rfloor} {n\choose j} \frac{(n-j)^{n-kj}}{(n-kj)!} (-1)^j \frac{1}{(k!)^j}.$$

This matches the result from PIE by @joriki.