Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and
Architecture-AIT
Advance Counting Techniques,
Introduction

Combination with
repetitions
Recursion
Ordered and
Unordered
Partitions
Belarmino, Kimberly Ann
Inclusions-
Exclusions
Principle Revisited
Manlongat, Kim Aebrahm
Pigeonhole
Olido, Jake
Principle Revisited
Palaganas, Lester John
Recurrence
Relations

Linera Recurrence
Department of Electronics Engineering
with constant
Coefficients

Solving Second
October 2,2018
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics
1 Introduction
College of
Engineering and
Architecture-AIT 2 Combination with repetitions
Introduction
3 Ordered and Unordered Partitions
Combination with
repetitions

Ordered and
4 Inclusions-Exclusions Principle Revisited
Unordered
Partitions
5 Pigeonhole Principle Revisited
Inclusions-
Exclusions
Principle Revisited 6 Recurrence Relations
Pigeonhole
Principle Revisited 7 Linera Recurrence with constant Coefficients
Recurrence
Relations 8 Solving Second Order Homogeneous Linear Recurrence
Linera Recurrence
with constant
Relations
Coefficients
9 Solving General Homogeneous Linear Recurrence
Solving Second
Order Relations
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and
Architecture-AIT

Introduction
1.1 INTRODUCTION
Combination with
repetitions Here we consider more sophisticated counting techniques
Ordered and
Unordered
and problems. This includes problems involving
Partitions combinations with repetition, ordered and unordered
Inclusions-
Exclusions partitions, and the Inclusion–Exclusion Principle and the
Principle Revisited
Pigeonhole Principle.
Pigeonhole
Principle Revisited We also discuss recursion in this chapter.
Recurrence
Relations

Linera Recurrence
with constant
Coefficients

Solving Second
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and 1.2 COMBINATION WITH REPETITIONS
Architecture-AIT
A combination with repetition of r objects from M is a
Introduction way of selecting r objects from a list of M. The selection
Combination with
repetitions rules are:
Ordered and 1 The order of selection does not matter (the same
Unordered
Partitions objects selected in different orders are regarded as
Inclusions-
Exclusions the same combination);
Principle Revisited
2 Each object can be selected more than once.
Pigeonhole
Principle Revisited
Thus, the difference between simple combinations and
Recurrence
Relations combinations with repetition is that objects can be
Linera Recurrence
with constant
selected only once in the former, while they can be
Coefficients
selected more than once in the latter.
Solving Second
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and
1.3 ORDERED AND UNORDERED PARTITIONS
Architecture-AIT An ordered partition of n objects into k distinct group of
Introduction sizes n1 , n2 , ...nr is any division of the n objects of the
Combination with combination of n1 objects into first group, n2 objects into
repetitions

Ordered and
second group,etc.
Unordered
Partitions
This number denoted by:
Inclusions-  
Exclusions
Principle Revisited
n
Pigeonhole
n1 , n2 , ...nr
Principle Revisited

Recurrence Let n1 , n2 , ..., nr = n be non negative integers where

Relations
n1 + n2 + ... + nr = n
Linera Recurrence
with constant The number of possible order partitions of n objects into
Coefficients

Solving Second
r distinct groups of sizes n1 , n2 , ..., nr
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and
Architecture-AIT

Introduction
Theorem
Combination with
repetitions The number m of ordered partitions of a set S with n
Ordered and
Unordered elements into r cells [A1, A2, ..., Ar ] where, for each
Partitions
i, n(Ai) = ni, follows:
Inclusions-
Exclusions
Principle Revisited n!
Pigeonhole m=
Principle Revisited n1 !n2 !...nr !
Recurrence
Relations

Linera Recurrence
with constant
Coefficients

Solving Second
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and
Architecture-AIT

Introduction
Unordered Partitions
Combination with
repetitions Frequently, we want to partition a set S into cells
Ordered and
Unordered
[A1 , A2 , ..., Ar ] where the cells are now unordered. The
Partitions
number m of such unordered partitions is obtained from
Inclusions-
Exclusions the number m0 of ordered partitions by dividing m0 by
Principle Revisited
each k! where k of the cells have the same number of
Pigeonhole
Principle Revisited elements.
Recurrence
Relations

Linera Recurrence
with constant
Coefficients

