Questions tagged [generating-functions]

Generating functions are formed by making a series $\sum_{n\geq 0} a_n x^n$ out of a sequence $a_n$. They are used to count objects in enumerative combinatorics.

84
votes
4answers
9k views

Factorial and exponential dual identities

There are two identities that have a seemingly dual correspondence: $$e^x = \sum_{n\ge0} {x^n\over n!}$$ and $$n! = \int_0^{\infty} {x^n\over e^x}\ dx.$$ Is there anything to this comparison? (I ...
43
votes
3answers
2k views

Expected maximum number of unpaired socks

Like all combinatoric problems, this one is probably equivalent to another, well-known one, but I haven't managed to find such an equivalent problem (and OEIS didn't help), so I offer this one as ...
39
votes
4answers
33k views

The generating function for the Fibonacci numbers

Prove that $$1+z+2z^2+3z^3+5z^4+8z^5+13z^6+...=\frac{1}{1-(z+z^2)}$$ The coefficients are Fibonacci numbers, i.e., the sequence $\left\{1,1,2,3,5,8,13,21,...\right\}$.
38
votes
7answers
7k views

Why are generating functions useful?

I was under the mistaken impression that if one could find the generating function for a sequence of numbers, you could just plug in a natural number $n$ to find the nth term of the sequence. I ...
38
votes
2answers
941 views

Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

In attempting to answer this question, I reduced it to a seemingly simple generating functions question, but after days of work was unable to construct a proof. Since I do not have experience trying ...
36
votes
2answers
7k views

Why do engineers use the Z-transform and mathematicians use generating functions?

For a (complex valued) sequence $(a_n)_{n\in\mathbb{N}}$ there is the associated generating function $$ f(z) = \sum_{n=0}^\infty a_nz^n$$ and the $z$-Transform $$ Z(a)(z) = \sum_{n=0}^\infty a_nz^{-n}$...
35
votes
7answers
2k views

How are we able to calculate specific numbers in the Fibonacci Sequence?

I was reading up on the Fibonacci Sequence, $\text {{1,1,2,3,5,8,13,....}}$ when I've noticed some were able to calculate specific numbers. So far I've only figured out creating an array and counting ...
35
votes
5answers
2k views

A nice but somewhat challenging binomial identity

