1
$\begingroup$

Let $S=\{1,2,3,4\}$. There're three persons: Jack, Mary, Ann which choose $3$ digits from $S$ to compose a string of $3$ digits.

For example, a) Jack chose $112$, Mary chose $222$, Ann chose $123$; b) Jack chose $123$, Mary chose $122$, Ann chose $433$.

In how many ways can they form the strings? In how many ways can they form the strings if each digit from $S$ has to appear at least in one string?

For the second subquestion the example a) would not be a valid choice because $4$ doesn't appear in any string, while example b) is valid.

The first subquestion is easy for each string there're $4^3$ possibilities and there're $3$ different people so $3!\cdot 4^3$.

The second subquestion is the harder one. I think this can be solved using inclusion/exclusion. We can count the ways where a given digit doesn't appear in any string, then two digits don't appear in any string, then 3 digits.

The case when one digit doesn't appear in any string: $$ {4\choose 3}3^3\cdot 3! $$ that is we choose only $3$ digits from $4$ available. The in each string there're $3^3$ options to build the string. Lastly there're $3$ strings in total. By this logic the final answer is: $$ {4\choose 3}3^3\cdot 3!-{4\choose 2}2^3!\cdot 3+{4\choose 1}1^3\cdot 3! $$

The problem is that when I permute the persons (the $3!$ in the calculation) it works if not two strings are the same. But if some strings are the same I will count too many if I use permutation.

$\endgroup$
  • 1
    $\begingroup$ For the first question, your answer seems to be based on the assumption that no two people can choose the same string. Each person can choose a string in $4^3$ ways, so the number of ways three people could independently choose a string is $(4^3)^3 = 4^9$. $\endgroup$ – N. F. Taussig Jun 12 '18 at 11:22
1
$\begingroup$

Let $S = \{1, 2, 3, 4\}$. Jack, Mary, and Ann each choose three digits from $S$ to compose a string of $3$ digits. For example, Jack chose $112$, Mary chose $222$, Ann chose $123$. In how many ways can they form the strings?

Since the question makes clear that repetition is permitted, each person can choose his or her string in $4^3$ ways. Hence, there are $(4^3)^3 = 4^9$ ways for Jack, Mary, and Ann to choose their strings.

Another way to see this is to observe that there are four choices for each of the nine entries, so the three strings can be selected in $4^9$ ways.

In how many ways can Jack, Mary, and Ann form the strings if each digit in $S$ has to appear in at least one string?

Suppose Jack chooses the string $(j_1, j_2, j_3)$, Mary chooses the string $(m_1, m_2, m_3)$, and Ann chooses the string $(a_1, a_2, a_3)$. Notice that we could concatenate the three strings of length $3$ into a single string of length $9$: $(j_1, j_2, j_3, m_1, m_2, m_3, a_1, a_2, a_3)$.

As stated above, we have four choices in $S$ for each of the nine entries, so there are $4^9$ ways to choose the strings. If we exclude $k$ of the four elements in $S$, the nine entries in the concatenated string can each be filled in $(4 - k)^9$ ways. Hence, the number of strings from which $k$ elements of $S$ have been excluded is $$\binom{4}{k}(4 - k)^9$$ Therefore, by the Inclusion-Exclusion Principle, the number of admissible strings is $$\sum_{k = 0}^{4} (-1)^k\binom{4}{k}(4 - k)^9 = \binom{4}{0}4^9 - \binom{4}{1}3^9 + \binom{4}{2}2^9 - \binom{4}{3}1^9 + \binom{4}{4}0^9$$

Where did you make your error?

You seem to have made the assumption that no two of the three people could choose the same string. However, Jack, Mary, and Ann can choose their strings independently.

$\endgroup$
  • 1
    $\begingroup$ I really like your suggestion to think of the problem as concatenating the strings into one big string. $\endgroup$ – user123429842 Jun 12 '18 at 12:31

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.