Lesson test: Generating functions

Generating functions

1.[1p]
What is the coefficient of $x^{5}$ in $\frac{1 + x}{1 - 3 x}$ ?

CorrectNot quite: 324

2.[2p]
What is the coefficient of $x^{6}$ in $\frac{1}{(1 - x)^{4}}$ ?

CorrectNot quite: 84

3.[2p]
Three ordinary dice are thrown. Using the coefficient of $x^{9}$ in $(x + x^{2} + \dots + x^{6})^{3}$ , in how many ways can they total $9$ , counting the dice as distinguishable?

CorrectNot quite: 25

4.[2p]
In how many ways can 15p be made from 1p, 2p and 5p coins, with any number of each and order ignored?

CorrectNot quite: 18

5.[3p]
In how many ways can 30p be made from 1p, 2p, 5p and 10p coins, with any number of each and order ignored?

CorrectNot quite: 98

6.[3p]
The sequence $a_{n} = 3 a_{n - 1} + 4 a_{n - 2}$ has $a_{0} = 2$ and $a_{1} = 3$ . Find its generating function, split it into partial fractions, and give $a_{5}$ .

CorrectNot quite: 1023

7.[1p]
How many ways are there to write $6$ pairs of matched brackets, the Catalan number $C_{6}$ ?

CorrectNot quite: 132

8.[1p]
With $F_{0} = 0$ , $F_{1} = 1$ and $F_{n} = F_{n - 1} + F_{n - 2}$ , what is the generating function $\sum F_{n} x^{n}$ of the Fibonacci numbers?

$\frac{x}{1 - x - x^{2}}$

Correct

$\frac{1}{1 - x - x^{2}}$

The answer is: $\frac{x}{1 - x - x^2}$

$\frac{x}{1 + x + x^{2}}$

The answer is: $\frac{x}{1 - x - x^2}$

$\frac{1 - x}{1 - x - x^{2}}$

The answer is: $\frac{x}{1 - x - x^2}$

9.[2p]
Match each sequence, starting from $n = 0$ , to its generating function.

$1, 2, 4, 8, \dots$
$1, 2, 3, 4, \dots$
$1, 0, 1, 0, \dots$
$1, - 1, 1, - 1, \dots$

$\frac{1}{(1 - x)^{2}}$
$\frac{1}{1 - x^{2}}$
$\frac{1}{1 + x}$
$\frac{1}{1 - 2 x}$

Show the answer

$1, 2, 4, 8, \dots$ : $\frac{1}{1 - 2 x}$ $1, 2, 3, 4, \dots$ : $\frac{1}{(1 - x)^{2}}$ $1, 0, 1, 0, \dots$ : $\frac{1}{1 - x^{2}}$ $1, - 1, 1, - 1, \dots$ : $\frac{1}{1 + x}$

1.[1p] What is the coefficient of x5 in 1+x1-3x?

2.[2p] What is the coefficient of x6 in 1(1-x)4?

3.[2p] Three ordinary dice are thrown. Using the coefficient of x9 in (x+x2+⋯+x6)3, in how many ways can they total 9, counting the dice as distinguishable?

4.[2p] In how many ways can 15p be made from 1p, 2p and 5p coins, with any number of each and order ignored?

5.[3p] In how many ways can 30p be made from 1p, 2p, 5p and 10p coins, with any number of each and order ignored?

6.[3p] The sequence an=3an-1+4an-2 has a0=2 and a1=3. Find its generating function, split it into partial fractions, and give a5.

7.[1p] How many ways are there to write 6 pairs of matched brackets, the Catalan number C6?

8.[1p] With F0=0, F1=1 and Fn=Fn-1+Fn-2, what is the generating function ∑Fnxn of the Fibonacci numbers?

9.[2p] Match each sequence, starting from n=0, to its generating function.

1.[1p]
What is the coefficient of $x^{5}$ in $\frac{1 + x}{1 - 3 x}$ ?

2.[2p]
What is the coefficient of $x^{6}$ in $\frac{1}{(1 - x)^{4}}$ ?

3.[2p]
Three ordinary dice are thrown. Using the coefficient of $x^{9}$ in $(x + x^{2} + \dots + x^{6})^{3}$ , in how many ways can they total $9$ , counting the dice as distinguishable?

4.[2p]
In how many ways can 15p be made from 1p, 2p and 5p coins, with any number of each and order ignored?

5.[3p]
In how many ways can 30p be made from 1p, 2p, 5p and 10p coins, with any number of each and order ignored?

6.[3p]
The sequence $a_{n} = 3 a_{n - 1} + 4 a_{n - 2}$ has $a_{0} = 2$ and $a_{1} = 3$ . Find its generating function, split it into partial fractions, and give $a_{5}$ .

7.[1p]
How many ways are there to write $6$ pairs of matched brackets, the Catalan number $C_{6}$ ?

8.[1p]
With $F_{0} = 0$ , $F_{1} = 1$ and $F_{n} = F_{n - 1} + F_{n - 2}$ , what is the generating function $\sum F_{n} x^{n}$ of the Fibonacci numbers?

9.[2p]
Match each sequence, starting from $n = 0$ , to its generating function.