Bài giảng về bài toán đếm bách khoa hà nội

Contents of Part 1 Chapter 0: Sets, Relations Chapter 1: Counting problem Discrete Mathematics Chapter 2: Existence problem Chapter 3: Enumeration problem Course preparation group: Nguyễn Khánh Phương Đỗ Phan Thuận
Chapter 4: Combinatorial optimization problem Phạm Quang Dũng Huỳnh Thanh Bình Trần Vĩnh Đức Bùi Quốc Trung Đinh Viết Sang Ban Hà Bằng 1 3 Contents PART 1 1. Basic counting principles COMBINATORIAL THEORY 2. E l
e mentary combinatorial configuration
3. The inclusion-exclusion principle (Lý thuyết tổ hợp) 4. Recurrence relation 5. Generating function PART 2 GRAPH THEORY (Lý thuyết đồ thị) 2 4 1 1. Basic counting principles 1.1. The sum rule 1.1. The sum rule
Generalized sum rule: If we have tasks T1, T2, …, Tk that can be
done in m1, m2, …, mk ways, respectively, and any two of these 1.2. The product rule
tasks can not be done at the same time, then there are m1 + m2 +
… + mk ways to do one of these tasks.
The sum rule can also be phrased in terms of set theory: The
size of the union on k finite pair wise disjoint sets is the sum of their sizes:
• Let A1, A2, …, Ak be disjoint sets. Then the number of ways
to choose any element from one of these sets is |A   1 A2
…  Ak| = |A1| + |A2| + … + |Ak|. 5 7 1.1. The sum rule 1. Basic counting principles Let us consider two tasks: Task 1 1.1. The sum rule
m1 is the number of ways to do task 1
m2 is the number of ways to do task 2
Tasks are independent of each other, i.e., 1.2. The product rule
Performing task 1 does not accomplish task 2 and vice versa. Task 2
Sum rule: the number of ways that “either task 1 or task 2 can be done, but not both”, is m1 + m2.
Generalizes to multiple tasks ... Things 1 2 3 … k ways m1 m2 m3 … mk
select one of them: m1 +m2 +m3 +...+ mk ways 8 2 The product rule 1.2. The product rule • Consider two tasks:
• If each element ai of k- tuple (a1, a2, ..., ak) has mi number of
– m1 is the number of ways to do task 1
ways to select (i = 1, 2, ..., k), then the number of tuples could be – m
generated is the product of these m
2 is the number of ways to do task 2 1m2 ... mk
– Tasks are independent of each other, i.e.,
• Performing task 1does not accomplish task 2 and vice versa.
Product rule: the number of ways that “both tasks 1 and 2 can be done” in m1m2. task 1 task 2
• Generalize to multiple tasks ... 9 11 1.2. The product rule Contents
Generalized product rule: If we have a procedure consisting of 1. Basic counting principles
sequential tasks T1, T2, …, Tk that can be done in m1, m2, …, mk ways, respectively, then there are m
2. Elementary combinatorial configuration
1 * m2 * … * mk ways to carry out the procedure.
3. The inclusion-exclusion principle
The product rule can also be phrased in terms of set theory: Let A 4. Recurrence relation 1, A2,
…, Ak be finite sets. Then the number of ways to choose one element 5. Generating function
from each set in the order of A1, A2, …, Ak is
|A1 x A2 x … x Ak| = |A1| * |A2| * … * |Ak|. 10 12 3
2. Elementary combinatorial configuration 2.1.1. Permutation 2.1. Permutation
A permutation of a set A of objects is an ordered arrangement of
the elements of A where each element appears only once 2.2. Combination
Example: If A = {a, b, c}, then the permutations of A are 1. abc 2. acb 3. bac 4. bca 5. cab 6. cba
The number of permutations of any set with n elements is
P(n) = n! = n(n − 1) · · · 2 · 1
(Note that by definition 0! = 1) 13 15
2. Elementary combinatorial configuration
2. Elementary combinatorial configuration 2.1. Permutation 2.1. Permutation 2.1.1. Permutation 2.1.1. Permutation 2.1.2. Circulation permutation 2.1.2. Circulation permutation
2.1.3. Permutation of multisets
2.1.3. Permutation of multisets 2.2. Combination 2.2. Combination 14 16 4 2.1.2. Circulation permutation
2.1.4. Permutations of multisets Circulation permutation n!/n=(n-1)!
A multiset M is a collection whose members need not be distinct.
Example 3: 6 people A, B, C, D, E, F are seated around a round table, how Example: The collection
many different circular arrangements are possible, if arrangements are
considered the same when one can be obtained from the other by rotations?
M = (a, a, a, b, b, c, d, d, d, 1, 2, 2, 2, 3, 3, 3, 3) ABCDEF, A
is a multiset; and sometimes it is convenient to write BCDEFA, B F
M = (3a, 2b, c, 3d, 1, 32, 43). CDEFAB,
A multiset M over a set S can be viewed as a function v : S → ℕ from S DEFABC, E C
to the set ℕ of nonnegative integers; each element x S is repeated t(x) EFABCD,
times in M; we write M = (S; t). FABCDE D
are the same arrangements circularly
 There are 6! ways to seat 6 people around the table
