Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Combinations and Permutations

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?

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations

Hi careless25;


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Combinations and Permutations

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.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations and Permutations

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)


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Combinations and Permutations

Can you explain where i went wrong?

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations and Permutations

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


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations

Hi careless25;

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

Hi anonimnystefy;


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations and Permutations

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) .


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Combinations and Permutations

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?

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations and Permutations

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.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Combinations and Permutations

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

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations and Permutations

Then I think we might be looking at some casework.


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Combinations and Permutations

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?

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Combinations and Permutations

ok so how do I divide this question into cases?

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations and Permutations

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


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Combinations and Permutations

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.

Offline

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

Bob
Administrator
Registered: 2010-06-20
Posts: 10,053

Re: Combinations and Permutations

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.  smile smile 

(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


Children are not defined by school ...........The Fonz
You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei
Sometimes I deliberately make mistakes, just to test you!  …………….Bob smile

Offline

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

careless25
Real Member
Registered: 2008-07-24
Posts: 560

Re: Combinations and Permutations

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.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations

Hi;

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


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations and Permutations

Hi bobbym


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations

Hi;


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations and Permutations

Hi bobbym


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations

Hi anonimnystefy;


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

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

anonimnystefy
Real Member
From: Harlan's World
Registered: 2011-05-23
Posts: 16,049

Re: Combinations and Permutations

Hi bobbym


“Here lies the reader who will never open this book. He is forever dead.
“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment
The knowledge of some things as a function of age is a delta function.

Offline

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

bobbym
bumpkin
From: Bumpkinland
Registered: 2009-04-12
Posts: 109,606

Re: Combinations and Permutations

Hi;


In mathematics, you don't understand things. You just get used to them.
If it ain't broke, fix it until it is.
Always satisfy the Prime Directive of getting the right answer above all else.

Offline

Board footer

Powered by FluxBB