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__
<br /><br />
+
{{User:Temperal/testtemplate|page 5}}
{| style='background:lime;border-width: 5px;border-color: limegreen;border-style: outset;opacity: 0.8;width:840px;height:300px;position:relative;top:10px;'
 
|+ <span style="background:aqua; border:1px solid black; opacity: 0.6;font-size:30px;position:relative;bottom:8px;border-width: 5px;border-color:blue;border-style: groove;position:absolute;top:50px;right:155px;width:820px;height:40px;padding:5px;">The Problem Solver's Resource</span>
 
|-
 
| style="background:lime; border:1px solid black;height:200px;padding:10px;" | {{User:Temperal/testtemplate|page 7}}
 
 
==<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.
<!-- will fill in later! -->
 
 
===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 in a straight line is <math>n!</math>. This is also known as a permutation, and can be notated <math>\,_{n}P_{r}</math>
+
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>n</math> objects from a set of <math>r</math> objects is <math>\frac{n!}{r!(n-r)!}</math>, which is notated as either <math>\,_{n}C_{r}</math> or <math>\binom{n}{r}</math>. (The latter notation is also known as taking the binomial coefficient.
+
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>
+
====Binomial Theorem====
*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 is <math>\frac{n!}{r_1!r_2!...r_s!}</math>
+
<math>(x+y)^n=\sum_{r=0}^{n}x^{n-r}y^r</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>.
 
  
[[User:Temperal/The Problem Solver's Resource6|Back to page 6]] | [[User:Temperal/The Problem Solver's Resource8|Continue to page 8]]
+
====Multinomial Coefficients====
|}<br /><br />
+
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 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 $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$ ordered distinct objects is $n!$. This is also known as a permutation, and can be notated $\,_{n}P_{r}$. We can see that this is true because there are $n$ objects which you can place in the first spot; when you've picked one there are $n-1$ objects to pick from for the second, and so on.

Combinations

The number of ways of choosing $r$ objects from a set of $n$ objects without replacement (i.e. you can't pick an object twice) is $\frac{n!}{r!(n-r)!}$, which is notated as either $\,_{n}C_{r}$ or $\binom{n}{r}$. If you allow replacement, then it's notated $\,_{n}P_{r}$ and is given by $\frac{n!}{(n-r)!}$. The reader should be able to deduce simple combinatorial arguments for these.

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 so that $\sum r_i=n$ 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 sequences $r_i$ so that $\sum_{i=1}^{s}r_i=n$.

Balls and Urns

There are ${n-1\choose k-1}$ ways to divide $k$ objects in $n$ groups such that no group is empty and the objects are indistinguishable. If groups can be empty, then it's $\binom{n+k-1}{k-1}$

Back to page 4 | Continue to page 6