###### Waste less time on Facebook — follow Brilliant.
×
Back to all chapters

# Generating Functions

This combinatorial tool is used for solving recurrence relations and other difficult problems.

# Generating Functions: Level 4 Challenges

Cody has 4 types of onions.

$$\bullet$$ The number of $$\color{Purple}{Purple}$$ onions can be any non-negative integer.

$$\bullet$$ The number of $$\color{Green}{Green}$$ onions is a multiple of 2.

$$\bullet$$ The number of $$\color{Red}{Red}$$ onions is a multiple of 3.

$$\bullet$$ The number of $$\color{Blue}{Blue}$$ onions is a multiple of 5.

If Cody has 23 onions, how many different distributions of colors can there be?

Details and Assumptions: Cody can't have a negative number of onions, but he may have 0 onions of a certain type(s).

A one year old bunny is sitting on the number 0 in the number line. His father, Bugs Bunny, is waiting for him on the number 10.

The bunny has to reach his father. At each minute, he can:

• Move one step forward;
• Move two steps forward;
• Stay still;
• Move one step backward;
• Move two steps backward.

There are $$N$$ possible ways the bunny can be on the number 10 after 10 minutes. Find the last three digits of $$N$$.

Details and assumptions

• The bunny is allowed to hop beyond 10, and then come back.

• There are no restrictions on the bunny entering the negative numbers. The bunny can go as much backwards as he wants.

• Order does matter. For example, the steps $$\{0000022222\}$$ and $$\{2020202020\}$$ are considered distinct.

How many polynomials $$P(x)$$ are there such that the coefficients of $$P(x)$$ are integers from 0 to 24 (inclusive) and $$P(5) = 1200$$?

Consider the recurrence relation $$a_n = 2a_{n-1} + 3 a_{n-2} + 3^n$$ for $$n \geq 2$$ with initial conditions $$a_0 = -1, a_1 = 1.$$

Given that $$a_{100}$$ is in the form of

$\LARGE \frac {x\cdot y^z - w}{v}$

where $$x,y,w,z$$ are prime numbers and $$v$$ as a perfect square, what is the value of $$w+v+x+y+z$$?

Find the general expression for $$c_n$$, where

$c_n - 3 c_{n-1} = 2 \cdot 5^n .$

×