Chapter 5: Lattices and Counting Principles

Lattices
 A partially ordered set in which every pair of elements has both a least upper bound (LUB) and a greatest
lower bound(GLB) is called a lattice.
 LUB({a,b}) is denoted by a v b and is called the join of a and b. GLB({a,b}) is denoted by a Λ b and is called
the meet of a and b.
 Lattices have many special properties. Furthermore, lattices are used in many different applications such as
models of information flow and play an important role in Boolean algebra.
Ex.1) Determine whether the posets represented by each of the Hasse diagrams in the following Figure
are lattices.

Solution: The posets represented by the Hasse diagrams in (i) and (iii) are both lattices because in each
poset every pair of elements has both a least upper bound and a greatest lower bound.
On the other hand, the poset with the Hasse diagram shown in (ii) is not a lattice, because the elements b
and c have no least upper bound. To see this, note that each of the elements d, e, and f is an upper
bound, but none of these three elements precedes the other two with respect to the ordering of this
poset.

Ex 2.)Is the poset (Z+, ∣) a lattice?

Solution: Let a and b be two positive integers. The least upper bound and greatest lower bound of these
two integers are the least common multiple and the greatest common divisor of these integers,
respectively. It follows that this poset is a lattice.
Properties of Lattices:
Theorem: a) a v b = b iff a ≤ b
1. Idempotent Properties b) a Λ b =a iff a ≤ b
c) a Λ b =a iff a v b = b
a) a v a = a
b) a Λ a = a
2. Commutative Properties
a) a v b = b v a
b) a Λ b = b Λ a
3. Associative Properties
a) a v (b v c)= (a v b) v c
b) a Λ(b Λ c)= (a Λ b) Λ c
4. Absorption Properties
b) a v (a Λ b) = a
b) a Λ (a v b) = a
Counting Principles
• We must count objects to solve many different types of problems.
• For instance, counting is used to determine the complexity of algorithms.
• We need to count the number of operations used by an algorithm to study its time complexity.
• Counting is also required to determine whether there are enough telephone numbers or Internet
protocol addresses to meet demand.
• Recently, it has played a key role in mathematical biology, especially in sequencing DNA.
• Furthermore, counting techniques are used extensively when probabilities of events are computed.
• Many counting problems can be solved by finding the number of ways to arrange a specified number of
distinct elements of a set of a particular size, where the order of these elements matters.
• Many other counting problems can be solved by finding the number of ways to select a particular
number of elements from a set of a particular size, where the order of the elements selected does not
matter.
• These arrangements, where the order of the elements matters, are called permutations
and the arrangements, where the order of the elements does not matters are called as
combinations.
• These are used in many counting problems.
 Permutations and Combinations
Permutations:
A permutation of a set of distinct objects is an ordered arrangement of these objects.
The ordered arrangements of some of the elements (r) of a set is called an r-permutation.
Ex1) Let S = {1, 2, 3}. The ordered arrangement 3, 1, 2 is a permutation of S.
The ordered arrangement 3, 2 is a 2-permutation of S.
The number of r-permutations of a set with n elements is denoted by P (n, r).
If n and r are integers with 0 ≤ r ≤ n, then P (n, r) = n!/ (n − r)! .
EX2) Let S = {a, b, c}. The 2-permutations of S are the ordered arrangements a, b; a, c; b, a; b, c; c, a; and
c, b. Consequently, there are six 2-permutations of this set with three elements. There are always six 2-
permutations of a set with three elements.
There are three ways to choose the first element of the arrangement. There are two ways to choose the
second element of the arrangement, because it must be different from the first element. Hence, by the
product rule, we see that P (3, 2) = 3 · 2 = 6. the first element. By the product rule, it follows that P (3, 2) =
3 · 2 = 6.
Ex.3)How many ways are there to select a first-prize winner, a second-prize winner, and a third-prize
winner from 100 different people who have entered a contest?
Solution: Because it matters which person wins which prize, the number of ways to pick the three prize
winners is the number of ordered selections of three elements from a set of 100 elements, that is, the
number of 3-permutations of a set of 100 elements.
P (n, r) = n!/ (n − r)!
n= 100 r=3
P(n , r) = 100!/ (100-3)!
Consequently, the answer is P (100, 3) = 100 · 99 · 98 = 970,200.
Ex4) How many permutations of the letters ABCDEFGH contain the string ABC ?
Solution: Because the letters ABC must occur as a block, we can find the answer by finding the
number of permutations of six objects, namely, the block ABC and the individual letters D, E, F, G,
and H.
Because these six objects can occur in any order, there are 6! = 720 permutations of the letters
ABCDEFGH in which ABC occurs as a block.
Combinations
• Combination of elements of a set is an unordered selection of those elements from the set.
• An unordered selection of r elements from the set is called as r-combination of elements of a set .
Thus, an r-combination is simply a subset of the set with r elements.
• The number of r-combinations of a set with n elements, where n is a nonnegative integer and r is
an integer with 0 ≤ r ≤ n, equals C(n, r) = n!/ r!(n − r)! .
• Ex1) How many different committees of three students can be formed from a group of four
students?
Solution: C(n, r) = n!/ r!(n − r)! .
n=4, r=3
C(n, r)= 4!/3!(4-3)!
= (4*3*2*1) / (3*2*1)(1)
= 4.
Answer is: 4
Ex2) How many ways are there to select five players from a 10-member tennis team to make a trip
to a match at another school?
Solution: The answer is given by the number of 5-combinations of a set with 10 elements.
C(n, r) = n!/r!(n-r)!
n=10 r=5.
So the number of such combinations is C(10, 5) = 10! /5! 5! = 252.
 Ex2) A group of 30 people have been trained as astronauts to go on the first mission to Mars. How
