# How many words of length $2n-2$ composed from $n$ different letters, each of which appears at least once? [closed]

What's the number of words whose length is $$2n-2$$ composed from $$n$$ different letters such that each letter appears at least one time?

Note: I know to find the number of words whose length is $$2n-2$$ composed from $$n$$ different letters without restrictions.

• Why closing this one, what isn't clear about my question? – user788860 Jun 20 '20 at 22:09
• Any hint please? – user788860 Jun 20 '20 at 22:21
• @Croissant Added what I know – user788860 Jun 20 '20 at 22:27
• Possible dupplicate of. – Invisible Jun 20 '20 at 22:33
• @Croissant there he had 3 not n which makes it much easier – user788860 Jun 20 '20 at 22:34

## 1 Answer

You need to use inclusion-exclusion principle. For simplicity, let's say you have 10 chars. and string length $$n$$. The total number of unique strings you can get is $$10^n$$. Some of these strings don\t contain certain chars. Without the first char, you have $$9^n$$ strings, same without the second, etc. So If you remove 1 char from your 'alphabet', you get $$\binom{10}{1}9^n$$ strings. This means you have overcounted, i.e. strings without char1 and char2 were counted twice: first, when you removed char1 from enumeration, then, when you removed char2 from enumeration. Therefore, you need to add back each pair: $$\binom{10}{2}8^n$$, etc.

In general, $$k^{th}$$ term $$0 \leq k < 10$$ in this sequence will be $$(-1)^k\binom{10}{k}(10-k)^n$$