1. Let a_n denote the number of sequences of length n that use the letters a, b, c, d, e, and f and have no two adjacent a's. Determine a recurrence relation for a_n along with appropriate initial condition Solution
   
   

2. Let a_n denote the number of sequences of length n that use the letters a, b, c, d, e, f and g and have an even total number of a's and b's. Determine a recurrence relation for a_n along with appropriate initial conditions. Solution
   
   

3. Let a_n = 4a_n-1 + 5ⁿ , a₀ =1. Find a formula for the value of a_n.
   (Hint: First find the generating function of the a_n's as a simplified rational function).
   Solution
   
   

4. Let a_n denote the number of sequences of {1, 2, 3, 4} of length n in which no 2 appears to the right of a 1. (so once a 1 appears, only 1's, 3's and 4's can follow). Determine a recurrence relation for a_n along with appropriate initial conditions. Solution
   

5. What is the probability that a permutation of 1, 2, 3, 4, ..., n - chosen at random - will have at more than 2 fixed points? Solution
   

6. Let a_n = 3a_n-1 + n , a₀ =1. Find the generating function for the a_n's. Solution

   
   

7. How many permutations of a, b, c, d, e, f, g, h, i, j do not contain any of the patterns abc, cdef, acd, efg? Solution

   
   

8. How many sequences of length n using the digits in {1, 2, 3, 4, 5} contain exactly 3 of the 5 digits? (Hint: first find the number of sequences that just use 1, 2 and 3 only)
   Solution
   
   

9. Let b_n denote the number of sequences of length n using 1, 2, 3, 4, 5, 6, 7, 8 in which the digit 1 is always followed immediately by an even integer. Find a recurrence for b_n.
   Solution
   

10. How many non-negative integer solutions are there to the equation
    ?
    (Use inclusion-exclusion) Solution
    
    

11. How many permutations of {1, 2, 3, 4, 5, 6, 7, 8} have exactly 3 numbers in their proper position? Solution
    
    

12. How many permutations of 1, 2, 3, 4, 5, 6, 7, 8, 9 have no even number in its proper position? Solution

The Stirling Numbers

A partition of a set S is a collection of non-empty sets say {A₁, A₂, ..., A_r }such that each element of S belongs to exactly one of the A_i's. For example, one partition of
{1, 2, 3, 4, 5, 6, 7, 8} is { {1}, {2, 5}, {3, 6, 7, 8} }

13. Let denote the number of ways to partition {1, 2, ..., n} into k non-empty sets. The numbers, , are called the Stirling Numbers.

So, since {a, b, c, d} can be partitioned into two non-empty sets as:

{ {a, b}, {c, d} }, or { {a, c}, {b, d} }, or { {a, d}, {b, c} }, or { {a}, {b, c, d} }, or

{ {b}, {a, c, d} }, or { {c}, {a, b, d} }, or { {d}, {a, b, c} }

(i). By listing partitions, show that ?
(ii). Verify the recurrence relation for : , .

(iii). Use (ii) to find the value of . Answer: 25

*(iv). Find a simple formula for .
(v). Find a simple formula for S_n,n and S_n,n-1?

(vi). Let a_n = S_n,3. Find a recurrence relation for a_n. Solution

(vii). Evaluate in terms of n: .
What else can you discover about these Stirling Numbers?

Solutions

1. Next Problem
   

2. We can construct a sequence of length n by beginning with c, d, e, f, or g (5 ways) and then follow with any legitimate sequence of length n-1 (a_n-1 of them). OR we can start with a or b (2 ways) and continue with any sequence of length n-1 that has an odd total number of a's and b's (7^n-1 - a_n-1 of them).
   So, a_n = 5a_n-1 + 2(7^n-1 - a_n-1 ) =3a_n-1 + 2.7^n-1.
   So, a_n = 3a_n-1 + 2.7^n-1, a₀ =1, a₁ = 5 Next Problem

3. Let . Then .
   So, .
   
   Now, by partial fractions, , and so . Next Problem
   
   

4. Next Problem
   
   

5. Next Problem
   

6. Next Problem
   

7. Next Problem
   

8. By inclusion-exclusion, the number of seqences that use exactly 1, 2, and 3 is . Thus, the answer to the question posed is 10().Next Problem
   

9. Next Problem
   

10. 
    Next Problem
    

11. Next Problem
    
    

12. Next Problem
    

13. (iv). S_n,2 = 2^n-1 - 1
    (v). S_n,n = 1, S_n,n-1 =
    (vi). a_n = 3a_n-1 +2^n-2 - 1
    Problem 1