Difference between revisions of "User:Temperal/The Problem Solver's Resource5"
m (nav) |
(→Balls and Urns: mieh) |
||
(5 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> | |
− | + | ||
+ | ====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]] | [[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