The Basics of Counting

The Basics of Counting

Counting problems arise throughout Mathematics and Computer Science.

Basic Counting Principles

The two basic counting principles are

1. The product rule

2. The sum rule

1. The product rule

If one job can be done in m ways and following this another job can be done in n ways then the total number of ways in which both the jobs can be done in the stated order is mn.

2. The sum rule

If one job can be done in m ways and another job can be done in n ways and if there is no way common to both jobs then the total number of ways in which either of the two jobs can be done is equal to m + n.

Example 1: How many different bit strings of length seven are there?

Solution: Each of the seven bits can be chosen in two ways, because each bit is either 0 or 1.

The product rule shows there are a total of 2⁷ = 128 different bit strings of length seven.

Example 2: How many different 8-bit strings are there that begin and end with one.

Solution: A 8-bit string that begins and end with 1 can be constructed in 6 steps, (i.e.,)

By selecting IInd bit, IIIrd bit, IV bit, Vth bit, VIth bit and VIIth bits and each bit can be selected in 2 ways.

Hence, the total number of 8-bit strings that begins and end with 1 is equal to 2.2.2.2.2 = 26 = 64.

Example 3: How many different 8-bit strings are there that end with 0111 ?

Solution: A 8-bit strings that end with 0111 can be constructed n 4 steps.

By selecting Ist bit, IInd bit, IIIrd bit and IVth bit and each bit can be selected in 2 ways.

The total number of 8-bit strings that end with 0111 is equal to 2.2.2.2 = 2⁴ = 16.

Example 4: How many different 2-digit numbers can be made from the digits 1, 2, 3, 4, 5, 6, 7, 8, 9, 0? When repetition is allowed ? When repetition is not allowed ?

Solution: Case (i) : When repetition is allowed.

The tens place can be filled by 10 ways and the units place can be filled by 10 ways.

The total number of 2-digit numbers = 10 x 10 =100

Case (ii): When repetition is not allowed.

The tens place can be filled by 10 ways and the units place can be filled by 9 ways.

The total number of 2-digit numbers = 10 x 9 = 90.

Example 5: Prove that a set containing n elements has 2ⁿ sub sets. Use principle of counting.

Solution: As we have n elements in the set, a subset can be constructed in n different steps.

Take or do not take first element.

Take or do not take second element.

…………………………….

…………………………….

Take or do not take nth element.

So each step can be done in two different ways.

Hence the possible number of subsets is equal to

2.2.2. ... n times = 2ⁿ.

Example 6: How many different license plates are available if each plate contain a sequence of three letters followed by three digits (and no sequences of letters are prohibited, even if they are obscene)?

Solution: There are 26 choices for each of the three letters. There are 10 choices for each of the three digits. Hence, by the product rule there are a total (26) (26) (26) (10) (10) (10) = 17,576,000 possible license plates.

Example 7: How many one-to-one functions are there from a set with m elements to one with n elements ?

Solution :

Case (i) : When m>n there are no one-to-one functions from a set with m elements  to a set with n elements.

Case (ii) : When m≤n

Suppose the elements in the domain are a₁, a₂, ….. a_m.

There are n ways to choose the value of the function at a1. The value of the function at a2 can be picked in n - 1 ways. In general, the value of the function at a can be chosen in n-k+1 ways.

By the product rule, there are n (n-1) (n-2)... (n - m + 1) one-to-one functions from a set with m elements to one with n elements.

Example 8: In how many ways can we draw a heart or a shade from an ordinary deck of playing cards? A heart or an ace ? An ace or a king? A card numbered 2 through 10? A numbered card or a king?

Solution: Since there are 13 hearts and 13 spades. We may draw a heart or a spade in 13 + 13 = 26 ways. We may draw a heart or an ace in 13 + 3 = 16 ways, since there are only three aces that are not hearts. We may draw an ace or a king in 4 + 4 = 8 ways.

Example 9: Suppose that either a member of the Chemistry faculty or a student who is a Chemistry major is chosen as a representative to a University committee. How many different choices are there for this representative if there are 23 members of the Chemistry faculty and 80 Chemistry majors and no one is both a faculty member and a student ?

Solution: There are 23 ways to choose a member of the Chemistry faculty and there are 80 ways to choose a student who is Chemistry major. To choose a member of the Chemistry faculty is never the same as choose a student who is a Chemistry major because no one is both a faculty member and a student. By the sum rule it follows that there are 23+ 80 = 103 possible ways to pick this representative.

