Introduction to Combinatorial Mathematics

George Voutsadakis1

1 Mathematicsand Computer Science

Lake Superior State University

LSSU Math 300

George Voutsadakis (LSSU) Combinatorics April 2016 1 / 71

 Outline

1 Generating Functions
Introduction
Generating Functions and Combinations
Enumerators for Permutations
Distributions of Distinct Objects Into NonDistinct Cells
Partitions of Integers
The Ferrers Graph
Elementary Relations

George Voutsadakis (LSSU) Combinatorics April 2016 2 / 71

 Generating Functions Introduction

Subsection 1

Introduction

George Voutsadakis (LSSU) Combinatorics April 2016 3 / 71

 Generating Functions Introduction

Representing Choices Using Algebraic Expressions

From three distinct objects a, b and c, there are three ways to choose
one object, namely, to choose either a or b or c.
We represent these possible choices symbolically as a + b + c.
From these three objects, there are three ways to choose two objects,
namely, to choose either a and b, or b and c, or c and a.
These can be represented symbolically as ab + bc + ca.
There is only one way to choose three objects, which can be
represented symbolically as abc.
Examining the polynomial
(1+ax)(1+bx)(1+cx) = 1+(a +b +c)x +(ab +bc +ca)x 2 +(abc)x 3
we discover that all these possible ways of selection are exhibited as
the coefficients of the powers of x:
The coefficient of x i is the representation of the ways of selecting i
objects from the three objects.
George Voutsadakis (LSSU) Combinatorics April 2016 4 / 71
 Generating Functions Introduction

Analysis of the Interpretation

This involves an interpretation of the polynomial according to the

combinatorial rules of sum and of product.
The factor 1 + ax means that for the object a, the two ways of
selection are “not to select a” or “to select a”. The variable a is a
formal variable and is used simply as an indicator. The coefficient of x 0
shows the ways no object is selected, and the coefficient of x 1 shows
the ways one object is selected.
Similar interpretation can be given to the factors 1 + bx and 1 + cx.
Thus, the product (1 + ax)(1 + bx)(1 + cx) indicates that for the
objects a, b and c, the ways of selection are: “to select or not to
select a” and “to select or not to select b” and “to select or not to
select c”.
Therefore, the powers of x in the polynomial indicate the number of
objects that are selected, and the corresponding coefficients show all
the possible ways of selection.
George Voutsadakis (LSSU) Combinatorics April 2016 5 / 71
 Generating Functions Introduction

Ordinary Generating Function of a Sequence

This example motivates the formal definition of the generating
function of a sequence.
Let (a0 , a1 , a2 , . . . , ar , . . .) be the symbolic representation of a
sequence of events, or let it simply be a sequence of numbers. The
function
F (x) = a0 µ0 (x) + a1 µ1 (x) + a2 µ2 (x) + · · · + ar µr (x) + · · ·
is called the ordinary generating function of the sequence (a0 , a1 ,
a2 , . . . , ar , . . .), where µ0 (x), µ1 (x), µ2 (x), . . ., µr (x), . . . is a
sequence of functions of x that are used as indicators.
Another kind of generating function called the exponential generating
function will be discussed later.
The indicator functions µ(x)’s are usually chosen in such a way that
no two distinct sequences will yield the same generating function.
The generating function of a sequence is just an alternative
representation of the sequence.
George Voutsadakis (LSSU) Combinatorics April 2016 6 / 71
 Generating Functions Introduction

Examples of an Ordinary Generating Function

Using 1, cos x, cos 2x, . . ., cos rx, . . . as the indicator functions, we
see that the ordinary generating function of the sequence
(1, ω, ω 2 , . . . , ω r , . . .) is
F (x) = 1 + ω cos x + ω 2 cos 2x + · · · + ω r cos rx + · · · .
Using 1, 1 + x, 1 − x, 1 + x 2 , 1 − x 2 , . . ., 1 + x r , 1 − x r , . . . as the
indicator functions, the ordinary generating function of the sequence
(3, 2, 6, 0, 0) is
3 + 2(1 + x) + 6(1 − x) = 11 − 4x.

The sequences (1, 3, 7, 0, 0) and (1, 2, 6, 1, 1) will also yield the same
ordinary generating function:
1 + 3(1 + x) + 7(1 − x) = 11 − 4x;
1 + 2(1 + x) + 6(1 − x) + (1 + x 2 ) + (1 − x 2 ) = 11 − 4x.
Thus, the functions 1, 1 + x, 1 − x, 1 + x 2 , 1 − x 2 , . . . should not be
used as indicator functions.
George Voutsadakis (LSSU) Combinatorics April 2016 7 / 71
 Generating Functions Introduction

Committing to a Specific Family of Indicator Functions

The most usual and useful form of µr (x) is x r .

In that case, for the sequence (a0 , a1 , a2 , . . . , ar , . . .), we have

F (x) = a0 + a1 x + a2 x 2 + · · · + ar x r + · · · .

From now on, when we talk about the generating functions of a

sequence, we shall mean the generating function of the sequence with
the powers of x as indicator functions.
Notice that the sequence (a0 , a1 , a2 , . . . , ar , . . .) can be an infinite
sequence. Then F (x) will be an infinite series. Since x is just a formal
variable, there is no need to question whether the series converges!

George Voutsadakis (LSSU) Combinatorics April 2016 8 / 71

 Generating Functions Generating Functions and Combinations

Subsection 2

Generating Functions and Combinations

George Voutsadakis (LSSU) Combinatorics April 2016 9 / 71

 Generating Functions Generating Functions and Combinations

Enumerators
We saw that the polynomial (1 + ax)(1 + bx)(1 + cx) is the ordinary
generating function of the different ways to select the objects a, b and
c.
Instead of the different ways of selection, we may only be interested
in the number of ways of selection.
By setting a = b = c = 1, we have
(1 + x)(1 + x)(1 + x) = (1 + x)3 = 1 + 3x + 3x 2 + x 3 .
We see that there are:
One way to select no objects from the three objects C (3, 0);
Three ways to select one object out of three, C (3, 1); etc.
A generating function that gives the number of combinations or
permutations is called an enumerator.
An ordinary generating function that gives the number of
combinations or permutations is called an ordinary enumerator.
George Voutsadakis (LSSU) Combinatorics April 2016 10 / 71
 Generating Functions Generating Functions and Combinations

Ordinary Enumerator for Combinations

To find the number of combinations of n distinct objects, we have the