For each seating, there are 6 “rotations” of the seating
Thus, the final answer is 6!/6 = 5! = 120 17 19
2. Elementary combinatorial configuration
2.1.4. Permutation of multisets 2.1. Permutation
Let M be a multiset and |M| = n. 2.1.1. Permutation
Proposition 1. Let M be a multiset of r different types where each type has 2.1.2. Circulation permutation
infinitely elements. Then the number of k-permutations of M equals 𝑟
2.1.3. Permutation of multisets 2.2. Combination
Example 1. What is the number of binary numerals with at most 4 digits?
Solution: The question is to find the number of 4-permutations of the multiset
(0, 1). Thus the answer is 24 = 16. 18 20 5
2.1.4. Permutation of multisets 2.2. Combination
Proposition 2. Let M be a multiset of r different types with repetition numbers 2.1.1. Definitions
n1, n2,…, nr respectively. Let n = n1+ n2 +… + nr . Then the number of permutations of M equals 2.2.2. Binomial coefficients 𝒏! 𝒏
2.2.3. Combinations of Multisets 𝟏! 𝒏𝟐! … 𝒏𝒓! Proof.
2.2.4. Multinomial coefficients nr 21 23
2. Elementary combinatorial configuration 2.2.1. Definitions 2.1. Permutation
A k-combination of a set of n elements is a subset of size k of n elements. 2.2. Combination
(Note: A permutation is a sequence while a combination is a set) Example:
The 2-permutation (sequence) of SOHN is:
SO, SH, SN, OH, ON, OS, HN, HS, HO, NS, NO, NH
The 2-combination (set) of SOHN is:
{S,O},{S,H},{S,N},{O,H},{O,N},{H,N} 22 24 6 2.2.1. Definitions Binomial Coefficients
The number of all k-combinations of a set of n elements denoted
(a + b)4 = (a + b)(a + b)(a + b)(a + b)  n , k C or C( , n k) 4   4   4   4   4     =   a4  +   a3  b +   a2  b2
+   ab3 +   b4  n k 0 1 2 3 4             and read “n choose k”.
Binomial Theorem: Let x and y be variables, and let n be any nonnegative integer.  n n! Then    Proof ??? n    k  k !(n  k)! n
(x  y )n    x n j y j j 0  j  
This number is also called a binomial coefficient because such numbers
occur as coefficients in the expansions of powers of binomial expressions such as (a+b)n 25 27 2.2. Combination 2.2. Combination 2.1.1. Definitions 2.1.1. Definitions 2.2.2. Binomial coefficients 2.2.2. Binomial coefficients
2.2.3. Combinations of Multisets
2.2.3. Combinations of Multisets
2.2.4. Multinomial coefficients
2.2.4. Multinomial coefficients 26 28 7
2.2.3. Combinations of multisets
2.2.4. Multinomial coefficients
Let M be a multiset {a1, a2, …, an} (M has n distinct objects):
The number of ordered arrangements of n objects, in which there are k1
A k-combination of M is an unordered collection of k objects selected from n types
objects of type 1, k2 objects of type 2, ..., and km objects of type m and of objects of M. where k1+k2+ ... +km = n, is
A k-combination of M is also called an k-combination with repetition allowed.
The number of k-combination of M is C(n+ k-1, k) = C(n+ k-1, n-1)
(the number of selections, with repetitions, of k objects from n distinct objects)  n  n!    k , k ,..., k k !k !...k !  
Need to divide k candies for n kids B 1 2 m 1 2 m
1, B2, …,Bn. How many different ways to divide?
Let tj be the number of candies for kid Bj, j=1,…,n. At this point, the above problem leads to the problem:
Let k and n be non-negative integers. How many non-negative integers in the following equation have?
t  t  t   t  k 1 2 3 n  t ,t ,,t  Z 1 2 n 29 31 2.2. Combination
2.2.4. Multinomial coefficients 2.1.1. Definitions The Multinomial Theorem: 2.2.2. Binomial coefficients  n  n k k
2.2.3. Combinations of Multisets 1 2 (x  x ...x )    x x ... mk x 1 2 m 1 2 k , k ,..., m k  
2.2.4. Multinomial coefficients 1 2 m
where the summation is over all sequences of non-negative integers
(k1, k2, ..., km) such that k1 + k2 + ... + km = n. 30 32 8 Contents
3.1. Inclusion-exclusion principle 1. Basic counting principles
The inclusion–exclusion principle is an equation relating the sizes of two sets
and their union. It states that if A and B are two (finite) sets, then
2. Elementary combinatorial configuration
|A B| = |A| + |B| - |A B|
3. The inclusion-exclusion principle
The meaning of the statement is that 4. Recurrence relation
the number of elements in the union 5. Generating function
of the two sets is the sum of the
elements in each set, respectively,
minus the number of elements that are in both.
Similarly, for three sets A, B and C:
|A B C| = |A| + |B| + |C| - |A B| - |A C| - |B C| + |A B C| 33 35
3. Inclusion-exclusion principle
3.1. Inclusion-exclusion principle
3.1. Inclusion-exclusion principle
More generally, for finite sets A1, A2,…,Am 3.2. Derangement 𝐴 ∪ 𝐴 ∪ ⋯ ∪ 𝐴 = 𝑁 − 𝑁 + ⋯ + (−1) 𝑁 where: N  A A A k m k
 |  ... |, 1,2,..., 1 i 2 i k i  1 i i ..  . i  1 2 k m
