Formal Power Series

A formal power series (or formal series) is an expression of the form $\sum_{n = 0}^{\infty} a_{n} x^{n}$ , where $a_{n}$ are coefficients.

(Unlike a power series, a formal power series is not necessarily convergent, and the variable $x$ is treated as an indeterminate, and is not assigned a value. The series is treated as an algebraic object, rather than a function to be evaluated.)

Operations

(Addition) $(\sum_{n = 0}^{\infty} a_{n} x^{n}) + (\sum_{n = 0}^{\infty} b_{n} x^{n}) = \sum_{n = 0}^{\infty} (a_{n} + b_{n}) x^{n}$
(Multiplication) $(\sum_{n = 0}^{\infty} a_{n} x^{n}) \cdot (\sum_{n = 0}^{\infty} b_{n} x^{n}) = \sum_{n = 0}^{\infty} c_{n} x^{n}$ where $c_{n} = \sum_{k = 0}^{n} a_{k} b_{n - k}$
(Division) $\frac{\sum _{n = 0}^{\infty} b _{n} x ^{n}}{\sum _{n = 0}^{\infty} a _{n} x ^{n}} = \sum_{n = 0}^{\infty} c_{n} x^{n}$ where $c_{n} = \frac{1}{a _{0}} (b_{n} - \sum_{k = 1}^{n} a_{k} c_{n - k})$ (assuming $a_{0} \neq = 0$ )
Extracting coefficientstodo
(Composition)todo

Generating Functions

A generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series.
The (ordinary) generating function for the sequence $(a_{n})$ is the formal power series $G (x)$ defined by $G (x) = \sum_{n = 0}^{\infty} a_{n} x^{n}$

todo read https://enumeration.ca/toolbox/generating-functions/

Usage

Usage for number of solutions

Generating function can also be used for number of nonnegative solutions of equation: $t_{1} + \dots + t_{n} = k$ . Then the coefficient of $x^{k}$ in the following generating function is the number of solutions. $f (x) = (1 + x + x^{2} + \dots)^{n} = \frac{1}{( 1 - x ) ^{n}} = \sum_{k = 0}^{\infty} (k n - k - 1) x^{k}$

Restrictions

Restriction for all Addends:

Special case example: a number of solutions of equation: $t_{1} + \dots + t_{n} = k$ . such that $1 \leq t_{i} \leq 6$ for any $i \leq n$ . The coefficient of $x^{k}$ in the following generating function is the number of solutions. $f (x) = (x + x^{2} + \dots + x^{6})^{n}$ Example generalization: a number of solutions of equation: $t_{1} + \dots + t_{n} = k$ . such that $p \leq t_{i} \leq q$ for any $i \leq n$ . The coefficient of $x^{k}$ in the following generating function is the number of solutions. $f (x) = (x^{p} + x^{p + 1} + \dots + x^{q - 1} + x^{q})^{n}$

Equation with Coefficients Greater than 1

Number of solutions of equation $a_{1} t_{1} + a_{2} t_{2} + \dots + a_{n} t_{n} = k$ . ^[question 7.13] The coefficient of $x^{k}$ in the following generating function is the number of solutions. $f (x) = (1 + x^{a_{1}} + x^{2 a_{1}} + \dots) (1 + x^{a_{2}} + x^{2 a_{2}} + \dots) \dots (1 + x^{a_{n}} + x^{2 a_{n}} + \dots)$

Partition

See Partition

Useful Generating Functions

Infinte Sum

