0
$\begingroup$

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.

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

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 $$

$\endgroup$