Note: Nk is the sum of the cardinalities of all intersections of k
from m given sets. For example: N1 = |A1| + ... + |Am| N   m = |A1 A2 ...  Am| 34 36 9
3. Inclusion-exclusion principle 3.2. Derangement
3.1. Inclusion-exclusion principle
Denote Dn the number of derangements of {1, 2, …, n} Dn = ?? 3.2. Derangement
Let S = set of all permutations of {1, 2, …, n}  |S| = n!
Let Ai = subset of permutations of {1, 2, …, n} such that the ith element = i in the permutation.
|𝐴 ∪ 𝐴 ∪ ⋯ ∪ 𝐴 | ? ? ?
|𝐴 ∪ 𝐴 ∪ ⋯ ∪ 𝐴 | counts the number of permutations in which at least one
object i of the n objects appears in the ith position (its original position).
Dn: number of permutations such that none of the n objects appears in their original positions. Therefore:
Dn = n! - |𝐴 ∪ 𝐴 ∪ ⋯ ∪ 𝐴 |
Remember the inclusion-exclusion principle: 37 39 3.2. Derangement Contents
A derangement of {1, 2, …, n} is a permutation on the set such that none 1. Basic counting principles
of elements i is placed at position ith in the permutation.
(In other words, derangement is a permutation that has no fixed points)
2. Elementary combinatorial configuration Example: n = 5
3. The inclusion-exclusion principle
Permutation (2,3,5,4,1) is not a derangement 4. Recurrence relation
Permutation (2,3,5,1,4) is a derangement 5. Generating function
Denote Dn the number of derangements of {1, 2, …, n} Dn = ?? 38 40 10 4. Recurrence relations 4.1. Recurrence relations 4.1. Recurrence relations
A recurrence without specifying any initial values (initial conditions).
4.2. Solve recurrence relations
 can have (and usually has) multiple solutions.
