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

You are not logged in.

- Topics: Active | Unanswered

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

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

but then again i get stuck in the induction step.

Any help ASAP is appreciated!!

Thanks a lot

Offline

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

for the first question my answer was:

Offline

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

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.

**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

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

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

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

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

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

Umm is there another way because I havent studied Diophantine equations nor generating functions.

Sorry for the trouble

but thanks!!!

Offline

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

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?

**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

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

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

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

Please reread post #7

**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

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

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

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

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

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

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

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

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

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

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

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

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

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

Yup got it thanks!!

Offline

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

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

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

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

Offline

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

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

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

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

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

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

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

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

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

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

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

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

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

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