Intereting Posts

How can I determine the sequence generated by a generating function?
The differential equation $xu_{x}+yu_{y}=2u$ satisfying the initial condition $y=xg(x),u=f(x)$
convexity of matrix “soft-max” (log trace of matrix exponential)
Minimizing sequence
How can I pack $45-45-90$ triangles inside an arbitrary shape ?
Prove that 1+1=2
How to factor cubics having no rational roots
Could Euclid have proven that multiplication of real numbers distributes over addition?
How do you prove that vectors are linearly independent in $ \mathcal{C}$?
What is a real-world metaphor for irrational numbers?
Find base and dimension of given subspace
Generating a binary code with maximized Hamming distance
What are the 2125922464947725402112000 symmetries of a Rubik's Cube?
Time derivative of Jacobian
Can we create a measure for infinitely countable sets with respect to eachother?

Given an alphabet of size $n$, how many strings of length $c$ contain every single letter of the alphabet at least once?

I first attempted to use a recurrence relation to work it out:

$$

T(c) = \left\{ \begin{array}{cr}

0 &\mbox{ if $c<n$} \\

n! &\mbox{ if $c = n$} \\

T(c-1) \cdot n \cdot c &\mbox{ if $c > n$}

\end{array} \right.

$$

- How many ways to get at least one pair in a seven card hand?
- What is the probability that if five hats are distributed among five boxes that box $B_1$ has hat $H_1$ or hat $H_2$ but not both?
- What is the combinatorial proof for the formula of S(n,k) - Stirling numbers of the second kind?
- Probability Question - An elevator & 5 Passengers
- How many 90 ball bingo cards are there?
- What is the count of the strict partitions of n in k parts not exceeding m?

As there’s no strings that contain every letter if c < n, and if c = n then it’s just all permutations. When c > n you can take any string of size (c-1) that contains all letters (of which there are $T(c-1)$ to choose from), you choose which letter to add (of which there are $n$ choices) and there are $c$ different positions to put it. However, this gives out results that are larger than $n^c$ (the total number of strings), so it can’t be right, and I realised it was because you could count some strings multiple times, as you can make them taking different inserting steps.

Then I thought about being simpler: you choose n positions in the string, put each letter of the alphabet in one of those positions, then let the rest of the string be anything:

$$

{c\choose{n}} \cdot n! \cdot n^{c-n}

$$

But again this counts strings multiple times.

I’ve also considered using multinomial coefficients, but as we don’t know how many times each letter appears in the string it seems unlikely they would be much help. I’ve also tried several other methods, some complicated and some simple, but none of them seem to work.

How would you go about working out a formula for this? I’m sure there’s something simple that I’m missing.

- How to count number of bases and subspaces of a given dimension in a vector space over a finite field?
- Total number of unordered pairs of disjoint subsets of S
- Inductive Proof for Vandermonde's Identity?
- How to prove a combinatorics identity
- Maximum number of edges that a bipartite graph with $n,m$ vertices can have when it doesn't contain $4$-cycle
- Count the number of strings containing $ac$ or $ca$ for a fixed length over ternary alphabet $A = \{a,b,c\}$ using rational series
- Is there a memorable solution to Kirkman's School Girl Problem?
- A conjecture relating Multiple Zeta Values and the Polya Enumeration Theorem
- Probability of rolling a dice 8 times before all numbers are shown.
- Wanted: Insight into formula involving binomial coefficients

Let $W(c,n)$ denote the number of words of length $c$ from an alphabet of $n$ letters. Then $W(c,n)=n^c$.

Out of these, the number of words of the same size that do not contain one of the letters is $W(c,n-1)=(n-1)^c$. The number of ways of choosing which letter is missing is $\binom{n}{1}$.

The number of words of the same size that do not contain two letters is $W(c,n-2)=(n-2)^c$. The number of ways of choosing which two letters are missing is $\binom{n}{2}$… and so on …

Now we use inclusion-exclusion principle: (subtract the number of words missing one of the letters, then add the number missing two of the letters, add the number missing three of the letters,…)

We get:

$$W(c,n)-\binom{n}{1}W(c,n-1)+\binom{n}{2}W(c,n-2)-\binom{n}{3}W(c,n-3)+…+(-1)^{n-1}\binom{n}{n-1}W(c,n-(n-1)).$$

This is

$$n^c-\binom{n}{1}(n-1)^c+\binom{n}{2}(n-2)^c+\binom{n}{3}(n-3)^c+…+(-1)^{n-1}\binom{n}{n-1}1^c.$$

or

$$\sum_{k=0}^{n-1}(-1)^k\binom{n}{k}(n-k)^c.$$

Another way could be: Denote $S_c^n$ the number of ways to partition the word of length $c$ into $n$ pieces. Then we just need to choose which letter goes to each of the $n$ pieces. This number is $n!$. So the number of words we are looking for is

$$n!S_c^n.$$

The numbers $S_c^n$ are called Stirling’s numbers of the second kind.

As you said, there are no solutions if c<=n.

then all results will contain all `n`

letters and `c-n`

random letters so the combinations are:

```
((c-n).n)
```

But string have fixed positions so we need all the permutations out of this:

```
((c-n).n).c!
```

For each character (c-n) there are possible duplicates of letters for which ordering does not meter, so have to divide to that.

```
((c-n).n).c!/ (c-n)! //not sure if this is correct
```

This is just a line of reasoning I hope to get you further, not sure if it is all correct.

- I need help finding a rigorous precalculus textbook
- A monomorphism of groups which is not universal?
- Counting number of $k$-sequences
- Why do we represent complex numbers as the sum of real and imaginary parts?
- Prove that $AB=BA$ if $A, B$ are diagonal matrices
- Can we recover a compact smooth manifold from its ring of smooth functions?
- $C$ with metric $d_2$ not complete
- Are there infinitely many $A\in \mathbb{C}^{2 \times 2}$ satisfying $A^3 = A$?
- Intuitive explanation for why $\left(1-\frac{1}{n}\right)^n \to \frac{1}{e}$
- An oddity in some linear equations
- Are there any non-trivial group extensions of $SU(N)$?
- Prove that $\sum_{n=1}^{\infty}\ a_n^2$ is convergent if $\sum_{n=1}^{\infty}\ a_n$ is absolutely convergent
- History of Lagrange Multipliers
- Why does the non-negative matrix factorization problem non-convex?
- Proof of the identity $2^n = \sum\limits_{k=0}^n 2^{-k} \binom{n+k}{k}$