Math Is Fun Forum

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

You are not logged in.

#1 2011-05-29 17:54:28

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

Perms and Combs! and some induction..

Ok so I have been working on this question for more than 8 hours in total...I cannot get it outta my Head so someone explain this to me!

How many arrangements of the word INDEPENDENCE are there? How
many such arrangements have the property that all the Ns come before all
the Es? (For example, CNNDNEEEPIED is one of them.)

Part 1 of the question is easy, its the Ns before the Es thats giving me a headache.

I eventually got to this:
My reasoning is that theres 5 letters that can be placed anywhere: IDPDC
4 Es which come before the 3 Ns

So I made 6 cases, one where all the Ns are the first 3 letters, so i get (9!/(4!2!)) combinations.
second case: 3Ns and 1 extra letter, which gives me: 8!/(3!2!)
third case: 3Ns and 2 letters and so on and so forth
until i get a total of 77220

but then i realized I over counted many many combinations and I gave up at this point

OK thats that question...another one i need help with is:
(n C r) notation means n choose r...

where i=r and the upper bound is n. I have to prove this by induction, I think i need to use this formula: (n C r) = (n-1 C r-1) + (n C r-1)
but then again i get stuck in the induction step.

Any help ASAP is appreciated!!
Thanks a lot

Offline

#2 2011-05-29 17:58:33

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

Re: Perms and Combs! and some induction..

for the first question my answer was:

Offline

#3 2011-05-29 18:30:47

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

Re: Perms and Combs! and some induction..

Hi;

How many arrangements of the word INDEPENDENCE are there?

many such arrangements have the property that all the Ns come before all
the Es?

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

#4 2011-05-29 18:41:15

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

Re: Perms and Combs! and some induction..

I dont want the answer, I want to know the logic behind the answer so for future reference i know how to get it. So can please explain how you got 47520?

Offline

#5 2011-05-29 18:57:01

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

Re: Perms and Combs! and some induction..

The model of the problem is this.

_n_n_n_e_e_e_e_

Now you have 5 letters I D P D C to go in those 8 slots around the n's and e's.

Supposing the letters were all the same... Then the number of ways to put them in there would be a bijection to the number of solutions to the diophantine equation.

a + b + c + d + e + f +g + h = 5 with 0 <= a,b,c,d,e,f,g,h <= 5

I solve the above diophantine equation using generating functions.

Expanding

Look at the coefficient of x^5, it is 792. That would be the answer if all the remaining letters were the same. But they are not.

There are 60 ways to arrange  I D P D C, so 60 * 792 = 47520.

Number is verified by computer.

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

#6 2011-05-29 19:12:16

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

Re: Perms and Combs! and some induction..

Umm is there another way because I havent studied Diophantine equations nor generating functions.
Sorry for the trouble
but thanks!!!

Offline

#7 2011-05-29 19:17:31

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

Re: Perms and Combs! and some induction..

The Diophantine equations are strictly for show, I assume you have studied polynomial multiplication. The generating function actually uses much less math than casework or binomials.

Do you understand the model? Then the number of ways to distribute n identical objects into those 8 slots is

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 2011-05-29 19:30:47

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

Re: Perms and Combs! and some induction..

Yes I have studied polynomial multiplication but I do not get how you got that equation for G(x). Also how are the 2 Ds handled here, if they are switched is this another combination or is it counted as 1? If it is counted as just one(as is what i need) then I do not understand how your calculations incorporate that.

Offline

#9 2011-05-29 19:31:54

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

Re: Perms and Combs! and some induction..

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

#10 2011-05-29 19:43:14

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

Re: Perms and Combs! and some induction..

is it not

?

I am comparing this to lets say putting n balls into 4 boxes....
i.e. n = 10
0001001000100

0s represent balls and 1s represent the slots
so its

then similarly
5 letters in 8 boxes....oh wait theres a limitation here that each box can only contain 1 or 0. Hmm, so no I dont understand how you get that.

Offline

#11 2011-05-29 19:44:42

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

Re: Perms and Combs! and some induction..

No that is incorrect.. Look at the model. How many ways can you put 2 identical balls into those 8 slots?

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

#12 2011-05-29 19:50:42

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

Re: Perms and Combs! and some induction..

