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
votes
1answer
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 ...
0
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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?
0
votes
1answer
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(...
0
votes
0answers
11 views

Walk generating function for adjacency matrix

In its book "Random Walks on Infinite Graphs and Groups", W. Woess defines the Green function (or walk generating function) as $$G(x,y|z) = \sum_{n = 0}^{\infty} p^{(n)}(x,y)z^n, \quad x, y \in X, z \...
-2
votes
0answers
16 views

use generating function to solve distribution problem

use generating function to solve this problem.50 Person,30 Presents,everybody can get one present ,how many solutions can we distrubute these presents?
0
votes
0answers
45 views

General formula for $n$-th derivative [on hold]

This question has 3 parts, please try to answer all of them I have been struggling since a long time Can anyone show me how to derive this summation for the value of the nth derivative at x=0 for ...
1
vote
3answers
196 views

Solving the recurrence $a_{n+2} = 3a_{n+1} - 2a_n, a_0 = 1, a_1 = 3$ using generating functions

Solve the following recurrence using generating functions: $a_{n+2} = 3a_{n+1} - 2a_n, a_0 = 1, a_1 = 3$. My partial solution: We can rewrite $a_{n+2} = 3a_{n+1} - 2a_n$, as $a_{n+2} - 3a_{n+1} + ...
1
vote
2answers
72 views

General formula for the value of the $n$th derivative at $x=0$

Can anyone show me how to derive this summation for the value of the $n$th derivative at $x=0$ for this function: $\frac{d}{dx^n}(\exp({\frac{x^2}{2}+x}))$ is this sum: $\frac{d}{dx^n}(\exp({\frac{...
1
vote
1answer
36 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 ...
4
votes
0answers
80 views

How to solve the recurrence relation $a_{1}=2, a_{n}=\frac{a_{n-1}+2}{2 a_{n-1}+1}(n \geq 2)$ with generating functions?

There's already a way to solve it, called "fixed point method", that is, from the relation we define its characteristic equation as $x=\dfrac{x+2}{2x+1}$,then we have $x_1=1,x_2=-1$. So the following ...
1
vote
0answers
21 views

Coefficient Analysis and Saddle Point Method for Bivariate Generating Series

I am trying to analyze a bivariate generating function. I will explain the parameters later. Let: $$ S^k_{D,d}(X,Y) = \frac{(1+XY)^2(1+X)^{n-k}}{(1+X^2Y^2)^m(1-X)(1-Y)} - \frac{(1+X)^n}{(1+X^2)^m(1-...
0
votes
1answer
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 ...
2
votes
1answer
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 ...
0
votes
3answers
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 ...
0
votes
1answer
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?
0
votes
1answer
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 ...
1
vote
1answer
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? ...
2
votes
2answers
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 ...
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-...
0
votes
1answer
17 views

what series the function $1/(1-ax)^r, a,r\in N $ generats.

I want to kmow what series the function $1/(1-ax)^r, a,r\in N $ generats. I thoghut about doing this: lets name y=ax now we have $1/(1-y)^r, r\in N $ and we know $1/(1-y)^r= \sum_{n=0}^{\infty}{n+r-...
-4
votes
1answer
45 views

What's the coefficient of $x^n$

I need to find the coefficient of $x^n$ in the following convolution $$\sum_{i=0}^{\infty} \frac{2^i}{i!}x^i \times \sum_{i=0}^{\infty} \frac{3^i}{i!}x^i$$ I didn't get too far, I tried just a ...
0
votes
1answer
39 views

Recurrence relation with generating function question

I have to solve the recurrence relation: $$a_n=a_{n-1}+n\quad(n\geq1), \quad a_0=0$$ with generating function. The final result I think should be: $a_n=\frac {n(n+1)}2$, but I don't know how to get it ...
1
vote
0answers
22 views

Asymptotics of the probability of passengers on wrong airplane seats

In this answer Jack D'Aurizio asserts that the probability $W(s,k)$ of $k$ passengers taking wrong seats on a plane capacity of $s$ seats, or the generating function coefficient $[x^k]g(s,x)$, ...
0
votes
1answer
1k views

How many ways can you make change for a dollar?

This is a generic generating functions problem, and you are left with 1/(x-1)(x^5-1)....(x^50-1) however now I want to find the coefficient of the x^100 term of this expression... how can I do this or ...
0
votes
1answer
45 views

I'm having trouble finding the sequence generated by this function.

$f(x)=\frac{1}{e^x(1-x)}$ I'm aware that $e^x$ generates $1,\frac{1}{1!},\frac{2}{2!},\frac{3}{3!}...$ And I think that $\frac{e^x}{(1-x)}$ generates $a_n=\sum_{i=0}^{n}{\frac{1}{i!}}$
1
vote
1answer
31 views

Creating a generating function for the Stirling transform

Does there exist a sequence $c_n$ such that $$S(n, k) = \frac{c_n}{c_k c_{n - k}}$$ for $0 \leq k \leq n$, where $S(n, k)$ are the Stirling numbers of the second kind? I ask because I'm trying to ...
0
votes
0answers
25 views

partition function - using each number once and using only odd numbers

1)I was asked to find a partition function , where each number appears only once. for example, for n=2 - 1+1 is not good but 2 is. I think the function is : $\prod\limits_{k=1}^{\infty}(1+q)^k$,...
0
votes
3answers
46 views

Generating functions with power series

How to find the series expansion for generating function $\frac {1} {1-2x-x^2}$? I have got so far $$\frac {1} {1-2x-x^2}=-\frac {1} {2\sqrt2} (\frac {1} {1-\sqrt2+x} -\frac {1} {1+\sqrt2+x})$$ $\...
0
votes
1answer
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)$ ...
0
votes
1answer
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)$ ...
9
votes
2answers
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 ...
2
votes
0answers
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 ...
1
vote
1answer
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 ...
1
vote
1answer
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
0
votes
0answers
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!
1
vote
0answers
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.
1
vote
0answers
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 ...
2
votes
2answers
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!
0
votes
0answers
38 views

Density of a set of numbers equal to limit at 1

Let $S(x) = \sum_{i \geq 0}a_ix^i \in \mathbb{R}[[x]]$. How do I prove that $\displaystyle \lim_{n \rightarrow \infty} \frac{\sum_{1 \leq i \leq n} a_i}{n}$ exists iff $\displaystyle \lim_{x \...
3
votes
3answers
142 views

Number of 1's among all partitions of an integer

I am trying find a recurrence relation for the number of 1's among all partitions of an integer. The OEIS database has an entry mentioning this particular sequence but does not give a recurrence ...
1
vote
2answers
61 views

Find formula for generating function of sequence [duplicate]

My task is to find formula for generating function of sequence $a_0, a_1...$ defined with following recurence $a_0=1$ and $a_n=\sum_{i=0}^{n-1} (n-i)a_i$. I rewrote the expression $a_n=\sum_{i=0}^{...
2
votes
4answers
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 ...
1
vote
1answer
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 ...
2
votes
1answer
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 ...
0
votes
0answers
71 views

Finding closed form of exponential generating function

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 ...
6
votes
4answers
3k views

Formal power series coefficient multiplication

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