Discrete Mathematics
See Sources, esp. Benson, Lindstrm, and Perkal (ch. 8)
Notation, Special Symbols

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!] The Binomial Theorem

(a + b)^n = (r=0, n) [C(n, r) * a^(n-r) * b^r] The Multinomial Theorem

(a1 + a2 + ... + ak)^n = (r1+r2+...+rk = n) [C(n, r1, r2, ..., rk) * a1^r1 * a2^r2 * ... * ak^rk ] 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 ú


Maths Index

All Subjects