1. ## Combination

THis is from the 2015 perms thread
A zoo keeper wants to place 6 tigers in 4 cages, each can fit a maximum of two tigers.
In how many ways can he place the tigers if no cage to be left empty?

I got

4! x (6C2 x 4C2 x 2C1 x 1C1) = 4320

Because: First Cage: 6C2
Second Cage: 4C2
Third Cage: 2C1
Fourth Cage: 1C1
4! ways to arrange these

Some people got 2160 which is 4320/2
some also got 1080 which is 4320/4

IM confused to what is the right answer. If so why am I wrong

2. ## Re: Combination

Are these four cages distinct or identical?

Are the tigers distinct or identical?

3. ## Re: Combination

Assuming the tigers and cages are identical and arranged in a straight line:

If no cage is to be empty and each cage can fit a maximum of two tigers, then there must be either one or two tigers in each cage.

Also, there must be exactly 6 tigers.

The only way to make 6 from adding 1 or 2, four times, is $2+2+1+1$ in any order (that sentence is a bit botched but hopefully you get what I mean).

So assuming the cages are identical and they're not arranged in a circle, the problem can be reduced to "How many ways can you arrange two 2's and two 1's?"

$\frac{4!}{2!\cdot 2!} = 6$

Another way to solve the problem is to consider each case by making something similar to a tree diagram.

If the tigers are distinct, multiply the answer by $6!$.

If the cages are distinct, multiply the answer by $4!$.

Your answer should be correct if the tigers are distinct but the cages are not ($6 \cdot 6! = 4320$).

4. ## Re: Combination

Originally Posted by HeroWise
THis is from the 2015 perms thread
A zoo keeper wants to place 6 tigers in 4 cages, each can fit a maximum of two tigers.
In how many ways can he place the tigers if no cage to be left empty?

I got

4! x (6C2 x 4C2 x 2C1 x 1C1) = 4320

Because: First Cage: 6C2
Second Cage: 4C2
Third Cage: 2C1
Fourth Cage: 1C1
4! ways to arrange these

Some people got 2160 which is 4320/2
some also got 1080 which is 4320/4

IM confused to what is the right answer. If so why am I wrong
Have you tried the Stars and Bars method?

5. ## Re: Combination

No I have not

I have heard of it and have seen @fan96 post something about it before,

6. ## Re: Combination

https://en.wikipedia.org/wiki/Stars_...combinatorics)

Basically if you want to place $n$ objects in $k$ boxes you can model it using something like

$\star | \star \star \star | \star \star$

Where the stars are the objects and the bars represent the dividers between boxes. So in the above case you would be placing 6 objects in 3 boxes.

By using the formula for permutations with repetition you can count the number of ways to distribute 6 objects across 3 boxes with no restriction:

$\frac{8!}{6!\cdot 2!}$,

since there are 6 stars and 2 bars.

It's pretty useful to know but for this question, since the numbers are small and there are quite a few restrictions (no more than 2 tigers in a cage, no cage empty), I don't think it's as useful here. You'd have to subtract the cases where two dividers are together (representing an empty box) and when there are more than two stars next to each other (i.e. more than two lions in a cage).

7. ## Re: Combination

Can you give me a good question and can you please work it out with this method?

8. ## Re: Combination

Originally Posted by HeroWise
Can you give me a good question and can you please work it out with this method?
$\noindent 1) There are 4 different types of lollipops available at a lolly store. Alice wants to buy 10 lollipops. How many different selections can she make?$

$\noindent 2) Let r be a positive integer and n a non-negative integer. Find the number of ordered r-tuples of non-negative integers (x_{1}, \ldots, x_{r}) that satisfy$

$x_{1} + \cdots + x_{r} = n.$

9. ## Re: Combination

Here's an easier question from one of my school's 4U Task 1 papers:

In how many ways can nine identical rings be placed on the four fingers of the left hand, excluding the thumb, if:
• there are no restrictions?
• there must be at least one ring on each finger?
• there are no restrictions and the rings are all different?

