UNIT - 3 COMBINOTORICS AND RECURRENCE

RELATIONS

STRUCTURE
3.0 Learning Objectives
3.1 Introduction
3.2 Basic Counting Principles
3.2.1 The Pigeonhole Principle
3.2.2 The Inclusion Exclusion Principle
3.2.3 Tree Diagrams
3.3 Mathematical Functions
3.3.1 Permutations
3.3.2 Combinations
3.3.3 Combinations with Repetitions
3.4 Recurrence Relations
3.4.1 Linear Recurrence Relations with Constant Coefficients
3.4.2 Solving General Homogeneous Linear Recurrence Relations
3.5 Summary
3.6 Learning Activity
3.7 Unit End Questions
3.8 References

39
3.0 LEARNING OBJECTIVES

After studying this unit, you will be able to:

 Apply basic counting principles such as the sum and product rules, permutations,
combinations, and the pigeonhole principle to solve counting problems.
 Explain the inclusion and exclusionary concept.
 Use the inclusion and exclusion principle to solve counting questions.
 Explain the pigeon-hole theory and use it to resolve easy counting problems.
 Explain the recurrence relation and solve problems by iteration method.
 Learn about and how to solve linear homogeneous recurrence relations.
 Familiarize yourself with the linear nonhomogeneous recurrence relation.
 Solve specific recurrence relations of the first and second orders.

3.1 INTRODUCTION

This chapter will cover how to solve counting problems using recursive strategies to derive
sequences. Recurrence relation refers to the process of iteratively determining a sequence's
terms. We research linear recurrence relation theory and its solutions.
An equation that represents a sequence based on a rule is called a recurrence relation. Finding
the following term, which is dependent upon the prior phrase, is made easier (previous term).
It is simple to predict the following term in a series if we know the preceding one. Now that a
common pattern has been established, we can locate the collection of novel phrases. This is
true for both geometric and algebraic sequences.
This chapter introduces several methods for counting the number of elements in a set or the
number of alternative outcomes of an event without actually counting them. Combinatorial
analysis is a term sometimes used to describe such intricate counting. The study of
permutations and combinations is a part of it.
Finding the number of elements in the union of two finite sets can be done using the principle
of inclusion and exclusion. When it's important to create a counting strategy that prevents an
object from being counted more than once, this is utilized to solve combinations and
probability problems.
The core ideas and methods provided in this part serve as the foundation of the majority of
counting procedures, either directly or indirectly. The most fundamental and often utilized
rules are sum, product, and quotient. The section also includes several instances of the
pigeonhole principle in practice, a brief overview of generating functions, and a number of
examples showing how to use Venn and tree diagrams.

40
 3.2 BASIC COUNTING PRINCIPLES

In many situations in mathematics, the size of a special set with a given set of qualities is of
interest. We are occasionally content to only demonstrate the existence of such a collection.
Let's look at some illustrations:

1. How many numbers are there in 2000, 2001,· · · , 5678 which are divisible by both 3
and 8?
2. If playing tic-tac-toe, is there a way for the first or second player to guarantee a draw?
3. How many distinct phone numbers can be made out of eight digits that don't begin
with nine?
4. How many different ways may 𝑛 letters be distributed among 𝑛 envelopes without a
single letter ending up in the wrong one?

These are collectively referred to as counting problems. Nearly every area of computer
science has counting problems. We will study some fundamental counting methods and
principles in this lesson.
There are two straightforward rules that are frequently employed to count.
1. Sum rule:
From two sets, the first of which contains 𝑎 elements and the other 𝑏 elements, we
must select one. It can be accomplished in methods 𝑎 + 𝑏 if the two sets are disjoint.
2. Product rule:
We must select two elements, one from each of two sets, the first of which contains 𝑎
elements and the other 𝑏 elements. The total number of possible ways is then 𝑎𝑏.
3. Quotient rule:
According to the quotient rule, there exist |𝑆| subsets when a set 𝑆 is divided into
𝑚

equal-sized subsets with 𝑚 items each.

Example 1

a. Counting Bit Strings: There are 2𝑛 bit strings of length 𝑛, since such a bit string
consists of 𝑛 bits, each of which is either 0 or 1.
b. Counting Palindrome: A palindrome is a string of symbols that is unchanged if the
symbols are written in reverse order, such as 𝑟𝑝𝑛𝑏𝑛𝑝𝑟 or 10011001. There are
𝑛
𝑘⌈2⌉palindromes of length 𝑛 where the symbols are chosen from a set of 𝑘 symbols.

41
 c. Counting restricted circular permutations: If 𝑛 women and 𝑛 men are to be seated
around a circular table, with no two of the same sex seated next to each other, the
number of possible arrangements is 𝑛(𝑛 − 1)!2.

3.2.1 The Pigeonhole Principle

The Pigeonhole Principle

