# Permutation and combination - Discrete Math

You have $15$ marbles and three jars labeled A, B, and C. How many ways can you put the marbles into the jars…

(a) If each marble is different? (My answer C(15,3) )

(b) If each marble is the same? ( My Answer that i think is C(15+3-1,3) as order doesnt matter) NOT SURE THOUGH!!

(c) If each marble is the same and each jar must have at least two marbles?

(d) If each marble is the same but each jar can have at most 6 marbles?

(e) If you have 10 identical red marbles and 5 identical blue marbles?

I am not sure about my answer so any help would be appreciated.

-
so would (a) be 3x15! ? – steven Dec 2 '11 at 7:27
oh so it would 3^15 for (a) ? – steven Dec 2 '11 at 7:31
and for (c) how would you go about starting it? – steven Dec 2 '11 at 7:34
On (b), I didn't notice you had $\binom{15+3-1}{3}$, it should be $\binom{15+3-1}{3-1}$. For details see Stars and Bars on Wikipedia. – André Nicolas Dec 2 '11 at 8:06
how would you start part c? – steven Dec 2 '11 at 8:08

If each marble is different?

You must decide between trhee jars for each marble, so $3^{15}$

If each marble is the same?

You must decide how many to put in A, then how many in B (the rest go in C). So:

being $N = 15$

• how many in A: $A$ balls ($0\le A\le 15$), N+1 posibilities
• how many in B: $B$ balls ($0\le B\le 15-A$), N-A+1 posibilities

$$\sum_{A=0}^{N}{(N-A+1)} =$$ $$= (N+1)(N+1) - \sum_{A=0}^{N}{A} =$$

$$= N(N+1) + (N+1) - \frac{N(N+1)}{2} =$$

$$= \frac{N(N+1)}{2} + (N+1) =$$

$$= \frac{N(N+1) + 2(N+1)}{2} =$$

$$= \frac{(N+2)(N+1)}{2}$$

If each marble is the same and each jar must have at least two marbles?

Put two marbles in each jar. Then you have 9 marbles left. So answer will be like (b) but with $N = 9$

If each marble is the same but each jar can have at most 6 marbles?

Put 6 marbles in each jar. Now you must take from them 3 balls to get a valid solution. You can pick how many balls to take from each jar. how many (0 to 3) from A, and then how many from B (0 to 3-A). That's analogous to the previous problem, but with three balls.

$$\frac{(N+1)(N+2)}{2}$$

where $N = 3$

If you have 10 identical red marbles and 5 identical blue marbles?

Place first red marbles, then blue marbles. They are independent so the number of posibilities will be the number posibilities for placing red marbles multiplied by the number of posibilities for placing the blue marbles.

$$\frac{(Na+1)(Na+2)}{2} . \frac{(Nb+1)(Nb+2)}{2}$$

$$Na = 10, Nb = 5$$

-
Oh, my! I have to correct the formula! – helios Dec 2 '11 at 10:55
Corrected. Now the formula is nicer. – helios Dec 2 '11 at 11:15
Corrected solution for "at most 6 marbles on each jar". It's not $3^3$ because the order is not relevant. – helios Dec 2 '11 at 15:33

I hope I am not misunderstanding your questions. Here are my answers (in some cases I'm giving only hints or partial answers).

a) In this case you have three choices to make for each marble. Therefore, the total number of arrangements is $3^{15}$.

b) If you know about generating functions, the answer is the coefficient of $x^{15}$ in $(1+x+x^2 \ldots + x^{15})^3$. This happens to be the same as the coefficient of $x^{15}$ in the expansion $(1-x)^{-3}$ which is $\binom{15+3-1}{3-1} = \binom{17}{2}$.

c) and d) You can use generating functions and solve for these cases. Andre Nicolas has already given you the answer in his comment for case c). Try and solve for case d) using generating functions.

e) The answer is the product of the answers for 10 identical red marbles and 5 identical blue marbles separately.

-
how would you start c? – steven Dec 2 '11 at 8:08
For (c) and (d) you could simply use stars and bars too. – Quixotic Dec 2 '11 at 12:31

### Solution 1

One marble may go into any Jar, independent of what the other marbles do. So, $3^N$.

### Alternative solution to 2

$N=15$ marbles that are identical, well enough.

$$\circ\vert\circ\circ\circ\circ \circ\circ\vert\circ\circ\circ \circ\circ\circ\circ\circ$$

Suppose I have two rods and place them in between the balls. Marbles to the left of the first rod are thrown into Jar A, between the rods, Jar B, and to the right of the second rod, into Jar C.

$$\vert\circ\vert\circ\vert\circ\vert\circ\vert\circ \vert\circ\vert\circ\vert\circ\vert\circ\vert\circ \vert\circ\vert\circ\vert\circ\vert\circ\vert\circ\vert$$

(It's clear that there are $N+1$ spaces in all to place the rods)

So there are $(N+1)$ spaces. If the two rods aren't placed into the same space, there will be $C_{n+1}^2$ methods of partition. If the rods are placed into the same space (where at least one jar will be empty) then there $(N+1)$ more methods.

All in all, we have $C_{n+1}^2+(n+1)=\frac{(n+1)(n+2)}{2}$ methods.

### Solution to 3

Well, rods will cleary have to be at least 2 marbles apart. There are two ways to finish this.

1. Calculate how many methods could we put the rods now, clearly $C_{n+1-4}^2-(n-4)$.

($-4$ because we can't let Jar A/C have less than 2 marbles; $-(n-4)$ because rods can't be on both sides of the same ball);

2. Use the method by helios, where this is $N=9$.

### Solution 4/5

Again, nice job, helios. :)

-