|
|
此文章由 SMART1968 原创或转贴，不代表本站立场和观点，版权归 oursteps.com.au 和作者 SMART1968 所有！转贴必须注明作者、出处和本声明，并保持内容完整
老朱我已前用这个方法教混了儿子 Easy Permutations and Combinations
I’ve always confused “permutation” and “combination” — which one’s which?
Here’s an easy way to remember: permutation sounds complicated, doesn’t it? And it is. With permutations, every little detail matters. Alice, Bob and Charlie is different from Charlie, Bob and Alice (insert your friends’ names here).
Combinations on the other hand, are pretty easy going. The details don’t matter. Alice, Bob and Charlie is the same as Charlie, Bob and Alice.
Permutations are for lists (order matters) and combinations are for groups (order doesn’t matter).
Permutations: The hairy details
Let’s start with permutations, or all possible ways of doing something. We’re using the fancy-pants term “permutation”, so we’re going to care about every last detail, including the order of items. Let’s say we have 8 people:
1: Alice
2: Bob
3: Charlie
4: David
5: Eve
6: Frank
7: George
8: Horatio
How many ways can we pick a Gold, Silver, and Bronze medal for “Best friend in the world”?
We’re going to use permutations since the order we hand out these medals matters. Here’s how it breaks down:
• Gold medal: 8 choices: A B C D E F G H (Clever how I made the names match up with letters, eh?). Let’s say A wins the Gold.
• Silver medal: 7 choices: B C D E F G H. Let’s say B wins the silver.
• Bronze medal: 6 choices: C D E F G H. Let’s say… C wins the bronze.
We picked certain people to win, but the details don’t matter: we had 8 choices at first, then 7, then 6. The total number of options was 8 * 7 * 6 = 336.
Let’s look at the details. We had to order 3 people out of 8. To do this, we started with all options (8) then took them away one at a time (7, then 6) until we ran out of medals.
We know the factorial is:
Unfortunately, that does too much! We only want 8 * 7 * 6. How can we “stop” the factorial at 5?
This is where permutations get cool: notice how we want to get rid of 5*4*3*2*1. What’s another name for this? 5 factorial!
So, if we do 8!/5! we get:
And why did we use the number 5? Because it was left over after we picked 3 medals from 8. So, a better way to write this would be:
where 8!/(8-3)! is just a fancy way of saying “Use the first 3 numbers of 8!”. If we have n items total and want to pick k in a certain order, we get:
just means “Use the first k numbers of n!”
And this is the fancy permutation formula: You have n items and want to find the number of ways k items can be ordered:
Combinations, Ho!
Combinations are easy going. Order doesn’t matter. You can mix it up and it looks the same. Let’s say I’m a cheapskate and can’t afford separate Gold, Silver and Bronze medals. In fact, I can only afford empty tin cans.
How many ways can I give 3 tin cans to 8 people?
Well, in this case, the order we pick people doesn’t matter. If I give a can to Alice, Bob and then Charlie, it’s the same as giving to Charlie, Alice and then Bob. Either way, they’re going to be equally disappointed.
This raises an interesting point — we’ve got some redundancies here. Alice Bob Charlie = Charlie Bob Alice. For a moment, let’s just figure out how many ways we can rearrange 3 people.
Well, we have 3 choices for the first person, 2 for the second, and only 1 for the last. So we have 3 * 2 * 1 ways to re-arrange 3 people.
Wait a minute… this is looking a bit like a permutation! You tricked me!
Indeed I did. If you have N people and you want to know how many arrangements there are for all of them, it’s just N factorial or N!
So, if we have 3 tin cans to give away, there are 3! or 6 variations for every choice we pick. If we want to figure out how many combinations we have, we just create all the permutations and divide by all the redundancies. In our case, we get 336 permutations (from above), and we divide by the 6 redundancies for each permutation and get 336/6 = 56.
The general formula is
which means “Find all the ways to pick k people from n, and divide by the k! variants”. Writing this out, we get our combination formula, or the number of ways to combine k items from a set of n:
A few examples
Here’s a few examples of combinations (order doesn’t matter) from permutations (order matters).
• Combination: Picking a team of 3 people from a group of 10. C(10,3) = 10!/(7! * 3!) = 10 * 9 * 8 / (3 * 2 * 1) = 120.
Permutation: Picking a President, VP and Waterboy from a group of 10. P(10,3) = 10!/7! = 10 * 9 * 8 = 720.
• Combination: Choosing 3 desserts from a menu of 10. C(10,3) = 120.
Permutation: Listing your 3 favorite desserts, in order, from a menu of 10. P(10,3) = 720.
Don’t memorize the formulas – it’s better to know why they work. Combinations sounds simpler than permutations, and they are. You have fewer combinations than permutations.
Navigate a Grid Using Combinations And Permutations
Puzzles can help develop your intuition -- figuring how to navigate a grid helped me understand combinations and permutations.
Suppose you're on a 4 × 6 grid, and want to go from the bottom left to the top right. How many different paths can you take? Avoid backtracking -- you can only move right or up.
Spend a few seconds thinking about how you'd figure it out.
Insight: Convert Pictures To Text
When considering the possible paths (tracing them out with your finger), you might whisper "Up, right, up, right...".
Why not write those thoughts down? Using "u" and "r" we can write out a path:
r r r r r r u u u u
That is, go all the way right (6 r's), then all the way up (4 r's).
The path in the diagram would be:
r r r r u u u u r r
Using the text interpretation, the question becomes "How many ways can we re-arrange the letters rrrrrruuuu?"
Ah, the ubiquitous combination/permutation problem -- never thought it'd be useful, eh?
Understanding Combinations And Permutations
There's several ways to see combination and permutation problems. Once the first explanation clicks, we can go back and see it a different way. When trying to build math intuition for a problem, I imagine several mental models circling a core idea. Starting with one insight, I work around to the others.
Approach 1: Start The Same
Instead of having 6 rights at 4 ups, imagine we start with 10 rights (r r r r r r r r r r).
Clearly this won't do: we need to change 4 of those rights into ups. How many ways can we pick 4 rights to change?
Well, we have 10 choices for the first 'right' to convert (see the combinations article). And 9 for the second, 8 for the third, and 7 choices for the final right-to-up conversion. There are 10 * 9 * 8 * 7 = 10!/6! = 5040 possibilities.
But, wait! We need to remove the redundancies: after all, converting moves #1 #2 #3 and #4 (in that order) is the same as converting #4 #3 #2 #1. We have 4! (4 * 3 * 2 * 1 = 24) ways to rearrange the ups we picked, so we finally get:
We're just picking the items to convert (10!/6!) and dividing out the redundancies (4!).
Approach 2: Just Use the Combination Formula
Halfway through that explanation, you might have realized we were recreating the combination formula:
That's the shortcut when you know order doesn't matter. However, sometimes I'm not sure whether I need a permutation or combination from the outset. While saying "Just use C(10,4)" may be accurate, it's not helpful as a teaching tool. Sometimes it helps to re-create the situation on your own.
Approach 3: Start Different
Here's another approach: instead of letting each r and u be interchangeable, label the 'right' moves r1 to r6, and the 'up' moves u1 to u4. How many ways can we re-arrange these 10 items?
This question is easy: 10! = 3,628,800 (wow, big number). We have 10 choices for the 1st move, 9 for the second, and so on, until we have 2 choices for the 9th and only 1 for the last. Cool.
Of course, we know that "r1 r2 u1 u2" is the same path as "r2 r1 u2 u1". We can shuffle the r's and u's in their own subgroups and the path will stay the same.
• How many ways can we shuffle all 10? 10! = 3,628,800
• How many ways can we shuffle 6 r's? 6! = 720
• How many ways can we shuffle 4 u's? 4! = 24
So, we start with the total number of possibilities (10! = 3,628,800) and divide out the cases where we shuffle the r's (6! = 720) and the u's (4! = 24):
Neat! It's cool seeing the same set of multiplications and divisions in different ways, just by regrouping them.
Definition:
Permutation:
An arrangement is called a Permutation. It is the rearrangement of objects or symbols into distinguishable sequences. When we set things in order, we say we have made an arrangement. When we change the order, we say we have changed the arrangement. So each of the arrangement that can be made by taking some or all of a number of things is known as Permutation.
Combination:
A Combination is a selection of some or all of a number of different objects. It is an un-ordered collection of unique sizes. In a permutation the order of occurence of the objects or the arrangement is important but in combination the order of occurence of the objects is not important.
Formula:
Permutation = nPr = n! / (n-r)!
Combination = nCr = nPr / r!
where,
n, r are non negative integers and r<=n.
r is the size of each permutation.
n is the size of the set from which elements are permuted.
! is the factorial operator.
Example:Find the number of permutations and combinations: n=6; r=4.
Step 1: Find the factorial of 6.
6! = 6×5×4×3×2×1 = 720
Step 2: Find the factorial of 6-4.
(6-4)! = 2! = 2
Step 3: Divide 720 by 2.
Permutation = 720/2 = 360
Step 4: Find the factorial of 4.
4! = 4×3×2×1 = 24
Step 5 ivide 360 by 24.
Combination = 360/24 = 15
The above example will help you to find the Permutation and Combination manually.
1. Determine whether the following situations would require calculating a permutation or a combination:
a.) Selecting three students to attend a conference in Washington, D.C.
permutation combination
b.) Selecting a lead and an understudy for a school play.
permutation combination
c.) Assigning students to their seats on the first day of school.
permutation combination
2. A teacher is making a multiple choice quiz. She wants to give each student the same questions, but have each student's questions appear in a different order. If there are twenty-seven students in the class, what is the least number of questions the quiz must contain?
3. A coach must choose five starters from a team of 12 players. How many different ways can the coach choose the starters?
4. The local Family Restaurant has a daily breakfast special in which the customer may choose one item from each of the following groups:
Breakfast Sandwich Accompaniments Juice
egg and ham
egg and bacon
egg and cheese breakfast potatoes
apple slices
fresh fruit cup
pastry orange
cranberry
tomato
apple
grape
a.) How many different breakfast specials are possible?
b.) How many different breakfast specials without meat are possible?
5. In how many ways can 3 different vases be arranged on a tray?
6. There are fourteen juniors and twenty-three seniors in the Service Club. The club is to send four representatives to the State Conference.
a.) How many different ways are there to select a group of four students to attend the conference?
b.) If the members of the club decide to send two juniors and two seniors, how many different groupings are possible?
排列（有顺序）：mPn＝m*（m-1）*.....*(m-n+1)
组合（无顺序）:mCn＝m*（m-1）*.....*(m-n+1)/(1*2*...*n)
排列：从n个不同的元素中取m(m≤n)个元素，按照一定的顺序排成一排，叫做从n个不同的元素中取m个元素的排列。
排列数：从n个不同的元素中取m(m≤n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，记为Pnm
排列公式：p(n,m)=n*(n-1)*.....(n-m+1)
组合：从n个不同的元素中，任取m(m≤n)个元素并成一组，叫做从n个不同的元素中取m个元素的组合。
组合数：从n个不同的元素中取m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数，记为Cnm
组合公式：c(n,m)=p(n,m)/m!=n!/(m!*(n-m)!)
2. If there were two questions on the quiz, we could prepare two quizzes with the questions in different order -- 2•1 = 2.
If there were three questions, we could get 3•2•1 = 6 different orders.
If there were four questions, we could get 4•3•2•1 = 24 different orders -- not quite enough for the class of 27 students.
If there were five questions, we could get 5•4•3•2•1 = 120 different orders. The teacher will need at least 5 questions on the quiz.
3.
Choose 5 starters from a team of 12 players. Order is not important.
4.
a.) Basic counting principle:
Sandwiches x Accompaniments x Juice
3 • 4 • 5 = 60 breakfast choices
b.) Meatless means that under Sandwiches there will be only one choice.
Sandwiches x Accompaniments x Juice
1 • 4 • 5 = 20 meatless breakfast choices
5. Basic counting principle:
3! = 3•2•1 = 6 ways
6. 14 juniors, 23 seniors
37 students total
a.) Choose 4 students from the total number of students. Order is not important.
b.) Choose 2 juniors and 2 seniors. |
|
有关孩子学中文的感想 (2009-3-6) floodp 
发表于 2010-8-16 23:47
charmaine难怪是个博士家长，敬仰啊。
