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,837 questions
16 views

Demonstration with Ferrers Diagram (Integer Partitions)

Demonstrate, using Ferrer Diagrams and partitions of an integer, the following identity: $$\sum_{k=1}^{r}2k - 1=r^{2}.$$ Explain why the parts are odd, distinct, and consecutive (they differ exactly ...
12 views

Extinction probability of modificated branching process

From An Intermediate Course in Probability by Allan Gut: Consider the following modification of a branching process: A mature >individual produces Children according to the generateing function g(...
31 views

Anagrams with n letters and Generating Functions.

Find an exponential generating function for ${a_r}$ , the number of $r-letter$ words with no vowel used more than once (consonants can be repeated). The answer is $(1 + x)^5e^{21x}$. One solution I ...
19 views

97 views

Sum with Bernoulli numbers

How to prove that: $$\sum_{k=0}^n \binom n k 2^k B_k = (2-2^n)B_n$$ In this sum, $B_n$ is the Bernoulli number with $B_1 = -\frac 1 2$. Thanks for your attention!
45 views

Bounded generated function

I am trying to understand Allen Schwenk's 1973 article "Almost all trees are cospectral" on spectral graph theory, (https://www.researchgate.net/publication/245264768_Almost_all_trees_are_cospectral) ...
86 views

What's the number of natural solutions of $x_1 + 2x_2 + 3x_3 = n$?

$$x_1 + 2x_2 + 3x_3 = n, \qquad x_1, x_2, x_3 \geq 0$$ Find a regression formula (or a recursive function, not sure how it's called in English) to calculate the number of solutions for all $n≥0$. ...
64 views

Understanding a formula for coefficients $a_n$ of the generating function$\sum_{n \ge 0} a_nx^n=\frac{1}{\sqrt{1-x}}$.

(HMMT 2019 Alge/NT 8) I am trying to understand the solution of this problem, but I don’t understand how the condition described in the title lead to $a_n=\frac{_{2n}C_n}{4^n}$ Does it have anything ...
31 views

16 views

Multi-folds of Generating Functions

Stochastic Process Generating Function Practice I don't understand how $G_{N}(s) = G_{M}(G_{Y_i}(s))$. $N = Y_1 + Y_2 + Y_3 + ... +Y_M$, which to my understanding the main generating function should ...
59 views