Combinations and Permutations

careless25 · 2012-06-21 07:35:44

Hi,

I needed some help with combinations and permutations.

the question is :

John has baked 31 cupcakes for 5 different students. He wants to give them all to
his students but he wants to give an odd number of cupcakes to each one. How many
ways can he do this?

so from reading the mathisfun page on combs and perms, I get this so far:

since theres 31 cupcakes to be shared in between 5 students, the combinations for this will be (31+5-1) choose 5. But this does not take into consideration the odd number restriction. How can I do this?

bobbym · 2012-06-21 15:59:21

Hi careless25;

careless25 · 2012-06-24 14:06:53

Hmm, I have a different approach. Just wondering if this would work:

Give each person one cupcake from the 31. So you have 26 left.
Then couple those 26 cupcakes so you never give a person an even number of cupcakes.
This gives you 13 pairs of cupcakes to share between 5 people.
So then the answer would be (13+5-1) choose 5.

anonimnystefy · 2012-06-24 14:26:42

That would not yield the correct answer. Bobbym's approach is okay and gets you the correct answer.

The generating function used is:

Last edited by anonimnystefy (2012-06-24 14:27:00)

careless25 · 2012-06-24 15:02:30

Can you explain where i went wrong?

anonimnystefy · 2012-06-24 15:09:41

If we use your way, there isn't a possibility to control the parity of the number of cupcakes each person has.

bobbym · 2012-06-24 19:14:31

Hi careless25;

The generating function takes care of the combinatorical reasoning all by itself.

Hi anonimnystefy;

anonimnystefy · 2012-06-24 23:36:28

Hi bobbym

My GF is correct. You probably used something like x*(1-x**60)/(1-x**2) instead of my x/(1-x**2) .

careless25 · 2012-06-25 00:54:09

We haven't been taught generating functions yet, thats why I am trying to find a way to solve it without that.

@bobbym: so is my way of counting correct?

anonimnystefy · 2012-06-25 00:56:07

It will be harder solving it without GF's. I suggest you learn something about them. You can start from the "generatingfunctionology" from Herbert Wilf.

careless25 · 2012-06-25 01:07:58

Its an assignment question and i need to solve it using what I have learned from class.

anonimnystefy · 2012-06-25 01:15:40

Then I think we might be looking at some casework.

careless25 · 2012-06-25 01:24:17

If i multiply my previous formula by (26 choose 2)+(24 choose 2)+(22 choose 2).....(2 choose2) should that take care of the parity of the cupcakes?

careless25 · 2012-06-25 02:39:42

ok so how do I divide this question into cases?

anonimnystefy · 2012-06-25 02:45:41

I am not sure. I never knew how to do this kind of problems without GFs.

careless25 · 2012-06-25 03:43:26

Ok I have another question I cant answer.
Prove this relationship is true.

from k=r to n. Given n,r are in N and r<=n.

Bob · 2012-06-25 07:10:38

hi careless25

I've got it here scribbled on a piece of paper. I'm hoping you'll accept an outline of what to do. It'll save me a big heap of Latex. And of course, it'll be good for you to work through the algebra yourself.

(i) Write both sides with factorials instead of combinations. You'll see that n! and r! occur in the right places in both expressions.

(ii) So start with the left hand side and factorise out those two factorials and you're half way there!

(iii) Cancel out the k! inside the sum.

(iv) To get the (n-r)! term as another common factor, force it. Introduce that term, top and bottom, to every term inside the summation.

Then factorise out the term from the denominators and the bits outside the sum are the required combination for the right hand side. 3/4 way done!

(v) In the sum, simplfy a bit.

(vi) Have a look at the Pascal's triangle formula for 2^n on this page:

http://en.wikipedia.org/wiki/Pascal's_triangle

It's about a quarter of the way down the page; and it's proved too, in case you need to do that rather than just quote it.

Apply that to the summation and you're finished!

Hope that helps.

Bob

careless25 · 2012-06-25 10:11:10

Thanks bob!
Got it, we actually proved the pascals triangle formula for 2^n in class. I just hadnt of thought of adding in the (n-r)! on top and bottom of the summation.

bobbym · 2012-06-26 01:30:16

Hi;

My GF is correct. You probably used something like x*(1-x**60)/(1-x**2) instead of my x/(1-x**2)

anonimnystefy · 2012-06-26 01:36:03

Hi bobbym

bobbym · 2012-06-26 01:52:13

Hi;

anonimnystefy · 2012-06-26 01:55:54

Hi bobbym

bobbym · 2012-06-26 02:04:12

Hi anonimnystefy;

anonimnystefy · 2012-06-26 02:29:04

Hi bobbym

bobbym · 2012-06-26 02:32:31

Hi;

Math Is Fun Forum

#1 2012-06-21 07:35:44

Combinations and Permutations

#2 2012-06-21 15:59:21

Re: Combinations and Permutations

#3 2012-06-24 14:06:53

Re: Combinations and Permutations

#4 2012-06-24 14:26:42

Re: Combinations and Permutations

#5 2012-06-24 15:02:30

Re: Combinations and Permutations

#6 2012-06-24 15:09:41

Re: Combinations and Permutations

#7 2012-06-24 19:14:31

Re: Combinations and Permutations

#8 2012-06-24 23:36:28

Re: Combinations and Permutations

#9 2012-06-25 00:54:09

Re: Combinations and Permutations

#10 2012-06-25 00:56:07

Re: Combinations and Permutations

#11 2012-06-25 01:07:58

Re: Combinations and Permutations

#12 2012-06-25 01:15:40

Re: Combinations and Permutations

#13 2012-06-25 01:24:17

Re: Combinations and Permutations

#14 2012-06-25 02:39:42

Re: Combinations and Permutations

#15 2012-06-25 02:45:41

Re: Combinations and Permutations

#16 2012-06-25 03:43:26

Re: Combinations and Permutations

#17 2012-06-25 07:10:38

Re: Combinations and Permutations

#18 2012-06-25 10:11:10

Re: Combinations and Permutations

#19 2012-06-26 01:30:16

Re: Combinations and Permutations

#20 2012-06-26 01:36:03

Re: Combinations and Permutations

#21 2012-06-26 01:52:13

Re: Combinations and Permutations

#22 2012-06-26 01:55:54

Re: Combinations and Permutations

#23 2012-06-26 02:04:12

Re: Combinations and Permutations

#24 2012-06-26 02:29:04

Re: Combinations and Permutations

#25 2012-06-26 02:32:31

Re: Combinations and Permutations

Board footer