Solving Second
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics
1.4 INCLUSION–EXCLUSION PRINCIPLE
College of
Engineering and REVISITED
Architecture-AIT
Let A1 , A2 , ..., Ar be subsets of a universal set U.
Introduction
Suppose we let sk denote the sum of the cardinalities of
Combination with
repetitions all possible k-tuple intersections of the sets, that is, the
Ordered and
Unordered
sum of all of the cardinalities
Partitions

Inclusions-
Exclusions n(Ai1 ∩ Ai2 ∩ ... ∩ Aik )
Principle Revisited

Pigeonhole X X
Principle Revisited
S1 = n(Ai ), S2 = n(Ai ∩ Aj )
Recurrence
Relations i i<j
Linera Recurrence X
with constant
Coefficients S3 = n(Ai1 ∩ Ai2 ∩ Ai3 )
Solving Second i1 <i2 <i3
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics
The Inclusion–Exclusion Principle, which appears in
College of
Engineering and Section 5.7, gave a formula for the number of elements
Architecture-AIT
in the union of the sets. Specifically, (Theorem 5.9) we
Introduction
have
Combination with
repetitions

Ordered and
Unordered
Partitions n(A1 ∪ A1 ∪ ... ∪ Ar ) = s1 − s2 + s3 − ... + (−1)r −1 sr
Inclusions-
Exclusions
Principle Revisited On the other hand, using DeMorgan’s law,
Pigeonhole
Principle Revisited

Recurrence
Relations n(AC1 ∩ AC2 ∩ ... ∩ ACr ) = n([A1 ∪ A2 ∪ ... ∪ Ar ]C )
Linera Recurrence
with constant
Coefficients

Solving Second
Order
=| U | −n(A1 ∪ A2 ∪ ... ∪ Ar )
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and
Architecture-AIT

Introduction
Theorem (Inclusions-Exclusions Principle Revisited)
Combination with
repetitions
Let A1 , A2 , . . . , Ar be subsets of a universal set U.
Ordered and
Unordered Then the number m of elements which do not appear in
Partitions
any of the subsets A1 , A2 , ..., Ar of U is:
Inclusions-
Exclusions
Principle Revisited

Pigeonhole
Principle Revisited m = n(AC1 ∩AC2 ∩...∩ACr ) =| U | −s1 +s2 −s3 +...+(−1)r s r
Recurrence
Relations

Linera Recurrence
with constant
Coefficients

Solving Second
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and
Architecture-AIT

Introduction Number of Onto Functions

Combination with
repetitions
An onto or a surjective function is a function in which
Ordered and
each and every element of the range is related to at least
Unordered
Partitions
one element in the domain, i.e. every output must be
Inclusions- originated from at least one input. In onto function,
Exclusions
Principle Revisited there cannot be any range element left out without
Pigeonhole mapping. In other words, it is a function that has its
Principle Revisited

Recurrence
image equal to its range.
Relations

Linera Recurrence
with constant
Coefficients

Solving Second
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and
Architecture-AIT

Introduction

Combination with
repetitions

Ordered and
PROBLEM Let A and B be sets such that | A |= 6 and
Unordered
Partitions
| B | = [Link] want to find the number of surjective
Inclusions- (onto) functions from A onto B.
Exclusions
Principle Revisited

Pigeonhole
Principle Revisited

Recurrence
Relations

Linera Recurrence
with constant
Coefficients

Solving Second
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and
Architecture-AIT
Theorem
Introduction
Suppose | A |= m and | B |= n where m ≥ n. Then the
Combination with
repetitions number N of surjective (onto) functions from A onto B
Ordered and
Unordered
is:
Partitions

Inclusions-
Exclusions
Principle Revisited N = nm − C (n, 1)(n − 1)m + C (n, 2)(n − 2)m − ...
Pigeonhole
Principle Revisited

Recurrence
Relations
+(−1)n−1 C (n, n − 1)1m
Linera Recurrence
with constant
Coefficients

Solving Second
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and
Architecture-AIT

Introduction

Combination with Derangements

repetitions
A derangement is a permutation of objects where each
Ordered and
Unordered object is not in its original position. For example, 453162
Partitions

Inclusions-
is not a derangement of 123456 since 3 is in its correct
Exclusions
Principle Revisited
position, but 264531 is a derangement of 123456.
Pigeonhole Let Dn denote the number of derangements of n objects.
Principle Revisited

Recurrence
Relations

Linera Recurrence
with constant
Coefficients

