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.

2,844 questions
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 ...
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 ...
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\}$.
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 ...
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 ...
7k views

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 ...
750 views

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 ...
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 ...
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 ...
201 views

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\...
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^... 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 ... 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, ... 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 sumF(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 ...
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 ...