Closed-form	GF $\sum_{k = 0}^{\infty} c_{k} x^{k}$	Sequence $c_{n}$	$c_{0}, c_{1}, \dots$
$\frac{1}{1 - x}$	$\sum_{k = 0}^{\infty} x^{k}$	$c_{n} = 1$	$1, 1, 1, \dots$
$\frac{1}{1 - x ^{r}}$	$\sum_{k = 0}^{\infty} x^{k r}$	$c_{n} = {10 if r ∣ n otherwise$	depends on a const. $r$
$\frac{1}{1 - a x}$	$\sum_{k = 0}^{\infty} a^{k} x^{k}$	$c_{n} = a^{n}$	$a, a^{2}, a^{3}, \dots$ ( $a$ is a const.)
$\frac{1}{1 - x ^{2}}$	$\sum_{k = 0}^{\infty} x^{2 k}$	$c_{n} = {10 if n is even if n is odd$	$1, 0, 1, 0, \dots$
$\frac{x}{1 - x ^{2}}$	$\sum_{k = 0}^{\infty} x^{2 k + 1}$	$c_{n} = {10 if n is odd if n is even$	$0, 1, 0, 1, \dots$
$\frac{1}{1 + x}$	$\sum_{k = 0}^{\infty} (- 1)^{k} x^{k}$	$c_{n} = {1 - 1 if n is even if n is odd$	$1, - 1, 1, - 1, \dots$
$e^{x}$	$\sum_{k = 0}^{\infty} \frac{x ^{k}}{k !}$	$c_{n} = \frac{1}{n !}$	$1, 1/2, 1/6, \dots$
$\frac{1}{( 1 - x ) ^{2}}$	$\sum_{k = 0}^{\infty} (k + 1) x^{k}$	$c_{n} = n + 1$	$1, 2, 3, \dots$
$\frac{x}{( 1 - x ) ^{2}}$	$\sum_{k = 0}^{\infty} k x^{k}$	$c_{n} = n$	$0, 1, 2, \dots$

Multiset coefficient

Closed-form	GF $\sum_{k = 0}^{\infty} c_{k} x^{k}$	Sequence $c_{n}$
$\frac{1}{( 1 - x ) ^{n}}$	$\sum_{k = 0}^{\infty} (k n + k - 1) x^{k}$	$(k n + k - 1)$
$\frac{1}{( 1 - x ) ^{2}}$	$\sum_{k = 0}^{\infty} (k + 1) x^{k}$	$k + 1$

Finte sum

Closed-form	GF $\sum_{k = 0}^{n} c_{k} x^{k}$	Coefficients $c_{k}$	$c_{0}, c_{1}, \dots, c_{k}, \dots, c_{n}$
$(1 + x)^{n}$	$\sum_{k = 0}^{n} (k n) x^{k}$	$c_{k} = (k n)$	$(0 n), (1 n), \dots, (k n), \dots, (n n)$
$(1 - x)^{n}$	$\sum_{k = 0}^{n} (- 1)^{k} (k n) x^{k}$	$c_{k} = (- 1)^{k} (k n)$	$(0 n), (1 - n), \dots, (k n), \dots, (n n)$
$(a + x)^{n}$	$\sum_{k = 0}^{n} (k n) a^{n - k} x^{k}$	$c_{k} = (k n) a^{n - k}$	$(0 n) a^{n}, (1 n) a^{n - 1}, \dots, (k n) a^{n - k}, \dots, (n n)$
$(1 + x^{r})^{n}$	$\sum_{k = 0}^{n} (k n) x^{r k}$	$c_{k} = {(k n) 0 if r ∣ k otherwise$	depends on a const. $r$
$(1 - x^{r})^{n}$	$\sum_{k = 0}^{n} (- 1)^{k} (k n) x^{r k}$	$c_{k} = {(- 1)^{k} (k n) 0 if r ∣ k otherwise$	depends on a const. $r$

OLD

	Generating function
basic	$\frac{1}{( 1 - x ) ^{n}} = \sum_{k = 0}^{\infty} (k n + k - 1) x^{k} = (1 + x + x^{2} + ...)^{n}$		$(k n + k - 1)$
multiplied by $(- 1)^{k}$	$\frac{1}{( 1 + x ) ^{n}} = \sum_{k = 0}^{\infty} (- 1)^{k} (k n + k - 1) x^{k} = (1 - x + x^{2} - ...)^{n}$		$(- 1)^{k} (k n + k - 1)$
$n = 2$	$\frac{1}{( 1 - x ) ^{2}} = \sum_{k = 0}^{\infty} (k + 1) x^{k} = 1 + 2 x + 3 x^{2} + \dots$	$1, 2, 3, \dots$	$k + 1$
$n = 2$ , and multiplied by $x$	$\frac{x}{( 1 - x ) ^{2}} = \sum_{k = 0}^{\infty} k x^{k} = x + 2 x^{2} + 3 x^{3} + \dots$	$0, 1, 2, \dots$	$k$
multiplied by $a^{k}$	$\frac{1}{( 1 - a x ) ^{n}} = \sum_{k = 0}^{\infty} a^{k} (k n + k - 1) x^{k} = (1 + a x + a^{2} x^{2} + ...)^{n}$		$a^{k} (k n + k - 1)$

useful identities of factoring out

$(x^{3} + x^{4} + \dots)^{n} = (x^{3})^{n} (1 + x + x^{2} + \dots)^{n}$
$(x + x^{2} + x^{4} + x^{5} + x^{7} + \dots)^{n} = (x + x^{2})^{n} (1 + x^{3} + x^{6} + \dots)^{n}$
$(1 + x^{2} + x^{3} + \dots)^{n} = (\frac{1}{1 - x} - x)^{n} = (1 - x (1 - x))^{n} \frac{1}{( 1 - x ) ^{n}} = (1 - x + x^{2})^{n} \frac{1}{( 1 - x ) ^{n}}$
$(1 - x)^{3} = (1 - x) (1 + x + x^{2})$

Explorer

Generating Functions

Formal Power Series

Operations

Generating Functions

Usage

Usage for number of solutions

Restrictions

Restriction for all Addends:

Equation with Coefficients Greater than 1

Partition

Useful Generating Functions

Infinte Sum

Multiset coefficient

Finte sum

OLD

useful identities of factoring out

Table of Contents

Backlinks