Solving Second
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and
Theorem
Architecture-AIT
1 1 1 1
Dn = n![1 −+ − + ... + (−1)n ]
Introduction 1! 2! 3! n!
Combination with
repetitions The probability that a derangement of n objects occurs
Ordered and equals Dn divided by n!, the number of permutations of
Unordered
Partitions the n objects. Thus Theorem yields:
Inclusions-
Exclusions
Principle Revisited
Corollary
Pigeonhole
Principle Revisited Let p be the probability of a derangement of n objects.
Recurrence
Relations
Then
Linera Recurrence
with constant 1 1 1 1
Coefficients p =1− + − + ... + (−1)n
Solving Second
1! 2! 3! n!
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of 1.5 PIGEONHOLE PRINCIPLE REVISITED

Engineering and
Architecture-AIT Consider a flock of pigeons nestled in a set of n
Introduction pigeonholes. If there are n pigeons, then it is possible for
Combination with all of the pigeons to rest happily in separate pigeonholes.
repetitions

Ordered and
However, if at least one more pigeon arrives, making a
Unordered
Partitions
total of more than n pigeons, then at least one of the
Inclusions- pigeonholes, inevitably, will end up with more than one
Exclusions
Principle Revisited pigeon.
Pigeonhole
Principle Revisited Theorem
Recurrence
Relations Every sequence of distinct n2 + 1 real numbers contains a
Linera Recurrence subsequence of length n + 1 which is strictly increasing
with constant
Coefficients or strictly decreasing.
Solving Second
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and 1.6 RECURRENCE RELATIONS
Architecture-AIT
Previously, we discussed recursively defined functions
Introduction
such as:
Combination with
repetitions

Ordered and (a) Factorial (b) Fibonacci (c) Ackermann

Unordered
Partitions function, sequence, function.
Inclusions-
Exclusions
Principle Revisited Here we discuss certain kinds of recursively defined
Pigeonhole sequences {an } and their solution. We note that a
Principle Revisited

Recurrence
sequence is simply a function whose domain is:
Relations

Linera Recurrence
with constant N = {1, 2, 3, ...}orN0 = N ∪ {0} = {0, 1, 2, 3}
Coefficients

Solving Second
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete 1.7 LINEAR RECURRENCE RELATIONS WITH

Mathematics
CONSTANT COEFFICIENTS
College of
Engineering and
Architecture-AIT
A recurrence relation of order k is a function of the form
Introduction

Combination with
an = Φ(an−1 , an−2 , ...an−k , n)
repetitions

Ordered and
Unordered
that is, where the nth term an of a sequence is a function
Partitions of the preceding k terms an−1 , an−2 , ..., an−k (and possibly
Inclusions-
Exclusions
n). In particular, a linear kth-order recurrence relation
Principle Revisited
with constant coefficients is a recurrence relation of the
Pigeonhole
Principle Revisited form
Recurrence
Relations

Linera Recurrence an = C1 an−1 + C2 an−2 + ... + Ck an−k + f (n)

with constant
Coefficients

Solving Second where C1 , C2 , ..., Ck are constants with Ck 6= 0, and f (n)

Order
Homogeneous is a function of n. The meanings of the names linear and
Linear Recurrence
Relations constant coefficients follow:
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and
Architecture-AIT
Linear : There are no powers or products of the aj0 s.
Introduction Constant coefficients: The C1 C2 , ..., Ck are constants (do
Combination with
repetitions not depend on n).
Ordered and If f (n) = 0, then the relation is also said to be
Unordered
Partitions homogeneous.
Inclusions-
Exclusions
Clearly, we can uniquely solve for an if we know the
Principle Revisited values of an−1 , an−2 , ..., an−k . Accordingly, by
Pigeonhole
Principle Revisited
mathematical induction, there is a unique sequence
Recurrence satisfying the recurrence relation if we are giveninitial
Relations
values for the first k elements of the sequence.
Linera Recurrence
with constant
Coefficients

Solving Second
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics 1.8 SOLVING SECOND-ORDER
College of HOMOGENEOUS LINEAR RECURRENCE
Engineering and
Architecture-AIT RELATIONS
Introduction
Consider a homogeneous second-order recurrence relation
Combination with with constant coefficients which has the form
repetitions

Ordered and
Unordered
Partitions
an = san−1 + tan−2 oran − san−1 − tan−2 = 0
Inclusions-
Exclusions
where s and t are constants with t 6= [Link] associate the
Principle Revisited following quadratic polynomial with the above recurrence
Pigeonhole
Principle Revisited relation:
Recurrence
Relations

