0

Here we choose multisets of men who get to have a certain number of razors. Are we dealing with a set of $12$ men or a multiset of $12$ men?

The formula for $\text {$n$ multichoose $k$}$ is $\left(\!\!\binom{n}{k}\!\!\right) = \binom{n + k - 1}{k}$ where ${n + k - 1}$ corresponds to a multiset. But it sounds like the men make up a set, not a multiset.

Do we choose $k$ multisets out of a multiset or a regular set?

JMoravitz
  • 79,518
effofexx
  • 35
  • Are the razors identifiable, that is, if two men swap one razor for another is that a different arrangement? If you give all the razors to one man, does it matter which man? – David K Dec 30 '14 at 19:46
  • All the razors are identical. Generally, I don't really care about this particular problem. What I want to know is if we choose multisets out of a multiset or a regular set or both. – effofexx Dec 30 '14 at 19:48
  • 1
    It should be mentioned to others reading this and to the OP, that \frac{,}{,} is very different from \binom{,}{,}. $\frac{n}{k}\neq \binom{n}{k}$. Also to mention, to typeset the multichoose function, I recommend \left(!!\binom{n}{k}!!\right) which displays as $\left(!!\binom{n}{k}!!\right)$ – JMoravitz Dec 30 '14 at 20:03

1 Answers1

1

The original $12$ men are a set (assuming they can be distinguished, which is a usual assumption in such problems).

Assuming the razors cannot be distinguished, then you can represent one arrangement of the razors by a multiset of $8$ members consisting of zero or more "copies" of each man. That is, if the first man receives exactly two razors, then the first man is listed exactly twice in the resulting multiset.

Hence $8$ razors can be distributed among $12$ men in $\left(\!\!\binom{12}{8}\!\!\right)$ ways.

The fact that $\left(\!\!\binom{n}{k}\!\!\right) = \binom{n+k-1}{k}$ is usually explained using the "stars and bars" method. What this fact tells us is that the number of ways to choose $k$ elements from $n$ with repetition is the same as the number of ways to choose $k$ elements from $n+k-1$ without repetition. In this case, $\left(\!\!\binom{12}{8}\!\!\right) = \binom{19}{8}.$ There is no obvious set of $19$ objects in this problem, so we have to make one up, namely the $19$ positions in a string of "stars" and "bars", from which we are going to choose $8$ places to put a "star". The other positions are filled with "bars". The number of razors received by the first man is the number of stars before the first bar, the razors received by the second man are the number of stars between the first and second bar, and so forth.

Note that $\binom{n+k-1}{k}$ is just an ordinary "choose" using ordinary sets, not a multichoose. There just happens to be a way to make each of these ordinary subsets correspond to one of the multisets that are counted by $\left(\!\!\binom{n}{k}\!\!\right)$.

David K
  • 98,388
  • $\binom{n}{k}$ is generalized as $\left(!!\binom{n}{k}!!\right) = (\frac {n + k - 1}{k})$, right? Does it mean we multichoose out of $n + k - 1$ which is a multiset? – effofexx Dec 30 '14 at 20:13
  • @effofexx I wouldn't call "multichoose" a generalization of "choose". I've expanded my answer to try to address the question as clarified by the above comment. – David K Dec 30 '14 at 20:34
  • Consider a generic multiset. We can encode it with $k$ stars and $n - 1$ bars. So, there's a bijection between the general multiset and $n - k + 1$. That means the number of all subsets sourced from $n - k + 1$ will equal the number of all submultisets sourced out of the general multiset. Is that correct? – effofexx Dec 30 '14 at 22:22
  • I'd be careful to write "$k$-element subsets of an $n-k+1$-element set" (there are a lot more subsets if you remove the $k$-element restriction). That's what you meant, right? I suppose if you populate an initial multiset with enough copies of the elements to choose then you can consider that you are taking submultisets. It feels like a workaround to me, however; I'd rather use a set as input, and make copies of its elements with repetition to form each multiset, that is, build the multiset up to size rather than trim it down to size. – David K Dec 30 '14 at 22:44
  • Just looked up the proof: consider ${1, 1, 1, 2, 3, 3, 5 }$. Encode it as $*|*|||*$. Generally, this code is a list $n - k + 1$. This is where I get stuck. All the subsets of $n - k + 1 $ correspond to something. What's that "something"? Submultisets? Do all the subsets correspond to all the submultisets just because the multiset and list they are sourced from correspond to each other? – effofexx Dec 30 '14 at 23:21
  • I think you're trying too hard to make too many correspondences between things we see when we "multichoose" and things we see when we "choose". The multisets and the subsets of the size-$n-k+1$ set correspond because we have algorithms (encoding/decoding) to translate one to the other and back again. The multisets aren't selected from a set or multiset of size $n-k+1$ (or at least I've never found any useful way to imagine that they are). But I applaud your effort. – David K Dec 30 '14 at 23:43