If n pigeonholes are occupied by n+1 or more pigeons, then at least one pigeonhole is occupied
by greater than one pigeon. Generalized pigeonhole principle is: - If n pigeonholes are occupied
by kn+1 or more pigeons, where k is a positive integer, then at least one pigeonhole is occupied
by k+1 or more pigeons.
In mathematics, the pigeonhole principle states that if n items are put into m containers, with n
> m, then at least one container must contain more than one item. For example, if one has three
gloves (and none is ambidextrous/reversible), then there must be at least two right-handed
gloves, or at least two left-handed gloves, because there are three objects, but only two
categories of handedness to put them into. This seemingly obvious statement, a type of
counting argument, can be used to demonstrate possibly unexpected results. For example, given
that the population of London is greater than the maximum number of hairs that can be present
on a human's head, then the pigeonhole principle requires that there must be at least two people
in London who have the same number of hairs on their heads.
Although the pigeonhole principle appears as early as 1624 in a book attributed to Jean
Leurechon, it is commonly called Dirichlet's box principle or Dirichlet's drawer principle after
an 1834 treatment of the principle by Peter Gustav Lejeune Dirichlet under the name
Schubfachprinzip ("drawer principle" or "shelf principle").
The principle has several generalizations and can be stated in various ways. In a more
quantified version: for natural numbers k and m, if n = km + 1 objects are distributed among
m sets, then the pigeonhole principle asserts that at least one of the sets will contain at least k
+ 1 objects. For arbitrary n and m, this generalizes to

denote the floor and ceiling functions, respectively.

Though the most straightforward application is to finite sets (such as pigeons and boxes), it is
also used with infinite sets that cannot be put into one-to-one correspondence. To do so requires
the formal statement of the pigeonhole principle, which is "there does not exist an injective

42
function whose codomain is smaller than its domain". Advanced mathematical proofs like
Siegel's lemma build upon this more general concept.
Dirichlet published his works in both French and German, using either the German Schubfach
or the French tiroir. The strict original meaning of these terms corresponds to the English
drawer, that is, an open-topped box that can be slid in and out of the cabinet that contains it.
(Dirichlet wrote about distributing pearls among drawers.) These terms were morphed to the
word pigeonhole in the sense of a small open space in a desk, cabinet, or wall for keeping
letters or papers, metaphorically rooted in structures that house pigeons.
Because furniture with pigeonholes is commonly used for storing or sorting things into many
categories (such as letters in a post office or room keys in a hotel), the translation pigeonhole
may be a better rendering of Dirichlet's original drawer metaphor. That understanding of the
term pigeonhole, referring to some furniture features, is fading—especially among those who
do not speak English natively but as a lingua franca in the scientific world—in favour of the
more pictorial interpretation, literally involving pigeons and holes. The suggestive (though not
misleading) interpretation of "pigeonhole" as "dovecote" has lately found its way back to a
German back-translation of the "pigeonhole principle" as the "Taubenschlagprinzip".
Example1: Find the minimum number of students in a class to be sure that three of them are
born in the same month.

Fig 2.1: Pigeon Hole

Solution:
Here n = 12 months are the Pigeonholes
And k + 1 = 3

43
K=2
The pigeonhole principle states that if n items are put into m containers, with n > m, then at
least one container must contain more than one item.

Example2: Show that at least two people must have their birthday in the same month if 13
people are assembled in a room.
Solution: We assigned each person the month of the year on which he was born. Since there
are 12 months in a year.
So, according to the pigeonhole principle, there must be at least two people assigned to the
same month.

Example 3 :Pick three natural numbers. Prove that there exist a pair whose sum or difference
is divisible by 3.
Solution: Observe that a number when divided by 3 has remainder 0, 1, 2.
Identify these remainders as the pigeonholes. So there are 3 pigeonholes. Given a number it
goes to the ith pigeonhole if the reminder after dividing it by 3 is i where i = 0, 1 or 2. Since
there are 3 numbers there can be two cases.

Case(i) When each number goes to distinct box. Take the numbers in the box 1 and 2 and add
them.

Fig :2.2: Pigeon Vs Pigeonholes

Case(ii) When a box contains at least two numbers. Then take the difference of those two
numbers.

44
Definition
Formally, think of the pigeonhole principle as the statement about a function f from domain P
→ PH, where pigeon n flies into pigeonhole f(n), as is shown below:
A: More pigeonholes than pigeons |n| < |f(n)|

B: Same number of pigeons as pigeonholes |n| = |f(n)|.

C: More pigeons than pigeonholes |n| > |f(n)|.
The three cases illustrate three types of functions from a domain (“pigeons”) to a codomain
“pigeonholes” which can be mapped to one another:
Case A: If |n| < |f(n)|, then the function is an injective non-surjective function (not a
bijection).
Case B: If |n|= |f(n)|, then the function is a injective surjective function (bijection)
Case C: If |n| > |f(n)|, then the function is a non-injective surjective function (not a bijection)
Example 4:
Among any group of eight people, at least two were born on the same day of the week. This
follows since there are seven pigeonholes (the seven days of the week) and more than seven
pigeons (the eight people).
Among any group of 25 people, at least four were born on the same day of the week. This
𝑚
follows from the generalized pigeonhole principle with 𝑚 = 25 and 𝑘 = 7, yielding ⌈ ⌉ =
𝑘
25
⌈ ⌉ = 4.
7

Let's say there are a lot of black socks and a few blue socks in a dresser drawer. To be fully
confident of having a pair of socks that are the same color when choosing in complete
darkness, one must take at least three socks. The pigeonhole principle states that three socks
(the pigeons) are sufficient; the two colors are pigeonholes.

3.2.2 The Inclusion Exclusion Principle

