Intereting Posts

the converse of Schur lemma
Are these two definitions equivalent?
Show that $n + 2$ and $n^2 + n + 1$ cannot both be perfect cubes
Is this Batman equation for real?
Are regular languages necessarily deterministic context-free languages?
Probability, conditional on a zero probability event
In what situations is the integral equal to infinity?
If $e^A$ and $e^B$ commute, do $A$ and $B$ commute?
Probability of a random binary string containing a long run of 1s?
Double check $G\sim H$ iff $G≈H$
Techniques to compute complex integrals over infinite contours
Am I wrong in thinking that $e^{i \pi} = -1$ is hardly remarkable?
Unique factorization domain and principal ideals
Evaluate $\sum_{n=1}^\infty \frac{n}{2^n}$.
Are integrable, essentially bounded functions in L^p?

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.

$$

- Secret Santa Combinatorics with couples
- How to find number of strings generated by permuting the given string satisfying the below conditions?
- What are the total number of ordered permutations of a list of elements (possibly repeated)?
- Combination - Infinite Sample Size
- What is the number of distinct 3 letter words out of different number of given letters?
- (Counting problem) very interesting Modular N algebraic eqs - for combinatorics-permutation experts

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.

- some questions about combinations
- Expand $\binom{xy}{n}$ in terms of $\binom{x}{k}$'s and $\binom{y}{k}$'s
- Combinatorial interpretation of Binomial Inversion
- How can i find closed-form expression of generating function of this series?
- Make up a reasonable definition for the bipartite complement of a bipartite graph
- Can this product be written so that symmetry is manifest?
- Combination problem
- A bridge hand void in one suit
- Given $n$ distinct elements, how many Young Tableaux can you make?
- $4$ letter words taken from the letters of CONCENTRATIONS

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.

- Good book for mathematical modeling
- Weak Law of Large Numbers for Dependent Random Variables with Bounded Covariance
- Intuition for Smooth Manifolds
- Proving $(A \cup B) -C = (A-C) \cup (B-C)$
- Symmetry in inequalities.
- How does he get a perfect swap numerator and denominator.
- Delta Dirac Function
- Nonattacking rooks on a triangular chessboard
- Properties of sin(x) and cos(x) from definition as solution to differential equation y''=-y
- Differences of consecutive hitting times
- Correlation in Bernoulli trial
- Decomposition of $l$ in a subfield of a cyclotomic number field of an odd prime order $l$
- Definable real numbers
- Necessary and sufficient conditions for the sum of two numbers to divide their product
- 6/2*(1+2) is 1 or 9?