Scribd
Upload
107 views

Basic Combinatorics 1 Basic Principles of Counting

1. The document outlines 14 main points about basic combinatorics principles including rules for counting sets, permutations, combinations, Fibonacci numbers, pigeonhole principle, and Ramsey theory. 2. Key concepts covered are addition and subtraction rules, multiplication rules, factorials, binomial coefficients, permutations with and without repetition, inclusion-exclusion principle, generating functions. 3. Examples of specific Ramsey numbers are given such as R(3,3)=6 and R(4,4)=18.

Uploaded by

Chung Lai MAK
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
107 views

Basic Combinatorics 1 Basic Principles of Counting

1. The document outlines 14 main points about basic combinatorics principles including rules for counting sets, permutations, combinations, Fibonacci numbers, pigeonhole principle, and Ramsey theory. 2. Key concepts covered are addition and subtraction rules, multiplication rules, factorials, binomial coefficients, permutations with and without repetition, inclusion-exclusion principle, generating functions. 3. Examples of specific Ramsey numbers are given such as R(3,3)=6 and R(4,4)=18.

Uploaded by

Chung Lai MAK
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

1

Basic Combinatorics

1 Basic Principles of Counting


Main Point 1.1 (Addition rule). Suppose A and B are disjoint sets, that is, A ∩ B = ∅.
Then
|A ∪ B| = |A| + |B|.
Main Point 1.2 (Subtraction rule). Suppose B ⊂ A. Then

|A \ B| = |A| − |B|.

Main Point 1.3 (Multiplication rule). Let A and B be sets. Then

|A × B| = |A||B|.

Main Point 1.4 (Division rule). Suppose n objects are classified into k groups so that
n
each group has the same number of objects. Then there are objects in each group.
k
Main Point 1.5 (Factorial). The number of ways to arrange n distinguishable objects in
a row is
n! = n × (n − 1) × (n − 2) × · · · × 3 × 2 × 1
Main Point 1.6 (Combination). The number of ways to choose k objects without order
and repetition from n distinguishable objects is
n!
Ckn =
k!(n − k)!

The number Ckn is known as binomial coefficient which is equal to the coefficient of xk in
the expansion (1 + x)n . It is also denoted as nk .
Main Point 1.7 (Permutation). The number of ways to choose k objects with order and
without repetition from n distinguishable objects is
n!
Pkn =
(n − k)!

Main Point 1.8 (Permutation of indistinguishable objects). Suppose there are k types
of objects and the number of objects of the i-th type is ni for i = 1, 2, · · · , k. Suppose two
objects are indistinguishable if they are of the same type. Then the number of ways to
arrange the n1 + n2 + · · · + nk objects in a row is
(n1 + n2 + · · · + nk )!
n1 !n2 ! · · · nk !
Main Point 1.9 (Combination with repetition). The number of ways to put n indistin-
guishable balls into k distinguishable bags is
n+k−1
Ck−1 (= Cnn+k−1 )
2

Main Point 1.10 (Inclusion exclusion principle). Suppose there are n sets A1 , A2 , · · · , An .
Then

|A1 ∪ A2 ∪ · · · ∪ An |
Xn X X
= |Ai | − |Ai ∩ Aj | + |Ai ∩ Aj ∩ Ak | −
1≤i≤n 1≤i<j≤n 1≤i<j<k≤n
n+1
· · · + (−1) |A1 ∩ A2 ∩ · · · ∩ An |

where | · | denotes the number of elements in the set.

Main Point 1.11 (Fibonacci numbers). The number of words formed by letters A and
B with length n without consecutive A is Fn+2 where
√ !k √ !k
 
1 1+ 5 1− 5 
Fk = √  −
5 2 2

is the k-th Fibonacci number, i.e., Fn , n ≥ 0, satisfies



F0 = 0,

F1 = 1,

Fn = Fn−1 + Fn−2 , for n ≥ 2

The first 8 Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13.

Main Point 1.12 (Pigeonhole principle). If n + 1 items are put into n containers, then
at least one container must contain more than one item.

Main Point 1.13 (Ramsey numbers). Let n1 , n2 , · · · , nk be positive integers. Then there
exists a positive integer R(n1 , n2 , · · · , nk ) such that if we color the edges of the complete
graph with R(n1 , n2 , · · · , nk ) vertices with colors C1 , C2 , · · · , Ck , then there exists i =
1, 2, · · · , k and a subgraph with ni vertices such that all edges of the subgraph are colored
Ci . We have the following facts.

1. R(a, b) ≤ R(a − 1, b) + R(a, b − 1)

2. R(3, 3) = 6

3. R(4, 4) = 18

4. R(3, 3, 3) = 17

Note: The values of R(5, 5) and R(6, 6) are unknown.

Main Point 1.14 (Generating function). The generating function associated with the
sequence an is
∞
X
an x n = a0 + a1 x + a2 x 2 + a3 x 3 + · · · .
n=0

You might also like