Combination with repeats

Question

I've been stuck for a while on this question and haven't found applicable resources.

I have 10 choices and can select 3 at a time. I am allowed to repeat choices (combination), but the challenge is that ABA and AAB are not unique.

10 choose 3 is the question.

I have been working on a smaller set to find a formula. 3 choose 3.

I came up with 27 results (if order matters) and 10 results if order doesn't matter. AAA, AAB, AAC, ABB, ACB, ACC, BBB, BBC, BCC, CCC

How do I go about solving these problems.

My closest hypothesis is choices^slots / slots! == 3^3/3!

Answer 1

This approach works because 3 is small.

Case 1: 3 distinct objects - ABC
There are ${ 10 \choose 3}$ ways here.

Case 2: 2 distinct objects, 1 repeated twice - AAB
There are $ 10 \times 9$ ways here.

Case 3: 1 distinct object, 1 repeated thrice - AAA
There are $10$ ways here.

---

This process becomes tedious as 3 gets large. You should look up Burnside's lemma for the general case.

Answer 2

Hint: First consider the case that all 3 chosen elements are distinct, and count the possibilities (taking into account that order doesn't matter). Then consider the case when exactly 2 chosen elements are equal, and count the possibilities. Finally count the possibilities when all 3 elements are equal.

Answer 3

Let us suppose that we have $m$ distinct object "types," but many objects of each type. You want to select $k$ objects, where selections may be repeated. Consider the equation $$x_1+x_2+\cdots+x_{m}=k.\tag{1}$$ Any selection of $k$ objects, not necessarily distinct, corresponds to a solution of Equation (1) in non-negative integers. Here $x_i$ is the number of Type $i$ objects selected.

It is a standard result that Equation (1) has $\binom{m+k-1}{k-1}$ solutions. For a good discussion, please see the Wikipedia article on Stars and Bars. There have also been many answers on MSE that use Stars and Bars.

Note that for your $3$ and $3$ problem, we get $\binom{6-1}{3-1}$, which is $10$. For your $10$ and $3$ problem, we get $\binom{12}{2}$. For $3$ objects to be selected, there are simpler ways to do the analysis, but for general $k$ Stars and Bars is the best approach.