# 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 = \...