Originally Posted by InteGrand
$\noindent 2) Let r be a positive integer and n a non-negative integer. Find the number of ordered pairs of non-negative integers (x_{1}, \ldots, x_{r}) that satisfy$

$x_{1} + \cdots + x_{r} = n.$
Is that a past HSC question?

10. ## Re: Combination

fan when there are no restrictions its 220 right?

I used the stars and bars method for it

9 stars 3 bars

12C3

for ii) it is 220 - cases with a finger or till 4 having no rings.

but how do i do it?

11. ## Re: Combination

Originally Posted by HeroWise
fan when there are no restrictions its 220 right?

I used the stars and bars method for it

9 stars 3 bars

12C3

for ii) it is 220 - cases with a finger or till 4 having no rings.

but how do i do it?
Yep it's 220.

For the second question, the marker's answer sets up the rings as such:

R_R_R_R_R_R_R_R_R

Where the eight "_" characters represent possible spaces for a divider, of which there must be three. Thus the answer is simply $^8C_3 = 56$.

12. ## Re: Combination

Originally Posted by fan96
Here's an easier question from one of my school's 4U Task 1 papers:

In how many ways can nine identical rings be placed on the four fingers of the left hand, excluding the thumb, if:
• there are no restrictions?
• there must be at least one ring on each finger?
• there are no restrictions and the rings are all different?

Is that a past HSC question?
I doubt it. If it is, it would be from a long time ago and would be coincidence (I didn't pick that question out of a past HSC paper). I included it since it's a nice application of Stars and Bars.

13. ## Re: Combination

Thanks for the link to the stripes and bars, the wiki article is way too complicated for me, but I think I get the gist of it.
Originally Posted by fan96
In how many ways can nine identical rings be placed on the four fingers of the left hand, excluding the thumb, if:
• a) there are no restrictions?
• b) there must be at least one ring on each finger?
• c) there are no restrictions and the rings are all different?
a) 9 stripes (identical) + (4-1) bars (identical), so: 12! / 9!3! <- dividing out the identical elements)
b) I didn't get this initially, but the explanation above made al ot of sense, so I get it now.
c) 9 stripes (each different) + 3 bars, so: 12! / 3! = 79833600 <-- dividing out the identical elements - the stripes are not identical, so not divided.
is that correct?

14. ## Re: Combination

Originally Posted by InteGrand
$\noindent 1) There are 4 different types of lollipops available at a lolly store. Alice wants to buy 10 lollipops. How many different selections can she make?$
nfi about the second question, but the first one:

13! / 10!3!

is that right?

and if she absolutely wanted one of each lollipop, it'd be:
9C3

15. ## Re: Combination

i didnt understand b

If going via Stars and Bars how does one accomplish it?

16. ## Re: Combination

Originally Posted by Roy G Biv
nfi about the second question, but the first one:

13! / 10!3!

is that right?

and if she absolutely wanted one of each lollipop, it'd be:
9C3
For the first one, we have 4 different lollipop types and want to buy a total of 10 lollipops. So we use 3 bars and 10 stars. Something like this:

*** | ** | **** | *.

That above pattern would represent buying 3 of the first lollipop type, and 2, 4, 1 of the second, third and fourth lollipop types respectively.

The total number of ways to buy the lollipops is the total number of ways to arrange the objects in the above picture, which is (13!)/((3!) (10!)).

17. ## Re: Combination

lol for 90% of reading your response, I thought I got it wrong :|

18. ## Re: Combination

btw why do u divide by 3! isnt that representing distinct lollipops? and How did u solve fan96's qtn b Roy G Biv?

19. ## Re: Combination

nah, read the stars and stripes method above. Combination

and b for fan96 question - just place 1 ring on each finger before you even start the question - since the rings are all identical, it doesn't matter which ones you place.
remaining 5 rings onto 4 fingers: use stars and stripes method, as explained above.

There are currently 1 users browsing this thread. (0 members and 1 guests)

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•