Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
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 ...
0
votes
0answers
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(...
1
vote
1answer
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 ...
1
vote
0answers
19 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-...
1
vote
2answers
62 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{...
0
votes
1answer
35 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
18 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
19 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
36 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
16 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
25 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
33 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 ...
0
votes
1answer
15 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-...
-6
votes
1answer
40 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
44 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
30 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
24 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
1answer
10 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)$ ...
2
votes
0answers
96 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
24 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
27 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.
0
votes
1answer
65 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)$ ...
1
vote
0answers
29 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 ...
0
votes
0answers
37 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 \...
2
votes
2answers
37 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!
4
votes
0answers
77 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
1answer
43 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
40 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
69 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 ...
1
vote
2answers
58 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
97 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
4answers
54 views

More elegant way of finding generating function coefficient

I am looking to find the number of ways to pay a £50 bill in £1 and £2 coins. The generating function for this is $g(x)=(1+x+...)(1+x^2+...)$, which after a few lines of algebra becomes $g(x) = \sum_{...
2
votes
2answers
68 views

Euler sum with Bernoulli numbers

In many sources, I find such equality: $$\dfrac{1}{n}\sum_{k=1}^n \binom n k B_kB_{n-k}+B_{n-1}=-B_n$$ where $B_1=-\dfrac{1}{2}$ $$$$However, there don't write how to get it. I think that it's ...
4
votes
2answers
72 views

Sum with Bernoulli polynomial

I'm trying to prove the following identity: $$\sum_{k=0}^n \dfrac {\binom n k B_k(x)} {(n-k+1)} = x^n$$ I transformed this identity as follow: $$\dfrac{1}{(n+1)}\sum_{k=0}^n \binom {n+1} k B_k(x) = x^...
4
votes
2answers
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!
0
votes
0answers
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) ...
1
vote
3answers
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$. ...
2
votes
3answers
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 ...
1
vote
2answers
31 views

How to find a generating function that has only coefficients $a_n \equiv 0~(mod~k)$ from the generating function for $\{a_n\}$?

I am trying to work through a few problems, and one asks to sum over the Fibonacci numbers which are even-valued (it is the Euler Project problem #2). I realized that (if we index like $\langle 1, 2, ...
2
votes
1answer
40 views

Characterization of the geometric distribution

$X,Y$ are i.i.d. random variables with mean $\mu$ , and taking values in {$0,1,2,...$}.Suppose for all $m \ge 0$, $P(X=k|X+Y=m)=\frac{1}{m+1}$ , $k=0,1,...m$. Find the distribution of $X$ in terms of $...
0
votes
0answers
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 ...
0
votes
2answers
59 views

Solving a recurrence relation such that $\sum_{k=0}^\infty x_k = 1$

Question Let $x_0$ be arbitrary, $p \in (0,1)$ and assume the following holds: $$x_1=\frac{(1-p)^2(1+2p)}{p^3}x_0$$ $$x_2=\frac{(1-p)^3(1+3p-3p^3)}{p^6}x_0$$ and in general: $$ x_k(1-p)^3 + 3p(1-p)^2 ...
1
vote
1answer
32 views

Is it possible to “invert” an exponential generating function?

Consider the exponential generating function for a sequence $\mathbf{a}$, given by: $$\text{EG}_\mathbf{a}(x) = \sum_{n=0}^\infty a_n \frac{x^n}{n!}.$$ In order to find the sequence $\mathbf{a}$ ...
0
votes
1answer
29 views

Properties of the probability generating function

My understanding of PGF is that it is just an efficient way to find the properties of the distribution (mean variance etc) and represents the whole distribution, and there isn’t really any meaning to ...
43
votes
3answers
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 ...