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.

4
votes
1answer
1k views

Finding a generating function for the Laguerre polynomials

I've started learning some quantum physics and one often encounters special functions (like Legendre polynomials, Laguerre polynomials, Bessel functions, ...). Many calculations with these functions ...
9
votes
2answers
1k views

Generating function for permutations in $S_n$ with $k$ cycles.

I was reading a little bit about Galois theory, and read that some computer algebra software try to compute Galois groups by finding cycle types. Anyway, this led me to a curious question. If I fix ...
2
votes
1answer
111 views

Is there a simple expression for this generating function that is almost like the binomial formula?

This is a curiosity I when looking at the binomial theorem. Say you have an ordinary generating function $\displaystyle\sum_{n,m\geq 0}\binom{n}{m}x^ny^m$. This looks kind of like $\displaystyle\sum_{...
4
votes
4answers
868 views

Find the ordinary generating function $h(z)$ for a Gambler's Ruin variation.

Assume we have a random walk starting at 1 with probability of moving left one space $q$, moving right one space $p$, and staying in the same place $r=1-p-q$. Let $T$ be the number of steps to reach 0....
0
votes
2answers
94 views

What is the generating function for these word types?

I'm curious to see what the generating function is for numbers of some words with a few constraints. Let's fix some $m$, and I'll denote by $[m]$ the set of $m$ symbols, say $\{1,2,\dots,m\}$. Now ...
4
votes
1answer
919 views

The generating function for permutations indexed by number of inversions

For $\sigma\in S_n$ an inversion is a pair $(\sigma_i,\sigma_j)$ such that $i<j$ and $\sigma_i>\sigma_j$. Could you help me to prove that the generating function of $S_n$ by number of ...
4
votes
1answer
82 views

Generating Functions: how do I get my answers in terms of differential operators?

I'm reading and enjoying "generatingfunctionology". What a great fun book! But, I'm having some difficulty with the exercises. For example, take the series $a_n = n^2$ I'd like to find the Generating ...
4
votes
4answers
713 views

How to get closed form from generating function?

I have this generating function: $$\frac{1}{2}\, \left( {\frac {1}{\sqrt {1-4\,z}}}-1 \right) \left( \,{ \frac {1-\sqrt {1-4\,z}}{2z}}-1 \right)$$ and I know that $\frac {1}{\sqrt {1-4\,z}}$ is ...
3
votes
2answers
199 views

Solving $A(x) = 2A(x/2) + x^2$ Using Generating Functions

Suppose I have the recurrence: $$A(x) = 2A(x/2) + x^2$$ with $A(1) = 1$. Is it possible to derive a function using Generating Functions? I know in Generatingfunctionology they shows show to solve ...
3
votes
2answers
364 views

how to find generating function with nested sums

I'm trying to figure out the generating function for this power series.. I have a few ideas but can't get any result.. $$\sum_{n=2}^\infty \left(\sum_{k=1}^{n} ((n-k)(k-1)M_{k-1}) z^n\right) $$ $M(k)...
3
votes
7answers
374 views

how to find this generating function

this is the power series: $$\sum_{i=0}^\infty n(n-1)^2 (n-2) z^n.$$ how can I find a generating function from it? I could use the third derivative but the $n-1$ is squared so I don't know what to do....
4
votes
2answers
2k views

I calculated the number of permutations with no 2-cycles in two ways but I got 2 different results

I calculated the number of permutations in $S_n$ with no 2-cycles in two ways but I got 2 different results. The first time I used the principle of inclusion-exclusion and I got $\sum_{k=0}^n \frac{n!}...
3
votes
1answer
929 views

Proving that every non-negative integer has an unique binary expansion with generating functions

Could you tell me how can I prove that every non-zero integer has an unique binary expansion using the generating functions, please?
0
votes
3answers
91 views

What is the $n$-th sequence element for the generating function $\frac{1}{(1-ax)^2}$?

for e.g. for $\frac{1}{(1-ax)} = a^n$ or for $\frac{1}{(1-x)^2} = n+1$ generating function = $\frac{1}{(1-ax)^2}$
2
votes
3answers
1k views

What's the difference between EGF & OGF?

I am learning about generating function now, and I am quite confused about where to use EGF and where to use OGF. You know, I could do the exercises following each section, but if there are some mixed ...
4
votes
1answer
549 views

Exponential generating function for restricted compositions

I wanted to know if it is possible to use exponential generating functions to evaluate composition of N using K distinct numbers (where the supply of numbers is infinite)? For e.g if N=10 and a1=2,a2=...
4
votes
2answers
615 views

Closed formula for entries of “Pascal's half triangle”

Rather than come up with a cumbersome explanation of what I mean, here is a picture of the beginning of the triangle: $$\begin{matrix} 1 & & & \\ 0 & 1 \\ 1 & 0 & 1 \\ 0 &...
3
votes
1answer
1k views

About the Stirling number of the second kind

Find the exponential generating function for $s_{n,r}$, the number of ways to distribute $r$ distinct objects into $n$ distinct boxes with no empty box, and determine $s_{n,r}$. My solution is $$\...
3
votes
1answer
412 views

Deep understanding on exponential generating function

In spite of having done some exercises, I still find it harder to understand exponential generating function deeply than ordinary generating function. Could someone explain it "deeply"? Or are there ...
2
votes
2answers
265 views

On a formula that relates 2-regular graphs on $n$ vertices and permutations of $n$ elements with no fixed points or cycles of length 2

Let $g_n=$ number of 2-regular graphs on $n$ vertices Let $c_n=$ permutations of $n$ with no fixed points or cycles of length 2 By a computation with the exponential generating function I think that ...
4
votes
4answers
219 views

Counting words with parity restrictions on the letters

Let $a_n$ be the number of words of length $n$ from the alphabet $\{A,B,C,D,E,F\}$ in which $A$ appears an even number of times and $B$ appears an odd number of times. Using generating functions I was ...
2
votes
1answer
301 views

Evaluating an expression using snake oil and convolutions gives different answers

I have to evaluate this expression $\sum \limits_{k=0}^n(-1)^k\binom{n}{k}\binom{m+n-k}{n-k}$ using snake oil and convolutions. The problem is that I got two different results, could you help me to ...
2
votes
2answers
299 views

Recurrence $A(n,x)=p(x)A(n-1,x-1)+q(x)A(n-1,x)$

What is the general approach to solving this recurrent equation given that $p(x)$ and $q(x)$ are not constant and do not depend on $n$ and $p(x)+q(x) \neq 1$. Please just give me some hints, don't ...
2
votes
2answers
304 views

On the symmetric labelled structure of 2-regular graphs

Let $G$ be the symmetric labelled structure of 2-regular graphs (indexed by the number of vertices) then $G(x)=\frac{e^{-\frac{x}{2}-\frac{x^2}{4}}}{\sqrt{1-x}}$. Could you help me to solve this ...
2
votes
1answer
600 views

Evaluating an expression using snake oil

I have to evaluate this expression: $\sum_k\binom{n}{k}\binom{2k}{k}(-2)^{-k}$, (In the original question we had $\sum_k\binom{n}{k}\binom{2k}{k}(-2)^{k}$) this is what I have done: $$\begin{...
0
votes
2answers
787 views

exponential generating function for distinct objects into distinct boxes

I have to find the exponential generating function for placing distinct objects into $k$ distinct boxes with at least $m$ object per box, indexed by the number of objects. Could you help me please? ...
5
votes
2answers
272 views

Evaluating the sum $\sum\limits_k \ k\binom{n}{k}^2$ using generating functions

I have to evaluate this expression $\sum\limits_k \ k\binom{n}{k}^2$ using generating function. Could you help me please? Also with some hints.
1
vote
2answers
803 views

Showing that a random sum of logarithmic mass functions has negative binomial distribution

Specific questions are bolded below. I've been unsuccessful in solving the following problem., which is exercise 5.2.3 from Probability and Random Processes by Grimmett and Stirzaker. Let $X_1, X_2,...
2
votes
3answers
171 views

Problem with generating functions and binary recurrences

I am considering the following recurrence: $a_0 = 1$; $a_1 = 2$ $a_{n} = 2 (a_{n - 1} + a_{n - 2})$ Then I proceeded with the generating function: $F(x) = \displaystyle\sum_{n = 0}^\infty a_n x^n =...
6
votes
2answers
307 views

How many ways dividing $n$ balls into $3$ buckets with limitations?

Problem How many ways dividing $n$ balls into $3$ buckets with the following limitations(?): 1st bucket contains odd number of balls. 2nd bucket contains a multiplication of 4 number of ...
6
votes
3answers
302 views

Two series relations, each one implies the other - from Andrews' partition book

That's my first question here, and i was encouraged to post because my question in MathOverflow (HERE) was beautifully and fast answered. But my questions in not at research level... As i said there, ...
4
votes
1answer
164 views

What's another form of $\sum\limits_{k=1}^\infty{\frac{x^k}{1-y^k}}$?

We can consider the function $$\displaystyle\sum_{k=1}^\infty{\frac{x^k}{1-y^k}} .$$ Is it possible to obtain a closed form expression for this? Or, if not, perhaps an integral is possible. Can we ...
7
votes
1answer
689 views

Expanding the generating function of the Fibonacci numbers to find a cute formula

$F_0=1$, $F_1=1$, $F_n=F_{n-1}+F_{n-2}$. The generating function is $-\frac{1}{x^2+x-1}$. I have to expand it to prove that $F_n=\sum_k\binom{k}{n-k}$. Could you help me please?
6
votes
1answer
915 views

On the generating function of the Fibonacci numbers

Let's define the Fibonacci numbers as $F_0=1$, $F_1=1$ and $F_n=F_{n-1}+F_{n-2}$. Using this recurrence I was able to calculate the generating function of the Fibonacci numbers to be $-\frac{1}{x^2+x-...
1
vote
1answer
121 views

Divisibility with sums going to infinity

I can't quite wrap my head around this. Given the formula $(1-x)(1+x+x^2+...) = 1$ It seems clear to me why this is true. All the x terms cancel out and we are left with one. And this is clearly ...
4
votes
1answer
224 views

Question about generating function

Let $a>0, b>0,m>0$ $H(t)=\sum\limits_{k=0}^{\infty} {k \choose a}{m-k \choose b}t^k$ So what is the closed form of $H(t)$? What I know currently is: $\sum\limits_{0 \le k \le t} {t-k \...
4
votes
1answer
138 views

HAKMEM 18(B): Cubic Partitions

Taken from HAKMEM 18. Quoting... A partition of $N$ is a finite string of non-increasing integers that add up to $N$. Thus 7 3 3 2 1 1 1 is a partition of 18. Sometimes an infinite string of zeros ...
3
votes
2answers
2k views

Finding a Particular Coefficient Using Generating Functions

I have a homework question to solve the number of ways to choose 25 ice creams of a selection of 6 types of ice creams and there are only 7 of each ice cream type. The question requires the use of ...
2
votes
1answer
1k views

Recursive Generating function for enumerating leaf labeled binary trees

Let be B(z) the exponential generating function for the number $b_n$ of different rooted unordered binary trees with exactly n leaves labeled only at their leaves (so the internal nodes are unlabeled)....
14
votes
4answers
1k views

Number of connected graphs on labeled vertices, counted according to parity

While trying to derive some formula, I encountered the following problem. Consider the set $C_n$ of all connected graphs on $n$ vertices. What is $$ \sum_{G \in C_n} (-1)^{|G|} ? $$ In other words, if ...
8
votes
3answers
1k views

Combinatorial proof for two identities [duplicate]

Does exist a combinatorial proof for the following two identities ? $\sum_{k = 0}^{n} \binom{x+k}{k} = \binom{x+n+1}{n}$ $\sum_{k = 0}^{n} k\binom{n}{k} = n2^{n-1}$ I know how to derive the ...
3
votes
1answer
475 views

Generating function of $a_{n}^2$ in terms of GF of $a_{n}$?

If we consider $A(x)$ as a generating function of a sequences $a_{n}$, is there any way to find the generating function of, say for example, the sequences : $v_{n}=a_{n}.a_{n+1}$ and $u_{n} = a_{n}^2$ ...
1
vote
1answer
160 views

generating functions and the sequence $x_{n+1}=x_{n}+\frac{1}{x_{n}}$

I start learning about generating functions , so I ask , for example , what all the deduces that a generatingfunctionologist can make for a sequence like : $x_{0}= c$ (some constant , say for ...
7
votes
1answer
552 views

What is the asymptotic behavior of a linear recurrence relation (equiv: rational g.f.)?

The question sounds simple: find the roots of the characteristic equation, take the one with the largest absolute value, and find its coefficient. Repeated roots do not substantially complicate ...
8
votes
5answers
688 views

finding the coefficient of $x^{14}$ in the expression: $\frac{5x^2-x^4}{(1-x)^3}$

I have a homework question which requires me to find the coefficient of $x^{14}$ in the expression: $\dfrac{5x^2-x^4}{(1-x)^3}$ I have not figured out a way to do this (I believe this is because my ...
3
votes
1answer
172 views

Coming up with a generating function

I have a homework assignment which is to write a Generating Function of the following problem: "There are $n$ identical boxes , there are $3$ different rooms in which they can be put. Each room can ...
1
vote
1answer
163 views

How to transform/expand a simple sum to prove equality of two sets?

I have the set $A=\left\{1+\displaystyle\sum_{i=1}^n (3-(-1)^i)\;\text{ where }\;n\in\mathbb{N}_0\right\}$ and I have to prove equality with $B=\{x\in\mathbb{N}\;\text{ where }\;2 \text{ and } 3 \text{...
12
votes
1answer
499 views

Construction of generating function from identity

I am trying to solve identity involving binomials and Fibonacci numbers by using generating functions: $$\sum_{k=0}^n{n \choose k}{n+k\choose k}f_{k+1}=\sum_{k=0}^n{n \choose k}{n+k\choose k}(-1)^{n-k}...
2
votes
1answer
293 views

What is $\mathbb C[a_1,a_2,a_3,\dots]/a(t)^2$ (where $a(t)$ is $a_1t+a_2t^2+\dots$)?

Take the graded algebra $A=\mathbb C[a_1,a_2,a_3,\dots]$ with grading given by $\deg a_{i}=2i$. Let $a(t)$ be the generating function for generators ($a(t)=a_1t+a_2t^2+\cdots\in A[[t]]$). What is the ...
3
votes
2answers
8k views

Moment generating function of Gamma distribution

I'm trying to show that as $\alpha$ tends to 0, the gamma distribution $$\Gamma(\lambda,\alpha),$$ is properly standardised, tends to the standard normal distribution. I have figured out that the ...