Exercises 449
- How many permutations are there for the 26 letters of the alphabet if the five vowels
occur together?
12. How many n-bit binary numbers have exactly r l's assuming n > r? Prove by induc-
tion that for n > 1, exactly half the n-bit binary strings have an even number of l's.
- Twelve-tone music requires that the 12 notes of the chromatic scale be played before
any tone is repeated. How many different ways can the 12 tones be played? How long
will it take to play all possible sequences of 12 tones if one sequence can be played in
four seconds?
- Find the sum of all four-digit numbers that can be obtained by using the digits 1, 2, 3,
4, and 5. Repeats are not allowed. Explain your reasoning.
- A raffle has three prizes to award to 10,000 ticket holders. How many different ways
can the prizes be distributed if no one can win more than one prize? If one person can
win more than one prize?
- Thirty contestants, including the local champion, enter a competition. When the first
six places are announced:
(a) How many different announcements are possible?
(b) How many different announcements are possible if the local champion is assured
of a place in the first six?
- How many ways are there to seat eight people at a round table? How many ways if
Smith and Jones cannot be seated next to each other?
- How many ways can 12 people be seated at a round table if a certain pair of individuals
refuse to sit next to one another?
- How many ways can n men and n women be seated at a round table if no two women
are seated next to each other?
- A party has n guests. Two of the guests do not get along well with each other. In how
many ways can the guests be seated in a row so that these two persons do not sit next
to each other?
- Determine the number of five-card poker hands with the following patterns:
(a) Four deuces (2's) and one other card
(b) Four of a kind and one other card
(c) Two pairs (but not four of a kind) and one card with a different value
(d) Three cards of one value and two cards of a second value (this is called a full
house)
(e) A straight flush (a straight with all the cards from one suit)
(f) A hand with five different card values that is not a straight and is not a flush
(g) Three of one kind and two other cards with different values
- A bridge hand consists of 13 of the 52 cards from a standard deck of cards. How many
bridge hands contain no cards in one or more suits?
- There are six points in a plane, no three of which are collinear. In how many ways can
you draw a pair of triangles with the six points as vertices.
- For an even integer n, prove that C(n, n/2) does not have polynomial order. Interpret
this in terms of implementing an algorithm that examines this number of subsets of a
set.
- Winning a state lottery is based on trying to guess which six randomly picked numbers
in the set { 1, 2,..., 30} will be chosen. No repeats are allowed. Winning a second state
