Difference between revisions of "User:Temperal/The Problem Solver's Resource5"
(notoc) |
(→Balls and Urns: mieh) |
||
Line 24: | Line 24: | ||
===Balls and Urns=== | ===Balls and Urns=== | ||
− | There are <math>{n | + | 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]] | [[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 17: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