Star and Bars Questions

[westin]

Hi, can someone teach me how to use star and bars to do this MathCount problem: "Lynn has 3 cats and a row of 4 cat beds. Each cat bed can hold one or two cats, and each cat is in a bed. Listing the number of cats in each bed from left to right, how many unique sequences are there? ". The answer is 16.

Thanks!

 

[westin]

I tried using stars equal to 4*2=8 and bars equal to 3-1 = 2,. using the star and bar formula (10!/8!2!), I got 45. however, i know that this answer is assuming the sequence of each bad is counted. as a result, I am over counting the sequences. but I don't know how I should get from 45 to 16 which is the correct answer.

 

[lex]

(a) First, you need to work out how many ways there are of distributing 3 cats in 4 beds (without any restrictions).
(b) Then take away the number of these arrangements which break the rule that a max of 2 can be in each bed i.e. how many different arrangements are there with all 3 cats in one of the beds?

To do (a) you simply have to understand the basic stars & bars method, which is described in the first half of the attached pdf.
(b) is easy.

 

[pka]

Hi, can someone teach me how to use star and bars to do this MathCount problem: "Lynn has 3 cats and a row of 4 cat beds. Each cat bed can hold one or two cats, and each cat is in a bed. Listing the number of cats in each bed from left to right, how many unique sequences are there? ". The answer is 16.

The so-called stars & bars refer to problems involving placing $N$ non-distinct objects into $K$ distinct cells.
This becomes a modeling problem: the $K-1$ bars model the $K$ cells and the $N$ stars model the $N$ objects. In this case: the $~*|~**~|\quad\quad|~$ models one cat in bed one, two cats in bed two, no cat in bed three and no cat in bed four. Whereas $~|~***~|\quad\quad|~$ models all three cats in bed two. There are $\dfrac{6!}{(3!)(3!)}=20$ SEE HERE ways to arrange those $3$ stars and $4-1$ bars. But those twenty ways include four in with all cats in the same cat-bed. So subtract $20-4=16$.
The main point: $N$ non-distinct objects into $K$ distinct cells can ne done in $\dfrac{(N+K-1)!}{(N!)((K-1)!)}$ ways.

 

[westin]

Thank you for the help! I understand now that you need to subtract the possibility that the 3 cats are in the same bed. Thanks!

 

[westin]

Hi Les, Thank you very much for the pdf. It is helpful!

 

[lex]

Yes. It is a good clear explanation.

 

[sky2rain]

c=Cats need to be separated by 3 I(bars). Since if before the first bar or behind the first bar bear different meanings, then before the last bar and behind last bar would bear different meanings. To demonstrate: cats before first bar has a meaning, behind first and before the second has a meaning, behind second and before third has a meaning, and behind the third has a meaning, hence four meanings implying four beds. Problem states that 3 cannot sleep in the same bed, use the starts and bars formula to calculate total number and eliminate the following 4 cases: cccIII, IcccII, IIcccI, IIIccc