Purchase Solution

# Combinatorics, recurrence relation, generating functions

Not what you're looking for?

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.

##### Solution Summary

The Solution addresses combinatorics, reccurence relation, generating functions and graph theory.

Solution provided by:
###### Education
• BSc, University of Bucharest
• MSc, Ovidius
• MSc, Stony Brook
• PhD (IP), Stony Brook
###### Recent Feedback
• "Thank you "
• "Thank You Chris this draft really helped me understand correlation."
• "Thanks for the prompt return. Going into the last meeting tonight before submission. "
• "Thank you for your promptness and great work. This will serve as a great guideline to assist with the completion of our project."
• "Thanks for the product. It is an excellent guideline for the group. "

##### Free BrainMass Quizzes

This quiz test you on how well you are familiar with solving quadratic inequalities.

##### Multiplying Complex Numbers

This is a short quiz to check your understanding of multiplication of complex numbers in rectangular form.

##### Geometry - Real Life Application Problems

Understanding of how geometry applies to in real-world contexts

##### Probability Quiz

Some questions on probability

##### Graphs and Functions

This quiz helps you easily identify a function and test your understanding of ranges, domains , function inverses and transformations.