0
$\begingroup$

Suppose we have a set of $4$ elements, $\{a_1, a_2, a_3, a_4\}$, and we are drawing four times from this set with replacement. How many combinations are there that have three unique elements, ie. a sample such as $(a_1, a_1, a_2, a_3)$?

I am messing something up here. I though the following: There are 4 choices for the first unique element, 3 choices for the second unique element and 2 choices for the repeated elements. And with that, there are $\frac{4!}{1!\cdot1!\cdot2!}$ ways to order these 4 elements. So I thought there should be $ 4 * 3 * 2 * 12 = 288 $ ways to choose 2 unique and 2 repeated elements. But this has to be wrong because there is only $4^4 = 256$ ways to chose 4 elements.

Could someone point out how I am thinking is wrong?

$\endgroup$
3
  • 1
    $\begingroup$ If I choose $a_1$ as my first unique element, $a_2$ as my second unique element, $a_3$ as the repeated element, and then choose to order them as "first, second, repeated, repeated" thus getting the final outcome of $a_1,a_2,a_3,a_3$ how does this compare to if I choose $a_2$ as my first unique element, $a_1$ as my second unique element, $a_3$ as repeated, and choose to order them as "second, first, repeated repeated"? $\endgroup$
    – JMoravitz
    Oct 2, 2023 at 17:45
  • 1
    $\begingroup$ The punchline is that you should pick the two unique elements simultaneously, not in sequence. This is the same error that is commonly seen for the problem of counting 3-of-a-kinds in poker. You have in effect double-counted. $\endgroup$
    – JMoravitz
    Oct 2, 2023 at 17:58
  • 1
    $\begingroup$ @JMoravitz ahh, so it should be $4\textbf{C}2 \cdot 2\textbf{C}1 \cdot 12 $? $\endgroup$
    – alpastor
    Oct 2, 2023 at 18:08

1 Answer 1

1
$\begingroup$

The error is in that you are implying an importance to the order in which you selected the values to use as the unique elements as well as an importance to the order in which they are arranged when in fact the order they are selected is irrelevant.

Picking $a_1$ as "first" and $a_2$ as "second" and having arranged them as "first,second,..." gives the same result as having picked $a_2$ as "first" and $a_1$ as "second" and having arranged them as "second,first,..." as they both appear as "$a_1,a_2,\dots$"

By selecting all elements which will be used for the same purpose simultaneously you will avoid this error, giving an answer of $\binom{4}{2}\times 2\times \frac{4!}{1!1!2!} = 144$


For the more generic problem of asking how many ways in which we can select $k$ unique elements out of $n$ available when picking $N$ with replacement, where we do not care about specific patterns or quantities (for example, when picking five times and wanting three unique we are happy both with $abccc$ as well as $abbcc$) it would be ideal to approach using Stirling Numbers of the Second Kind.

The Stirling Number of the Second Kind ${N\brace k}$ counts the number of ways in which we can partition $N$ elements into $k$ non-empty unlabeled parts.

Here, we break the positions within our $N$-tuple into $k$ non-empty parts, and then assign a specific element for each part giving a final count of:

$${N\brace k}\cdot n^{\underline{k}}$$

where $n^{\underline{k}}$ is notation for the falling factorial $n^{\underline{k}} = \frac{n!}{(n-k)!} = \underbrace{n(n-1)(n-2)\cdots (n-k+1)}_{k~\text{terms}}$

In your problem, that would be ${4\brace 3}\cdot 4^{\underline{3}} = 6\times 4\times 3\times 2 = 144$

$\endgroup$
1
  • $\begingroup$ This is actually what I wanted! I didn't know about Sterling numbers of the second kind. Thanks for this. $\endgroup$
    – alpastor
    Oct 2, 2023 at 18:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .