7.4: General Combinatorics Problems

Last updated
Save as PDF

Page ID: 40936

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

As is often the case, practicing one type of problem at a time is helpful to master the techniques necessary to solve that type of problem. More difficult is deciding which type of problem you are working on and choosing which techniques to use to solve the problem. In this section, the problem types from the previous three sections are combined.

EXERCISES 4.4
SET I
1) How many strings of six lower case letters from the English alphabet contain
\(\quad\) a) the letter \(a ?\)
\(\quad\) b) the letters \(a\) and \(b\) in consecutive positions with \(a\) preceding \(b\), with all the letters distinct?
\(\quad\) c) the letters \(a\) and \(b\), where \(a\) is somewhere to the left of \(b\) in the string, with all the letters distinct?
2) Seven women and nine men are on the faculty in the mathematics department at a school.
\(\quad\) a) How many ways are there to select a committee of five members of the department if at least one woman must be on the committee?
\(\quad\) b) How many ways are there to select a committee of five members of the department if at least one woman and at least one man must be on the committee?
3) Suppose that a department contains 10 men and 15 women. How many ways are there to form a committee with 6 members if it must have the same number of men and women?
4) The English alphabet contains 21 consonants and 5 vowels. How many strings of 6 lower case letters of the English alphabet contain:
\(\quad\) a) exactly one vowel?
\(\quad\) b) exactly 2 vowels?
\(\quad\) c) at least 1 vowel?
\(\quad\) d) at least 2 vowels?
5) How many ways are there to select 12 countries in the United Nations to serve on a council if 3 are selected from a block of 45,4 are selected from a block of \(57,\) and the others are selected from the remaining 69 countries?
6) Suppose that a department contains 10 men and 15 women. How many ways are there to form a committee with 6 members if it must have more women than men?
7) How many license plates consisting of three letters followed by three digits contain no letter or digit twice?
8) In the women's tennis tournament at Wimbledon, two finalists, A and B, are competing for the title, which will be awarded to the first player to win two sets. In how many different ways can the match be completed?
9) In the men's tennis tournament at Wimbledon, two finalists, \(A\) and \(B\), are competing for the title, which will be awarded to the first player to win three sets. In how many different ways can the match be completed?
10) In how many different ways can a panel of 12 jurors and 2 alternate jurors be chosen from a group of 30 prospective jurors?

SET II
11) A class has 20 students, of which 12 are female and 8 are male. In how many ways can a committee of five students be picked from the class if:
\(\quad\) a) No restrictions are placed on the choice of students
\(\quad\) b) No males are included on the committee
\(\quad\) c) The committee must have three female members and 2 male members
12) A school dance committee is to be chosen from a group of students consisting of six freshman, eight sophomores, twelve juniors and ten seniors. If the committee should consist of two freshman, three sophomores, four juniors and five seniors, how many ways can this be done?
13) A theater company consists of 22 actors - 10 men and 12 women. In the next play, the director needs to cast a leading man, leading lady, supporting male role, supporting female role and eight extras (three men and five women). In how many ways can this play be cast?
14) A hockey coach has 20 players of which twelve play forward, six play defense and two are goalies. In how many ways can the coach pick a lineup consisting of three forwards, two defense players and one goalie?
15) In how many ways can ten students be arranged in a row for a class picture if John and Jane want to stand next to each other and Ed and Sally also want to stand next to each other?
16) In how many ways can the students in the previous problem be arranged if Ed and Sally want to stand next to each other, but John and Jane refuse to stand next to each other?
17) In how many ways can four men and four women be seated in a row of eight seats if:
\(\quad\) a) The first seat is occupied by a man
\(\quad\) b) The first and last seats are occupied by women

SET III
18) The social security number of a person is a sequence of nine digits that are not necessarily distinct. How many social security numbers are possible?
19) A variable name in the BASIC programming language is either a letter of the alphabet or a letter followed by a digit. How many distinct variable names are there in the BASIC language?
20) a) How many even numbers are there between 0 and 100?
b) How many even numbers with distinct digits are there between 0 and
\(100 ?\)
21) There are six characters - three letters of the English alphabet followed by three digits - which appear on the back panel of a particular brand of printer as an identification number. Find the number of possible identification numbers if
\(\quad\) a) characters can be repeated
\(\quad\) b) digits cannot repeat
\(\quad\) c) letters cannot repeat
\(\quad\) d) characters cannot repeat
22) A sequence of characters is called a palindrome if it reads the same forwards and backwards. For example \(\mathrm{K} 98 \mathrm{EE} 89 \mathrm{K}\) is an eight character palindrome and \(\mathrm{K} 98 \mathrm{E} 89 \mathrm{K}\) is a seven character palindrome. A MAN A PLAN A CANAL PANAMA is also a palindrome as are WAS IT A RAT I SAW, TACO CAT, TANGY GNAT, and NEVER ODD OR EVEN. Find the number of nine character palindromes that can be formed using the letters of the alphabet such that no letter appears more than twice in each one.
23) Find the number of ways to form a four-letter sequence using the letters \(A\),
B, \(C, D\) and \(E\) if:
\(\quad\) a) repetitions are permitted
\(\quad\) b) repetitions are not permitted
\(\quad\) c) the sequence contains the letter \(A\) but repetitions are not permitted
\(\quad\) d) the sequence contains the letter \(A\) and repetitions are permitted
24) There are 10 members A, B, C, D, E, F, G, H, I and J in a fund raising committee. The first task of the committee is to choose a chairperson, a secretary and a treasurer from this group. No individual can hold more than one office. How many ways can these three positions be filled if:
\(\quad\) a) no one has any objection for holding any of these offices
\(\quad\) b) Cneeds to be the chairperson
\(\quad\) c) \(\quad\) B does not want to be the chairperson
\(\quad\) d) \(\quad\) A is not willing to serve as chairperson or secretary
\(\quad\) e) either I or J must be the treasurer
\(\quad\) f) \(\quad\) E or \(F\) or \(G\) must hold one of the three offices
25) Find the number of ways of picking each of the following from a standard deck of cards.
\(\quad\) a) a king and a queen
\(\quad\) b) a king or a queen
\(\quad\) c) a king and a red card
\(\quad\) d) a king or a red card
26) There are three bridges connecting two towns A and B. Between towns B and
C there are four bridges. A salesperson needs to travel from A to C via B. Find:
\(\quad\) a) the number of possible choices of bridges from A to \(C\)
\(\quad\) b) the number of choices for a round trip from A to C and back to A
\(\quad\) c) the number of choices for a round trip if no bridge may be crossed twice
27) A sequence of digits in which each digit is 0 or 1 is called binary number. Eight digit binary numbers are often referred to as "bytes."
\(\quad\) a) How many bytes are possible?
\(\quad\) b) How many bytes begin with 10 and end with \(01 ?\)
\(\quad\) c) How many bytes begin with 10 but do not end with \(01 ?\)
\(\quad\) d) How many bytes begin with 10 or end with \(01 ?\)
28) A group of 12 is to be seated in a row of chairs. How many ways can this be done if:
\(\quad\) a) two people, \(A\) and \(B\) must be seated next to each other?
\(\quad\) b) two people \(A\) and \(B\) must not be seated next to each other?
29) A variable in the FORTRAN language is a sequence that has at most six characters with the first character being a letter of the alphabet and the remaining characters (if any) being either letters or digits. How many distinct variable names are possible?
30) Four station wagons, five sedans and six vans are to be parked in a row of
15 spaces. Find the nubmer of ways to park the vehicles if:
\(\quad\) a) the station wagons are parked at the beginning, then the sedans, then the vans
\(\quad\) b) vehicles of the same type must be parked together