# Combinatorics, recurrence relation, generating functions

1. Let R(s,t) denote the smallest positive integer p such that the complete graph on p vertices, whose edges are colored red or blue, there always exists either a complete subgraph on s vertices which is entirely blue, or a complete subgraph on t vertices which is entirely red. Show that R(3,4) = 9.

2. Given a positive integer. Let a_1, a_2,...,a_n^2+1 be a sequence of n^2+1 distinct real numbers. Show that there exists a decreasing subsequence of n+1 terms or an increasing subsequence of n+1 terms.

3. Determine the number a_n of n digit numbers with only odd digits so that the number of times each of 1 and 5 occurs is a multiple of 3.

4. Use the generated function to find the solution to the following recurrence relations.

a) Compute a_n where a_0 = 1, a_1 = -2, and a_n = 5a_n-1 - 6a_n-2 for n>= 2.

b) Compute the Catalan number C_n where C_1 = 1, and

(see the attachment for the full equation)

5. Find the number of nonnegative integer solutions of

x_1 + 2x_2 + 3x_3 + 6x_4 = n

with

0 <= x_1 <= 1, and 1 <= x_2 <= 3.

© SolutionLibrary Inc. solutionlibary.com 9836dcf9d7 https://solutionlibrary.com/math/discrete-math/combinatorics-recurrence-relation-generating-functions-j7qp