Problems on Counting - Solutions

In exercises 1 - 5, two dice are rolled one blue and one red.

  1. How many outcomes are possible?

Cartesian product A x A where A = {1,2,3,4,5,6}

6 x 6 = 36

  1. How many outcomes are doubles (both dice show the same number)?

6

  1. How many outcomes have the blue die showing 2?

6 : Cartesian product A x B where A = {2, blue die} B = {1,2,3,4,5,6, red die}

  1. How many outcomes have at least one die showing 2?

Fix the red die to show 2, 6 values for the blue die → 6 outcomes

Fix the blue die to show 2, 6 values for the red die → 6 outcomes

total is 12 – 1 = 11, we subtract the repeated case of both dice showing 2.

  1. How many outcomes have neither die showing 2?

Cartesian product A x A where A = {1,3,4,5,6}

5x 5 = 25

Exercises 6 – 10 refer to 8-bit strings

  1. How many 8-bit strings begin 1100?

Since the first 4 bits are fixed, we count the number of 4-bit strings: 24

  1. How many 8-bit strings begin and end with 1?

We count the number of 6-bit strings: 26

  1. How many 8-bit strings have either the second or the forth bit or both equal to 1?

There are 3 choices for second and the fourth bit: 01, 10, 11

For each choice there are 26 possible assignments of values to the remaining 6 bits.

Thus the total number of outcomes is 3x26

  1. How many 8-bit strings have exactly two 1's?

We choose the positions of the two bits that contain 1: combinations of 2 out of 8 - C(8,2) = 8C2

  1. How many 8-bit strings have at least one 1?

28 - 1 : total number of 8-bit string minus the string that contains only 0's

In exercises 11 - 14, a six-person committee composed of Alice, Ben, Connie, Dolph, Egbert and Frank is to select a chairperson, secretary and treasurer.

  1. How many selections exclude Connie?

P(5,3)

  1. How many selections are there in which neither Ben nor Frank is an officer?

P(4,3)

  1. How many selections are there in which Dolph is an officer and Frank is not an officer?

Dolph can be either chairperson, secretary or treasurer.

The remaining two officers are chosen among 4 persons – P(4,2)

Thus the total selections are 3*P(4,2)

  1. How many selections are there in which Ben is either a chairperson or treasurer?

2*P(5,2)

In exercises 15 - 20, the letters ABCDE are to be used to form strings of length 3

  1. How many strings can be formed if we allow repetitions?

Each position in the string may have 5 possible values: 35

  1. How many strings can be formed if we do not allow repetitions?

Permutations P(5,3)

  1. How many strings begin with A, allowing repetitions?

We count the choices for the remaining 2 positions: 25

  1. How many strings begin with A, not allowing repetitions?

P(4,2)

  1. How many strings contain A, allowing repetitions?

“A” can appear in the first, second or third position.

The remaining 2 positions can take any letter: 3*52

  1. How many strings contain A, not allowing repetitions?

“A” can appear in the first, second or third position.

The remaining two positions are permutations P(4,2)

Thus the outcomes are 3*P(4,2)

In exercises 21 - 23, determine how many strings can be formed by ordering the letters ABCDE subject to the conditions given

  1. Containing the substring ACE.

The substring ACE can start at position 1, 2 or 3.

The remaining positions are permutations 2!

Thus the outcomes are 3*2!

  1. Containing the letters ACE in any order. – assuming they are not split by other letters, i.e. they are kept together

There are 3! ways to order the letters ACE.

Any ordering can start at position 1, 2 or 3.

The remaining 2 letters can appear in 2! ways.

Thus the total outcomes are 3!*3*2!

  1. Containing either the substring AE or the substring EA

Each of the substrings can be placed in 4 possible positions in the string.

The remaining 3 positions can be filled in 3! ways.

Thus the total outcomes are 4*3!

  1. In some versions of FORTRAN, an identifier consists of a string of one to 6 alphanumeric characters beginning with a letter (an alphanumeric character is one of A to Z or 0 to 9.) How many valid FORTRAN identifiers are there?

The first position in the identifier is chosen among 26 letters.

The rest of the identifier with length 0 to 5 can be filled with any of 36 alphanumeric characters

For an identifier with length k+1 the number of choices are:

26*36k

For k = 0 to 5 we have:

26*( 360 + 361 + 362 + 363 + 364 + 365 ) = 26* ( 366- 1 ) /35

1