Example: an = 2an-1 – an-2 for n = 2, 3, 4. It has the following sequences an as solution: an=5 an=3n an=n+1
If both the initial conditions and the recurrence relation are specified, then the
sequence is uniquely determined.
Example: an = 2an-1 – an-2 for n = 2, 3, 4 where a0=0; a1 = 3
The sequence an=5 is not the solution
The sequence an=3n is the unique solution 41 4.1. Recurrence relations
Modeling with Recurrence Relations
Example 1: Someone deposits $10,000 in a savings account at a bank yielding 5% per year Definition:
with interest compounded annually. How much money will be in the account after 30 years?
A recurrence relation for the sequence {an} is the equation that expresses an Solution:
in terms of one or more of the previous terms in the sequence namely, a0, a1, …, a
• Let Pn denote the amount in the account after n years.
n-1, for all integers n with n  n0, where n0 is a nonnegative integer. How can we determine P
A sequence is called a solution to a recurrence relation if its terms satisfy the n on the basis of Pn-1? recurrence relation.
• We can derive the following recurrence relation:
Example: Consider the recurrence relation
Pn = Pn-1 + 0.05Pn-1 = 1.05Pn-1. a • The initial condition is P
n = 2an-1 – an-2 for n = 2, 3, 4, … 0 = 10,000.
P30 = (1.05)3010,000 = 43,219.42 The sequence a Then we have:
n=3n is a solution of this recurrence relation? For n  2 we see that: 2a • P1 = 1.05P0
n-1 – an-2 = 2(3(n – 1)) – 3(n – 2) = 3n = an • Therefore, the sequence a P2 = 1.05P1 = (1.05)2P0
n=3n is a solution of the recurrence relation • P The sequence a 3 = 1.05P2 = (1.05)3P0
n=5 is also a solution of the this recurrence relation? •…
For n  2 we see that: 2an-1 – an-2 = 25 - 5 = 5 = an •P Therefore, the sequence a n = 1.05Pn-1 = (1.05)nP0
n=5 is also a solution of the recurrence relation
 We now have a formula to calculate Pn for any natural number n and can avoid the iteration. 44 11 4. Recurrence relations