many ways are there to select a crew of six people to go on this mission (assuming that all crew
members have the same job)?
Solution: The number of ways to select a crew of six from the pool of 30 people is the number of 6-
combinations of a set with 30 elements, because the order in which these people are chosen does
not matter, the number of such combinations is
C(30, 6) = 30!/ 6! 24! = 30 · 29 · 28 · 27 · 26 · 25 /6 · 5 · 4 · 3 · 2 · 1 = 593,775

Ex3) How many bit strings of length n contain exactly r 1s?

Solution: The positions of r 1s in a bit string of length n form an r-combination of the set {1, 2, 3,...,n}. Hence,
there are C(n, r) bit strings of length n that contain exactly r 1s.
Ex.4) Suppose that there are 9 faculty members in the mathematics department and 11 in the
computer science department. How many ways are there to select a committee to develop a
discrete mathematics course at a school if the committee is to consist of three faculty members
from the mathematics department and four from the computer science department?
Solution: By the product rule, the answer is the product of the number of 3-combinations of a set
with nine elements and the number of 4-combinations of a set with 11 elements.
The number of ways to select the committee is
C(9, 3) · C(11, 4) = 9!/ 3!6! · 11! /4!7! = 84 · 330 = 27,720.
1)List all the permutations of {a, b, c}.

2. How many different permutations are there of the set {a, b, c, d, e, f, g}?

3. How many permutations of {a, b, c, d, e, f, g} end with a?

4. Let S = {1, 2, 3, 4, 5}.

a) List all the 3-permutations of S. b) List all the 3-combinations of S.
5.) Find the value of each of these quantities.
a) P (6, 3)
b) P (6, 5)
c) P (8, 1)
d) P (8, 5)
e) P (8, 8)
f) P (10, 9)
6. Find the value of each of these quantities.
g) C(5, 1)
h) C(5, 3)
i) C(8, 4)
j) C(8, 8)
k) C(8, 0)
l) C(12, 6)

7. Find the number of 5-permutations of a set with nine elements.

8)How many permutations of the letters ABCDEFG contain
a) the string BCD?

b) the string CFGA?

c) the strings BA and GF?

d) the strings ABC and DE?

e) the strings ABC and CDE?

f) the strings CBA and BED?

9)How many possibilities are there for the win, place, and show (first, second, and third) positions in

a horse race with 12 horses if all orders of finish are possible?

10) In how many ways can a set of five letters be selected from the English alphabet?
Ex.5)How many bit strings of length 10 contain
a) exactly four 1s?
b) at most four 1s?
c) at least four 1s?
d) an equal number of 0s and 1s?
Generalized Permutations and Combinations :
 In this section we will show how to solve counting problems where elements may be used more
than once.
 In this section we will describe how to solve counting problems in which some elements are
indistinguishable.
 Combinations and Permutations With and Without Repetition.
Type Repetition Allowed? Formula
r-permutations No n!/ (n − r)!
r-combinations No n! /r! (n − r)!
r-permutations Yes nr
r-combinations Yes (n + r − 1)! /r! (n − 1)!

 The number of different permutations of n objects, where there are n1 indistinguishable objects of
type 1, n2 indistinguishable objects of type 2,..., and nk indistinguishable objects of type k, is
n!/ n1! n2!··· nk! .