Combinatorics

Question 1

the mathematics of counting and
arranging

Answer 1

Combinatorics

Question 2

applies mathematical operations to count quantities that are much too large to be counted the conventional way.

Answer 2

Combinatorics

Question 3

Two main rules in Combinatorics

Answer 3

Sum rule and Product rule

Question 4

the number of ways that “either
task 1 or task 2 can be done, but not both”

Answer 4

Sum rule

Question 5

Sum rule formula

Answer 5

m + n

Question 6

Set Theoretic Version of Sum Rule

Answer 6

A union B|=|A|+|B|

Question 7

the number of ways that “both
tasks 1 and 2 can be done”

Answer 7

Product rule

Question 8

Product rule formula

Answer 8

m x n

Question 9

Set Theoretic Version of Sum Rule

Answer 9

|A x B|=|A|·|B|

Question 10

How many different bit strings are there of length seven?

Answer 10

128 bit strings

128 bit stringsThere are 2^7 =

Question 11

Suppose that either a member of the CS faculty or a student who is a CS major can be on a university committee. How many different choices are there if there are 37 CS faculty and 83 CS majors ?

Answer 11

120 different choices

Question 12

How many different license plates are available if
each plate contains a sequence of three letters
followed by three digits numbers?

Answer 12

17,576,000 possible plates

26 x 26 x 26 x 10 x 10 x 10 = 17,576 x 1000 = 17,576,000

Question 13

Suppose statement labels in a programming
language can be either a single uppercase letter, or
a lowercase letter followed by a digit. Find the
number of possible labels.

Answer 13

286

(26 x 10) + 26 = 260 + 26 = 286

Question 14

Suppose statement labels in a programming language can be either a single uppercase letter followed by a digit or a lowercase letter then followed by a digit. Find the number of possible labels.

Answer 14

520

(26 x 10) + (26 x 10) = 260 + 260 = 520

Question 15

Suppose we have a set of passwords that can either start with an uppercase letter followed by a digit, or with a three lowercase letter followed by two digits. How many possible passwords are there?

Answer 15

1,757,860

26×10 + (26×26×26)×(10×10) = 1,757,860

Question 16

Inclusion-Exclusion Principle
(relates to the “sum rule”)
formula

Answer 16

m + n - k

Question 17

Inclusion-Exclusion Principle (relates to the “sum rule”) Formula - Set theory

Answer 17

|A u B|=|A|+|B|−|A intersection B|.

Question 18

Suppose we have 95 students enrolled in NDDU. Of
these students, 50 are taking Circuits, 45 are taking
Programming, and 30 are taking both Circuits and
Programming. How many students are taking at least one of these subjects?

Answer 18

65

50 + 45 − 30 = 65

Question 19

How many strings of length eight either start with a 1 bit or end with the two bit string 00?

Answer 19

128 + 64 - 32 = 160

1 bit: 2^7 = 128 | bits 00: 2^6 = 64 |1 bit with bits 00 : 2^5 = 32

Question 20

can be used determine the number of possible outcomes when there are two or more characteristics .

Answer 20

Fundamental Counting Principle

Question 21

states that if an event has m possible outcomes and another independent event has n possible outcomes, then there are m* n possible outcomes for the two
events together.

Answer 21

Fundamental Counting Principle

Question 22

A student is to roll a die and flip a coin. How
many possible outcomes will there be?

Answer 22

12

(D)6 x (C)2 = 12

Question 23

For a college interview, Robert has to choose what
to wear from the following: 4 slacks, 3 shirts, 2
shoes and 5 ties. How many possible outfits does he
have to choose from?

Answer 23

120 outfits

4 * 3 * 2 * 5 = 120 outfits

Question 24

we make use of the word “(blank)” without thinking if the order is important.

Answer 24

Combination

Question 25

is an arrangement of
items in a particular order.

Answer 25

Permutation

Question 26

To find the number of Permutations of n items, we can use the

Answer 26

Fundamental Counting
Principle or factorial notation.

Question 27

Suppose you have 5 different books on a shelf, and
you want to arrange them in a specific order on the
shelf. How many different ways can you arrange these books on the shelf?

Answer 27

120

5 × 4 × 3 × 2 × 1 = 120

Question 28

To find the number of Permutations of n items
chosen r at a time, you can use the formula

Answer 28

nPr = (n!) / (n-r)!
where 0 <= r <= n

Question 29

The number of ways to arrange the letters
How many permutations are there of 2 letters
from ABCD? (note: the arrangement AB is not the
same as BA.)

Answer 29

12

4P2 = (4!) / (4-2)! = (4x3x2x1) / (2x1) = 4 x 3 = 12

Question 30

is an arrangement of
items in which order does not matter.

Answer 30

Combination

Question 31

ORDER DOES NOT MATTER!

Answer 31

Combination

Question 32

ORDER DOES MATTER!

Answer 32

Permutation

Question 33

are a “subset”
of the permutations

Answer 33

Combination

Question 34

To find the number of Combinations of n items
chosen r at a time, you can use the formula

Answer 34

nCr = (n!) / r!(n-r)!
where 0 <= r <= n

Question 35

There are 10 children in your class but you can invite only 5 to your birthday party. How many different
combinations of friends could you invite?

Answer 35

252

10C5 = (10!)/5!(10-5)! = (10x9x8x7x6)/(5x4x3x2x1) = 30240/120 = 252

Question 36

can be used to develop estimates about how many operations a computer algorithm will require.

Answer 36

Combinatorics methods