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
0 <= x_1 <= 1, and 1 <= x_2 <= 3.© SolutionLibrary Inc. solutionlibary.com September 24, 2020, 5:20 pm 9836dcf9d7 https://solutionlibrary.com/math/discrete-math/combinatorics-recurrence-relation-generating-functions-j7qp