4.2. Solving Recurrence Relations 4.1. Recurrence relations
Definition: A linear homogeneous recurrence relation of degree
k with constant coefficients is a recurrence relation of the form:
4.2. Solving recurrence relations
an = c1an-1 + c2an-2 + … + ckan-k where c 
1, c2, …, ck are real number constants, and ck 0.
• A sequence satisfying such a recurrence relation is uniquely
determined by the recurrence relation if it also satisfying k initial conditions:
a0 = C0, a1 = C1, a2 = C2, …, ak-1 = Ck-1
where C0, C1, ..., Ck-1 are constants. 45 47
4.2. Solving Recurrence Relations
4.2. Solving Recurrence Relations
Solving the recurrence relation for a sequence a0, a1, a2, a3,….an,… is to give
Definition: A linear homogeneous recurrence relation of degree
the explicit formula to compute the value for the general term an, i.e., to find an
k with constant coefficients is a recurrence relation of the form:
expression for an that does not involve any other ai
Example: Given the recurrence relation:
an = c1an-1 + c2an-2 + … + ckan-k a where c  0.
n = 2an-1 – an-2 where n = 2, 3, 4,…
1, c2, …, ck are real number constants, and ck a0=0; a1 = 3
The explicit formula for the above recurrence relation is an=3n Explain:
an=3n is the solution to the above recurrence relation
• Linear: the right-hand side is the sum of the terms before the term a
• Does not exist the method to solve all types of recurrence relation. n
in the sequence where the coefficients (c1, c2, ..,ck) are constant (not
• Consider method to solve the recurrence relation with following types: a function dependent on n)
• A linear homogeneous recurrence relation of degree k with constant
• Homogeneous: the right-hand side has no additional terms other coefficients
than the terms ai of the sequence
• A linear nonhomogeneous recurrence relation of degree k with constant
• Degree k: the right hand side has the (n-k)th term of the sequence coefficients 46 48 12
A linear homogeneous recurrence relation of degree k Example 1 with constant coefficients
• We try to find solution of the form a
Fibonacci sequence is given by the following recurrence relation: n = rn, where r is a constant. • The sequence {a Fn = Fn-1 + Fn-2, n  2,
n = rn } is a solution of the recurrence relation F a 0 = 0, F1 = 1. n = c1an−1 + … + ckan−k
Find the explicit formula for Fn. if and only if r satisfying:
Solution: Solve the characteristic equation: rn = c
(subtract the right-hand side from the left 1rn−1 + … + ckrn−k, or r2 - r - 1 = 0, rk − c and × by rk−n) 1rk−1 − … − ck = 0 its characteristic roots are: Leonardo Fibonacci 1 5 1  5 r  ; r  1170-1250 1 2
this is called the characteristic equation of the recurrence relation, and 2 2
its solution is called characteristic roots of the recurrence relation.
• We will use characteristic roots to obtain explicit formula for the sequence. 49 51
A linear homogeneous recurrence relation of degree k Example 1 with constant coefficients • Theorem 1. Let c • The explicit formula: 1 and c2 be real numbers. F Suppose that r2 - c n = 1.(r1)n + 2.(r2)n
1 r - c2 = 0 has 2 distinct roots r1 and r2. Then the sequence {a where 
n} is a solution of the recurrence relation
1,  2 are constants and could be determined by using initial conditions F0, F1. F a 0= 1+ 2 = 0 n = c1 an-1 + c2 an-2 F1= 1r1+ 2r2 = 1 if and only if
Solving these two equations, we have: 1 1   ;    1 2 5 5 an = 1(r1)n + 2(r2)n (1) n = 0, 1, ..., where  Muavre formula 1 and 2 are constants. Therefore n n 1     F     n  n 5   1 5  1 5  , 0. 2 2    50 52 13
The case: one characteristic root with multiplicities 2 General case
But what happens if the characteristic equation has only one root?
Theorem 3. Let c1, c2, ..., ck be real numbers. Assume the characteristic Theorem 2: Let c  equation
1 and c2 be real numbers with c2 0. Suppose that r2 - c rk - c
1 r - c2 = 0 has only one root r0. Then a sequence {an } is a solution of
1 rk-1 - c2 rk-2 - . . . - ck = 0
the recurrence relation an = c1 an-1 + c2 an-2
has k distinct roots r1, r2, ..., rk . Then a sequence {an} is a solution of if and only if the recurrence relation: a  rn  nrn  
an = c1 an-1 + c2 an-2 +...+ ck an-k, n 1 0 2 0 if and only if
n = 0, 1, ..., where 1 , 2 are constants. a n n n
n = 1 r1 + 2 r2 + . . . + k rk
where n = 0, 1, 2,..., and 1, 2, ..., k are constants 53 55 Example 2 Example 3
Solving the following recurrence relation
Solving the recurrence relation: an = 6 an-1 - 9 an-2 an = 6 an-1 - 11 an-2 + 6 an-3
with initial conditions a0 = 1 and a1 = 6. where initial conditions Solution: a Characteristic equation: 0 = 2, a1 = 5, a2 = 15.
r2 - 6 r + 9 = 0 has one root r = 3. The solution is:
Solution: Characteristic equation a r3 - 6 r2 + 11 r - 6 = 0 n = 1 3n + 2 n 3n
To determine 1, 2 , using the initial conditions, we have:
has 3 distinct roots r1 = 1, r2 = 2, r3 = 3. a0 = 1 = 1 , Therefore, the solution is a1 = 6 = 1 * 3 + 2 *1* 3 a  
n = 1 1n + 2 2n + 3 3n for some constants 1, 2, 3
Solving these equations, we have 1 = 1 and 2 = 1.
Therefore, the solution of the recurrence relation is: an = 3n + n 3n 54 56 14 Example 3 Example 4
Using the initial conditions, we have following equations to
Solve the following recurrence relation:
determine the value for constants 1, 2, 3: c a
n = – 4cn-1 + 3cn-2 + 18cn-3 , n  3, 0 = 2 = 1 + 2 + 3 c a 0 = 1; c1 = 2; c2 = 13. 1 = 5 = 1 + 2.2 + 3.3
Solution: Characteristic equation
a2 = 15 = 1 + 2.4 + 3.9.
Solving above equations, we have
r3 + 4r2 – 3r – 18 = (r – 2)(r + 3)2 = 0 
Hence, the solution of the recurrence relation:
1 = 1, 2 = -1 and 3 = 2.
Therefore, the solution of the recurrence relation is
cn = α10 2n + (α20 + α21 n)(– 3)n a where α n = 1 - 2n + 2. 3n 10, α20, α21 are constants 57 59 General case Example 4
Given linear homogeneous recurrence relation of degree k with constant
These constants are determined by using initial conditions: coefficients k 0 = c
Its characteristic equation is: a  c a n  i ni
0 = α10 20 + (α20 + α21.0) (-3)0 = α10 + α20 i1 2 = c k
1 = α10 21 + (α20 + α21.1) (-3)1 = 2α10 - 3α20 - 3α21 k r   ki c r  0 i
13 = c2 = α10 22 + (α20 + α21.2) (-3)2 = 4α10 + 9α20 +18α21 i 1 
Theorem 4: If the characteristic equation has t distinct roots
Solving three equations above, we have: α10 =1 ; α20 = -1; α21=1
r1,…,rt with multiplicities m1,…,mt (m1+…+mt = k). Then:
an = ( , +  , n + … +  , 𝑛 ) 𝑟 +
The solution of recurrence relation is: ( t m 1 n n , +  , n + … +  , 𝑛 ) 𝑟 + ... i      a  n r c 2 ( 1 n)( 3) n n   j n   ( i, j  i t,0 +  , n + … +  , 𝑛 ) 𝑟 i1  j0 
where n≥0, and αij are constants. 58 60 15
Linear nonhomogeneous recurrence relation with constant coefficients 2.5.2. Generating functions
• Linear nonhomogeneous recurrence relation with constant
Generating functions are a tool to solve a wide variety of counting
problems and recurrence relations.
coefficients) has the term F(n) dependent on n (and independent on any value of a Example 1: i ) : a
How many ways to give 12 oranges for three children: A, B and C such that:
n = c1an−1 + … + ckan−k + F(n)
A gets at least four, and B and C gets at least two, but C gets no more than five
a, b , c are the number of oranges
Linear homogeneous recurrence relation Nonhomogeneous term
that A, B and C gets, respectively
Find the number of integer solutions to
a + b + c = 12 where a ≥ 4, b ≥ 2, 2 c  5 63
2.5. Recurrence relations and generating functions 2.5.2. Generating functions 2.5.1. Recurrence relations Example 1:
Find the number of integer solutions to
a + b + c = 12 where a ≥ 4, b ≥ 2, 2 c  5 2.5.2. Generating functions Let
a: a(x) = x4 + x5 + x6 + x7 + x8
(since b + c  4  a  8)
b : b(x) = x2 + x3 + x4 + x5 + x6
(since a + c  6  b  6) c : c(x) = x2 + x3 + x4 + x5 (since 2  c  5) n=12
The coefficient of x12 in g(x) = a(x) b(x) c(x)
=(x4+ x5+ x6+ x7+ x8) (x2+ x3+x4+ x5+ x6)(x2+ x3+x4+ x5) =??? is the solution to the problem Why???
g(x) is called a generating function.
Assume xa, xb, xc are terms derived from (x4+ x5+ x6+ x7+ x8) , (x2+ x3+x4+ x5+ x6), (x2+ x3+x4+ x5)
respectively when developing the right-hand side  4 a  8, 2 b  6, 2 c  5
When developing the right-hand side, these three terms give us the term xn where n = a +b + c:
g(x) = (x4+ x5+ x6+ x7+ x8) (x2+ x3+x4+ x5+ x6)(x2+ x3+x4+ x5) = …. + Kxn +…..
The coefficient of xn in f(x) is the number of positive integer solutions to
a + b + c = n where 4 a  8, 2 b  6, 2 c  5 62 64 16 2.5.2. Generating functions 2.5.2. Generating functions Example 1:
Find the number of integer solutions to
Example 2: For the binomial coefficients we already know that:
a + b + c = 12 where a ≥ 4, b ≥ 2, 2 c  5 n n Let
(x  y)n  C(n,k) k nk x y
 (x 1)n  C(n,k) kx  g(x)
