Math Is Fun Forum

critterlady

Member

Registered: 2011-10-28

Posts: 1

Combinations vs Permutations

Can you PLEASE help me?  I`ve read your page on combinations & permutations & still can`t see which my problem is.

I need to know how many possible paths there are from origin (0,0) to (4,3) on a graph ONLY moving up and right (not left or down).

To me, the set is (r,r,r,r,u,u,u).  But is it combination (answer 35), permutation (answer 5040) or have I really confused myself & it`s something else all together???

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations vs Permutations

Hi;

The answer is 35, just as you calculated.

To me, the set is (r,r,r,r,u,u,u)

That is exactly what it is. The r's are all the same and so are the u's. The number of ways of arranging those 4 r's and 3 u's is

Welcome to the forum!

---

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.

TMorgan

Member

Registered: 2011-04-13

Posts: 25

Re: Combinations vs Permutations

Since the only difference in the paths is the order of the steps isn't that by definition a permutation?

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations vs Permutations

Yes, when talking about the paths that is a permutation. I have corrected the above post for that mistake.

---

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.

Bob

Administrator

Registered: 2010-06-20

Posts: 10,621

Re: Combinations vs Permutations

hi

Here's another way to think about this problem which shows the answer is 35.

Show the points on a grid. 

Write, for each point, how many ways there are to get there.  (diagram below)

eg.  To get to (1,0) just one way. 

eg. To get to (1,1) there are two ways (0,0) - (1,0) - (1,1)     and      (0,0) - (0,1) - (1,1)

Each point number is the sum of the ways from previous points.

eg to get to (3,2) ( see red arrows)  you must have come from either (3,1) or (2,2) so add 6 + 4 together to get 10 ways.

Bob

Last edited by Bob (2011-10-31 14:44:14)

---

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

Bob

Administrator

Registered: 2010-06-20

Posts: 10,621

Re: Combinations vs Permutations

hi critterlady,

I`ve read your page on combinations & permutations & still can`t see which my problem is.

I've been having a further think about this.  I think it is neither a permutaion nor a combination!

Given that we've all been getting 9C5 = 35, that might seem a bit outrageous but here's my reasoning:

You did something rather clever at the start. 
You abandoned the actual problem set and converted it, quite correctly,  into a different problem with the same answer.

Here's the full proof for that.  Represent each step to the right by a letter 'r' and each step up by a 'u'.

Then one possible way of getting from (0,0) to (4,3) is rurururur.  Furthermore, every possible way can be written as such a 9 letter 'word'.  And any 9 letter word made up only from five 'r' s and four 'u' s, can be used to move from (0,0) to (4,3).  So there is a one to one correspondence between the number of possible words and the number of possible ways of moving.

Now there is a standard way to solve such word problems.

First you pretend that all the letters are different.

Then ask, "How many nine letter words can I make from these letters.?"

Now that is a permutation problem.

So that gives us 9!

But the letters aren't all distinct.  The five 'r' s are all alike.  So ask another question.  "How many ways can I re-arrange the 'r' s within the word?"  Answer 5!.  And "How many ways can the 'u' s be re-arranged?"  Answer 4!.  So the number of ways the 9 letter 'word' can be made is

Now that looks like a combination answer.  But it isn't.  It's just that the non-r letters are 'u' s so the two factorials on the denominator look like they are related.

Consider this problem and you'll see what I'm getting at.

In 3D, how many ways are there of getting from (0,0,0) to (4,3,2) by going along the co-ordinate axes.  As 'u' could be confusing I'll use 'x' for a step in the x direction, and 'y' and 'z' similarly.

So a possible route is xxxxxyyyyzzz.  Another is xyzxyzxyzxyx.

The total number of ways is

No combinations there.

Are you convinced? 

Bob

Last edited by Bob (2011-10-31 20:17:53)

---

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

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations vs Permutations

Hi all;

It is difficult to see, but it is a permutation with repetitions. The standard textbook one is Mississippi.

It is explained here:

http://www.mathwarehouse.com/probabilit … -items.php

---

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.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Combinations vs Permutations

Hi bobbym,

A nice g.f there!
Looks familiar, but do not remember where.

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations vs Permutations

Hi gAr;

Anywhere there is a block walk that one is the answer. It is not new I am sure we talked about it already.

---

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.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Combinations vs Permutations

Yes, we have talked about it.

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations vs Permutations

I think you are correct. I think if I remember, it was you that pointed it out first to me.

---

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.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Combinations vs Permutations

I searched for that, it's not the same one...

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations vs Permutations

I think I found it in a PDF that had a whole bunch of multivariable generating functions. Can not remember where it is though.

I got it:

www.math.upenn.edu/~pemantle/papers/twenty.pdf

---

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.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Combinations vs Permutations

I too remember about the pdfs, can't find it now!
Meanwhile, I found a nice geogebra demonstration: http://analemma.wikispaces.com/Missing+square+puzzle

Okay, thanks for finding it!

Last edited by gAr (2011-11-04 00:11:18)

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations vs Permutations

Hi gAr;

Thanks for finding that. I have been looking over

http://www.youtube.com/user/GeoGebraChannel

---

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.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Combinations vs Permutations

Hi bobbym,

I occasionally check that too.

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations vs Permutations

I have been doing some work with circumscribing shapes and getting high accuracy. Have not posted it yet.

---

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.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Combinations vs Permutations

That's nice!
What are you doing with those?

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations vs Permutations

Trying to derive formulas for things like square inscribed in a circle inscribed in a equilateral triangle using just geogebra.

---

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.

gAr

Member

Registered: 2011-01-09

Posts: 3,482

Re: Combinations vs Permutations

Sounds interesting!

---

"Believe nothing, no matter where you read it, or who said it, no matter if I have said it, unless it agrees with your own reason and your own common sense"  - Buddha?

"Data! Data! Data!" he cried impatiently. "I can't make bricks without clay."

bobbym

bumpkin

From: Bumpkinland

Registered: 2009-04-12

Posts: 109,606

Re: Combinations vs Permutations

I haven't worked all the kinks out to getting geogebra to do it all.

---

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.