Perms and Combs! and some induction..

careless25 · 2011-05-29 17:54:28

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 Ns come before all
the Es? (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

careless25 · 2011-05-29 17:58:33

for the first question my answer was:

bobbym · 2011-05-29 18:30:47

Hi;

How many arrangements of the word INDEPENDENCE are there?

many such arrangements have the property that all the Ns come before all
the Es?

The answer is 47520.

careless25 · 2011-05-29 18:41:15

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?

bobbym · 2011-05-29 18:57:01

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.

careless25 · 2011-05-29 19:12:16

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

bobbym · 2011-05-29 19:17:31

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

Do you follow that?

careless25 · 2011-05-29 19:30:47

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.

bobbym · 2011-05-29 19:31:54

Please reread post #7

careless25 · 2011-05-29 19:43:14

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.

bobbym · 2011-05-29 19:44:42

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

careless25 · 2011-05-29 19:50:42

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?

bobbym · 2011-05-29 19:53:41

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

careless25 · 2011-05-29 19:58:12

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)

bobbym · 2011-05-29 20:02:04

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?

careless25 · 2011-05-29 20:03:00

Yup got it thanks!!

bobbym · 2011-05-29 20:04:10

Are you sure?

careless25 · 2011-05-29 20:08:50

Yes but I will have to review tomorrow morn after a good nights sleep
btw reread post# 12

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

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

bobbym · 2011-05-29 20:10:28

Hi;

I am not following 8 choose 2 is not the correct answer it is 9 choose 2.

careless25 · 2011-05-29 20:13:37

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!

bobbym · 2011-05-29 20:21:18

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.

careless25 · 2011-05-29 20:42:03

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?

bobbym · 2011-05-29 20:47:19

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

How many different values?

careless25 · 2011-05-29 20:49:39

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.

bobbym · 2011-05-29 20:56:42

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.

Math Is Fun Forum

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

Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

#8 2011-05-29 19:30:47

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

#20 2011-05-29 20:13:37

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

#22 2011-05-29 20:42:03

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

#24 2011-05-29 20:49:39

Re: Perms and Combs! and some induction..

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

Re: Perms and Combs! and some induction..

Board footer