1
$\begingroup$

How many ways to distribute 10 identical cups between three distinguishable tables?

So I know the answer is 12C2 but I'm not exactly sure why. The answer given says to arrange it so you have T(1)cccT(2)T(3)ccccccc and then you just have to see that there are 12 spaces to put the two tables in. However I can only see eleven spaces (since if you put T(2) to the left of T(3) it's the same as putting T(2) at the very end because both ways T(2) will have no cups on it, same goes for T(3)). One way I saw on here that explained in a way I understood that it's just the number of ways to arrange 12 symbols in a line (with there being 2 types of symbol). But I'd like to know the reasoning behind the answer given in my lecture notes.

$\endgroup$
2
$\begingroup$

Here are your cups:

$\cup\cup\cup\cup\cup\cup\cup\cup\cup\cup$

You can put dividers in between to divide which table they go on. Here's one way:

$|\cup\cup\cup\cup\cup\cup|\cup\cup\cup\cup$

How many ways can you do this?

$\endgroup$
  • $\begingroup$ I initially thought you'd used $\cup$ instead of U and were making a nice pun. $\endgroup$ – pjs36 Jul 14 '17 at 19:45
  • 1
    $\begingroup$ @pjs36 Ha! Well I can't let that opportunity pass! Edited. :) $\endgroup$ – John Jul 14 '17 at 19:47
  • $\begingroup$ Yes, I know what the answer is. What I'm looking for is an explanation to the method given in my lectures $\endgroup$ – nic Jul 22 '17 at 21:52
  • $\begingroup$ What wasn't clear about the method I gave you? $\endgroup$ – John Jul 22 '17 at 22:06
0
$\begingroup$

Let's see how many ways to distribute 10 cups between 3 tables. Let's start with no cups on the first table: 0 0 10, 0 1 9, 0 2 8, 0 3 7, 0 4 6, 0 5 5, 0 6 4, 0 7 3, 0 8 2, 0 9 1, 0 10 0. So, 11 ways to distribute the cups when there are no cups on the first table. The total number will be 11 + 10 + 9 +...+ 1 = 12C2

$\endgroup$
0
$\begingroup$

The following is quite a famous theorem in Combinatorics.

Stars And Bars Theorem: For any pair of positive integers $n$ and $k$, the number of $k$-tuples of $non-negative$ integers whose sum is $n$ is equal to $\binom{n+k-1}{k-1}$

For your given problem we have $10$ cups which have to be distributed among $3$ tables(assuming that some of the tables can be empty)

Here each table constitutes to a tuple, so $k=3$ and total number of cups $n=10$

$$\binom{n+k-1}{k-1}=\binom{12}{2}$$

$\endgroup$
  • $\begingroup$ How is that formula derived? $\endgroup$ – nic Jul 22 '17 at 21:52
0
$\begingroup$

Let $x_k$ be the number of cups placed on the $k$th table. Then $$x_1 + x_2 + x_3 = 10$$ where $x_1$, $x_2$, and $x_3$ are nonnegative integers. A particular solution corresponds to the placement of two addition signs in a row of ten ones. For instance, $$1 1 1 + + 1 1 1 1 1 1 1$$ corresponds to the solution $x_1 = 3$, $x_2 = 0$, and $x_3 = 7$, while $$1 1 1 1 1 + 1 1 1 1 + 1 1 1$$ corresponds to the solution $x_1 = 5$, $x_2 = 5$, and $x_3 = 3$. The number of such solutions is the number of ways two addition signs can be inserted in a row of ten ones, which is $$\binom{10 + 2}{2} = \binom{12}{2}$$ since we must choose which two of the twelve positions (for ten ones and two addition signs) will be filled with addition signs.

Edit: The general problem we wish to solve is finding the number of ways $n$ identical objects can be distributed to $k$ distinguishable boxes.

Let $x_j$, with $1 \leq j \leq k$, denote the number of objects placed in the $k$th box. Note that $x_j$ may equal zero. Then $$x_1 + x_2 + x_3 + \cdots + x_k = n$$ A particular solution corresponds to the placement of $k - 1$ addition signs in a row of $n$ ones. Thus, the number of such solutions is the number of ways of arranging the $n + k - 1$ symbols consisting of $n$ ones and $k - 1$ additions signs in a row, which is $$\binom{n + k - 1}{k - 1}$$ since we must choose $k - 1$ of the $n + k - 1$ positions for the addition signs.

In your example, the objects are the cups and the boxes are the tables on which they are placed. Hence, $n = 10$ and $k = 3$, so there are $$\binom{10 + 3 - 1}{3 - 1} = \binom{12}{2}$$ ways to distribute the cups to the tables.

Note: A related problem that also reduces to solving the equation $$x_1 + x_2 + x_3 + \cdots + x_k = n$$ is selecting $n$ objects from $k$ types of objects, in which there are at least $n$ objects of each type available. This is a combination with repetition problem.

$\endgroup$
  • $\begingroup$ Thank you for your answer but I was looking for an explanation to the method given in my lectures. I understood the answer when using a different method, just not the one used in lectures $\endgroup$ – nic Jul 22 '17 at 21:54
  • $\begingroup$ I have added a derivation of the general formula. $\endgroup$ – N. F. Taussig Jul 22 '17 at 23:47

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.