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

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 $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

@@ Line 1: / Line 1: @@
+__NOTOC__
 {{User:Temperal/testtemplate|page 5}}
 ==<span style="font-size:20px; color: blue;">Combinatorics</span>==
 This section cover combinatorics, and some binomial/multinomial facts.
-<!-- will fill in later! -->
 ===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>.
@@ Line 24: / Line 24: @@
 ===Balls and Urns===
-There are <math>{n+k-1\choose n-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.
+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]]

Page

Toolbox

Search