Discrete Math

If there are \(n\) ways event \(E\) can occur and \(m\) ways to event \(F\) can occur, where the occurance of \(E\) has no effect on \(F\), then there are \(nm\) ways \(E\) and \(F\) can occur.

A startup with four employee rents an office suite with seven offices. How many ways are there to assign the employees?

The first employee has 7 offices to choose from, the second has 6 offices to choose from, the third can choose from 5, and the fourth can choose from 4. By the product rule, there are \(7 \times 6 \times 5 \times 4 = 840\) ways to assign the offices.

What will be the value 'counter' when the following code is run?

Suppose there are 27 computers in a computer center and each computer has 15 ports. How many different ways are there to choose a specific port?

Choosing a port means you first choose a computer and then a port on that computer. Since there are 27 computers and 15 ways to choose a port on a computer, there are \(27 \times 15 = 405\) ways to choose a port.

How many functions are there from a set \(A\) with \(m\) elements to a set \(B\) with \(n\) elements?

If there are \(n\) ways event \(E\) can occur and \(m\) ways event \(F\) can occur, and suppose that both events cannot occur at the same time, then there are \(n + m\) ways for \(E\) or \(F\) to occur.

A student in a Capstone course can choose a project from three different professors. The professors have 3, 7, and 4 possible projects, and no project is on more than one professor’s list. How many possible projects can the student choose?

The student can pick out a project by choosing from the first professor, the second professor, or the third professor. Since no project is on more than one list, the sum rules says that there are \(3 + 7 + 4 = 14\) projects to choose from.

If a card is drawn from a standard 52-card deck, how many ways can the card be an even number or a King?

Suppose event \(E\) can occur \(n\) ways, event \(F\) can occur \(m\) ways, and there are \(p\) ways that \(E\) and \(F\) both occur. Then there are \(n+m-p\) ways \(E\) or \(F\) can occur.

A tech company recieves 200 applications for a position. 150 of the applicants were ITEC majors, 43 were business majors, and 25 were double majors in business and ITEC. How many application did not major in ITEC or business?

By the subtraction rule, there are \(150 + 43 - 25 = 168\) applicants that majored in ITEC or business. Thus \(200 - 168 = 32\) majored in neither of these.

How many bit strings of length four start with 1 or end with 00?

A bit string of length four that starts with 1 will be of the form \(1~*~*~*\). For each \(*\) there are two choices, 0 or 1, so by the product rule, there are \(2^3\) bit strings of this form. A bit string of length four that ends with 00 will be of the form \(*~*~0~0\), so there are \(2^2\) bit strings of this form. Finally, a bit string of length four that starts with 1 and ends with 00 will be of the form \(1~*~0~0\), so there are 2 bit strings of this form. By the subtraction rule there are \(2^3 + 2^2 - 2 = 8+4-2=10\) possibilities.

If a card is drawn from a standard 52-card deck, how many ways can the card be black or a face card?

If \(n+1\) pigeons are resting in \(n\) pigeonholes then at least one pigeonhold contains more than one pigeon.

In a group of 367 people at least two will have the same birthday because there are only 366 possible birthdays (counting February 29).

How many people, with English names, must be in a room for two of them to have a first name that starts with the same letter?

\(P(n,r) = n(n-1)(n-2) \cdots (n-r+1) = \displaystyle \frac{n!}{(n-r)!}\).

Try to predict what happens with the code and verify.

Try using Pythontutor to list permutations of 5 objects taken 4 at a time.

The code below calculates the number of permutations given \(n\) and \(r\). Try to predict the variable names, values, and data types at different steps in the execution. Use the Next button to check your answers.

Try using Pythontutor to count permutations using a factorial formula.

If there are 10 runners in a race, how many different ways can the gold, silver, and bronze medals be awarded?

There are 10 objects (the runners) and we are choosing 3 to win medals. So the number of ways they can be awarded is

\(P(10,3) = \displaystyle \frac{10!}{(10-3)!} = \frac{10!}{7!} = 10 \times 9 \times 8 = 720\)

Alternatively, we could have used the product rule and noticed that there are 10 ways to award the gold, then there are 9 ways to award the silver, then 8 ways to award the brozne.

How many permutations of the digits 0123456789 are there that contain the string 456?

We can regard this as a permutation of 8 objects: the string 456 and the other 7 digits. Since they can occur in any order, the number of permutations is

\(P(8,8) = 8! = 40320.\)

From a group of 100 workers, how many ways can there be a union President, Vice President, and Treasurer?

How many different words (including nonsense words), can be formed using the letters in 'HEROIC' where the vowels must appear together?

\(C(n,r) = \displaystyle \frac{P(n,r)}{r!} = \frac{n!}{r!(n-r)!}\)

The code below calculates the number of and lists combinations given \(n\) and \(r\). Try to predict the variable names, values, and data types at different steps in the execution. Use the Next button to check your answers.

Try using Pythontutor to list and count combinations of 5 choose 4.

Now try using Pythontutor to calculate combinations using factorials.

How many ways can five cards be dealt from a standard 52-card deck?

We are choosing 5 cards from 52 cards and the order does not matter, so \(C(52,5)=\displaystyle \frac{52!}{5!47!}\)

How many bit strings of length \(n\) contain exactly \(r\) 0s?

Choosing the positions of the \(r\) 0s corresponds to the \(r\)-combinations of the set \(\{1, 2, 3, \dots, n\}\). Thus there are exactly \(C(n,r)\) such bit strings.