Generating Functions · Theory Problems

Lesson 1

Nikolai Chukhin · Alexander S. Kulikov

Basic Problems.

  1. (5 points) Find the generating function for the sequence \((0, 0, 1, 3, 6, 10, \dotsc)\), i.e. \[A(n)=\frac{n(n-1)}{2}.\]
  2. (10 points) Find the generating functions (in the form of a fraction of polynomials) and explicit formulas for the elements of the sequences defined by the recurrence relations (\(n \geq 0\)):
    1. (5 points) \(a_{n+3}= 5a_{n+2}- 8a_{n+1}+ 4a_{n}, \quad a_{0} = 1, \ a_{1} = 2, \ a_{2} = 0\).
    2. (5 points) \(a_{n+2}= a_{n+1}+ 2a_{n} + 5^{n}, \quad a_{0} = 0, \ a_{1} = 1\).
  3. (10 points) Let \(a_{n}\) denote the number of solutions of the equation \[2w + 8x + y + 9z = n\] in nonnegative integers. Find the generating function of the sequence \(a_{n}\).
  4. (15 points) Let \(A(x)\) be the generating function of the sequence \((a_{0}, a_{1}, a_{2}, …)\). It is known that \(A(x) = \frac{P(x)}{Q(x)}\), where \(P(x), Q(x)\) are nonzero polynomials with complex coefficients and no common roots. Let \(\deg Q = k\). Prove that, starting from some index \(n\), the sequence satisfies the linear recurrence relation: \[a_{n+k}= c_{1}a_{n+k-1}+ c_{2}a_{n+k-2}+ \cdots + c_{k}a_{n}.\] Here, \(c_{1}, c_{2}, …, c_{k} \in \mathbb{C}\) are constants.
  5. (15 points) A king is placed on the square \((0,0)\) on an infinite grid. He can move only in three directions: up, right, and up-right. Let \(a_{(m,n)}\) (resp. \(b_{(m,n)}\)) be the number of king's paths ending at \((m,n)\) that contain an even (resp. odd) number of up-right moves.

    For a doubly indexed sequence \(c_{m,n}\), the generating function depends on two variables and is defined as \[F(x,y) = \sum_{m,n \ge 0}c_{m,n}x^{m} y^{n} .\]

    1. (7 points) Find the generating function \(F(x,y)\) for the sequence \(a_{(m,n)}+b_{(m,n)}\).
    2. (8 points) Compute explicitly the value of \(a_{(m,n)}-b_{(m,n)}\).
  6. (20 points) Write (not necessarily in closed form; you may use infinite products in the answer) the generating functions of the following sequences:
    1. (3 points) \(a_{k}\) is the number of partitions of \(k\) into distinct positive integers (order disregarded).
    2. (4 points) \(b_{k}\) is the number of compositions of \(k\) into positive integers (order matters).
    3. (3 points) \(c_{k}\) is the number of partitions of \(k\) into positive integers (order disregarded).
    4. (3 points) \(d_{k}\) is the number of partitions of \(k\) into odd positive integers (order disregarded).
    5. (7 points) Prove that \(a_{k} = d_{k}\).