1
$\begingroup$

The following two questions are from Richard Stanley's Enumerative Combinatorics:

  1. A box is filled with three blue socks, three red socks, and four chartreuse socks. Eight socks are pulled out, one at a time. In how many ways can this be done? (Socks of the same color are indistinguishable.)
  2. How many functions $f : [5]=\{1,2,\ldots,5\} → [5]=\{1,2,\ldots,5\} $are at most two-to-one, i.e., $\#f^{−1}(n) \leq 2$ for all $n \in [5]$?

For the first one, I tried to reformulate the question of finding the number of integral solutions of $$x_1+x_2+x_3=8$$ where $0 \leq x_1, x_2 \leq 3$ and $0\leq x_3\leq4$.By using inclusion-exclusion principle, I calculate the required number is $$H^3_8 - ( H^3_4+H^3_4 + H^3_3 -1 -0-0+0)=5.$$ For example, the first term refers to the case where the upper bounds are all ignored; the second term refers to the case where the upper bound of $x_1$ is not satisfied, etc. But the suggested solution is $2660$, which is surprisingly large. Which one is correct?


For the second one, I notice that there can only be three cases:

  1. Every integer is mapped to a distinct integer ($5!$ ways to do so)
  2. Exactly one integer in the co-domain has no pre-image.
  3. Exactly two integers in the co-domain have no pre-image.

But I am stuck at here to compute the number of ways in doing case 2 and 3. Any hint will be appreciated.

$\endgroup$
  • $\begingroup$ Hint for the first one: to get a number that large, the order must signify. That is, $BBBRRRCC\neq CCRRRBBB$. $\endgroup$ – lulu Dec 8 '15 at 11:02
  • $\begingroup$ Hint for the second one: it is very similar to the first. Your cases are good. to handle $2.$, say, you have the numbers $\{2,1,1,1,0\}$ and you need to permute these (of course the $1's$ are indistinguishable. Place the $2$, then the $0$. For $3.$ same idea starting with $\{2,2,1,0,0\}$. $\endgroup$ – lulu Dec 8 '15 at 11:19
  • $\begingroup$ @lulu : The first one becomes clear now. For the second one, case 2, to permute these numbers we have $\frac{5!}{1!3!1!}$ ways to do so. Then, to put the numbers $\{1,2,3,4,5\}$ in place, we can simply choose $C^5_2$ to have the same image. Am I correct? $\endgroup$ – Nighty Dec 8 '15 at 13:10
  • $\begingroup$ I agree with the permutation count, but not the pre-image count. Each permutation is the same, let's stick with $\{2,1,1,1,0\}$. Need to pick two elements that map to $1$...that's $\binom 52$. Now need to pick one element to map to $2$, that's $3$. Now need to pick one element to map to $3$, that's $2$. remaining element is mapped to $4$, no choice. So: $\binom 52 * 3 *2$. $\endgroup$ – lulu Dec 8 '15 at 13:23
  • $\begingroup$ @lulu : Thanks for your explanation. Please consider put all these in the answers. They solve my problems! $\endgroup$ – Nighty Dec 8 '15 at 15:32
1
$\begingroup$

For problem #1 (assuming that the order of selection matters).

We'll go case by case according to the number of $C's$ selected (can't be more than $4$, can't be fewer than $2$, else we'd have more than $3$ of one of the others).

Case $4C's$: Pick slots for the $C's$, $\binom 84$ wasys to do it. Then we have $4$ slots left. Ignoring restrictions we'd have $2^4=16$ ways to do it. As we can't have $4R$ or $4B$ we have to discard $2$ cases. Hence $${8\choose 4} (2^4-2)$$

Case $3C's$: Pick slots for the $C's$, $\binom 83$ wasys to do it. Then we have $5$ slots left. Ignoring restrictions we'd have $2^5=32$ ways to do it. As we can't have $4R$ or $4B$ we have to discard cases with $4$ or $5$ of one color. Clearly $2$ ways to have $5$ of one color and $10$ ways to have exactly $4$ (for four $R$, say, we have $5$ ways to select the slot for the single $B$). Hence $${8\choose 3} (2^5-2*5-2)$$

Case $2C's$: Pick slots for the $C's$, $\binom 82$ wasys to do it. Then we have $6$ slots left. Ignoring restrictions we'd have $2^6=64$ ways to do it. But the only way to fill the remaining slots is to have three each of the other colors, so we just need to pick the slots for the three $B's$, say. Hence $$\binom 82 \binom 63$$

Summing these cases yields the desired answer $\fbox {2660}$

The second problem was largely sorted out in the comments. As the OP points out, we have three cases to consider separately, counting the number of values not in the image of the function.

Case $0$: As the OP says, $\fbox {5!=120}$

Case $1$: then we know the image is some permutation of $\{2,1,1,1,0\}$. There are exactly $20$ such permutations (pick a slot for the $2$, then a slot for the $0$). To count the number of functions with image a given permutation (say $\{2,1,1,1,0\}$, we just need to choose $2$ values which map to the slot $1$ ($\binom 52=10$ ways), then $1$ value to map to slot $2$ ($3$ ways), then $1$ value to map to slot $3$ ($2$ ways). That's $10*3*2=60$ functions for a given permutation hence $\fbox {20*60=1200}$

Case $2$: then we know the image is some permutation of $\{2,2,1,0,0\}$. There are exactly $30$ such permutations (pick a slot for the $1$, $5$ ways, then two slots for the $2's$, $\binom 42 = 6$ ways). Now we need to count the functions attached to a particular such permutation. As before, pick two values to map to slot $1$ ($10$ ways) then pick two values to map to slot $2$ ($3$ ways), then the remaining value is forced to map to slot $3$. That's $30$ functions for a given permutation, hence $\fbox {30*30=900}$

All told, that's $\fbox {2220}$.

Warning: while not complex, the above is fairly error prone. I'd check it.

Update: Indeed, as noted in the comments below, there was a careless error which has now been corrected. Sadly, this does not guarantee that there are no others.

$\endgroup$
  • $\begingroup$ Thanks again. In case 2 of question 2, 'to pick two values to map to slot 2', shouldn't we have $C^3_2$ ways to do so? $\endgroup$ – Nighty Dec 9 '15 at 3:52
  • $\begingroup$ Indeed! Good catch, I'll correct it. $\endgroup$ – lulu Dec 9 '15 at 12:12

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.