A counting method known as the principle of inclusion and exclusion (PIE) determines the
number of elements that fulfil at least one of several qualities while ensuring that components
that satisfy several properties are not counted more than once.
The founding principle of PIE is that double counting is avoided by adding the number of
elements that satisfy at least one of two categories and taking away the overlap. For instance,
you can calculate the proportion of people who own at least one cat or dog by counting the
number of cat owners, adding the proportion of dog owners, and then deducting the proportion
of individuals who own both.
A non-disjoint union of finite sets is counted using the inclusion/exclusion principle. Applying
this idea to a carefully selected group of sets can provide solutions to a wide range of counting
45
issues. Examples are the most effective way to explain the approaches used in this process.
If two finite sets 𝐴 and 𝐵 have no items in common, then the total number of elements in the
union of the two sets is equal to |𝐴| + |𝐵|. However, in most cases, components that were

shared by both groups were added twice to the total. By deducting the quantity of these
common elements, the sum is modified to account for their double counting:

|𝐴 𝖴 𝐵| = |𝐴| + |𝐵| − |𝐴 ∩ 𝐵|
The number of elements in the union of three finite sets is similar to,
|𝐴 𝖴 𝐵 𝖴 𝐶| = |𝐴| + |𝐵| + |𝐶| − |𝐴 ∩ 𝐵| − |𝐴 ∩ 𝐶| − |𝐵 ∩ 𝐶| + |𝐴 ∩ 𝐵 ∩ 𝐶|
Example 5:

A. Of 70 people surveyed, 37 drink coffee, 23 drink tea, and 25 drink neither. Find the
number who drink both coffee and tea. Using 𝐶 to represent the set of coffee drinkers
and 𝑇 to represent the set of tea drinkers, the size of 𝐶 ∩ 𝑇 must be found. Since
|̅𝑇̅𝖴
̅𝐶̅ | = 25, we see that |𝐶 𝖴 𝑇| = 70 − 25 = 45. According to the
inclusion/exclusion principle,
|𝐶 ∩ 𝑇| = |𝐶| + |𝑇| − |𝐶 𝖴 𝑇| = 37 + 23 − 45 = 15

B. Suppose that 16 high-school juniors enroll in Algebra, 17 in Biology, and 30 in

Chemistry; that 5 students enroll in both Algebra and Biology, 4 in both Algebra and
Chemistry, and 7 in both Biology and Chemistry; that 3 students enroll in all three;
and that every junior takes at least one of these three subjects. Then the total number
of students in the junior class is 16 + 17 + 30 − (5 + 4 + 7) + 3 = 50.

C. Each of 11 linguists translates at least one of the languages Amharic and Burmese into
English. The numbers who translate only Amharic or Burmese are both odd primes.
More linguists translate Burmese than Amharic. How many can translate Amharic?
Based on experimentation or on an analytic approach, the only possible assignment of
numbers to regions that fits all these facts leads to 6.

3.2.3 Tree Diagrams

A tree diagram is a new management planning tool that depicts the hierarchy of tasks and
subtasks needed to complete and objective. The tree diagram starts with one item that branches
into two or more, each of which branch into two or more, and so on. The finished diagram
bears a resemblance to a tree, with a trunk and multiple branches.
46
It is used to break down broad categories into finer and finer levels of detail. Developing the
tree diagram helps you move your thinking step by step from generalities to specifics.
The visual way of representing a hierarchy in a tree-like structure is called a tree diagram. A
typical tree structure consists of a root node, node and leaf node
Root node: A root node is a member that has no superior parent
Node: The nodes are connected from the root nodes that are linked together with the help of
line connections called links or branches which shows the relationship between the members.
Leaf Node: Leaf node called as end nodes are the members which do not contain any children
or child node.
In mathematics, the tree diagram is used in probability and statistics and it allows us to calculate
the number of possible outcomes of an event where those outcomes are listed in an organised
manner. Each path of the branches in the tree diagram represents one outcome of an event. It
is a simple way of representing the sequences of events and it records all the possible outcomes
in an uncomplicated and clear manner.
In general, tree diagram starts with the one item or node, that branches into two or more, then
each of the nodes will branch into two or more, and so on. Then the final diagram resembles a
tree with a trunk and multiple branches.
Tree Diagram in Probability
In probability theory, a tree diagram could be utilised to express a probability space. These
diagrams may describe a sequence of independent events (for example a set of a coin tossed)
or conditional probabilities (like drawing cards from a deck, without substituting the cards).
Every node on the tree diagram shows an event and is connected with the probability of that
happening. The root node denotes the specific event and therefore it has a probability as 1. All
set of sibling joints or nodes designates an independent and exhaustive distribution of the parent
event.
Sometimes we feel difficulties while calculating probabilities and it is hard to figure out what
to do. Tree diagram will rescue this difficulty. Consider an example in probability to draw a
tree diagram for tossing a coin. There are two branches: head and tail. The probability of an
event is written on the branch and the outcome is written at the end of the branch.
Therefore, the tree diagram to represent the probability of tossing a coin is given below.
We can also draw a tree diagram for tossing two coins:
How to calculate the overall probability in the Tree Diagram?
Probability means the likelihood of occurrence of the events. The probability value is a
numerical value and it always lies between 0 and 1. The probability of an impossible event is