When working on a problem I was faced with the following binomial identity valid for integers $m,n\geq 0$: \begin{align*} \color{blue}{\sum_{l=0}^m(-4)^l\binom{m}{l}\binom{2l}{l}^{-1} \sum_{k=0}^n\...
32
votes
5answers
1k views

Unexpected Proofs Using Generating Functions

I recently came across this beautiful proof by Erdős that uses generating functions in a unique way: Let $S = \{a_1, \cdots, a_n \}$ be a finite set of positive integers such that no two subsets of ...
31
votes
4answers
835 views

A sequence of coefficients of $x+(x+(x+(x+(x+(x+\dots)^6)^5)^4)^3)^2$

Let's consider a function (or a way to obtain a formal power series): $$f(x)=x+(x+(x+(x+(x+(x+\dots)^6)^5)^4)^3)^2$$ Where $\dots$ is replaced by an infinite sequence of nested brackets raised to $n$...
29
votes
2answers
5k views

Connection between the Laplace transform and generating functions

As I was sitting through a boring lecture rehashing basic techniques to solve ordinary differential equations, I began thinking about the Laplace transform and scribbled down a few ideas that I've ...
27
votes
3answers
3k views

Any ideas on how I can prove this expression?

I don't have a lot of places to turn because i am still in high school. So please bear with me as i had to create some notation. In order to understand my notation you must observe this identity for ...
27
votes
7answers
20k views

Making Change for a Dollar (and other number partitioning problems)

I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the one quoted ...
26
votes
5answers
3k views

When the product of dice rolls yields a square

Succinct Question: Suppose you roll a fair six-sided die $n$ times. What is the probability that the product of the rolls is a square? Context: I used this as one question in a course for ...
26
votes
1answer
903 views

What is the intuition behind generating functions? What makes them valuable?

I'm sorry if this question makes no sense. I have been reading generatingfunctionology and I have been able to solve the problems in the first chapters and I understand the mechanism I have to follow ...
25
votes
3answers
12k views

How many connected graphs over V vertices and E edges?

Is there a way to calculate the number of simple connected graphs possible over given edges and vertices? Eg: 3 vertices and 2 edges will have 3 connected graphs But 3 vertices and 3 edges will have ...
25
votes
1answer
410 views

Odd digits of $2^n$

Let $u_{b}(n)$ be equal to to number of odd digits of $n$ in base $b$. For example: In base $10$, $u_{10}(15074) = 3$ In base $13$, $u_{13}(15610) = u_{13}([7, 1, 4, 10]_{13}) = 2$ What is the ...
21
votes
4answers
10k views

Generating functions for combinatorics

I have no formal education in generating functions, but, based on another question, I have seen that they can be powerful for combinatorics. Are there a few general principles for using generating ...
21
votes
4answers
424 views

How can I learn about generating functions?

The intent of this question is to provide a list of learning resources for people who are new to generating functions and would like to learn about them. I'm personally interested in combinatorics, ...
19
votes
1answer
910 views

What function satisfies $F'(x) = F(2x)$?

The exponential generating function counting the number of graphs on $n$ labeled vertices satisfies (and is defined by) the equations $$ F'(x) = F(2x) \; \; ; \; \; F(0) = 1 $$ Is there some closed ...
19
votes
3answers
302 views

If $\sum\limits_{n=1}^{\infty}\frac{1}{p(n)}\in\mathbb{Q}$, is $\sum\limits_{n=1}^{\infty}\frac{n}{p(n)}\in\mathbb{Q}$?

Suppose $p(n)$ is a polynomial with rational coefficients and rational roots of degree at least $3$. If we know $$\sum_{n=1}^{\infty}\frac{1}{p(n)}\in\mathbb{Q}$$ are we able to infer that $$\sum_{n=...
18
votes
3answers
1k views

Solving the recursion $3a_{n+1}=2(n+1)a_n+5(n+1)!$ via generating functions

I have been trying to solve the recurrence: \begin{align*} a_{n+1}=\frac{2(n+1)a_n+5((n+1)!)}{3}, \end{align*} where $a_0=5$, via generating functions with little success. My progress until now is ...
18
votes
5answers
750 views

Splitting $r^k (r+n)!$ as a sum of factorials

I wanted to split the expression $r^k (r+n)!$ as a sum of factorials, where $k ,n \ \in \ \mathbb{Z} \ ;\ k>0$. For example, $r(r+n)! = (r+n+1)! - (n+1)(r+n)!$ $r^2(r+n)! = (r+n+2)! - (2n+3)(r+...
17
votes
7answers
1k views

Proving a binomial sum identity $\sum _{k=0}^n \binom nk \frac{(-1)^k}{2k+1} = \frac{(2n)!!}{(2n+1)!!}$

Mathematica tells me that $$\sum _{k=0}^n { n \choose k} \frac{(-1)^k}{2k+1} = \frac{(2n)!!}{(2n+1)!!}.$$ Although I have not been able to come up with a proof. Proofs, hints, or references are all ...
17
votes
6answers
973 views

Generating function for binomial coefficients $\binom{2n+k}{n}$ with fixed $k$

Prove that $$ \frac{1}{\sqrt{1-4t}} \left(\frac{1-\sqrt{1-4t}}{2t}\right)^k = \sum\limits_{n=0}^{\infty}\binom{2n+k}{n}t^n, \quad \forall k\in\mathbb{N}. $$ I tried already by induction over $k$ but i ...
17
votes
1answer
336 views

How to compute the coefficients of this generating function

Working on some combinatorial problem, I arrived at the following generating function $$K_m(x) = \sum_{n\geq 0}K_{mn}x^n =\frac{x}{1-\sqrt{1+x^2}\cdot\frac{\displaystyle{y_+(x)^{m+1}+y_-(x)^{m+1}}}{\...
16
votes
3answers
1k views

Why is generating function proof of Fibonacci formula correct?

The proof goes as follows:- Let $F = 1 + x + 2x^2 + 3x^3 + 5x^4 + 8x^5 + ...$ Then $$\begin{align} 1 + Fx + Fx^2 &= 1 + (x + x^2 + 2x^3 + 3x^4 + ...) + (x^2 + x^3 + 2x^4 + 3x^5) \\ 1 + Fx + Fx^...
16
votes
3answers
1k views

How do I prove this combinatorial identity

Show that $${2n \choose n} + 3{2n-1 \choose n} + 3^2{2n-2 \choose n} + \cdots + 3^n{n \choose n} \\ = {2n+1 \choose n+1} + 2{2n+1 \choose n+2} + 2^2{2n+1 \choose n+3} + \cdots + 2^n{2n+1 \choose ...
16
votes
2answers
3k views

Generating function with Stirling's numbers of the second kind

It's very easy to prove that: $$\sum_k \left\{k\atop n\right\}z^k=\frac{z^n}{(1-z)(1-2z)...(1-nz)}$$ But this generating function looks very pretty, so my question is: does this identity have some ...
16
votes
2answers
59k views

Finding the Moment Generating function of a Binomial Distribution

Suppose $X$ has a $\rm{Binomial}(n,p)$ distribution. Then its moment generating function is \begin{align} M(t) &= \sum_{x=0}^x e^{xt}{n \choose x}p^x(1-p)^{n-x} \\ &=\sum_{x=0}^{n} {n \...
15
votes
0answers
375 views

Random sum in coupon collection

I have a problem which involves the standard coupon collector's problem to find a probability density from the generating convolution. I start by defining the problem and a few basic statistics. Let ...
14
votes
1answer
1k views

Integral Representation of Infinite series

Let's take a look at the following integrals : 1) $\displaystyle \int\limits_{0}^{1} \frac{\log{x}}{1+x} \ dx = -\frac{\pi^{2}}{12} = -\frac 1 2 \sum\limits_{n=1}^{\infty} \frac{1}{n^2}= -\frac 1 2 \...
14
votes
4answers
1k views

Number of connected graphs on labeled vertices, counted according to parity

While trying to derive some formula, I encountered the following problem. Consider the set $C_n$ of all connected graphs on $n$ vertices. What is $$ \sum_{G \in C_n} (-1)^{|G|} ? $$ In other words, if ...
14
votes
1answer
293 views

Deriving the asymptotic estimate (9.62) in Concrete Mathematics

I was reading Chapter 9: Asymptotics in Graham, Knuth, Patashnik: Concrete Mathematics, and I got stuck while deriving the following asymptotic estimate on page 466: $$ \begin{equation} g_n = \frac{...
14
votes
1answer
668 views

What is the combinatoric significance of an integral related to the exponential generating function?

Suppose that you have an exponential generating function.: $E(z)=\sum_{n=0}^{\infty} \frac{a_{n}z^{n}}{n!}$, and that the definition of $a_{n}$ can be reasonably extended to noninteger arguments. (the ...
14
votes
1answer
859 views

Equation about generating functions and subfactorial

Suppose $G_n(w)$ is a formal power series (really a probability generating function, see the following explanation) of variable $w$, try to solve out $G_n(w)$ for all $n\ge0$ from the formal-power-...
13
votes
7answers
8k views

Using generating functions find the sum $1^3 + 2^3 + 3^3 +\dotsb+ n^3$

I am quite new to generating functions concept and I am really finding it difficult to know how to approach problems like this. I need to find the sum of $1^3 + 2^3 + 3^3 +\dotsb+ n^3$ using ...
13
votes
4answers
7k views

Exponential Generating Function For Derangements

I have been introduced to the concept of exponential generating functions a few days ago. However, my understanding of them are still quite limited, and I would like to see some examples. Earlier this ...
13
votes
3answers
1k views

Harmonic Numbers series I

Can it be shown that \begin{align} \sum_{n=1}^{\infty} \binom{2n}{n} \ \frac{H_{n+1}}{n+1} \ \left(\frac{3}{16}\right)^{n} = \frac{5}{3} + \frac{8}{3} \ \ln 2 - \frac{8}{3} \ \ln 3 \end{align} where $...
13
votes
1answer
585 views

Why is it important to have the closed form of a generating function?

I am having introductory lectures on combinatorial analysis, I've been presented to the concept of generating functions and it's applications to solving combinatorial problems. The generating function ...
13
votes
4answers
960 views

Why would you take the logarithmic derivative of a generating function?

Today, my climbing expedition scaled Mt. Sloane to request the Oracle's Extensive Insight into Sequences. The monks there had never heard of our plight, so they inscribed our query in mystical runes ...
13
votes
3answers
412 views

Words built from $\{0,1,2\}$ with restrictions which are not so easy to accomodate.

We assume a ternary alphabet $V=\{0,1,2\}$ and are looking for a generating function describing the number of words of $V^*$ fulfilling certain restrictions. The words I am interested in do not ...
13
votes
1answer
201 views

What is the number of squares in $S_n$?

Let $$X_n=\{\sigma\mid\sigma=\tau^2 \text{ for some }\tau\in S_n\}.$$ What is the cardinality of $X_n$? For example, permutation $(12)(3456)$ is not a square in S_n. I know that $X_n=A_n$ for $n\leq ...
13
votes
2answers
345 views

Generalized Harmonic Number Summation $ \sum_{n=1}^{\infty} {2^{-n}}{(H_{n}^{(2)})^2}$

Prove That $$ \sum_{n=1}^{\infty} \dfrac{(H_{n}^{(2)})^2}{2^n} = \tfrac{1}{360}\pi^4 - \tfrac16\pi^2\ln^22 + \tfrac16\ln^42 + 2\mathrm{Li}_4(\tfrac12) + \zeta(3)\ln2 $$ Notation : $ \...
13
votes
1answer
408 views

Prove that $\exp(\log(\frac{1}{1-x})) = \frac{1}{1-x}$

I am trying to prove this directly by comparing the coefficients in the two series rather than using formal calculus. Here is what I have so far, but I think I made a mistake: \begin{align*} e^{\log\...
13
votes
1answer
980 views

Generalizing Ramanujan's sum of cubes identity?

Ramanujan's sum of cubes identity is defined by the generating functions, $$\begin{aligned} \sum_{n=0}^\infty a_n x^n &= \frac{1+53x+9x^2}{R_1}\\ \sum_{n=0}^\infty b_n x^n &= \frac{2-26x-12x^...
13
votes
1answer
573 views

Challenging identity regarding Bell polynomials

Note: [2015-03-08] A proof of the identity below was aimed to close the gap of a rather extensive elaboration of this answer of mine. The identity (1) below is part of a more complex one, which is ...
13
votes
1answer
437 views

Finding a combinatorial formula for the following sequence of tables

While studying a subject in mathematical physics and topology (which is not necessarily relevant to this question anyway), I bumped into the following sequence of tables, let's call them $M_0, M_1, ...
12
votes
3answers
397 views

Dealing with a difficult sum of binomial coefficients, $\sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j} $

I am interested in finding an upper bound for the sum $$F(n)= \sum_{l=0}^{n}\binom{n}{l}^{2}\;\sum_{j=0}^{2l-n}\binom{l}{j}$$ Ideally it should be possible to evaluate it exactly using some ...
12
votes
1answer
1k views

Generating functions for context-free languages

I have a question about context free grammars and their relationship with generating functions. It is well-know how to associate a generating function $\mathsf{gf}{(R)}$ with a non-ambiguous regular ...