Wouldnt that just be 8 choose 2? As i am only selecting any 2 slots out of the 8 slots to put the balls in?

Offline

#13 2011-05-29 19:53:41

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

Re: Perms and Combs! and some induction..

You are missing some. You are getting mixed up with a binary sequence. 28 + 8 = 36 , remember 2 balls can go in each slot! That is why it is

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

#14 2011-05-29 19:58:12

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

Re: Perms and Combs! and some induction..

GAH!!! OK makes sense! This is what happens at 4 am in the morning .
ok so we have

now thats accounting for all the possibilities where the letters can go...how do we account for the order? and the 2Ds?

PS OH!!! 5! is the possibilities to arrange 5 letters and then divide by 2! to account for Ds!! THANKS!!! !!!!
WOOT!

Last edited by careless25 (2011-05-29 20:00:13)

Offline

#15 2011-05-29 20:02:04

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

Re: Perms and Combs! and some induction..

792 is the number of ways for 5 identical letters to fit into those 8 slots. Remember the restrictions on the equation.

a + b + c + d + e + f +g + h = 5 with 0 <= a,b,c,d,e,f,g,h <= 5

Each variable stands for how many is in the slot. We see that the 0 letters could be in any slot or up to 5 letters could be in one slot.

But the letters are not the same. Question, how many arrangements are there of the letters I D P D C?

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

#16 2011-05-29 20:03:00

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

Re: Perms and Combs! and some induction..

Yup got it thanks!!

Offline

#17 2011-05-29 20:04:10

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

Re: Perms and Combs! and some induction..

Are you sure?

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

#18 2011-05-29 20:08:50

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

Re: Perms and Combs! and some induction..

Yes but I will have to review tomorrow morn after a good nights sleep

Also I still need help with the proof by induction on n on:

Last edited by careless25 (2011-05-29 20:09:58)

Offline

#19 2011-05-29 20:10:28

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

Re: Perms and Combs! and some induction..

Hi;

I am not following 8 choose 2 is not the correct answer it is 9 choose 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 2011-05-29 20:13:37

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

Re: Perms and Combs! and some induction..

Sorry i meant post# 14
Yes its 9 choose 2.
Thanks a lot bobbym!! I can get some sleep now
Its been bugging me since friday!

Offline

#21 2011-05-29 20:21:18

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

Re: Perms and Combs! and some induction..

Your welcome! This is why the generating function approach is very superior to the way combinatorics is taught. People learn casework and binomials first and then generating functions when they become graduate students.

This is backwards! Generating functions have been around since Abraham de Moivre, a buddy of Sir Isaac Newton. Everybody from about the 7th grade on, can multiply two polynomials but many people never see a binomial until they get to college algebra. Once you set up the gf you have changed a combinatoric problem into mere arithmetic. In other words a seventh grader can do it.

Whenever I work on a combinatorics problem and I start doing 12 choose 5, 6! and I can not find a gf, I begin to think that the problem has got me beat.

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 2011-05-29 20:42:03

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

Re: Perms and Combs! and some induction..

Yes I dont know why we havent been taught Generating Functions but for now this will do. Ok so I have a doubt about one of my answers, the question is:
In the game of Badugi, the goal is to get 4 cards that have different suits and different values. Such a hand is called a Badugi.
What is the probability that you are dealt a 4-card hand that contains 3 cards of different suits and different values, but is not a Badugi?

I divided this into 3 cases where, first case is whee the second card is either the same suit or the same value as the first
second case is where third card is the same suit/value as 2nd or 1st card.
third case " " fourth card is the same suit/value as one of the 3 cards.

Am I thinking this through correctly?

Offline

#23 2011-05-29 20:47:19

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

Re: Perms and Combs! and some induction..

4-card hand that contains 3 cards of different suits and different values, but is not a Badugi?

How many different values?

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 2011-05-29 20:49:39

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

Re: Perms and Combs! and some induction..

It does not specify so i assumed that 3 different values, while the 4th card can be the same value as one of the 3.

Offline

#25 2011-05-29 20:56:42

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

Re: Perms and Combs! and some induction..

Since a badugi has 4 different suits and 4 different cards. Any one of the 3 different cards and 3 different suits can never be a badugi. So we just have to find out how arrangeements of 4 card hands there are.

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