2.3.3 Counting
This part is taken almost directly from Benson,
p.64-67
An algebraic expression with two terms is called a binomial. Multiplying
two binomials gives us:
(A + B)(a + b) = Aa + Ab + Ba + Bb
Multiplying three binomials gives us:
(A + B)(a + b)(a + b)
= Aaa
+ Aba
+ Baa
+ Bba
+ Aab
+ Abb
+ Bab
+ Bbb
and so on...
But what if the binomials are equal?
(x + 1)(x + 1)(x + 1) = (x * x * x) + (x * 1 * x) + (1 * x * x) + (1 *
1 * x) + (x * x * 1) + (x * 1 * 1) + (1 * x * 1) + (1 * 1 * 1)
Here, some of the terms on the right side are equal. We se that the expansion
is the sum of eight products. Call one of these products abc:
a must be either x or 1
b must be either x or 1
c must be either x or 1
"The number of terms equal to x^2
is the number of ways of choosing two x's and one 1. This is the number
3 choose 2," (-Benson) which
here will be denoted C(3, 2).
C(n, r) = n! / [(n-r)!r!]
2.3.3.1 The Binomial Theorem
Notation
(a + b)^n = å(r=0,
n) [C(n, r) * a^(n-r) * b^r]
2.3.3.2 The Multinomial Theorem
(a1 + a2 + ... + ak)^n
= å(r1+r2+...+rk
= n) [C(n, r1, r2, ..., rk)
* a1^r1 * a2^r2
* ... * ak^rk ]
2.3.3.3 Combinatorics
This section draws heavily upon Perkal
(ch. 8)
The Multiplication Rule
If task 1 can be performed in m distinct ways, and task 2 can be performed
in n distinct ways, the number of ways to perform task 1 and then task
2 (independently of task 1) in that order is m * n.
If A and B are sets then their Cartesian product is
A x B := {(a, b) | a
Î A and b
Î B}.
Corollary: If A and B are finite sets, then |A x B| = |A| x |B|
The Addition Rule
If task 1 and task 2 are mutually exclusive, and task 1 can be performed
in m ways and task 2 in n ways, then there are m + n ways to perform either
task 1 or 2.
Two sets A and B are called disjoint if they have no elements in common,
that is A Ç
B = Æ
A Ç
B (A AND B = Æ)
Corollary: If A and B are disjoint, then |A Ç
B| = |A| + |B|
The Inclusion-Exclusion Principle
If A and B are finite sets, then
|A È
B| = |A| + |B| - |A Ç
B|
That is; the size of A OR B equals the size of A plus the size of B,
take away the size of A AND B. This makes sense, because when we have
added together the number of elements of A with the number of elements
in B, we need to take out again those elements we have counted twice;
i.e. the elements which are in both sets.
Permutations and combinations
A permutation of an ordered set S = {a,b,...,x} is a rearrangement of
the elements of S.
If |S| = n, then there are n! permutations of S.
Note that, by convention, 0! = 1.
For example, if we have the set S = {a,b,c}, then n = 3 and there are
3! = 3 * 2 * 1 = 6 permutations:
{a,b,c}, {a,c,b}, {b,a,c}, {b,c,a}, {c,a,b}, {c,b,a}
Maths
Index
All Subjects
P
ab
c d
e f
g h
l m
p q
³ £Ãº¹ÙÚ
Î
Ï Ç
È É
Ê Ë
Ì Í
® ±
Û Ü
Ý Þ
ß å
ò ¥Æ
|