Difference between revisions of "User:Temperal/The Problem Solver's Resource5"
(switch) |
(→Balls and Urns: mieh) |
||
(7 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
__NOTOC__ | __NOTOC__ | ||
− | + | {{User:Temperal/testtemplate|page 5}} | |
− | |||
− | |||
− | |||
− | |||
==<span style="font-size:20px; color: blue;">Combinatorics</span>== | ==<span style="font-size:20px; color: blue;">Combinatorics</span>== | ||
This section cover combinatorics, and some binomial/multinomial facts. | This section cover combinatorics, and some binomial/multinomial facts. | ||
− | |||
===Permutations=== | ===Permutations=== | ||
The factorial of a number <math>n</math> is <math>n(n-1)(n-2)...(1)</math> or also as <math>\prod_{a=0}^{n-1}(n-a)</math>,and is denoted by <math>n!</math>. | The factorial of a number <math>n</math> is <math>n(n-1)(n-2)...(1)</math> or also as <math>\prod_{a=0}^{n-1}(n-a)</math>,and is denoted by <math>n!</math>. | ||
Line 13: | Line 8: | ||
Also, <math>0!=1</math>. | Also, <math>0!=1</math>. | ||
− | The number of ways of arranging <math>n</math> distinct objects | + | The number of ways of arranging <math>n</math> ordered distinct objects is <math>n!</math>. This is also known as a permutation, and can be notated <math>\,_{n}P_{r}</math>. We can see that this is true because there are <math>n</math> objects which you can place in the first spot; when you've picked one there are <math>n-1</math> objects to pick from for the second, and so on. |
===Combinations=== | ===Combinations=== | ||
− | The number of ways of choosing <math> | + | The number of ways of choosing <math>r</math> objects from a set of <math>n</math> objects without replacement (i.e. you can't pick an object twice) is <math>\frac{n!}{r!(n-r)!}</math>, which is notated as either <math>\,_{n}C_{r}</math> or <math>\binom{n}{r}</math>. If you allow replacement, then it's notated <math>\,_{n}P_{r}</math> and is given by <math>\frac{n!}{(n-r)!}</math>. The reader should be able to deduce simple combinatorial arguments for these. |
===Binomials and Multinomials=== | ===Binomials and Multinomials=== | ||
− | + | ====Binomial Theorem==== | |
− | + | <math>(x+y)^n=\sum_{r=0}^{n}x^{n-r}y^r</math> | |
− | |||
− | [[User:Temperal/The Problem Solver's | + | ====Multinomial Coefficients==== |
− | + | The number of ways of ordering <math>n</math> objects when <math>r_1</math> of them are of one type, <math>r_2</math> of them are of a second type, ... and <math>r_s</math> of them of another type so that <math>\sum r_i=n</math> is <math>\frac{n!}{r_1!r_2!...r_s!}</math> | |
+ | |||
+ | ====Multinomial Theorem==== | ||
+ | <math>(x_1+x_2+x_3...+x_s)^n=\sum \frac{n!}{r_1!r_2!...r_s!} x_1+x_2+x_3...+x_s</math>. The summation is taken over all sequences <math>r_i</math> so that <math>\sum_{i=1}^{s}r_i=n</math>. | ||
+ | |||
+ | ===Balls and Urns=== | ||
+ | There are <math>{n-1\choose k-1}</math> ways to divide <math>k</math> objects in <math>n</math> groups such that no group is empty and the objects are indistinguishable. If groups can be empty, then it's <math>\binom{n+k-1}{k-1}</math> | ||
+ | |||
+ | [[User:Temperal/The Problem Solver's Resource4|Back to page 4]] | [[User:Temperal/The Problem Solver's Resource6|Continue to page 6]] |
Latest revision as of 16:14, 1 February 2009
Introduction | Other Tips and Tricks | Methods of Proof | You are currently viewing page 5. |
Combinatorics
This section cover combinatorics, and some binomial/multinomial facts.
Permutations
The factorial of a number is or also as ,and is denoted by .
Also, .
The number of ways of arranging ordered distinct objects is . This is also known as a permutation, and can be notated . We can see that this is true because there are objects which you can place in the first spot; when you've picked one there are objects to pick from for the second, and so on.
Combinations
The number of ways of choosing objects from a set of objects without replacement (i.e. you can't pick an object twice) is , which is notated as either or . If you allow replacement, then it's notated and is given by . The reader should be able to deduce simple combinatorial arguments for these.
Binomials and Multinomials
Binomial Theorem
Multinomial Coefficients
The number of ways of ordering objects when of them are of one type, of them are of a second type, ... and of them of another type so that is
Multinomial Theorem
. The summation is taken over all sequences so that .
Balls and Urns
There are ways to divide objects in groups such that no group is empty and the objects are indistinguishable. If groups can be empty, then it's