a: a(x) = x4 + x5 + x6 + x7 + x8
(since b + c  4  a  8) k 0 k 0 1. x4*x3*x5
b : b(x) = x2 + x3 + x4 + x5 + x6 (since a + c 6  b  6)
(x+1)n is the generating function for the sequence 2. x4*x4*x4 c : c(x) = x2 + x3 + x4 + x5 (since 2  c  5) 3. x4*x5*x3
C(n, 0), C(n, 1),…,C(n, k),…, C(n, n), 0,0,0…
The coefficient of x12 in g(x) = a(x) b(x) c(x) 4. x4*x6*x2
=(x4+ x5+ x6+ x7+ x8) (x2+ x3+x4+ x5+ x6)(x2+ x3+x4+ x5) 5. x5*x2*x5 which is 14, is the solution 6. x5*x3*x4
g(x) is called a generating function. 7. x5*x4*x3 8. x5*x5*x2 9. x6*x2*x4 10. x6*x3*x3 11. x6*x4*x2 12. x7*x2*x3 13. x7*x3*x2 14. x8*x2*x2 65 67 2.5.2. Generating functions 2.5.2. Generating functions Definition: Let a Definition: Let a
0, a1, a2, … be a sequence of real numbers. The function
0, a1, a2, … be a sequence of real numbers. The function   g(x)  a  a x  ... k a x  ...  a x g(x)  a  a x  ... k a x  ...  a x k  i k  i 0 1 i 0 1 i i0 i0
is called the generating function for the given sequence.
is called the generating function for the given sequence. A finite sequence
Some useful generating function: a
Ex1: (1  xn+1) = (1  x)(1 + x + x2 + x3 + ...+ xn). 0, a1, a2, …, an
So (1-xn+1)/(1-x) = 1 + x + x2 + x3 + ...+ xn,
can be regarded as the infinite sequence
 (1-xn+1)/(1-x) is the generating function for the sequence:
