Combinations and Permutations

Newzed · 2004-08-05 12:38

I have ten variables.· I can call 3 of the 10 variables at a time, abc. def. aad, ggg, and so on.

What is the formula for determining how many 3-digit permutations are possible?

Thanks

Sid

Dave_h · 2004-08-05 13:39

Permutations use factorials ... n! = 1 x 2 x 3 ... (n - 1) x n .. in other words, 5! = 5 x 4 x 3 x 2 x 1.

If you don't have ! on your calculator there's a list of factorials is at http://www.newdream.net/~sage/old/numbers/fact.htm.

The formula you're looking for is n!/[noparse][[/noparse](n - m)! x m!] ... where n is the number of elements, and m is the times they're taken.

In your case:

10!/[noparse][[/noparse](10-3)! x 3!] = 120

I hope this makes sense.

Newzed · 2004-08-05 13:51

Dave_h said...
Permutations use factorials ... n! = 1 x 2 x 3 ... (n - 1) x n .. in other words, 5! = 5 x 4 x 3 x 2 x 1.

If you don't have ! on your calculator there's a list of factorials is at http://www.newdream.net/~sage/old/numbers/fact.htm.

The formula you're looking for is n!/[noparse][[/noparse](n - m)! x m!] ... where n is the number of elements, and m is the times they're taken.

In your case:

10!/[noparse][[/noparse](10-3)! x 3!] = 120

I hope this makes sense.

That doesn't sound right.· The Flordia Lottery has a 3-number game where you pick 3 numbers ranging from 0 to 9.· The stated odds against you picking the correct number is 1:1000.· The number of permutations must therefore be 1000, but I don't know how to calculate it.

Sid

Jon Williams · 2004-08-05 14:39

It makes sense as each digit position has ten possibilities and 10 x 10 x 10 = 1000.

I found this on the Internet: http://mathforum.org/dr.math/faq/faq.comb.perm.html

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Jon Williams
Applications Engineer, Parallax
Dallas Office

AlWilliamsAWC · 2004-08-05 14:47

This is a branch of math known as "discrete math". The difference lies in taking things more than once.

For example, if I say how many ways can I arrange 3 digits from 0 to 9, the obvious answer is 1000 (000 to 999).

But if I say how many ways can I select 3 cards from a deck of 52, that's a different problem because while I can use "9" 2 or 3 times (in the numbers example), I only have 1 King of Diamonds in the deck.

To make things simpler, say you have the cards from Ace to 10 of, I don't know, clubs, let's say. It would be wrong to say that I could make 1000 arrangements of these cards. Instead I can pick 10x9x8 combinations. The first time I pick, I have 10 cards to pick from, then I have 9 left, then I have 8 left. This is actually 10!/(10-3)! or 10!/7! which is:

10x9x8x7x6x5x4x3x2x1

7x6x5x4x3x2x1

which is, strangely enough, 10x9x8.

So mathematically, n!/(n-m)! is correct, but intuitively, if you think about the cards, it makes sense. I have 10 choices, then 9 choices, then 8 choices.

Been awhile since I took discrete math, but I think I got that right. I'm sure Tracy will set us all straight :-)

Now the hard part is when you have things like 3 red balls, 3 blue balls, and 3 white balls and you need to arrange them. In other words, you have a limited pool of similar·objects. It also matters if you consider sequences with the same members, but in different orders, the same or different. In other words, is 456 and 654 the same?

Makes your head hurt after awhile. Go to the library and look for a text on Discrete Math if you really want to get a handle on this. I have Discrete and Combinatorial Mathmatics by Grimaldi. All of this stuff is important for programmers!

http://math.about.com/od/discretemath/

Regards,

Al Williams
AWC
Kits!
http://www.awce.com/kits.htm

Post Edited (Al Williams/AWC) : 8/5/2004 3:00:11 PM GMT

Dave_h · 2004-08-05 14:51

After thinking about my answer, I had to come back on and correct it. I gave you the formula for unique combinations. I think what you want is total possible combinations where the order matters .. {a,b,c} is not the same as {c,b,a}

n!/(n-m)! is the formula I should have written. This gives permutations of n elements taken m times. Each element can be used once and only once in each individual permutation.

1st position any of the 10 elements can be used
2nd position any of the remaining 9 elements can be used
3rd position any of the remaining 8 elements can be used

10 x 9 x 8 = 10!/(10-3)! = 720

this makes 720 permutations.

In the case of the lottery, each permutation can have repeated elements (factorials aren't needed in this case) You simple take the power .. n^m ... where n is the number of elements taken m at a time:

1st position 10 elements
2nd position 10 elements
3rd position 10 elements

10 x 10 x 10 = 10^3 = 1000

Sorry for overcomplicating a simple problem.

Newzed · 2004-08-05 15:22

Dave_h said...
After thinking about my answer, I had to come back on and correct it. I gave you the formula for unique combinations. I think what you want is total possible combinations where the order matters .. {a,b,c} is not the same as {c,b,a}

n!/(n-m)! is the formula I should have written. This gives permutations of n elements taken m times. Each element can be used once and only once in each individual permutation.

1st position any of the 10 elements can be used
2nd position any of the remaining 9 elements can be used
3rd position any of the remaining 8 elements can be used

10 x 9 x 8 = 10!/(10-3)! = 720

this makes 720 permutations.

In the case of the lottery, each permutation can have repeated elements (factorials aren't needed in this case) You simple take the power .. n^m ... where n is the number of elements taken m at a time:

1st position 10 elements
2nd position 10 elements
3rd position 10 elements

10 x 10 x 10 = 10^3 = 1000

Sorry for overcomplicating a simple problem.

Now that makes sense!
Sid

Combinations and Permutations

Comments