Suppose you want all players to start with a unique setup in terms of the number of each of the four spices, with a total number of spices equal to 0 to the maximum 10 in a caravan. How many players could you have?

A first guess would be that each of the 10 caravan positions can have one of five possible values (one of the four spices or no spice). Thus, we might think that there are $5^{10}=9765625$ setups. However, as we don't distinguish, for example, one yellow (turmeric) and one red (saffron) from one red and one yellow, this dramatically over counts the number of unique setups.

One approach to dealing with this type of problem is to always order the spices in a certain way. Imagine the 10 caravan spaces laid out in a line, starting with brown (cinnamon), then green (cardamom), red (saffron), yellow (turmeric), and finally no spice. We can express each unique setup in terms of the number of each spice. Equivalently, we may note the transition points. For example, instead of focusing on 3 brown cubes, 2 green cubes, 1 red cube, 3 yellow cubes, and 1 blank space, we can look at the transitions after positions 3, 5, 6, and 9. In terms of numbers, this hasn't helped us much, though we have reduced down from five parameters to four (we could have done this other ways, since we know there are 10 total spots for cubes, so the initial numbers must sum to 10). However, if we look at the nine possible transition points between the ten caravan locations, we can see that each unique setup is a unique selection of four of those nine possible transition points. Selecting a subset from a larger set is a problem we know how to solve with our handy combination or binomial coefficient,

\begin{align} \binom{n}{k} = \frac{n!}{k! \cdot (n-k)!}, \end{align}However, that's not quite right. Let's consider what happens when we have none of one type of the spices. That means that two of our transition points overlap, which isn't accounted for when always choosing four transition points. We could handle this by adding up different scenarios, but that's ugly and boring. So while it could give us the answer, let's find something more elegant.

We're trying to count the number of ways to take 10 of something and allocate it into 5 buckets, where each bucket can hold 0 through 10. We can add one into each of the buckets and not change the situation. Since there are five buckets, that means adding five to the number of possible transition points. That is, the number of ways to take 15 of something and allocate it into 5 buckets where each bucket can hold 1 through 11 is the same. Thus, we can take $n+5-1$ choose $4$,

\begin{align} \binom{10+5-1}{4} = \binom{14}{4} = \frac{14!}{4! \cdot 10!} = 1001. \end{align}

As a check for this method, we can look at a simpler case, where it's easier to count or come up with the number in another way. Suppose there are only 2 spots on the caravan. Our formula above says there should be $\binom{2+5-1}{4} = \binom{5}{4} = 15$ setups. With only 2 caravan spots, there are only two types of pattern: two of one spice (including no spice) and one each of two different spices. For the two of one there are 5 ways to do this, and for the one of each, there are $\binom{5}{2} = 10$ ways of doing it. Summing these two ways we get 15. This isn't a perfect check, and it's probably more useful to use to think about the problem and how it works.

## No comments:

## Post a Comment