ordinary enumerator
n(n−1) 2
(1 + x)n = 1 + nx + 2! x + · · ·
+1) r
+ n(n−1)···(n−r
r! x + ··· + xn
= C (n, 0) 2
+ C (n, 1)x + C (n, 2)x + · · ·
+ C (n, r )x r + · · · + C (n, n)x n .

In the expansion of (1 + x)n , the coefficient of the term x r is the

number of ways the term x r can be formed by taking r x’s and n − r
1’s among the n factors 1 + x.
For this reason the C (n, r )’s are called the binomial coefficients.
In a binomial expansion, nr is a common alternative notation for

C (n, r ).

George Voutsadakis (LSSU) Combinatorics April 2016 11 / 71

 Generating Functions Generating Functions and Combinations

Some Consequences
From n0 + n1 x + n2 x 2 + · · · + nr x r + · · · + nn x n = (1 + x)n , by

setting x = 1, we get
         
n n n n n
+ + + ··· + + ··· + = 2n .
0 1 2 r n
The combinatorial significance of this identity is that both sides give
the number of ways of selecting none, or one, or two, . . ., or n objects
out of n distinct objects.
By
setting x =
−1, we also have
the identity
n n
n r n + · · · + (−1)n n = 0. Rewriting as


0 − 1 + 2 − · · · + (−1) r n
           
n n n n n n
+ + + ··· = + + + ··· ,
0 2 4 1 3 5
we see that
the number of ways of selecting an even number of objects is equal to
the number of ways of selecting an odd number of objects from n
distinct objects.
George Voutsadakis (LSSU) Combinatorics April 2016 12 / 71
 Generating Functions Generating Functions and Combinations

Example (Algebraic Proof)

2
2
2
2
Claim: n0 + n1 + · · · + nr + · · · + nn = 2n


n .
Method 1: By the
binomial
theorem

(1 + x)n = 1 + n1 x + n2 x 2 +
· · · + nn
x n .
Similarly, (1 + x −1 )n = 1 + n1 x −1 + n2 x −2 + · · · + nn x −n .

Therefore, the constant term in (1 + x)n (1 + x −1 )n is

 2  2  2  2
n n n n
+ + ··· + + ··· + .
0 1 r n

On the other hand, we get

(1 + x)n (1 + x −1 )n (1 + x)n ((1 + x)x −1 )n
=
(1 + x)n (1 + x)n x −n
=
(1 + x)2n
x −n

=
(1 + 2n 2n 2 2n

2n −n
= 1 x + 2 x + ··· + 2n x )x .
The constant term is therefore 2n


n .
George Voutsadakis (LSSU) Combinatorics April 2016 13 / 71
 Generating Functions Generating Functions and Combinations

Example (Combinatorial Proof)

2
2
2
2
Claim: n0 + n1 + · · · + nr + · · · + nn = 2n


n .
Method 2:
The identity to be proved can
be rewritten as


n
n
n n
n
n
n n
n n 2n

0 n + 1 n−1 + 2 n−1 + · · · + r n−r + · · · + n 0 = n .
The right side is the number of ways to select n objects out of a total
of 2n objects.
The same selection can also be performed as follows:
First divide the 2n objects into two piles with n objects in each pile.
To select n objects, we may select i objects from the first pile and n − i
objects
from the second pile. There are:
n
i
ways to select i objects from the first pile;
n


n−i
ways to select n − i objects from the second pile.
Hence, the total number of ways to make the selection is
n     
X n n 2n
= .
i n−i n
i =0

George Voutsadakis (LSSU) Combinatorics April 2016 14 / 71

 Generating Functions Generating Functions and Combinations

An Application

Find the number of 2n-digit binary sequences which are such that the
number of 0’s in the first n digits of a sequence is equal to the
number of 0’s in the last n digits of the sequence.
Since the number of n-digit binary sequences containing r 0’s is nr ,

the number of 2n-digit binary sequences
containing r 0’s in the first n

2
digits as well as in the last n digits is nr . Therefore, the number of
2n-digit binary sequences which are such that the number of 0’s in
the first n digits of a sequence is equal to the number of 0’s in the
last n digits of the sequence is
 2  2  2  2  
n n n n 2n
+ + ··· + + ··· + = .
0 1 r n n

What does the combinatorial argument used in the previous slide tell
us in this case?
George Voutsadakis (LSSU) Combinatorics April 2016 15 / 71
 Generating Functions Generating Functions and Combinations

Example

Prove the identity

       
n n n n
+2 + ··· + r + ··· + n = n2n−1 .
1 2 r n

Start with
       
n n n r n n
+ x + ··· + x + ··· + x = (1 + x)n .
0 1 r n

Differentiate both sides with respect to x:

       
n n n r −1 n n−1
+2 x + ··· + r x + ··· + n x = n(1 + x)n−1 .
1 2 r n

Now set x = 1.

George Voutsadakis (LSSU) Combinatorics April 2016 16 / 71

 Generating Functions Generating Functions and Combinations

Example

What is the coefficient of the term x 23 in (1 + x 5 + x 9 )100 ?

x 5 x 9 x 9 = x 23 is the only way the term x 23 can be made up in the
expansion of (1 + x 5 + x 9 )100 . Moreover, there are:
C (100, 2) ways to choose the two factors x 9 ;
Then, there are C (98, 1) ways to choose the factor x 5 .
Thus, the coefficient of x 23 is
100 · 99
C (100, 2) · C (98, 1) = · 98 = 485, 100.
2

George Voutsadakis (LSSU) Combinatorics April 2016 17 / 71

 Generating Functions Generating Functions and Combinations

Example
Claim: The ordinary
generating function of the sequence
0
2
4
2r −1/2 .
0 , 1 , 2 , . . . , r , . . . is (1 − 4x)
Recall the binomial theorem
∞
n
X n(n − 1)(n − 2) · · · (n − r + 1) r
(1 + x) = 1 + x
r!
r =1
for n not a positive integer.
Applying the theorem, we get
(−1/2)(−1/2−1)···(−1/2−r +1)
(1 − 4x)−1/2 = 1 + ∞ (−4x)r
P
Pr =1 r!
4r (1/2)(3/2)(5/2)···((2r −1)/2) r
= 1+ ∞ x
Pr =1 2r (1·3·5···(2r −1)) r
r!
= 1+ ∞ x
Pr =1 r!
(2r ·r !)(1·3·5···(2r −1)) r
= 1+ ∞ x
Pr =1 r !r !
(2·4·6···2r )(1·3·5···(2r −1)) r
= 1+ ∞ x
Pr =1 (2r )! r
r !r ! P
= 1+ ∞ r =1 r !r ! x = 1 +
∞ 2r
r
r =1 r x .

George Voutsadakis (LSSU) Combinatorics April 2016 18 / 71

 Generating Functions Generating Functions and Combinations

An Application
Evaluate the sum
t   
X 2i 2t − 2i
, for a given t.
i t −i
i =0

We know:
2i
is the coefficient of the term x i in (1


i − 4x)−1/2 ;
2t−2i
is the coefficient of the term x t−i


t−i in (1 − 4x)−1/2 .
Thus, ti=0 2ii 2t−2i is the coefficient of the term x t in
P


t−i
(1 − 4x)−1/2 (1 − 4x)−1/2 .
But, we have (1 − 4x)−1/2 (1 − 4x)−1/2 = (1 − 4x)−1 =
1 + 4x + (4x)2 + (4x)3 + · · · + (4x)r + · · · . Thus,
t   
X 2i 2t − 2i
= 4t .
i t −i
i =0

George Voutsadakis (LSSU) Combinatorics April 2016 19 / 71

 Generating Functions Generating Functions and Combinations

Selections With Repetitions

We can extend the framework for the case when repetitions are
allowed in the selections.
Example: The ordinary generating function for the combinations of
the objects a, b and c, where a can be selected twice is

(1 + ax + a2 x 2 )(1 + bx)(1 + cx)

= 1 + (a + b + c)x + (ab + bc + ac + a2 )x 2
+ (abc + a2 b + a2 c)x 3 + (a2 bc)x 4 .

Notice the difference between the combinatorial significance of the

preceding polynomial and that of

(1 + ax)(1 + a2 x 2 )(1 + bx)(1 + cx)

= (1 + ax + a2 x 2 + a3 x 3 )(1 + bx)(1 + cx).

George Voutsadakis (LSSU) Combinatorics April 2016 20 / 71

 Generating Functions Generating Functions and Combinations

Selections With Repetitions (Cont’d)

Example: Consider the generating function

(1 + ax)(1 + a2 x)(1 + bx)(1 + cx)

= 1 + (a + b + c + a2 )x + (db + bc + ac + a3 + a2 b + a2 c)x 2
+ (abc + a3 b + a2 bc + a3 c)x 3 + (a3 bc)x 4 .

We can imagine that there are four boxes:

one containing a;
one containing two a’s;
one containing b;
one containing c.
The generating function gives all possible outcomes of the selection of
the boxes.

George Voutsadakis (LSSU) Combinatorics April 2016 21 / 71

 Generating Functions Generating Functions and Combinations

Enumerator of Combinations With Repetitions

Example: Find the ordinary enumerator for the combinations of the
objects a, b and c, where a can be selected twice.
For the object a,
there is one way not to select it;
one way to select it once;
one way to select it twice.
This is modeled by a factor 1 + x + x 2 .
For the objects b, there is one way not to select it and one way to
select it. This is modeled by a factor of (1 + x).
Similarly for c.
Thus, the ordinary enumerator for the combinations of the objects
a, b and c, where a can be selected twice is

(1 + x + x 2 )(1 + x)2 = 1 + 3x + 4x 2 + 3x 3 + x 4 .

George Voutsadakis (LSSU) Combinatorics April 2016 22 / 71

 Generating Functions Generating Functions and Combinations

Example
Given two each of p kinds of objects and one each of q additional
kinds of objects, in how many ways can r objects be selected?
The ordinary enumerator for the combinations is
(1 + x + x 2 )p (1 + x)q .
r

2, if r is even
Let ⌊ 2r ⌋ denote the integral part of r
2: ⌊ 2r ⌋ = r −1 .
2 , if r is odd
Note that in the product above, to form the r
power x we may select:
i x 2 ’s among the p factors of the form 1 + x + x 2 ;
r − 2i x’s among the p − i remaining factors of the form 1 + x + x 2
and the q factors of the form 1 + x.
Thus, the coefficient of x r in the enumerator above is
⌊r /2⌋   
X p p+q−i
.
i r − 2i
i =0

George Voutsadakis (LSSU) Combinatorics April 2016 23 / 71

 Generating Functions Generating Functions and Combinations

Enumerator of Selections with Unlimited Repetitions

The ordinary enumerator for the selection of r objects out of n

objects with unlimited repetitions is

(1 + x + x 2+ · · · +x k + · · · )n
n
1
=
1−x
= (1 − x)−n
(−n)(−n − 1) · · · (−n − r + 1)
=1+ ∞ (−x)r
P
r =1
r!
(n)(n + 1) · · · (n + r − 1) r
=1+ ∞
P
r =1 x
r !
= ∞ n+r −1
r
P
r =0 r x .

This verifies the formula we developed for the number of ways to

select r objects from n objects with unlimited repetitions.

George Voutsadakis (LSSU) Combinatorics April 2016 24 / 71

 Generating Functions Generating Functions and Combinations

Selections with Unlimited Repetitions with a Restriction

The ordinary enumerator for the selection of r objects out of n

objects (r ≥ n), with unlimited repetitions but with each object
included in each selection, is

(x + x 2 + · · · + x k + · · · )n
= x n (1 + x + · · · + x k−1 + · · · )n
 n
1
=x n = x n (1 − x)−n
1−x
= xn ∞ x = ∞
n+i −1
i n+i −1
n+i
P P
i =0 i i =0 i x
P∞ r −1
r
= r =n r −n x
= ∞ r −1
r
P
r =n n−1 x .

George Voutsadakis (LSSU) Combinatorics April 2016 25 / 71

 Generating Functions Generating Functions and Combinations

Example

Claim: The number of ways in which r nondistinct objects can be

distributed into n distinct cells, with the condition that no cell
contains less than q nor more than q +  z − 1 objects, is the
z n

1 − x
coefficient of x r −qn in the expansion of .
1−x
Since the ordinary enumerator for the ways a particular cell can be
filled is x q + x q+1 + · · · + x q+z−1 the ordinary enumerator for the
distributions is
(x q + x q+1 + · · · + x q+z−1 )n
= x qn (1 + x + · · · + x z−1 )n
1 − xz n
 
= x qn .
1−x

George Voutsadakis (LSSU) Combinatorics April 2016 26 / 71

 Generating Functions Generating Functions and Combinations

An Application
Find the number of ways in which four persons, each rolling a single
die once, can have a total score of 17.
For r = 17, n = 4, q = 1 and z = 6, the ordinary enumerator is
6 4
 
x 4 1−x
1−x . We have:

(1 − x 6 )4 = 1 − 4x 6 + 6z 12 − 4z 18 + x 24 ;
4 4·5 2 4·5·6 3
(1 − x)−4 = 1+ x + x + x + ··· .
1! 2! 3!
Thus, the coefficient of x 13 in (1 − x 6 )4 (1 − x)−4 is
4 · 5 · 6 · · · 16 4 · 5 · 6 · · · 10 4
−4· +6·
13! 7! 1!
14 · 15 · 16 8 · 9 · 10 4
= −4· +6· = 104.
3! 3! 1!

George Voutsadakis (LSSU) Combinatorics April 2016 27 / 71

 Generating Functions Enumerators for Permutations

Subsection 3

Enumerators for Permutations

George Voutsadakis (LSSU) Combinatorics April 2016 28 / 71

 Generating Functions Enumerators for Permutations

Permutation Enumerators and Commutativity

There is an obvious difficulty when attempting to extend the previous
results to generating functions of permutations.
Multiplication in the ordinary algebra in the field of real numbers is
commutative (that is, ab = ba). As a result, we cannot handle the
case of permutations using ordinary algebra.
Example: Consider the permutations of the two objects a and b.
What we want to have as a generating function for the permutations is
1 + (a + b)x + (ab + ba)x 2 .
However, this polynomial is equivalent to
1 + (a + b)x + (2ab)x 2 ,
in which the two distinct permutations ab and ba can no longer be
recognized.
Instead of introducing a new algebra that is noncommutative for the
case of permutations, we discuss enumerators for permutations which
can still be handled by the ordinary algebra in the real numbers.
George Voutsadakis (LSSU) Combinatorics April 2016 29 / 71
 Generating Functions Enumerators for Permutations

Introducing a Different Generating Function

An enumerator for the permutations of n distinct objects would have
the form
F (x) = P(n, 0)x 0 + P(n, 1)x + P(n, 2)x 2 + · · ·
+ P(n, r )x r + · · · + P(n, n)x n
n! n! n!
= 1 + (n−1)! x + (n−2)! x 2 + · · · + (n−r r n
)! x + · · · + n!x .

There is no simple compact closed-form expression for F (x).

To carry along the entire polynomial defeats the purpose of using the
generating function representation.
Recall the binomial expansion
(1 + x)n = 1 + C (n, 1)x + C (n, 2)x 2 + · · ·
+ C (n, r )x r + · · · + C (n, n)x n
P(n,r ) r
= 1 + P(n,1) P(n,2) 2
1! x + 2! x + · · · + r! x + · · · +
P(n,n) n
n! x .
We see that the key lies in defining another kind of generating
function, the exponential generating function.
George Voutsadakis (LSSU) Combinatorics April 2016 30 / 71
 Generating Functions Enumerators for Permutations

The Exponential Generating Function

Let (a0 , a1 , a2 , . . . , ar , . . .) be the symbolic representations of a

sequence of events or simply be a sequence of numbers. The function
a0 a1 a2 ar
F (x) = µ0 (x) + µ1 (x) + µ2 (x) + · · · + µr (x) + · · ·
0! 1! 2! r!
is called the exponential generating function of the sequence
(a0 , a1 , a2 , . . . , ar , . . .), with µ0 (x), µ1 (x), µ2 (x), . . ., µr (x), . . ., as
the indicator functions.
Example: (1 + x)n is the exponential generating function of the
P(n, r )’s with the powers of x as the indicator functions.
An exponential generating function that gives the number of
combinations or permutations is called an exponential enumerator.

George Voutsadakis (LSSU) Combinatorics April 2016 31 / 71

 Generating Functions Enumerators for Permutations

Examples of Exponential Generating Functions I

Claim: The exponential generating function of the sequence

(1, 1, 1, . . . , 1, . . .) is e x .
Recall Maclaurin’s series for e x : e x = ∞ 1 n x
P
n=0 n! x . This shows that e
is the exponential generating function of (1, 1, 1, . . . , 1, . . .).
Claim: The exponential generating function of the sequence
(1, 1 · 3, 1 · 3 · 5, . . . , 1 · 3 · 5 · · · (2r + 1), . . .) is (1 − 2x)−3/2 .
P∞ −3/2

(1 − 2x)3/2 = n=0 n (−2x)n
P∞ (− 32 )(− 52 )(− 72 )···(− 23 −n+1)
= n=0 n! (−2)n x n
P∞ (−3)(−5)(−7)···(−2n−1)
= n=0 2n n! (−1)n 2n x n
P∞ xn
= n=0 (3 · 5 · 7 · · · (2n + 1)) n! .
This proves the claim.

George Voutsadakis (LSSU) Combinatorics April 2016 32 / 71

 Generating Functions Enumerators for Permutations

Examples of Exponential Generating Functions II

Claim: The exponential generating function of the sequence

(P(0, 0), P(2, 1), P(4, 2), . . . , P(2r , r ), . . .) is (1 − 4x)−1/2 .

P∞ −1/2

(1 − 4x)−1/2 = n=0n (−4x)n
P∞ (− 12 )(− 32 )(− 52 )···(− 12 −n+1)
= n=0 n! (−4)n x n
P∞ (−1)(−3)(−5)···(−2n+1)
= n=0 2n n! (−1)n 2n 2n x n
P∞ 1·3·5···(2n−1)n!2n x n
= n=0 n! n!
P∞ (2n)! x n
= n=0
P∞ n! n! x n
= n=0 P(2n, n) n! .

George Voutsadakis (LSSU) Combinatorics April 2016 33 / 71

 Generating Functions Enumerators for Permutations

Permutations With Repetitions

The exponential enumerator for the permutations of:
a single object with no repetitions is 1 + x.
n distinct objects with no repetitions is (1 + x)n .
When repetitions are allowed in the permutations, the extension is
immediate:
The exponential enumerator for the permutations of all p of p identical
p
objects is xp! , since there is only one way of doing so.
The exponential enumerator for the permutations of none, one, two,
. . ., p of p identical objects is 1 + 1!1 x + 2!1 x 2 + · · · + p!
1 p
x .
Similarly, the exponential enumerator for the permutation of all p + q
of p + q objects, with p of them of one kind and q of them of another
p q p+q
x p+q
kind, is xp! xq! = xp!q! = (p+q)!
p!q! (p+q)! , which agrees with the known
result that the number of permutations is (p+q)! p!q! .
The exponential enumerator for the permutations of none, one, two,
. . ., p + q of p + q objects, with p of them of one kind and q of them
1 p
of another kind, is (1 + 1!1 x + · · · + p! x )(1 + 1!1 x + · · · + q!
1 q
x ).

George Voutsadakis (LSSU) Combinatorics April 2016 34 / 71

 Generating Functions Enumerators for Permutations

Examples

The exponential enumerator for the permutations of two objects of

one kind and three objects of another kind is
1 1 2 1 1 2 1 3
(1 + 1! x + 2! x )(1 + 1! x + 2! x + 3! x )
1 1 1 1 1 2 1 1 1
= 1 + ( 1! + 1! )x + ( 1!1! + 2! + 2! )x + ( 1!2! + 1!2! + 3! )x 3
1 1 4 1 5
+ ( 1!3! + 2!2! )x + ( 2!3! )x .

The number of r -permutations of n distinct objects with unlimited

repetitions is given by the exponential enumerator
∞
x2 x3 X nr r
(1 + x + + + · · · )n = e nx = x .
2! 3! r!
r =0

George Voutsadakis (LSSU) Combinatorics April 2016 35 / 71

 Generating Functions Enumerators for Permutations

Example

Find the number of r -digit quaternary sequences in which each of the

digits 1, 2, and 3 appears at least once.
This problem is the same as that of permuting four distinct objects
with the restriction that three of the four objects must be included in
the permutations. The exponential enumerator for the permutations:
of the digit 0 is (1 + x + 2!1 x 2 + · · · ) = e x ;
of the digit 1 (or 2, or 3) is (x + 2!1 x 2 + 3!1 3
x + · · · ) = e x − 1.
It follows that the exponential enumerator for the permutations of the
four digits is

e x (e x − 1)(e x − 1)(e x − 1) = e x (e 3x − 3e 2x + 3e x − 1)
= e 4x − 3e 3x + 3e 2x − e x
P∞ (4r −3·3r +3·2r −1) r
= r =0 r! x .

Therefore, the number of r -digit quaternary sequences in which each

of the digits 1, 2, and 3 appears at least once is 4r − 3 · 3r + 3 · 2r − 1.
George Voutsadakis (LSSU) Combinatorics April 2016 36 / 71
 Generating Functions Enumerators for Permutations

Example

Find the number of r -digit quaternary sequences that contain an even

number of 0’s.
The exponential enumerator for the permutations of the digit 0 is
2 4
(1 + x2! + x4! + · · · ) = 12 (e x + e −x ).
The exponential enumerator for the permutations of each of the digits
x 2 3
1, 2, and 3 is (1 + 1! + x2! + x3! + · · · ) = e x .
It follows that the exponential enumerator for the number of
quaternary sequences containing an even number of 0’s is
1 x 1 4x
2 (e + e −x )(e x )3 = 2x
2 (e P+ e ) r
1 (4 +2r ) r
= 1+ ∞ r =1 2 r! x .

Therefore, the number of r -digit quaternary sequences that contain

r r
an even number of 0’s is 4 +2
2 .

George Voutsadakis (LSSU) Combinatorics April 2016 37 / 71

 Generating Functions Enumerators for Permutations

Example

To find the number of r -digit quaternary sequences that contain an

even number of 0’s and an even number of 1’s, we have the
exponential enumerator
1 x
2 (e + e −x ) 12 (e x + e −x )e x e x = 1 2x
4 (e + 2 + e −2x )e 2x
1 4x 2x + 1)
= 4 (e P+ 2e
1 (4r +2·2r ) r
= 1+ ∞ r =1 4 r! x .

Thus, the number of r -digit quaternary sequences that contain an

even number of 0’s and an even number of 1’s is
1 r
(4 + 2 · 2r ).
4

George Voutsadakis (LSSU) Combinatorics April 2016 38 / 71

 Generating Functions Enumerators for Permutations

Example

Find the exponential enumerator for the number of ways to choose r

or less objects from r distinct objects and distribute them into n
distinct cells, with objects in the same cell ordered.
There are:
C (r , m) ways to select m objects out of r objects;
n(n + 1) · · · (n + m − 1) ways to arrange them in the n distinct cells.
Since m can range from 0 to r , the total number is

C (r , 0) + C (r , 1) · n + C (r , 2) · n(n + 1) + C (r , 3) · n(n + 1)(n + 2)

h + · · · + C (r , r ) · n(n + 1) · · · (n + r − 1)
1 1 1
= r! r! ·1+ (r −1)!1! ·n+ (r −2)!2! · n(n + 1)+
i
1 1
(r −3)!3! · n(n + 1)(n + 2) + · · · + r! · n(n + 1) · · · (n + r − 1) .

George Voutsadakis (LSSU) Combinatorics April 2016 39 / 71

 Generating Functions Enumerators for Permutations

Example (Cont’d)

We obtained
h
r ! r1! · 1 + (r −1)!1!
1
·n+ 1
(r −2)!2! · n(n + 1)+
i
1 1
(r −3)!3! · n(n + 1)(n + 2) + · · · + r! · n(n + 1) · · · (n + r − 1) .

The expression in the square brackets is the coefficient of the term x r

in the product of the two series
2 r
x
e x = 1 + 1! + x2! + · · · + xr ! + · · ·;
(1 − x)−n = 1 + 1! n
+ n(n+1) 2
2! x + · · · +
n(n+1)···(n+r −1) r
r! x + · · ·.
Therefore, the sought after exponential enumerator is
ex
.
(1 − x)n

George Voutsadakis (LSSU) Combinatorics April 2016 40 / 71

 Generating Functions Distributions of Distinct Objects Into NonDistinct Cells

Subsection 4

Distributions of Distinct Objects Into NonDistinct Cells

George Voutsadakis (LSSU) Combinatorics April 2016 41 / 71

 Generating Functions Distributions of Distinct Objects Into NonDistinct Cells

Stirling Numbers of the Second Kind

We consider the number of ways of distributing r distinct objects into

n distinct cells so that no cell is empty and the order of objects within
a cell is not important.
It is the same as the number of the r -permutations of the n distinct
cells with each cell included at least once in a permutation.
The exponential enumerator for the permutations is
2 3
(x + x2! + x3! + · · · )n = (e x − 1)n = ni=0 ni (−1)i e (n−i )x
P

Pn n

i
P∞ 1 r r
= i =0 i (−1) r =0 r ! (n − i ) x
P∞ x r Pn i n

r
= r =0 r ! i =0 (−1) i (n − i ) .

Thus, the number of ways of placing

Pn r distinct objects into n distinct
n

cells with no cell left empty isP i =0 (−1)
i (n − i )r = n!S(r , n)
i
1 n i n r
where S(r , n) is defined as n! i =0 (−1) i (n − i ) . S(r , n) is called
the Stirling number of the second kind.
George Voutsadakis (LSSU) Combinatorics April 2016 42 / 71
 Generating Functions Distributions of Distinct Objects Into NonDistinct Cells

Allowing Empty Cells

The number of ways of placing r distinct objects into n nondistinct

cells with no cell left empty is equal to S(r , n).
Claim: The number of ways of distributing r distinct objects into n
nondistinct cells with empty cells allowed is:
S(r , 1) + S(r , 2) + · · · + S(r , n), for r ≥ n;
S(r , 1) + S(r , 2) + · · · + S(r , r ), for r ≤ n.
To distribute r distinct objects into n nondistinct cells with empty
cells allowed, we can do one of the following:
Distribute them so that one cell is not empty in S(r , 1) ways;
Distribute them so that two cells are not empty in S(r , 2) ways;
..
.
Thus, by the Sum Rule, the claim follows.

George Voutsadakis (LSSU) Combinatorics April 2016 43 / 71

 Generating Functions Distributions of Distinct Objects Into NonDistinct Cells

Exponential Enumerator for r ≤ n

When r ≤ n, i.e., there are at least as many cells as objects, there is a
closed-form expression for the ordinary generating function of the
numbers of ways of distributing the objects.
Since S(i , j) = 0, for i < j, the count S(r , 1) + S(r , 2) + · · · + S(r , r )
does not change if we add to it an infinite number of terms as follows:
S(r , 1) + S(r , 2) + · · · + S(r , r ) + S(r , r + 1) + S(r , r + 2) + · · ·. But
e x −1 S(1,1) S(2,1) 2 S(r ,1) r
1! = S(0, 1) + 1! x + 2! x + · · · + r! x + · · ·
(e x −1)2
2! = S(0, 2) + 1! x + 2! x + · · · + S(rr !,2) x r + · · ·
S(1,1) S(2,2) 2

..
.
x r
(e −1) S(1,r ) S(2,r ) 2 S(r ,r ) r
r! = S(0, r ) + 1! x + 2! x + · · · + r ! x + ···
(e x −1)r +1
(r +1)! = S(0, r + 1) + S(1,r1!+1) x + S(2,r2!+1) x 2 + · · · + S(r ,r +1) r
r! x + ···
..
.

George Voutsadakis (LSSU) Combinatorics April 2016 44 / 71

 Generating Functions Distributions of Distinct Objects Into NonDistinct Cells

Exponential Enumerator for r ≤ n (Cont’d)

Therefore, the expression

S(r , 1) + S(r , 2) + · · · + S(r , r ) + S(r , r + 1) + S(r , r + 2) + · · · ,

which is the number of ways of distributing r distinct objects into r or

r
more nondistinct cells, is the coefficient of xr ! , in

e x − 1 (e x − 1)2 (e x − 1)r (e x − 1)r +1

+ + ··· + + + ··· .
1! 2! r! (r + 1)!

This generating function is

x −1
ee − 1.

George Voutsadakis (LSSU) Combinatorics April 2016 45 / 71

 Generating Functions Partitions of Integers

Subsection 5

Partitions of Integers

George Voutsadakis (LSSU) Combinatorics April 2016 46 / 71

 Generating Functions Partitions of Integers

Nondistinct Objects Into Nondistinct Cells and Partitions

A partition of an integer is a division of the integer into positive

integral parts, in which the order of these parts is not important.
Example: The five different partitions of the integer 4 are

4, 3 + 1, 2 + 2, 2 + 1 + 1, 1 + 1 + 1 + 1.

A partition of the integer n is equivalent to a way of distributing n

nondistinct objects into n nondistinct cells with empty cells allowed.
We discuss these distributions in the context of the partitions of
integers because this is also an important topic in number theory.

George Voutsadakis (LSSU) Combinatorics April 2016 47 / 71

 Generating Functions Partitions of Integers

Number of Ways to Pick 1’s, 2’s, etc.

In the polynomial 1 + x + x 2 + x 3 + · · · + x n the coefficient of x k is

the number of ways of having k 1’s in a partition of the integer n:
In a partition of n there can be from no 1’s to at most n 1’s.
There is one way of having k 1’s, for 0 ≤ k ≤ n;
There is no way of having k 1’s, for k > n.
1
Hence, in the infinite sum 1 + x + x 2 + x 3 + · · · + x r + · · · = 1−x , the
k
coefficient of x is the number of ways of having k 1’s in a partition
of any integer larger than or equal to k.
Similarly, in the polynomial 1 + x 2 + x 4 + · · · + x ⌊x/2⌋ the coefficient
of x 2k is the number of ways of having k 2’s in a partition of the
integer n.
1
Also, in the infinite sum 1 + x 2 + x 4 + x 6 + · · · + x 2r + · · · = 1−x 2 the
2k
coefficient of x is the number of ways of having k 2’s in a partition
of any integer larger than or equal to 2k.
George Voutsadakis (LSSU) Combinatorics April 2016 48 / 71
 Generating Functions Partitions of Integers

Partition Enumerators

We conclude that the ordinary generating function of the sequence

(p(0), p(1), . . . , p(n)), where p(i ) denotes the number of partitions of
the integer i , is

F (x) = (1 + x + x 2 + x 3 + · · · + x r + · · · )
(1 + x 2 + x 4 + x 6 + · · · + x 2r + · · · )
(1 + x 3 + x 6 + x 9 + · · · + x 3r + · · · )
(1 + x 4 + x 8 + x 12 + · · · + x 4r + · · · )
· · · (1 + x n + x 2n + x 3n + · · · + x nr + · · · )
1
= .
(1 − x)(1 − x )(1 − x 3 )(1 − x 4 ) · · · (1 − x n )
2

F (x) does not enumerate the p(j)’s for j > n. It only enumerates the
number of partitions of the integer j that have no part exceeding n.

George Voutsadakis (LSSU) Combinatorics April 2016 49 / 71

 Generating Functions Partitions of Integers

Examples
From (1−x)(1−x1 2 )(1−x 3 ) = 1 + x + 2x 2 + 3x 3 + 4x 4 + 5x 5 + 7x 6 + · · ·,
we get:
There are three ways to partition the integer 3.
There are seven ways to partition the integer 6, such that the parts do
not exceed 3.
The ordinary generating function of the infinite sequence
(p(0), p(1), p(2), . . . , p(n), . . .) is
1
F (x) = .
(1 − x)(1 − x 2 )(1 − x 3 ) · · ·
1
In (1−x)(1−x 3 )(1−x 5 )···(1−x 2n+1 )
:
the coefficient of x k for k ≤ 2n + 1 is the number of partitions of the
integer k into odd parts;
the coefficient of x k for k > 2n + 1 is the number of partitions of the
integer k into odd parts not exceeding 2n + 1.
George Voutsadakis (LSSU) Combinatorics April 2016 50 / 71
 Generating Functions Partitions of Integers

More Examples

In (1−x)(1−x13 )(1−x 5 )··· the coefficient of x k is the number of partitions

of the integer k into odd parts.
1
In (1−x 2 )(1−x 4 )(1−x 6 )···(1−x 2n ) :

the coefficient of x k for k ≤ 2n is the number of partitions of the

integer k into even parts;
the coefficient of x k for k > 2n is the number of partitions of the
integer k into even parts not exceeding 2n.
In (1−x 2 )(1−x14 )(1−x 6 )··· the coefficient of x k is the number of partitions
of the integer k into even parts.
The polynomial (1 + x)(1 + x 2 )(1 + x 3 ) · · · (1 + x n ) enumerates:
the partitions of integers ≤ n into distinct (unequal) parts;
the partitions of integers > n into distinct parts not exceeding n.
(1 + x)(1 + x 2 )(1 + x 3 ) · · · (1 + x n ) · · · enumerates the partitions of
the integers into distinct parts.
George Voutsadakis (LSSU) Combinatorics April 2016 51 / 71
 Generating Functions Partitions of Integers

Example
Note that
(1 + x)(1 + x 2 )(1 + x 3 )(1 + x 4 ) · · · (1 + x r ) · · ·
1 − x2 1 − x4 1 − x6 1 − x 2r
= · · · · · ···
1 − x 1 − x2 1 − x3 1 − xr
1
= .
(1 − x)(1 − x 3 )(1 − x 5 ) · · ·
So, the number of partitions of an integer into distinct parts is equal
to the number of partitions of the integer into odd parts.
Example The integer 6 can be partitioned into distinct parts in four
different ways:
6, 5 + 1, 4 + 2, 3 + 2 + 1.
There are also exactly four different ways in which 6 can be
partitioned into odd parts:
5 + 1, 3 + 3, 3 + 1 + 1 + 1, 1 + 1 + 1 + 1 + 1 + 1.

George Voutsadakis (LSSU) Combinatorics April 2016 52 / 71

 Generating Functions Partitions of Integers

Example
Note that
r
(1 − x)(1 + x)(1 + x 2 )(1 + x 4 )(1 + x 8 ) · · · (1 + x 2 ) · · ·
r
= (1 − x 2 )(1 + x 2 )(1 + x 4 )(1 + x 8 ) · · · (1 + x 2 ) · · ·
r
= (1 − x 4 )(1 + x 4 )(1 + x 8 ) · · · (1 + x 2 ) · · ·
= · · · = 1.
So, we have the identity
1 r
= (1 + x)(1 + x 2 )(1 + x 4 )(1 + x 8 ) · · · (1 + x 2 ) · · · .
1−x
1
Recalling that 1−x = 1 + x + x 2 + x 3 + x 4 + · · ·, we conclude that
any integer can be expressed as the sum of a selection of the integers
1, 2, 4, 8, . . . , 2r , . . . (without repetition) in exactly one way.
This is the well-known fact that a decimal number can be represented
uniquely as a binary number.
George Voutsadakis (LSSU) Combinatorics April 2016 53 / 71
 Generating Functions Partitions of Integers

Example

Note that
1
1−x = (1+x)(1+x 2 )(1+x 4 )(1+x 8 )···(1+x 2r )···
= (1 − x + x 2 − x 3 + x 4 − · · · )
(1 − x 2 + x 4 − x 6 + x 8 − · · · )
(1 − x 4 + x 8 − x 12 + x 16 − · · · ) · · ·
r r r r
(1 − x 2 + x 2·2 − x 3·2 + x 4·2 − · · · )...

Thus, to partition any integer n larger than 1 into parts that are
powers of 2, namely, 1, 2, 4, 8, . . . , 2r , . . ., the number of partitions
that have an even number of parts is equal to the number of
partitions that have an odd number of parts.
The series 1 − x + x 2 − x 3 + x 4 − · · · enumerates the number of 1’s in
a partition, with terms corresponding to an even number of 1’s in the
partition having +1 as the coefficients and terms corresponding to an
odd number of 1’s in the partition having −1 as the coefficients.
George Voutsadakis (LSSU) Combinatorics April 2016 54 / 71
 Generating Functions Partitions of Integers

Example (Cont’d)

The series 1 − x 2 + x 4 − x 6 + x 8 − · · · enumerates the number of 2’s in

a partition, with terms corresponding to an even number of 2’s having
positive coefficients and terms corresponding to an odd number of
2’shaving negative coefficients.
The series 1 − x 4 + x 8 − x 12 + x 16 − · · · enumerates the number of 4’s
in a partition, with terms corresponding to an even number of 4’s
having positive coefficients and terms corresponding to an odd number
of 4’s having negative coefficients.
Therefore, in the expansion of the product
(1 − x + x 2 − x 3 + x 4 − · · · )(1 − x 2 + x 4 − x 6 + x 8 − · · · )(1 − x 4 +
r r r r
x 8 − x 12 + x 16 − · · · ) · · · (1 − x 2 + x 2·2 − x 3·2 + x 4·2 − · · · ) · · · a
term +x n corresponds to a partition of the integer n into an even
number of parts, and a term −x n corresponds to a partition of the
integer n into an odd number of parts.

George Voutsadakis (LSSU) Combinatorics April 2016 55 / 71

 Generating Functions Partitions of Integers

Example (Illustrated)

Example: The four partitions of the integer 5 into parts that are
powers of 2 are

4 + 1, 2 + 1 + 1 + 1, 2 + 2 + 1, 1 + 1 + 1 + 1 + 1.

Two (4 + 1 and 2 + 1 + 1 + 1) have an even number of parts.

The other two have an odd number of parts.

George Voutsadakis (LSSU) Combinatorics April 2016 56 / 71

 Generating Functions The Ferrers Graph

Subsection 6

The Ferrers Graph

George Voutsadakis (LSSU) Combinatorics April 2016 57 / 71

 Generating Functions The Ferrers Graph

Ferrers Graphs

A Ferrers graph consists of rows of dots.

The dots are arranged in such a way that an upper row has at least as
many dots as a lower row.
A partition of an integer can be represented by a Ferrers graph by
making each row in the graph correspond to a part in the partition,
with the number of dots in a row specifying the value of the
corresponding part.
Example: The partition of the integer 14 into 6 + 3 + 3 + 2 is
represented by
• • • • • •
• • •
• • •
• •

George Voutsadakis (LSSU) Combinatorics April 2016 58 / 71

 Generating Functions The Ferrers Graph

Relating Various Kinds of Partitions

Claim: The number of partitions of an integer into exactly m parts is
equal to the number of partitions of the integer into parts, the largest
of which is m.
Note that the transposition of a Ferrers graph (the leftmost column
becomes the uppermost row and so on) is also a Ferrers graph.
It follows that the transposition of the Ferrers graph of a partition
having exactly m parts becomes the Ferrers graph of a partition
having m as the largest part.
Example: Integer 6 has exactly two partitions that have exactly four
parts each 2 + 2 + 1 + 1 and 3 + 1 + 1 + 1. There are also two
partitions that have 4 as their largest part: 4 + 2 and 4 + 1 + 1.
• • • • • • • • • • • • •
• • • • • •
• • •
• •
George Voutsadakis (LSSU) Combinatorics April 2016 59 / 71
 Generating Functions The Ferrers Graph

Connection with Ordinary Enumerators

The number of partitions of an integer into at most m parts is equal
to the number of partitions of the integer into parts not exceeding m.
Therefore, the ordinary generating function of the numbers of
partitions of integers into at most m parts is also
1
.
(1 − x)(1 − x 2 ) · · · (1 − x m )
The ordinary generating function of the numbers of partitions of
integers into at most m − 1 parts is
1
.
(1 − x)(1 − x 2 ) · · · (1 − x m−1 )
Thus, the ordinary generating function of the numbers of partitions of
integers into exactly m parts is
1 m
(1−x)(1−x 2 )···(1−x m )
− (1−x)(1−x 21)···(1−x m−1 ) = (1−x)(1−xx 2 )···(1−x m ) .
George Voutsadakis (LSSU) Combinatorics April 2016 60 / 71
 Generating Functions The Ferrers Graph

Partitions into Exactly m Unequal Parts

Find the partitions of 8 into exactly 3 unequal parts.
Consider the partitions of 8 − 3(3−1)
2 = 5 into 3 (not necessarily
unequal) parts.
• • • • •
• • •
• •
Now do the following:
Add 2 bullets in the first row;
Add 1 bullet in the second row;
Add no bullets in the last row.
We get
• • • • • • • • •
• • • • •
• •
These are the partitions of 8 into 3 unequal parts!
George Voutsadakis (LSSU) Combinatorics April 2016 61 / 71
 Generating Functions The Ferrers Graph

Generating Partitions into Exactly m Unequal Parts

Find the ordinary generating function of the numbers of partitions of

integers into exactly m unequal parts.
Consider the Ferrers graph of an m-part partition of the integer
n − m(m−1)
2 . Add
m − 1 dots to the first row;
m − 2 dots to the second row;
..
.
one dot to the (m − 1)-st row.
We get the Ferrers graph of a partition of the integer n into m
unequal parts.
This gives a one-to-one correspondence between the m-part partitions
of the integer n − m(m−1)
2 and the partitions of the integer n into m
unequal parts.

George Voutsadakis (LSSU) Combinatorics April 2016 62 / 71

 Generating Functions The Ferrers Graph

Generating Partitions into m Unequal Parts (Cont’d)

The number of partitions of the integer n into exactly m unequal

parts equals the number of partitions of the integer n − m(m−1)
2 into
exactly m parts.
Therefore, the ordinary generating function of the numbers of the
partitions of integers into m distinct parts is
xm
x m(m−1)/2
(1 − x)(1 − x 2 ) · · · (1 − x m )
x m(m+1)/2
= .
(1 − x)(1 − x 2 ) · · · (1 − x m )

George Voutsadakis (LSSU) Combinatorics April 2016 63 / 71

 Generating Functions Elementary Relations

Subsection 7

Elementary Relations

George Voutsadakis (LSSU) Combinatorics April 2016 64 / 71

 Generating Functions Elementary Relations

Sum and Product of Generating Functions

Let A(x), B(x) and C (x) be the ordinary generating functions of the
sequences (a0 , a1 , . . . , ar , . . .), (b0 , b1 , . . . , br , . . .) and
(c0 , c1 , . . . , cr , . . .), respectively.
By definition,
C (x) = A(x) + B(x)
if and only if the members of the sequences are related as follows:
c0 = a0 + b0 , c1 = a1 + b1 , . . . , cr = ar + br , . . . .

Similarly, by definition,
C (x) = A(x) × B(x)
if and only if the members of the sequences are related as follows:
c0 = a0 b0 , c1 = a1 b0 + a0 b1 , . . . ,
cr = ar b0 + ar −1 b1 + ar −2 b2 + · · · + a1 br −1 a0 br , . . . .

George Voutsadakis (LSSU) Combinatorics April 2016 65 / 71

 Generating Functions Elementary Relations

The Summing Operator

Let A(x) be the ordinary generating function of the sequence

1
(a0 , a1 , a2 , . . . , ar , . . .). Since 1−x is the ordinary generating function
1
of the sequence (1, 1, 1, . . . , 1, . . .), 1−x A(x) is the ordinary
generating function of the sequence

(a0 , a0 + a1 , a0 + a1 + a2 , . . . , a0 + a1 + a2 + · · · + ar , . . .).
1
1−x is, therefore, called the summing operator.
Example: Find the coefficient of the term x 37 in

1 − 3x 2 + 4x 7 + 12x 21 − 5x 45
.
1−x
We have as the answer 1 − 3 + 4 + 12 = 14.

George Voutsadakis (LSSU) Combinatorics April 2016 66 / 71

 Generating Functions Elementary Relations

The Generating Function of the Squares

Evaluate the sum 12 + 22 + 32 + · · · + r 2 .

We first find the ordinary generating function of the sequence
(02 , 12 , 22 , 32 , . . . , r 2 , . . .).
We have in sequence:
1 2 3 4 r
1−x = 1 + x + x + x + z + · · · + x + · · · .
d 1 1 2 3 r −1
dx 1−x = (1−x)2 = 1 + 2x + 3x + 4x + · · · + rx + ··· .
x 2 3 4 r
(1−x)2 = x + 2x + 3x + 4x + · · · + rx + · · · .
d x 1+x 2 2 2 2 2 3 2 r −1
dx (1−x)2 = (1−x)3 = 1 + 2 x + 3 x + 4 x + · · · + r x + ··· .
1+x 2 2 2 2 3 2 4 2 r
x (1−x) 3 = 1 x + 2 x + 3 x + 4 x + ··· + r x + ··· .

Therefore, the ordinary generating function of the sequence

x(1 + x)
(02 , 12 , 22 , 32 , . . . , r 2 , . . .) is .
(1 − x)3

George Voutsadakis (LSSU) Combinatorics April 2016 67 / 71

 Generating Functions Elementary Relations

Summing the Squares

We found that x dx d x
(x−1)2
= x(1+x)
(1−x)3
is the ordinary generating function
of the sequence (0 , 1 , 2 , 3 , . . . , r 2 , . . .).
2 2 2 2

Thus, the ordinary generating function of the sequence

(02 , 02 + 12 , 02 + 12 + 22 , . . . , 02 + 12 + 22 + 32 + · · · + r 2 , · · · ) is
x(1+x)
(1−x)4
.
1
By the binomial theorem, the coefficient of x r in (1−x)4
is
(−4)(−4−1)(−4−2)···(−4−r +1) 4·5·6···(r +3) (r +1)(r +2)(r +3)
r! (−1)r = r! = 1·2·3 .
x(1+x)
Therefore, the coefficient of x r in the expansion of (1−x)4
is
r (r +1)(r +2) (r −1)r (r +1) r (r +1)(2r +1)
+
1·2·3 1·2·3 = 6 .
We conclude
r (r + 1)(2r + 1)
12 + 22 + 32 + · · · + r 2 + · · · = .
6

George Voutsadakis (LSSU) Combinatorics April 2016 68 / 71

 Generating Functions Elementary Relations

Operations on Exponential Generating Functions

Let A(x), B(x) and C (x) be the exponential generating functions of
the sequences (a0 , a1 , . . . , ar , . . .), (b0 , b1 , . . . , br , . . .) and
(c0 , c1 , . . . , cr , . . .), respectively.
By definition,
C (x) = A(x) + B(x)
if and only if the members of the sequences are related as follows:

c0 = a0 + b0 , c1 = a1 + b1 , . . . , cr = ar + br , . . . .

By definition,
C (x) = A(x) × B(x)
if and only if the members of the sequences are related as follows:

c0 = a0 b0 , c1 = a1 b0 + a0 b1 , c2 = 2!( a02!b0 + a1!1! 1 b1

+ a02!b2 ), . . . ,
a b r r
cr = r ![ arrb! 0 + (r −1)!1! + · · · + a0r b! r ] = i =0 i ar −i bi , . . .
r −1 1
P

George Voutsadakis (LSSU) Combinatorics April 2016 69 / 71

 Generating Functions Elementary Relations

Example
Pr r!
Evaluate the sum i =0 (r −i +1)!(i +1)! .
Note
P that
r r! Pr r! 1 1 Pr r
1 1
i =0 (r −i +1)!(i +1)! = i =0 (r −i )!i ! r −i +1 i +1 = i =0 i r −i +1 i +1 .
We also have
1 1 2 1 r
ex = 1+ 1! x + 2! x + ··· + r! x + · · ·
1 x 1 1 2 1 r −1
x (e − 1) = 1+ 2! x + 3! x + ··· + r! x + ···

Thus, the exponential generating function of (1, 12 , 13 , · · · , 1r , · · · ) is

1 x
x (e − 1). We conclude that the exponential generating function of
the sequence
1·1, 12 ·1+1· 12 , 20 · 13 ·1+ 21 · 12 · 12 + 22 ·1· 13 , · · · , ri=0 ri r −i1+1 i +1
1



P

,···
is
1 x
(e − 1)2 .
x2

George Voutsadakis (LSSU) Combinatorics April 2016 70 / 71

 Generating Functions Elementary Relations

Example (Cont’d)

Note that
1 1
x2
(e x − 1)2 = x2
(e 2x − 2e x + 1)
1 (2x) (2x)2 x x2
= x2
((1 + 1! + 2! + · · · ) − 2(1 + 1! + 2! + · · · ) + 1)
(22 −2) (23 −2)
= 1
x2
(((1 − 2) + (2x−2x)
1! + 2! x2 + 3! x 3 + · · · ) + 1)
2 3 4
= ( 22! − 2!
2
) + ( 23! − 3!
2
)x + ( 24! − 2
4! )x
3 + ···
r+2
+ ( (r2+2)! − 2
(r +2)! )x
r + ··· .

Thus, we obtain that

r
2r +2 2(2r +1 − 1)
 
X r! 2
= r! − = .
(r − i + 1)(i + 1)! (r + 2)! (r + 2)! (r + 2)(r + 1)
i =0

George Voutsadakis (LSSU) Combinatorics April 2016 71 / 71