Difference between revisions of "User:Temperal/The Problem Solver's Resource5"

(rmv)
m (Balls and Urn)
Line 18: Line 18:
 
*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 sums <math>\sum_{i=1}^{s}r_i</math> so that <math>\sum_{i=1}^{s}r_i=n</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 sums <math>\sum_{i=1}^{s}r_i</math> so that <math>\sum_{i=1}^{s}r_i=n</math>.
  
===Ball and Urn===
+
===Balls and Urn===
The ball and urn argument states that, there are this many ways to place <math>k</math> balls in <math>n</math> urns:
+
The balls and urn argument states that, there are this many ways to place <math>k</math> balls in <math>n</math> urns:
  
 
<math>{n+k-1\choose n-1}</math>
 
<math>{n+k-1\choose n-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]]

Revision as of 21:40, 10 January 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 $n$ is $n(n-1)(n-2)...(1)$ or also as $\prod_{a=0}^{n-1}(n-a)$,and is denoted by $n!$.

Also, $0!=1$.

The number of ways of arranging $n$ distinct objects in a straight line is $n!$. This is also known as a permutation, and can be notated $\,_{n}P_{r}$

Combinations

The number of ways of choosing $n$ objects from a set of $r$ objects is $\frac{n!}{r!(n-r)!}$, which is notated as either $\,_{n}C_{r}$ or $\binom{n}{r}$. (The latter notation is also known as taking the binomial coefficient.

Binomials and Multinomials

  • Binomial Theorem: $(x+y)^n=\sum_{r=0}^{n}x^{n-r}y^r$
  • Multinomial Coefficients: The number of ways of ordering $n$ objects when $r_1$ of them are of one type, $r_2$ of them are of a second type, ... and $r_s$ of them of another type is $\frac{n!}{r_1!r_2!...r_s!}$
  • Multinomial Theorem: $(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$. The summation is taken over all sums $\sum_{i=1}^{s}r_i$ so that $\sum_{i=1}^{s}r_i=n$.

Balls and Urn

The balls and urn argument states that, there are this many ways to place $k$ balls in $n$ urns:

${n+k-1\choose n-1}$

Back to page 4 | Continue to page 6