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

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.

• Frankly, I have not the faintest idea what you are asking. Could you elaborate what a "n choose r" is, so that we know how to count "n choose r"'s. – Tomas Aug 21 '13 at 9:37
• Can you clarify the terms of the question? Are you choosing $n$-tuplets from a pool of $n$ people? Are you choosing $n$-tuplets from that pool while only allowing $r$ people to actually appear? – Jonathan Y. Aug 21 '13 at 9:38
• @Tomas Thank you for your comment - by n choose r, I mean n to the power of r in the title and in the first and third case of the suggested formula, and fact n / fact (n-r) * fact r for the middle case in the formula. – גלעד ברקן Aug 21 '13 at 9:39
• @groovy: I know how $\binom nr$ is defined. But you are asking "How many n choose r", the meaning of which I cannot grasp. Maybe you can try to formulate the question in plain (maybe figurative) english, without to much math symbols involved? Try something like "How many people can we choose from a group of "... – Tomas Aug 21 '13 at 9:42
• @groovy, it is still not clear. Maybe you could give an example with small values of $n$ and $r$ – Igor Shinkar Aug 21 '13 at 9:42

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

• Thank you (for the answer and title-edit), I'll study your answer. – גלעד ברקן Aug 21 '13 at 10:09
• @groovy: The answer is not super-detailed. If you don't know about the Inclusion-Exclusion principle, you might want to study the Wikipedia article first. – Tomas Aug 21 '13 at 10:10

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

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$

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

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

• Naffi, how do you figure? – Jonathan Y. Aug 21 '13 at 9:55
• @JonathanY. If $r >= n$, You can have $n!$ combinations having all $n$ elements. The remaining $(r-n)$ places can be filled up by $n$ elements, with repetition. – Naffi Aug 21 '13 at 9:58
• I'm getting 1*2*3*3^(4-3) = 18. But my brute-force computer enumeration was 36. How's that? – גלעד ברקן Aug 21 '13 at 9:59
• Indeed, but some $r$-tuplets are counted twice that way. – Jonathan Y. Aug 21 '13 at 10:00
• Using a computer, I came up with 36 for the example, choose 4 from 3. There are 81 combinations, and I found only 45 combinations that include 2 or less of the three elements. – גלעד ברקן Aug 21 '13 at 10:02
? = 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$.

• Thank yo for your answer. Using a computer, I came up with 36 for the example, choose 4 from 3. There are 81 combinations, and I found only 45 combinations that include 2 or less of the three elements. – גלעד ברקן Aug 21 '13 at 10:02
• If $?=A$ you have counted $?A$ and $A?$ as distinct combinations, but they end up the same. This is why you have $72$ instead of $36$ - you need to divide by $2$. – Mark Bennet Aug 21 '13 at 10:23
• I missed that point. Then 72/2 = 36. Thanks @Mark Bennet – Felix Marin Aug 21 '13 at 10:32