Deck 8: Advanced Counting Techniques

Question 1

List the derangements of the set {1, 2, 3, 4}.

Answer 1

The derangements of {1, 2, 3, 4} are the permutations of these four integers that leave no integer in its original position. These are 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, and 4321.

Question 2

Use generating functions to solve the recurrence relation =1,2,3, ... , with initial condition
a₀=3

Answer 2

Let be the generating function for the sequence https://d2lvgg3v3hfg70.cloudfront.net/TB34225555/. Then =
,It follows that: =3, because of the given recurrence relation and initial condition. Thus ,so
it follows from an identity in table 1 of section 8.4 that . consecuently .

Question 3

Suppose that f(n) satisfies the divide-and-conquer relation What is f(81)?

Answer 3

Question 4

Find the solution of the recurrence relation

Question 5

How many positive integers not exceeding 1000 are not divisible by 4, 6, or 9?

Question 6

How many onto functions are there from a set with six elements to a set with four elements?

Question 7

Suppose that satisfies the divide-and-conquer recurrence relation What is ?

Question 8

How many ways are there to assign six jobs to four employees so that every employee is assigned at least one job?

Question 9

Suppose that
How many elements are in

Question 10

Find a generating function for the sequence 2, 3, 4, 5, . . ..

Question 11

How many permutations are there of the digits in the string 12345 that leave 3 fixed but leave no other integer fixed? (For instance, 24351 is such a permutation.)

Question 12

Find a recurrence relation and initial condition for the number of fruit flies in a jar if there are 12 flies initially and every week there are six times as many flies in the jar as there were the previous week.

Question 13

(a) Find a recurrence relation for the number of ways to climb n stairs if stairs can be climbed two or three at a time. (b) What are the initial conditions? (c) How many ways are there to climb eight stairs?

Question 14

What is the solution to the recurrence relation

Question 15

How many positive integers not exceeding 1000 are not divisible by either 4 or 6?

Question 16

Find the solution of the linear homogeneous recurrence relation a1 = 4.