Inclusin - Exclusion Principle in General

Let P₁, P₂, …. P_n are finite sets.

Example 10: In a survey of 200 musicians, it was found that 40 wore gloves on the left hand and 39 wore gloves on the right hand. If 160 wore no gloves at all, how many wore a glove on only the right hand? Only the left hand ? On both hands?

Sol. Total number of musicians wore gloves on left, right or both hands (i.e.,)

| LUR | = 200 - 160 = 40

Musicians wore gloves on left hand |L| = 40

Musicians wore gloves on right hand |R| = 39

Musicians who wore gloves on both hands

| L∩R | = | L | + | R | - | LUR | = 40 + 39 - 40 = 39

Musicians who wore gloves only on right hand = 40 - 39 = 1

Musicians who wore gloves only on left hand = 39 - 39 = 0.

Example 11: 40 computer programmers interviewed for a job. 25 knew JAVA, 28 knew ORACLE, and 7 knew neither language. How many knew both languages?

Solution: Now

| J | = 25   ['.' J → JAVA]

| O | = 28   ['.' O → ORACLE]

| J U O | = 40 – 7 = 33

Computer progrmmers who knew both languages are

| J U O | = 25 + 28 - 33 = 20.

Example 12: In a survey of 300 students, 64 had taken a Mathematics course, 94 had taken a English course, 58 had taken a Computer course, 28 had taken both a Mathematics and a Computer course, 26 had taken both a English and a Mathematics course, 22 had taken both a English and a Computer course, 14 had taken all three courses.

(a) How many students were surveyed who had taken non of the three courses ?

(b) How many had taken only a Computer course?

Solution: Now | M | = 64; | E | = 94; | C | = 58

|M ∩C| = 28; |M ∩ E| = 26; |E ∩ C| = 22

|M∩N∩C| = 14

(a) |M U E U C| = |M|+|E|+|C|- |M ∩ C| -  |M ∩ E| - |E ∩ C| + |M ∩ E ∩ C|

= 64 + 94 + 58 – 28 – 26 - 22 + 14

= 154

Students who had taken none of the courses = 300 - 154 = 146.

(b) 14 had taken all three courses.

28 - 14 = 14 had taken both a Mathematics and a Computer but not all three 22-14 = 8 had taken both a English and a Computer courses but not all three

58 – 14 – 8 – 14 = 22 had taken only Computer course.

EXERCISE 2.3

1. A multiple-choice test contains 10 questions. There are four possible answers for each questions.

(a) How many ways can a student answer the question on the test if the student answers the question?   [Ans. 4¹⁰]

(b) How many ways can a student answer the questions on the test if the student can leave answers blank?   [Ans. 5¹⁰]

2. There are 18 mathematics majors and 325 computer science majors at a college.

(a) How many ways are there to pick two representatives so that one is a mathematics major and the other is a computer science major?   [Ans. 5850]

(b) How many ways are there to pick one representative who is either a mathematics major or a computer science major?   [Ans. 343]

3. How many different three-letter initials can people have?   [Ans. 26³]

4. How many bit strings of length ten both begin and end with a 1?   [Ans. 2⁸1

5. How many different three-letter initials are there that begin with an A?   [Ans. 676]

6. How many strings are there of lowercase letters of length four or less?   [Ans. 475, 255 (counting the empty string)]

7. How many bit strings with length not exceeding n, where n is a positive integer, consist entirely of 1 s?    [Ans. n+1 (counting the empty string)]

8. How many positive integers between 100 and 999 inclusive ?

(a) are divisible by 7?   [Ans. 128]

(b) have the same three decimal digits?   [Ans. 9]

(c) are not divisible by 4?   [Ans. 675]

(d) are not divisible by either 3 or 4?   [Ans. 450]

(e) are divisible by 3 but not by 4?    [Ans. 225]

(f) are divisible by 3 and 4?    [Ans. 75]

9. A committee is formed consisting of one representative from each of the 50 states in the United States, where the representative from a state is either the governor or one of the two senators from that state. How many ways are there to form this committee?   [Ans. 350]

10. How many one-to-one functions are there from a set with five elements to sets with the following number of elements ?

(a) 4    (b) 5    (c) 6    (d) 7

[Ans. (a) 0, (b) 120, (c) 720, (d) 2520]

11. How many bit strings of length 10 either begin with three 0s or end with two 0s?     [Ans. 352]

12. How many positive integers not exceeding 100 are divisible either by 4 or by 6?     [Ans. 33]