a0, a1, a2, …, an, 0, 0,… [set all terms higher than n to 0]
1, 1, 1, …, 1, 0, 0, 0, … . (where the first n+1 terms are 1) and its generating function
Ex2: From Ex1, If n   and |x| < 1, then 1 = (1  x)(1 + x + x2 + x3 + ...).
g(x) = a0 + a1x + a2x2 + … + anxn
So, 1/(1-x) = 1 + x + x2 + x3 + ... is a polynomial.
 1/(1-x) where |x| < 1 is the generating function for the sequence: 1, 1, 1, …, 1, … . 66 68 17 2.5.2. Generating functions
Generating functions are a tool to solve a wide variety of counting problems and recurrence relations.
Definition: Let a0, a1, a2, … be a sequence of real numbers. The function  g(x)  a  a x  ... k a x  ...  a x k  i 0 1 i i0
is called the generating function for the given sequence. 69 2.5.2. Generating functions
Example: Solve the recurrence relation an-3an-1 = n, n1, a0=1 𝑥
𝑔 𝑥 − 1 − 3𝑥𝑔(𝑥) = (1 − 𝑥) 1 𝑥 𝑔 𝑥 = + 1 − 3𝑥 (1 − 3𝑥)(1 − 𝑥) 1 𝐴 𝐵 𝐶 𝑔 𝑥 = + + + 1 − 3𝑥 (1 − 3𝑥) (1 − 𝑥) (1 − 𝑥) 3 1 1 
⇒ 𝐴 = ; 𝐵 = − ; 𝐶 = − ; g x  a  a x   k a x   i 4 4 2 ( ) ... ... a x k  0 1 i 7/4 −1/4 −1/2 i0 𝑔 𝑥 = + + (1 − 3𝑥) (1 − 𝑥) (1 − 𝑥)
We find an by determining the coefficient of xn in g(x)
 determining the coefficient of xn in each of the three summands 70 18