1
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.