Linera Recurrence
∆(x) = x 2 − sx − t
with constant
Coefficients This polynomial ∆(x) is called the characteristic
Solving Second
Order
polynomial of the recurrence relation, and the roots of
Homogeneous
Linear Recurrence
∆(x) are called its characteristic roots.
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics Theorem
College of
Engineering and Suppose the characteristic polynomial
Architecture-AIT
∆(x) = x 2 − sx − t of the recurrence relation
Introduction

Combination with
repetitions an = san−1 + tan−2
Ordered and
Unordered has distinct roots r1 and r2 . Then the general solution of
Partitions

Inclusions-
the recurrence relation follows, where c1 and c2 are
Exclusions
Principle Revisited
arbitrary constants:
Pigeonhole
Principle Revisited
an = c1 r1n + c2 r2n
Recurrence
Relations
We emphasize that the constants c1 and c2 may be
Linera Recurrence
with constant
Coefficients
uniquely computed using initial [Link] note that
Solving Second
the theorem is true even when the roots are not real.
Order
Homogeneous
Such cases lie beyond the scope of this text.
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics Solution when Roots of the Characteristic
College of
Engineering and
Polynomial are Equal
Architecture-AIT Suppose the roots of the characteristic polynomial are
Introduction not distinct. Then we have the following result.
Combination with
repetitions Theorem
Ordered and
Unordered Suppose the characteristic polynomial
Partitions
∆(x) = x 2 − sx − t of the recurrence relation
Inclusions-
Exclusions an = san−1 + tan−2 has only one root r0 . Then the
Principle Revisited

Pigeonhole
general solution of the recurrence relation follows, where
Principle Revisited c1 and c2 are arbitrary constants:
Recurrence
Relations

Linera Recurrence an = c1 r0n + c2 r0n

with constant
Coefficients
The constants c1 and c2 may be uniquely computed
Solving Second
Order using initial conditions.
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete 1.9 SOLVING GENERAL HOMOGENEOUS

Mathematics

College of
LINEAR RECURRENCE RELATIONS
Engineering and
Architecture-AIT
an = C1 an−1 + C2 an−2 + C3 an−3 + ... + Ck an−k
Introduction

Combination with
repetitions k
X
Ordered and
Unordered
= Ci an−1
Partitions i=1
Inclusions-
Exclusions where C1 ,C2 , ..., Ck are constants with Ck 6= 0. The
Principle Revisited
characteristic polynomial ∆(x) of the recurrence relation
Pigeonhole
Principle Revisited

Recurrence
Relations ∆(x) = x k − C1 x k−1 − C2 x k−2 − C3 x k−3 − ... − Ck = x k
Linera Recurrence
with constant
Coefficients
k
X
Solving Second
Order = Ci x k−1
Homogeneous
Linear Recurrence i=1
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and
Architecture-AIT
The roots of Delta(x) are called the characteristic roots
of the recurrence relation.
Introduction

Combination with
The following remarks are in order.
repetitions

Ordered and
Remark
Unordered
Partitions If p(n) and q(n) are solutions of (6.1), then any linear
Inclusions-
Exclusions
combination
Principle Revisited

Pigeonhole
Principle Revisited
c1 p(n) + c2 q(n)
Recurrence
Relations of p(n) and q(n) is also a solution. (This is not true if
Linera Recurrence the recurrence relation is nonhomogeneous.)
with constant
Coefficients

Solving Second
Order
Homogeneous
Linear Recurrence
Relations
 Introduction Combination with repetitions Ordered and Unordered Partitions Inclusions-Exclusions Principle Revisited Pigeonhole

Discrete
Mathematics

College of
Engineering and
Architecture-AIT Remark
Introduction If r is a root of multiplicity m of the characteristic
Combination with polynomial ∆(x) of (6.1), then each of the following:
repetitions

Ordered and
Unordered
Partitions
r n , nr n , n2 r n , ..., nn−1 r n
Inclusions-
Exclusions
is a solution of (6.1). Thus any linear combination
Principle Revisited

Pigeonhole
Principle Revisited c1 r n + c2 nr n + c3 n2 r n + cm nm−1 r n
Recurrence
Relations

Linera Recurrence
with constant
= (c1 + c2 n + c3 n2 + ... + cm nm−1 )r n
Coefficients

Solving Second
Order
Homogeneous
Linear Recurrence
Relations