1

Arrange the bottles of liquor in the following order: rum, tequila, whiskey, vodka. Then assign to each bottle of tequila its position number increased by $1$, to each bottle of whiskey its position number increased by $2$ and to each bottle of vodka its position number increased by $3$. The position numbers of rum are unchanged. For example, $2, 3, 4, 5, 7, 8, 9$ represents the purchase of $4$ bottles of tequila and $3$ bottles of whiskey. So, then the number of all these $7$-sequences is the number of $7$-combinations of $10$ numbers: $C(10, 7) = 120$.

What I don't get is why we count $7$-sequences as if they are $7$-sets. Please, elaborate.

  • Maybe because the sequences must be in increasing order, which means you are really choosing a combination rather than an arbitrarily ordered sequence. Similar to why the number of 6-sequences of Heads and Tails with exactly 2 Heads is C(6,2). You might also search this site for "stars and bars" which is another way of looking at this sort of combinatorial problem. – Ned Jan 01 '15 at 22:38
  • Does a sequence with increasing order of elements correspond to a set? If so, why? – effofexx Jan 01 '15 at 22:43

1 Answers1

4

Each possible set of $7$ bottles corresponds to a unique sequence of a particular type. We assign the value $0$ to rum, $1$ to tequila, $2$ to whiskey, and $3$ to vodka. Then we take our seven bottles and list them in numerical order. Let me give an example more complicated than the one in the question: we have $2$ bottles of rum, $1$ of tequila, $3$ of whiskey, and $1$ of vodka. This gives us the liet $$\begin{array}{ccc}0&0&1&2&2&2&3\end{array}\;.\tag{1}$$ Now write below each bottle its position number in the list, and add the two rows:

$$\begin{array}{ccc} 0&0&1&2&2&2&3\\ 1&2&3&4&5&6&7\\ \hline 1&2&4&6&7&8&10 \end{array}$$

The bottom row, below the line, is the sequence corresponding to this set of bottles.

What kinds of sequences can we get? First, they must be increasing. As we go to from one column to the next, the bottle number either stays the same or increases, and the position number increases, so the total must increase. Next, the first term of the sequence must be at least $1$, and the last is at most $10$. In fact, the possible sequences are precisely the strictly increasing sequences of positive integers whose last term is at most $10$, and each such sequence can be reverse engineered to yield the unique set of bottles producing it. Suppose, for instance, that I have the sequence

$$\begin{array}{ccc}2&4&5&6&8&9&10\end{array}\;.\tag{2}$$

Subtracting the position numbers reduces this to

$$\begin{array}{ccc}1&2&2&2&3&3&3\end{array}\;,\tag{3}$$

and I see that my sequence describes a set of one bottle of tequila, three of whiskey, and three of vodka.

What we have here is a bijection between sequences like $(1)$ and $(3)$ that describe a set of $7$ bottles by listing the types of bottles in numerical order, and increasing sequences like $(2)$. Specifically, if $B$ is the set of all non-decreasing $7$-tuples from the set $\{0,1,2,3\}$, and $S$ is the set of all strictly increasing sequences of positive integers with last term at most $10$, then we’ve described a bijection between $B$ and $S$. The members $B$ pretty obviously correspond to the possible sets of $7$ bottles, and the existence of the bijection tells us that $|B|=|S|$, so we can find the number of possible sets of bottles by calculating $|S|$. And that’s pretty straightforward: every $7$-subset of $\{1,\ldots,10\}$ can be arranged as a strictly increasing sequence in exactly one way, and every member of $S$ obviously gives us a unique $7$-subset of $\{1,\ldots,10\}$, so $|S|=\binom{10}7$.

The point of using $S$ is that $|S|$ is easy to calculate, while $|B|$ is a bit harder to calculate directly. For another approach to the problem you might like to take a look at this Wikipedia article.

Brian M. Scott
  • 616,228