Lecture 1: Basic Counting and Enumeration: 1.1 Permutation

Discrete Mathematics 28-07-2014
Lecture 1: Basic Counting and Enumeration

Instructor: Sushmita Ruj Scribe: Kanishka Dhamija and Prateek Pandey
1 Basic Counting
1.1 Permutation
In mathematics, the notion of permutation relates to the act of permuting, or rearranging,
members of a set into a particular sequence or order (unlike combinations, which are se-
lections that disregard order). For example, 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). As another example, an ana-
gram of a word, all of whose letters are different, is a permutation of its letters. The study
of permutations of finite sets is a topic in the field of combinatorics.
r-permutation {x1 , x2 , . . . , xr } from a set of n elements {a1 , a2 , . . . , an } is the number
of ways to pick r elements and arrange them in order. This is the product
n(n − 1)...(n − r + 1)
which is also called falling factorial. The formula for permutation is given by
n n!
Pr = (n)r =
(n − r)!
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.
1.2 Combination
A combination is a way of selecting members from a group, such that (unlike permutations)
the order of selection does not matter. In smaller cases it is possible to count the number of
combinations. For example, given three fruits, say an apple, an orange and a pear, there are
three combinations of two that can be drawn from this set: an apple and a pear; an apple
and an orange; or a pear and an orange. More formally, a k-combination of a set S is a
subset of k distinct elements of S. If the set has n elements, the number of k-combinations
is equal to the binomial coefficient

n n(n − 1)...(n − k + 1)
=n Ck =
k k(k − 1)...1
which can be written using factorials as
n!
k!(n − k)!
whenever k ≤ n, and which is zero when k > n. The set of all k-combinations of a set S is
sometimes denoted by
S
k
1-1
1.3 Balls and Bins Problem
Distributing k distinguishable balls into n distinguishable bins, with exclusion, corresponds
to forming a permutation of size k, taken from a set of size n. Therefore, there are
n
Pk = (n)k = n(n − 1)...(n − r − 1)
different ways to distribute k distinguishable balls into n distinguishable boxes, with exclu-
sion.
Distributing k distinguishable balls into n distinguishable boxes, without exclusion,
corresponds to forming a permutation of size k, with unrestricted repetitions, taken from
a set of size n. Therefore, there are nk different ways to distribute k distinguishable balls
into n distinguishable boxes, without exclusion.
Distributing k indistinguishable balls into n distinguishable boxes, with exclusion cor-
responds to forming a combination of size k, taken from a set of size n. Therefore, there
are
n
C(n, k) =n Ck =
k
different ways to distribute k indistinguishable balls into n distinguishable boxes, with
exclusion.
Distributing k indistinguishable balls into n distinguishable boxes, without exclusion,
corresponds to forming a combination of size k with unrestricted repetitions, taken from a
set of size n. Therefore, there are

n+k−1 n+k−1
C(n + k − 1, k) = Ck =
k
different ways to k distribute k indistinguishable balls into n distinguishable boxes, without

exclusion.
The number of ways to distribute k distinguishable balls into n distinguishable boxes,
with exclusion, in such a way that no box is empty, is n! if k = n and 0 if k 6= n.
The number of ways to distribute k distinguishable balls into n distinguishable boxes,
without exclusion, in such a way that no box is empty is:

n k n k n k n−1 n
(n − 0) − (n − 1) + (n − 1) − ... + (−1) (1)k
0 1 1 n−1
1-2
2 Enumeration
2.1 Lexicographic Ordering
The lexicographic or lexicographical order (also known as lexical order, dictionary order, al-
phabetical order or lexicographic(al) product) is a generalization of the way the alphabetical
order of words is based on the alphabetical order of their component letters.
Given two partially ordered sets A and B, the lexicographical order on the Cartesian
product A × B is defined as
(a, b) <= (a0 , b0 ) if and only if a < a0 or (a = a0 and b <= b0 )
The result is a partial order. If A and B are each totally ordered, then the result is a total
order as well. Here is the pseudo code to generate all the permutation of a string as well as
increasing lexicographical order of the string.
1-3
2.2 Pseudo code to generate power set of a set-
1-4
2.3 Pseudo code to generate r combination out of n numbers-
3 Ramsey’s Theorem
3.1 Theorem
Ramsey’s theorem states that in any colouring of the edges of a sufficiently large complete
graph, one will find monochromatic complete subgraphs. For two colours, Ramsey’s theorem
states that for any pair of positive integers (r, s), there exists a least positive integer R(r, s)
such that for any 2-colouring of the complete graph on R(r, s) vertices, there exists a
complete monochromatic subgraph on either r or s vertices. Here R(r, s) signifies an integer
that depends on both r and s. It is understood to represent the smallest integer for which
the theorem holds.
An extension of this theorem applies to any finite number of colours, rather than just
two. More precisely, the theorem states that for any given number of colours c, and any
given integers n1 , · · · , nc , there is a number, R(n1 , . . . , nc ), such that if the edges of a
complete graph of order R(n1 , · · · , nc ) are coloured with c different colours, then for some i
between 1 and c, it must contain a complete subgraph of order ni whose edges are all colour
i. The special case above has c = 2 (and n1 = r and n2 = s).
1-5
4 References
Following Sites :
http://en.wikipedia.org/
http://www.elcamino.edu/
http://www.stackoverflow.com/
http://www.geeksforgeeks.org/
1-6

Lecture 1: Basic Counting and Enumeration: 1.1 Permutation

Uploaded by

Copyright:

Available Formats

Lecture 1: Basic Counting and Enumeration: 1.1 Permutation

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Lecture 1: Basic Counting and Enumeration: 1.1 Permutation

Uploaded by

Copyright:

Available Formats

Discrete Mathematics 28-07-2014

Lecture 1: Basic Counting and Enumeration

different ways to k distribute k indistinguishable balls into n distinguishable boxes, without

(a, b) <= (a0 , b0 ) if and only if a < a0 or (a = a0 and b <= b0 )

You might also like