91Ó°ÊÓ

What is the probability that none of 10 people receives the correct hat if a hatcheck person hands their hats back randomly?

a) Find a recurrence relation for the number of ternary strings of length n that do not contain two consecutive 0s or two consecutive 1s. b) What are the initial conditions? c) How many ternary strings of length six do not contain two consecutive 0s or two consecutive 1s?

Use generating functions to find the number of ways to choose a dozen bagels from three varieties—egg, salty, and plain—if at least two bagels of each kind but no more than three salty bagels are chosen.

a) Find a recurrence relation for the number of ternary strings of length n that contain either two consecutive 0s or two consecutive 1s. b) What are the initial conditions? c) How many ternary strings of length six contain two consecutive 0s or two consecutive 1s?

Suppose that the votes of n people for different candidates (where there can be more than two candidates) for a particular office are the elements of a sequence. A person wins the election if this person receives a majority of the votes. a) Devise a divide-and-conquer algorithm that determines whether a candidate received a majority and, if so, determine who this candidate is. [Hint: Assume that \(n\) is even and split the sequence of votes into two sequences, each with \(n / 2\) elements. Note that a candidate could not have received a majority of votes without receiving a majority of votes in at least one of the two halves. b) Use the master theorem to give a big-O estimate for the number of comparisons needed by the algorithm you devised in part (a).

How many elements are in the union of four sets if each of the sets has 100 elements, each pair of the sets shares 50 elements, each three of the sets share 25 elements, and there are 5 elements in all four sets?

How many elements are in the union of four sets if the sets have \(50,60,70,\) and 80 elements, respectively, each pair of the sets has 5 elements in common, each triple of the sets has 1 common element, and no element is in all four sets?

Solve the recurrence relation \(a_{n}=-3 a_{n-1}-3 a_{n-2}-\) \(a_{n-3}\) with \(a_{0}=5, a_{1}=-9,\) and \(a_{2}=15 .\)

How many terms are there in the formula for the number of elements in the union of 10 sets given by the principle of inclusion-exclusion?

A bus driver pays all tolls, using only nickels and dimes, by throwing one coin at a time into the mechanical toll collector. a) Find a recurrence relation for the number of different ways the bus driver can pay a toll of n cents (where the order in which the coins are used matters). b) In how many different ways can the driver pay a toll of 45 cents?