In how many ways can $r$ elements be chosen from $n$ elements with repetition, such that every element is chosen at least once?

Question

Thank you for your comments -- hopefully a clarifying example --

In choosing all combinations of 4 elements from (A,B,C), (e.g., AAAA,BBBB,ACAB,BBBC, etc.) how many of these combinations include A, B and C? Using a computer, I came up with 36 for this example. There are 81 combinations, and I found only 45 combinations that include 2 or less of the three elements.

That is, where element order is considered and repetition allowed. I can't seem to get my head around it. What I came up with was n choose r - (n choose n-1) * (n-1 choose r) but the latter overlap and I was not sure how to calculate the overlaps.

Can anyone please help?

Thanks in advance.

Answer 1

Yes, you need to subtract some cases and overlapping is to be regarded. Where this is the case, the Inclusion–exclusion principle usually comes into play:

---

Let $N=\{1,\dots,n\}$ be the set, where we want to choose $r$ elements from and of course $n\leq r$. Also let $A_i$ for $i\in N$ denote the set of combinations of $r$ elements of $N$, such that $i$ not appears. Then clearly, the number you want to calculate is: $$n^r - \left|A_1\cup\dots\cup A_n\right|$$ First, we can calulate $$\left|\bigcap_{i\in I}A_i\right|=\left(n-|I|\right)^r$$ for any $I\subset N$. Since this number does not depend on $I$, we will shortly write $\alpha_{|I|}$ for it.

Now we can apply the Inclusion–exclusion principle in a simplified form: $$\left|\bigcup_{i=1}^{n}A_i\right|=\sum_{i=1}^n(-1)^{i-1}\binom{n}{i}\alpha_i=\binom n1 (n-1)^r-\binom n2 (n-2)^r+\binom n3 (n-3)^r - \dots (n-r)^r$$

---

Back to your example with $n=3$ and $r=4$: $$3^4-|A_1\cup A_2\cup A_3|=3^4-\left(3\cdot 2^4-3\cdot 1^4+1\cdot 0^4\right)=36$$

Answer 2

Thw answer in general is $r!S(n,r)$, where $S(n,r)$ is the Stirling number of the second kind.

Answer 3

The number of "combinations" of four elements chosen from $ABC$ where the order does matter is $3^4$ - the first element can be chosen in three ways, the second also in three ways and the third in three ways etc.

This includes combinations which do not contain all three letters. They might contain $AB$ only - this can happen in $2^4$ ways, or $BC$, or $AC$ similarly - $3\times 2^4$

But both $AB$ and $BC$ produce the combination $BBBB$, which has therefore been counted twice, and similarly for $AAAA$ and $CCCC$ - so we have to add back $3\times 1$

So the answer is $3^4-3\times 2^4+3\times 1^4=81-48+3=36$

This is a simple application of the inclusion-exclusion principle. This is clearer if we write the expression as:$$\binom 3 3 3^4-\binom 3 2 2^4+\binom 3 1 1^4 -\binom 30 0^4$$

$\binom 32$ arises, for example, because we took three pairs of letters from $ABC$ at the second stage, and this can be done in $\binom 32=3$ ways. I pinched the last term from the answer given by Tomas - we don't need it - it is zero - but it does show where the final binomial coefficient goes.

---

A second way of counting in this instance is to see that if a combination of four letters contains each of $ABC$ then it has just one doubled letter. This can be chosen in three ways. Then we place the letters by choosing a place for $A$ if it is undoubled, or $B$ if $A$ is doubled. This can be done in four ways. The second single letter can then be placed in one of the three remaining places - three ways.

The number of combinations is then $3 \times 4 \times 3 = 36$

Answer 4

If $r < n$, then the answer is $0$.

For $r \ge n$, the answer is $n! \times n^{r-n}$

Answer 5

? = A or B or C

$$ \begin{array}{l} ABC\,?\ \mbox{yields}\ 3. \\[2mm] \mbox{Permutation of}\ ABC\ \mbox{(above) yields}\ 6. \\[2mm] \mbox{With}\ ABC\,?\ \mbox{we have}\ 6 \times 3 = 18. \\[2mm] \mbox{We have 4 positions for}\ ?. \\[2mm] \mbox{Then, we get}\ 4 \times 18 = 72. \end{array} $$

By following @Mark Bennet, it should be $72/2 = 36$.