47
zero and the probability of the sure event is 1. The formula to find out the probability is given
as Probability of an event, P(E) = Number of favourable outcomes/ Total number of
outcomes. Also, there is the number of probability formulas in probability theory, each
depends upon thetype of event.

While tossing a coin, the probability of getting heads is 0.5 or 1/2 and the probability of getting
tails is 0.5 or 1/2.

Steps to calculate overall probability:

 Write the probability value on the branches.
 Then, multiply the probability value along the branches.
 Finally, add the probability value obtained after the multiplication process.
When you add all the probability values obtained, the result should be equal to 1.
A tree diagram is often used:
In mathematics and computer science
To show family relations
In taxonomy, to show classification
How to use a tree diagram to find probability?
In order to use a tree diagram to find probability:
Fill in the probabilities on the branches.
Consider which outcomes are required to answer the question.
Find the probability of those outcomes by multiplying along the branches.
Use the probability/probabilities you have calculated to answer the question.
WHEN TO USE A TREE DIAGRAM
When an issue is known or being addressed in broad generalities and you must move to
specific details, such as when developing logical steps to achieve an objective
When developing actions to carry out a solution or other plan
When analyzing processes in detail
When probing for the root cause of a problem
When evaluating implementation issues for several potential solutions
After an affinity diagram or interrelationship diagram has uncovered key issues
As a communication tool, to explain details to others.

48
 Fig 2.3: Utility of Tree Diagram

3.3 MATHEMATICAL FUNCTIONS

Combinations count the number of ways to choose things from a set, while permutations
count the number of arrangements of elements. A combination coefficient counts the number
of ways to choose a subset, whereas a permutation coefficient counts the possible
arrangements of a set of objects.
Falling powers mathematically model the process of selecting k items from a collection
of n items in circumstances where the ordering of the selection matters and repetition is
not allowed.

3.3.1 Permutations

A permutation of a list is any rearrangement of the list.

In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members
into a sequence or linear order, or if the set is already ordered, a rearrangement of its
elements. The word "permutation" also refers to the act or process of changing the linear
order of an ordered set.

49
Permutations differ from combinations, which are selections of some members of a set
regardless of order. For example, written as tuples, there are six permutations of the set {1, 2,
3}, namely (1, 2, 3), (1, 3, 2), (2, 1, 3), (2, 3, 1), (3, 1, 2), and (3, 2, 1). These are all the
possible orderings of this three-element set. Anagrams of words whose letters are different
are also permutations: the letters are already ordered in the original word, and the anagram is
a reordering of the letters. The study of permutations of finite sets is an important topic in the
fields of combinatorics and group theory.
Permutations are used in almost every branch of mathematics, and in many other fields of
science. In computer science, they are used for analyzing sorting algorithms; in quantum
physics, for describing states of particles; and in biology, for describing RNA sequences.
The number of permutations of n distinct objects is n factorial, usually written as n!, which
means the product of all positive integers less than or equal to n.
Technically, a permutation of a set S is defined as a bijection from S to itself. That is, it is a
function from S to S for which every element occurs exactly once as an image value. This is
related to the rearrangement of the elements of S in which each element s is replaced by the
corresponding f(s). For example, the permutation (3, 1, 2) mentioned above is described by
the function α as
α(1)=3, α(2)=1, α(3)=2
The collection of all permutations of a set form a group called the symmetric group of the set.
The group operation is the composition (performing two given rearrangements in succession),
which results in another rearrangement. As properties of permutations do not depend on the
nature of the set elements, it is often the permutations of the set {1,2,…, n} that are considered
for studying permutations.
In elementary combinatorics, the k-permutations, or partial permutations, are the ordered
arrangements of k distinct elements selected from a set. When k is equal to the size of the set,
these are the permutations of the set.
In 1677, Fabian Stedman described factorials when explaining the number of permutations of
bells in change ringing. Starting from two bells: "first, two must be admitted to be varied in
two ways", which he illustrates by showing 1 2 and 2 1. He then explains that with three bells
there are "three times two figures to be produced out of three" which again is illustrated. His
explanation involves "cast away 3, and 1.2 will remain; cast away 2, and 1.3 will remain; cast
away 1, and 2.3 will remain". He then moves on to four bells and repeats the casting away
argument showing that there will be four different sets of three. Effectively, this is a recursive

50
process. He continues with five bells using the "casting away" method and tabulates the
resulting 120 combinations. At this point he gives up and remarks:

“Now the nature of these methods is such, that the changes on one number comprehends the
changes on all lesser numbers, ... insomuch that a compleat Peal of changes on one number
seemeth to be formed by uniting of the compleat Peals on all lesser numbers into one entire
body;”
An arrangement of n elements into a list is called a permutation of a set of n elements. A
string whose contents are in the list order is frequently used to represent such a list and/or the
permutation itself.
An ordered selection of k items from a collection of n items constitutes a k-permutation of
that set. A string or a sequence can be used to represent a k-permutation.
The number of k-permutations, or methods to choose an ordered selection of k things from a
set of n items, is the permutation coefficient(𝑛, 𝑘).
A list is said to be deranged when no entry from the original order of the list exists after the
entries have been permuted.
The permutation coefficient can be found using the following formula:
𝑛!
𝑃(𝑛, 𝑘) =
(𝑛 − 𝑘 )!
Example 1:

A. Dealing a row of playing cards: Suppose that five cards are to be dealt from a deck of
52 cards and placed face up in a row. There are,
52!
(52, 5) = = 52 × 51 × 50 × 49 × 48 = 311,875,200 ways to do this.
(52−5)!

B. Placing distinct balls into distinct bins: k differently-colored balls are to be placed into n
bins (n ≥ k), with at most one ball to a bin. The number of different ways to arrange
𝑛!
the balls is 𝑃(𝑛, 𝑘) = (Think of the balls as if they were numbered 1 to k, so
(𝑛−𝑘)!

that placing ball j into a bin corresponds to placing that bin into the 𝑗𝑡ℎ position of the
list.)
C. Counting ballots: Voters are asked to rank their three top choices from the eleven
candidates running for office. A first-choice vote is worth 3 points, second choice 2
points, and third choice 1 point. Since a completed ballot is an ordered selection in
11!
this situation, each voter has 𝑃(11, 3) = = 11 × 10 × 9 = 990 distinct ways
(11−3)!

to cast a vote.

51
 3.3.2 Combinations

When the order of the selection is irrelevant and repeats are not permitted, the process of
choosing k items from a collection of n things is mathematically modelled by binomial
coefficients.
A subset of k items from a set S is an unordered selection of k things from S.
A k-combination from a set S is an unordered selection of k items.
The combination coefficient(𝑛, 𝑘) is the number of k-combinations of n objects.
𝑛
The binomial coefficient( ) is the coefficient of 𝑥𝑘𝑦𝑛−𝑘 in the expansion of (𝑥 + 𝑦)𝑛.
𝑘
The binomial coefficient can be found using the following formula:
𝐶(𝑛, 𝑘) = 𝑃(𝑛, 𝑘) = 𝑛! 𝑛
=( )
𝑘! 𝑘! (𝑛 − 𝑘)! 𝑘
Example 1:

A. Subsets: A set with 20 elements has (20, 4) subsets with four elements. The total
number of subsets of a set with 20 elements is equal to 𝐶(20, 0) + 𝐶(20, 1) + ⋯ +
(20, 20), which is equal to 220.
B. Non-distinct balls into distinct bins: Suppose k identically colored balls are to be
placed into n bins (n ≥ k), at most one ball to a bin. The number of different ways to
𝑛!
do this is 𝐶(𝑛, 𝑘) = . (This amounts to selecting from the n bins the k bins into
𝑘!(𝑛−𝑘)!

which the balls are placed.)

C. Counting ballots: Each voter is asked to identify three choices for trustee from eleven
candidates nominated for the position, without specifying any order of preference.
Since a completed ballot is an unordered selection in this situation, each voter has
11!
(11, 3) = = 165 distinct ways to cast a vote.
3!(11−3)!

D. Dealing a hand of playing cards: A hand of five cards (where order does not matter)
52!
can be dealt from a deck of 52 cards in 𝐶(52, 5) = = 2,598,960 ways.
5!(52−5)!

3.3.3 Combinations with Repetitions

Some problems concerning counting the number of ways to select k objects from a set
of n objects permit choices of objects to be repeated. Some of these situations are also
modeled by binomial coefficients.
An ordered selection with replacement is one where each item in the selection set has an
unlimited number of possible choices.

52
The number of times each object must be picked is fixed by an ordered selection with defined
replacement.
Each object in the selection set may be chosen at random and frequently in an unordered
selection with replacement.
The combination-with-replacement coefficient𝐶(𝑛, 𝑘) is the number of ways to
choose a multiset of k items from a set of n items.
Note:

1. If you choose an item from a set, write down its name, put it back in the set, then
repeat the procedure, you can have an ordered list of names. This is known as an
ordered selection with replacement.
2. The number of ways to make an unordered selection with replacement of k items from
(𝑛+𝑘−1)!
a set of n items is 𝐶(𝑛 + 𝑘 − 1, 𝑘). Thus 𝐶(𝑛, 𝑘) = 𝐶(𝑛 + 𝑘 − 1, 𝑘) = .
𝑘!(𝑛−1)!

3. Combinatorial interpretation: It is sufficient to show that the k-multisets that can be

chosen from a set of n items are in one-to-one correspondence with the bit strings of
length (𝑛 + 𝑘 − 1) with 𝑘 ones.

Example 1:

a. Distinct balls into distinct bins: 𝑘 differently coloured balls are to be placed into 𝑛
bins, with arbitrarily many balls to a bin. The number of different ways to do this is
𝑛𝑘. (Apply the rule of product to the number of possible bin choices for each ball.)
b. When three dice are rolled, the “outcome” is the number of times each of the numbers
1 to 6 appears. For instance, two 3s and a 5 is an outcome. The number of different
8
possible outcomes is 𝐶(6 + 3 − 1, 3) = ( ) = 56.
3
c. Non-distinct balls into distinct bins with multiple balls per bin allowed: The number
of ways that k identical balls can be placed into n distinct bins, with any number of
balls allowed in each bin, is 𝐶(𝑛 + 𝑘 − 1, 𝑘)
d. Non-distinct balls into distinct bins with no bin allowed to be empty: The number of
ways that k identical balls can be placed into n distinct bins, with any number of balls
allowed in each bin and no bin allowed to remain empty, is𝐶(𝑘 − 1, 𝑛 − 1)
e. How many ways are there to choose one dozen donuts when there are 7 different
kinds of donuts, with at least 12 of each type available? Order is not important, so a
multiset of size 12 is being constructed from 7 distinct types. Accordingly, there are
(7 + 12 − 1, 12) = 18,564 ways to choose the dozen donuts.

