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
40 views

Generating function of a parametrized binomial coefficient

Let be $m$ an integer and $A_p(m) = \binom{mp}{p}$. I'd like to know more about $B_m(z) = \sum_{p \geq 0} A_p(m) z^p$. At least, I'd love to be able to compute $B_m\left(\dfrac{1}{q}\right)$ for ...
21 views

Extraction of coefficient from Generating Function with partitions

Determine the coefficient of $~x ^ {15}~$ in: $(1+𝑥^3+𝑥^6+𝑥^9+𝑥^{12}+𝑥^{15})(1+𝑥^6+𝑥^{12})(1+𝑥^9)$ How to use the fact that the desired coefficient is the number of partitions of 15 in parts ...
29 views

Extraction of coefficient from Generating Function

Determine the coefficient of $~x ^ {12}~$ in: $(1+𝑥^2+𝑥^4+𝑥^6+𝑥^8+𝑥^{10}+𝑥^{12})(1+𝑥^4+𝑥^8+𝑥^{12})(1+𝑥^6+𝑥^{12})(1+𝑥^8)(1+𝑥^{10})(1+𝑥^{12})$ How to proceed with the resolution of this ...
41 views

Partitions of an integer with polynomials

Determine the coefficients of the polynomial $$a_0 + 𝑎_1𝑥_1 + 𝑎_2𝑥_2 + 𝑎_3𝑥_3 + ⋯ + 𝑎_𝑟𝑥_𝑟$$ that has the property that $~𝑎_𝑛 = 𝑝~$ . Where $p$ is the number of partitions of $n$ composed ...
17 views

Number of partitions of an odd number

Provide a generic formula for the number of partitions of an odd number $n$ in that one part has even value and another part has odd value. How to approach this problem using generating functions?
23 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(...
11 views

36 views

Recurrence relation using generating function no solution

I have a problem with the solution of this recurrence relation:$$a_{n+2}=2a_{n+1}-a_n+1\qquad(n≥1),\ a_0=0,\ a_1=1$$ I found the generating function, then I used partial fraction decomposition to ...
19 views

Find the number of ways to choose $7$ integers Generating Funciton

Find the number of ways to choose $7$ integers from $\{1, 2,.., x\}$ where the gap between the smallest integer and the 2nd smallest one is at least $5$, and the gap between the 2nd and 3rd smallest ...
23 views

Expanding a generating function in a series

For a given recurrence relation the generating function is A(x)=$\frac{x}{(1-x)(1-2x)}$. Then the book says that if we want to find an explicit formula for the $a_n$'s we would have to expand A(x) in ...
40 views

Anagrams with Generating Functions

Consider the letters {a, b, c, d}. How many 5-letter sequences containing an even number of b's and odd d's exist? How to approach this problem using generating functions?
22 views

Selection of objects with generating functions

Use generating functions to find the number of ways to choose $r$ objects of $n$ different types, knowing that we must choose at least 1 object of each type. How can we express in the solution that ...
26 views

Formation of commissions with generating functions

Representatives of three research institutes should form a commission of 9 researchers. How many ways can this committee be formed such that no institute should have an absolute majority in the group? ...
36 views

Generating Function functional relation

Suppose I have a generating function which I know satisfies the relation $$x = T(x) (1 - x - T(x^2)).$$ Can I say anything about the coefficients? Ideally I would be able to get some kind of closed ...
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-...
17 views

67 views

Find B(x) such that $A(x) = P(x) \cdot B(x)$

A(x) is enumerator (generating function) of partitions of number such that contain exactly $1$ (but maybe multi times) of $2,3,5$. P(x) is enumerator of all partitions. Find compact pattern for $B(x)$ ...
11 views

A(x) is the generating function of the series $\{a_n\}^\infty$ ( n from 0), what generates,$f_n=(-1)^na_n$

A(x) is the generating function of the series $\{a_n\}^\infty$ ( n from 0) I am given the series $f_n=(-1)^na_n$ and need to find the function F(x). I thought that because the function $1/(1+x)$ ...
277 views

Average number of inversions in an involution

I'm working through some exercises in Sedgewick's Analysis of Algorithms, but I'm stuck on 7.45: Find the CGF for the total number of inversions in all involutions of length $N$. Use this to find ...
97 views

Proof needed for the combinatorial identity $\sum_{a=0}^n\binom{n+a}{a}/{2^{n+a}}=1$ [duplicate]

I need some algebraic and combinatorial proofs for the following. $$\sum_{a=0}^n\frac{\binom{n+a}{a}}{{2^{n+a}}}=1.$$ Every kind of using combinatorial consideration, generating function, algebraic ...
25 views

Finding formula for generating function coefficient

You have $n$ stones. You break the stones into some number of groups, and place the stones within each group into a line. You then arrange these lines in a circle. Let $s_n$ be the number of ways to ...
28 views

what is exponential generating function with n Choose k as coefficient

If we fix a positive integer $k$, what is the EGF of $\sum_{n=0} \binom{n}{k} \frac{x^n}{n!}$ ? I know EGF of $\sum_{n=0}\frac{x^n}{n!}$ is $e^x$, but the addition of $\binom{n}{k}$ confuses me
23 views

Express in closed form: $\sum_{i=0}^n (-1)^i (\binom{n}{i})^2$ [duplicate]

I know the answer is 0 for odd $n$, but I’m not sure what to do for even $n$. Any help would be appreciated!
14 views

Let $f(n)$ the number of partitions on $n$ with distinct parts. Let $g(n)$ be the number of partitions with odd parts only. Show $f(n)=g(n)$ [duplicate]

I have no clue how to start. Any hint would be appreciated!
12 views

Prove $\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=4^n$ [duplicate]

My approach: change $4^n$ to $2^{2n}$, then we're trying to show $\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=\sum_{k=0}^{2n} \binom{2n}{k}$, but then I got stuck. Any help would be appreciated.
30 views

Karmata's proof of Hardy-Littlewood Tauberian theorem

I understand Karamata's proof of Hardy Littlewood Tauberian theorem as http://individual.utoronto.ca/jordanbell/notes/karamata.pdf, but what on earth is the motivation behind Lemma 4 - i.e what would ...
38 views

Find generating function for $\sum_{n\ge 0} \binom{m+n}{n}x^n$, $m \in\mathbb{Z}$

I’ve tried applying Vandermonde’s identity, but got stuck. Any help would be appreciated!
38 views

99 views

solving a problem with generating functions

This is a problem from a course of MIT. Find the coefficients of the power series $y = 1 + 3 x + 15 x^2 + 184 x^3 + 495 x^4 + \cdots$ satisfying $$(27 x - 4)y^3 + 3y + 1 = 0 .$$ This is an ...
45 views

Finding exponential generating function

A teacher has $n$ students and breaks the students up into some number of groups. Within each group, they assign one student to be a president and another to be a vice president. Let $t_n$ be the ...
41 views

Finding closed form of exponential generating function involving identity permutation

Fix a prime number $p > 1$ and for a positive integer $n$, let $a_n$ be the number of permutations $π ∈ S_n$ such that $π^p = id$, where $id$ is the identity permutation. Find a closed form for the ...
Let $S(n, k)$ be the Stirling number of the second kind. For a fixed positive integer $k$, find a closed form for the exponential generating function $B(x) = \sum_{n\ge0}S(n,k)\frac{x^n}{n!}$. I ...
Given that I have two formal power series: $$A(x) = \sum_{k \ge 0} a_k x^k$$ $$B(x) = \sum_{k \ge 0} b_k x^k$$ The Cauchy Product gives a series $$C(x) = \sum_{k \ge 0} c_k x^k$$  c_k = \...