53
 3.3.4 Ordered and Unordered Partitions

A set S is partitioned into k nonempty subsets, 𝐴1, 𝐴2, 𝐴3, … , 𝐴𝑘if:

1. Every pair of subsets in disjoint: that is 𝐴𝑖 ∩ 𝐴𝑗 = ∅ if 𝑖 ≠ 𝑗.

2. 𝐴1 𝖴 𝐴2 𝖴 𝐴3 𝖴 … 𝖴 𝐴𝑘 = 𝑆

The partition mentioned above is ordered; if 𝐴1 and 𝐴2 are switched, a different partition
result. Ordered partitions appear when several subsets of the partition have traits that set them
apart from one another. (Just like in the example about distributing programs, providing
refreshments, and ushing)
The number of ways to partition a set with n elements into k subsets 𝐴1, 𝐴2, 𝐴3, … , 𝐴𝑘 with 𝐴𝑖
having 𝑟𝑖 elements is,
𝑛 𝑛 − 𝑟1 𝑛 − 𝑟1 − 𝑟2 − ⋯ − 𝑟𝑘−1 ) = 𝑛!
(𝑟 ) × ( 𝑟 ) × … × ( 𝑟𝑘 𝑟 !× 𝑟 !× …× 𝑟 !
1 2 1 2 𝑘

Example 1:
How many different ways are there for the six friends Alan, Cassie, Maggie, Seth, Roger, and
Beth to be divided into three groups of two each for the tasks of handing out programs,
manning the refreshments table, and serving as ushers?
Sol:
This system divides the group of six buddies into exactly one group for each participant.
Because one is tasked with programs, one with refreshments, and one with usher duties, the
subsets can be separated (in order). Thus, the response is
6 ) = 6!
( = 90
2, 2, 2 (2!)3
Example 2:
In how many ways can a set of ten people be divided into groups of five, three and two?
Sol:
10 ) = 10! 10 × 9 × 8 × 7 × 6
(
5, 3, 2 5! × 3! × 2! = 12
= 9 × 8 × 7 × 5 = 2520

Example 3:
The Electric Car Company will divide a group of 12 new recruits into three groups. Three
will go to Los Angeles, four to Dallas, and five to Portland. How many different ways may
this division be made for the new hires' group?
Sol:

54
This is an ordered partition problem since the entire set of 12 new hires is divided into 3
disjoint subsets which can be distinguished. Hence the answer is as follows:

12 12! 12 × 11 × 10 × 9 × 8 × 7 × 6
( )= = = 11 × 10 × 9 × 4 × 7 = 27,720
4, 3, 5 4! × 3! × 5! 144

Unordered Partitions
When there is no differentiation between subsets of the same size (and regardless of their
order), the partition is said to be unordered. The number of unordered divisions can be
calculated using the "overcounting" approach.
Example 4:
Our group of 6 friends Alan, Cassie, Maggie, Seth, Roger and Beth have signed up to
distribute fliers in the neighborhood. The person who hired them doesn’t care how they do
this but wants two people in each group. Alan wants to know how many ways they can divide
up. In particular the six pairings shown next give us the same unordered partition and is
counted only as one such unordered partition or pairing.
Sol:
If we had a different assignment for each group, the aforementioned one unordered partition
would have been counted as six distinct ordered partitions. The number of unordered
partitions can be calculated by dividing the total number of ordered partitions by 3! Similarly,
each unordered partition into three sets of two results in 3! ordered partitions. Consequently,
a set of six elements can be divided into three randomly ordered subsets of two elements.

1 6 6!
( )= = 5 × 3 = 15
3! 2, 2, 2 3! × (2!)3
Note:
In a similar way, we can derive a formula for the number of unordered partitions of a set.
A set of 𝑛 elements can be partitioned into 𝑘 unordered subsets of 𝑟 elements each (𝑘𝑟 = 𝑛)
in the following number of ways:
1 𝑛 𝑛!
( )=
𝑘! 𝑟, 𝑟, 𝑟, … , 𝑟 𝑘! × (𝑟!)𝑘
Example 5:
In how many ways can a set with 12 elements be divided into four unordered subsets with
three elements in each?

Sol:
55
 1 12 12!
( )= = 15,400
4! 3, 3, 3, 3 4! × (3!)4

Example 6:
The draw for the first round of the middleweight division for the Bengal Bouts is about to be
made. There are 32 competitors in this division. In how many ways can they be paired up for
the matches in the first round?
Sol:
1 32 32!
( = 191, 898, 783, 962, 511, 000
16! 2, 2, 2, 2, … , 2 ) = 16! × (2!)16

3.4 RECURRENCE RELATIONS

A recurrence relation is an equation which represents a sequence based on some rule. It helps
in finding the subsequent term (next term) dependent upon the preceding term (previous
term). If we know the previous term in a given series, then we can easily determine the next
term. Since a standard pattern is developed now, we can find the set of new terms. This is
also applicable for arithmetic and geometric sequence.

For any integers 𝑛 with 𝑛 ≥ 𝑛0, where𝑛0 is a nonnegative integer, a recurrence relation for
the sequence {𝑎𝑛} is an equation that expresses 𝑎𝑛 in terms of one or more of the previous
components of the sequence, specifically, 𝑎0, 𝑎1, 𝑎2, … 𝑎𝑛−1.

 A sequence is called a solution of a recurrence relation if its terms satisfy the

recurrence relation.
 The initial conditions for a sequence specify the terms that precede the first term
where the recurrence relation takes effect.

2.5.1 Linear Recurrence Relations with Constant Coefficients

A linear homogenous recurrence relation of degree k with constant coefficients is a

recurrence relation of the form,

56
 𝑎𝑛 = 𝑐1𝑎𝑛−1 + 𝑐2𝑎𝑛−2 + 𝑐3𝑎𝑛−3 + ⋯ + 𝑐𝑘𝑎𝑛−𝑘
Where, 𝑐1, 𝑐2, 𝑐3, … , 𝑐𝑘 are real numbers and 𝑐𝑘 ≠ 0.

Solving Method

1. We will write the characteristic equation of the recurrence relation.

2. Solve the characteristic equation to find the solution for the recurrence relation.

Example 1:
The Fibonacci recurrence,
𝐹𝑛 = 𝐹𝑛−1 + 𝐹𝑛−2
Sol:
The characteristic equation is as follows:
𝑟2 = 𝑟 + 1
𝑟2 − 𝑟 − 1 = 0
𝑟 = 1.61803, −0.61803
Proposition 1:
𝑟 is a solution of the equation 𝑟𝑘 − 𝑐1𝑟𝑘−1 − 𝑐2𝑟𝑘−2 − 𝑐3𝑟𝑘−3 − ⋯ − 𝑐𝑘 = 0 if and only if
𝑟𝑛 is a solution of 𝑎𝑛 = 𝑐1𝑎𝑛−1 + 𝑐2𝑎𝑛−2 + 𝑐3𝑎𝑛−3 + ⋯ + 𝑐𝑘𝑎𝑛−𝑘
Theorem 1:
Consider the characteristic equation 𝑟𝑘 − 𝑐1𝑟𝑘−1 − 𝑐2𝑟𝑘−2 − 𝑐3𝑟𝑘−3 − ⋯ − 𝑐𝑘 = 0 and the
recurrence relation 𝑎𝑛 = 𝑐1𝑎𝑛−1 + 𝑐2𝑎𝑛−2 + 𝑐3𝑎𝑛−3 + ⋯ + 𝑐𝑘𝑎𝑛−𝑘.

1. Assume the characteristic equation has 𝑡 ≤ 𝑘distinct solutions.

2. Let ∀𝑖 (1 ≤ 𝑖 ≤ 𝑡), 𝑟𝑖, with multiplicity 𝑚𝑖 be a solution of the equation.

3. Let ∀𝑖, 𝑗 (1 ≤ 𝑖 ≤ 𝑡)(0 ≤ 𝑗 ≤ 𝑚𝑖 − 1), 𝛼𝑖𝑗 be a constant.

So, 𝑎𝑛 = (𝛼10 + 𝛼11𝑛 + ⋯ + 𝛼1, −1𝑛𝑚1−1)𝑟𝑛 + (𝛼20 + 𝛼21𝑛 + ⋯ + 𝛼2,𝑚 𝑚 −1 𝑛

−1𝑛 2 )𝑟 +
1 1 2 2
⋯ (𝛼𝑡0 + 𝛼𝑡1𝑛 + ⋯ + 𝛼𝑡, −1𝑛𝑚𝑡−1)𝑟𝑛 satisfies the recurrence relation.
𝑡 𝑡

2.5.2 Solving General Homogeneous Linear Recurrence Relations

The Fibonacci recurrence falls under a general class of recurrence relations which are called
linear homogeneous recurrence relations with constant coefficients. The general form of such
recurrence is as follows:
𝑎𝑛 = 𝑐1𝑎𝑛−1 + 𝑐2𝑎𝑛−2 + 𝑐3𝑎𝑛−3 + ⋯ + 𝑐𝑘𝑎𝑛−𝑘, 𝑛 ≥ 𝑘
Where, 𝑐1, 𝑐2, 𝑐3, … , 𝑐𝑘 are real numbers and 𝑐𝑘 ≠ 0.
57
The characteristic equation is as follows:
𝑟𝑘 − 𝑐1𝑟𝑘−1 − 𝑐2𝑟𝑘−2 − 𝑐3𝑟𝑘−3 − ⋯ − 𝑐𝑘 = 0
The solution to the above characteristic equation is as follows:
1. For distinct roots:
𝑎𝑛 = (𝛼10)𝑛 + (𝛼20)𝑟𝑛 + ⋯ (𝛼𝑡0)𝑟𝑛
1 2 𝑡

2. For repeated roots:

𝑚1−1
𝑎𝑛 = (𝛼10 + 𝛼11𝑛 + ⋯ + 𝛼1, −1𝑛 )𝑟𝑛
1 1
𝑚2−1
+ (𝛼20 + 𝛼21𝑛 + ⋯ + 𝛼2, −1𝑛 )𝑟𝑛
2 2
+ ⋯ (𝛼𝑡0 + 𝛼𝑡1𝑛 + ⋯ + 𝛼𝑡, −1𝑛𝑚𝑡−1)𝑟𝑛
𝑡 𝑡

3.5 SUMMARY

 An equation that represents a sequence based on a rule is called a recurrence relation.

 If n pigeonholes are occupied by kn+1 or more pigeons, where k is a positive integer,
then at least one pigeonhole is occupied by k+1 or more pigeons.
 A tree diagram is a new management planning tool that depicts the hierarchy of tasks
and subtasks needed to complete and objective.
 A permutation of a list is any rearrangement of the list.

 An arrangement of n elements into a list is called a permutation of a set of n elements.

A string whose contents are in the list order is frequently used to represent such a list
and/or the permutation itself.
 The inclusion/exclusion principle is used to count a non-disjoint union of finite sets.
Many counting problems can be resolved by using this concept on a carefully chosen
set of sets.
 A recurrence relation is an equation which represents a sequence based on some rule. It
helps in finding the subsequent term (next term) dependent upon the preceding term
(previous term).
 “Second-order” refers to the fact that 𝑎𝑘−1 and 𝑎𝑘−2 are present in the expression for
𝑎𝑘 as separate terms to the first power, homogeneous refers to the fact that each term
has the same total degree (there is therefore no constant term), and “constant
coefficients” refers to the fact that 𝐴 and 𝐵 are constant real numbers that are
independent of 𝑘.
 The Fibonacci recurrence falls under a general class of recurrence relations which are
called linear homogeneous recurrence relations with constant coefficients.

58
 3.6 LEARNING ACTIVITY

1. Give examples of permutations and combinations.

2. Make a presentation on Pigeonhole Principle?

3.7 UNIT END QUESTIONS

A. Descriptive Questions
Short Questions:

1. What do you mean by permutations and combinations?

2. Write the relation between permutations and combinations.
3. What is the factorial formula?
4. How many anagrams of BEAD exist so that the vowels appear all next to each
other?
5. How many 5-digit telephone numbers can be constructed using the digits 0 to 9, if
each number starts with 67 and no digit appears more than once?

Long Questions:

1. How many rectangle sub-boards with at least two rows and columns exist on a 8 × 8
chessboard?
2. Show that in a class of 30 students in 10B (consisting of freshmen, sophomores,
juniors, and seniors), there exists at least 10 freshmen, 8 sophomores, 8 juniors, or 7
seniors.
3. Solve the recurrence relation an = an-1 – n with the initial term a0 = 4.
4. What are probability tree diagrams?
5. How to use a tree diagram to find probability?

59
B. Multiple Choice Questions

1. A drawer contains 12 red and 12 blue socks, all unmatched. A person takes socks out
at random in the dark. How many socks must he take out to be sure that he has at least
two blue socks?
a. 18
35
28
14

2. The least number of computers required to connect 10 computers to 5 routers to

guarantee 5 computers can directly access 5 routers is
a. 74
b. 104
c. 30
d. 67

3. When four coins are tossed simultaneously, in number of the outcomes at

most two of the coins will turn up as heads.
a. 17
b. 28
c. 11
d. 43

4. Quality table is also known as

a. Relationship diagram
b. Tree diagram
c. Matrix diagram
d. Arrow diagram

5. A pigeonhole is occupied by more than one pigeon if n pigeonholes are occupied by

or more pigeons?
a. n
b. n+1
c. n-1
d. None of the above

Answers:
1-d, 2-c, 3-c, 4-c, 5-b

60
3.8 REFERENCES

References Books
 Von Wright, Georg Henrik (1955). "Ludwig Wittgenstein, A Biographical Sketch".
The Philosophical Review. 64 (4): 527–545 (p. 532, note 9). doi:10.2307/2182631.
JSTOR 2182631.
 Post, Emil (July 1921). "Introduction to a general theory of elementary propositions".
American Journal of Mathematics. 43 (3): 163–185. doi:10.2307/2370324.
hdl:2027/[Link]:/13960/t9j450f7q. JSTOR 2370324.
 Anellis, Irving H. (2012). "Peirce's Truth-functional Analysis and the Origin of the
Truth Table". History and Philosophy of Logic. 33: 87–97.
doi:10.1080/01445340.2011.621702. S2CID 170654885.
Textbooks
 Bocheński, Józef Maria (1959). A Précis of Mathematical Logic. Translated by Bird,
Otto. D. Reidel. doi:10.1007/978-94-017-0592-9. ISBN 978-94-017-0592-9.
 Enderton, H. (2001). A Mathematical Introduction to Logic (2nd ed.). Harcourt
Academic Press. ISBN 0-12-238452-0.
 Quine, W.V. (1982). Methods of Logic (4th ed.). Harvard University Press. ISBN
978-0-674-57175-4.
 Peirce's publication included the work of Christine Ladd (1881): Peirce's Ph.D.
student Christine Ladd-Franklin found the truth table in Tractatus Logico-
Philosophicus Proposition 5.101, 40 years earlier than Wittgenstein. Ladd, Christine
(1881). Peirce, C.S. (ed.). On the Algebra of Logic. Studies in Logic
Website
 [Link]
compoundpropositions2/data/downloads/002_logic-compoundpropositions2_000.pdf
 [Link]
 [Link]

61