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.

learn more… | top users | synonyms

0
votes
1answer
21 views

Finding a moment generating function

I want to find $M(t)$ of $$f(x)= \begin{cases} e^{(-x-1)} & \text{for } x > -1 \\ 0 & \text{otherwise} \end{cases}$$ $e^{(-x-1)}$ I tried to do $$\int_{-1}^{∞ {}} e^{tx} ...
2
votes
0answers
26 views

What is the meaning of the cumulant generating function itself?

If we define the characteristic function for a random variable X as $\Phi(t)=<e^{itX}>$ then it seems like we can think of it as essentially a spectral decomposition that measures the ...
2
votes
1answer
35 views

Harmonic Generating Function

I have noticed an interesting generating function involving Harmonic Numbers. $$\sum_{n=1}^{\infty}H_nx^n=\frac{\ln(1-x)}{x-1}$$ But, I have not seen a generating function involving second-order ...
-1
votes
0answers
40 views

Finding distribution from PGF not in closed from.

$X_1,X_2,\ldots,X_N$ are independent and identically distributed random variables. We have $X = e^{-Y}$, where $Y\sim\mathrm{Poisson}(\lambda_u)$, and $$Z =X_1+X_2+\cdots+X_N ,$$ where $N \sim ...
5
votes
1answer
93 views

How to evaluate this double infinite sum (Catalan number)

Let $C_n = \dfrac{1}{n+1}\binom{2n}{n}$. Is it possible to find the exact value of this infinite sum ? $$\sum_{n=1}^\infty \sum_{k=n}^\infty ...
2
votes
0answers
44 views

Sum taken over the specified set of integer: $\sum_{3 \mid n} a_n$

Let's consider a sum $$S_{m}=\sum_{ 3 | n}^{m} {a_{n}}$$ where the sum is taken over all the integers $3t$, where $0 \leq 3t \leq m$. Assume that $G(z)$ is a generating function of the sequence ...
0
votes
1answer
34 views

How to reconstruct distribution from the generating function

Suppose $$F(x)=\sum_n p(n)x^n$$ is a generating function, and we have the expression for $F(x)$ explicitly. Then how we can get the expression for $p(n)$ from this generating function?
1
vote
2answers
37 views

Closed form for multiplicative recurrence relation

In this StackOverflow question, I found an interesting recurrence relation: $$f(n) = \begin{cases} 1 & n \leq 2 \\ nf(n-1) + (n-1)f(n-2) & \text{otherwise.}\end{cases}$$ I plugged it into ...
1
vote
2answers
54 views

How can I find the generating function of this sequence?

I am preparing for a test and I came across this example: Find the closed form generating function of: $$\dbinom{50}{1}, 2\dbinom{50}{2}, 3\dbinom{50}{3},..., 50\dbinom{50}{50},0,0,0,0$$ I know ...
20
votes
1answer
377 views

What function satisfies $F'(x) = F(2x)$?

The exponential generating function counting the number of graphs on $n$ labeled vertices satisfies (and is defined by) the equations $$ F'(x) = F(2x) \; \; ; \; \; F(0) = 1 $$ Is there some closed ...
0
votes
3answers
64 views

generating function for $\frac{n!}{(2n)!}$ [closed]

How to construct generating function such that $$g(x) = \sum_{n=0}^\infty \frac{n!}{(2n)!} t^n $$
4
votes
1answer
49 views

Recurrence relation in terms of another sequence

How do I solve a recurrence of the form $$nd^{n-1}a_n+a_{n+1}d^{n+1}=b_n$$ for $a_n$, where $b_n$ is another (known) sequence and $d$ is a constant? My only idea was to use a generating function and ...
0
votes
1answer
50 views

Mountain of coins

Let a mountain of coins be an arrangement coins in rows such that the coins in each row form a single block, and that in all rows (except the bottom row) each coin touches exactly two coins from the ...
2
votes
1answer
39 views

Bernoulli Numbers generating function and Riemann Zeta function

I've been studying Bernoulli numbers and I came across this summation: $$ \sum_{n=1}^{\infty}\frac{B_n x^n}{n!} = \sum_{n=1}^{\infty}\frac{-n \zeta(1-n) x^n}{n!} = -\sum_{n=1}^{\infty}\frac{\zeta(1-n) ...
0
votes
0answers
45 views

Question on how to manipulate terms in this expression

sorry for the vague title, i dont know how else to express what i mean with this question. But what i need to do is find out which terms on the RHS of the expression are constants. It is clear that it ...
21
votes
1answer
377 views

What is the intuition behind generating functions? What makes them valuable?

I'm sorry if this question makes no sense. I have been reading generatingfunctionology and I have been able to solve the problems in the first chapters and I understand the mechanism I have to follow ...
1
vote
1answer
43 views

Find the Sum using bijection

Find the sum of $S=\displaystyle\sum_{i,j,k \ge 0, i+j+k=17} ijk$. I am looking for a solution that uses some bijection. I couldn't find any bijection. I am able to do the problem by other method by ...
4
votes
2answers
165 views

Find $a_{n,i,j}$ in the expansion $(x + D)^n = \sum\limits_{i,j} a_{n,i,j} x^i D^j.$

This is problem 47c. in Stanley's Enumerative Combinatorics Vol. 1. Background: Let $D$ be the operator $\frac{d}{dx}$. Part (a) asks to prove $$ (xD)^n = \sum\limits_{k = 0}^n S(n,k)x^k D^k $$ ...
0
votes
0answers
37 views

What will be Terms after repeating this step(Differentiation and multiplication) F times.

I was solving a probability problem and got stuck on the following situation, where each x_i is independent of others: $$f=(x_1+x_2+..x_k)^N$$ I'm interested in the expression obtained after ...
1
vote
0answers
65 views

Stirling number Combinatorics. Summation .

$$ \sum_{k=0}^n \left\{ {n\atop k} \right\} *(x)_k = x^n $$ is well known . What if the k-th term of LHS summation is divided by $q^k$ where $q$ is some positive constant, What about $$ ...
3
votes
1answer
56 views

finding the partial bell polynomial of $e^x$

$$ \left(e^{x+z} - e^x\right) = \sum_{n=1}^\infty \frac{z^n}{n!} \frac{d^n}{dx^n}[e^x] $$ $$ \left(e^{x+z}-e^x\right)^k = \sum_{n \geq k} Y^{\Delta}_{e^x}(n,k,x)z^n $$ Where: $$ Y^{\Delta}(n,k,x) = ...
6
votes
4answers
378 views

How to solve this recurrence $K(n)=2K(n-1)-K(n-2)+C$?

The recurrence is $K(n)=2K(n-1)-K(n-2)+C$ where $C$ is a constant. What I have tried is substituting $2K(n-1)$ as we do in fibonnacical recurrences. It didn't gave me a fruitful expression! Can ...
1
vote
1answer
52 views

Better closed form for generating function $\sum \binom{n}{2k} x^k$

I have a power series $F_n(x) = \sum_k \binom{n}{2k} x^k$, which has a closed form of $F_n = \frac12 \left((1 + \sqrt{x})^n + (1 - \sqrt{x})^n\right)$. $$\begin{align} (1 + \sqrt{x})^n + (1 - ...
2
votes
2answers
46 views

How many solutions exists for this equation? [duplicate]

$$x_1 + x_2 + x_3 + x_4 = 28$$ I tried to solve it with generating functions. Is it correct to get to the form of $${(1 + x + {x^2} + {x^3} + ....)^4}$$ and this equals to: $${(1 - x)^{ - 4}}$$ ...
0
votes
1answer
21 views

Finding probabilities from probabilty generating function

Given that I have a probability generating function for $Q$ given by $\dfrac{4s^{2}}{9-3s-2s^{2}}$, I want to find $P(Q = n)$ for $n \geq 2$. I understand that I could actually use the definition of ...
1
vote
1answer
17 views

How to find the generating function from recurrence relation $t_n=(1+c~q^{n-1})~p~t_{n-1}+a +b+nbq, ~~n\ge 2$?

How to find the generating function $T(z)=\sum_{n=0}^{\infty} t_n~z^n$ from the recurrence relation $$t_n=(1+c~q^{n-1})~p~t_{n-1}+a +b+nbq,\qquad n\ge 2.$$ given that $$t_1=b+(1+c~p)(a~q^{-1}+b),$$ ...
4
votes
2answers
53 views

Determining probability generating function for event “$SS$”

Given a sequence of Bernouilli trials, we have $P(S) = \frac{2}{3}$ with $0<p<1$. The event "SS" occurs on the $i$-th trial if we observe an $S$ on the $i$-th trial following a $S$ on the ...
1
vote
3answers
62 views

How to solve this combinations with repetitions problem using generating functions?

Find the number of solutions to : $$x_1 + x_2 + x_3 + x_4 + x_5 = 10$$ where none of the variables can be the number $3$. I can solve this with Inclusion-Exclusion Principle, but I really love ...
1
vote
0answers
48 views

How to Evaluate this Summation to Find a Closed Form

While taking the incomplete Bell Polynomil of $x^a$ i found out that: $$ B_{n,k}^{x^a}(x) = x^{ak-n} \sum_{m=0}^k \frac{(am)!(-1)^{k-m}}{m!(k-m)!(am-n)!} $$ Now, what i am wondering is, what is the ...
1
vote
1answer
37 views

Determining Probability Generating Function from Probability Mass Function and Convergence

I am trying to solve the following: Suppose $X_{nk}, k=1,2,\ldots,n, n≥ 2$ are i.i.d. random variables $$P(X_{nk}=0)=1-\frac{1}{n}-\frac{1}{n^2}\\P(X_{nk}=1)=\frac{1}{n}\\P(X_{nk}=2)=\frac{1}{n^2}$$ ...
1
vote
1answer
37 views

Deriving Probability Density Function from Probability Generating Function for Random Sum

I am trying to solve the following: Let $X_{i}$~$Geometric(q) i=1,2,...,N$ with $q=1-p, 0<p<1$. $N$~$Geometric(p)$. Define $Y=\sum_{i=1}^{N}X_i$ and assume each $X_i$ is i.i.d. and ...
5
votes
2answers
78 views

Generating functions of bills

Using generating functions, find the number of ways to make change for a $\$$100 bill using only dollar coins and $\$$1, $\$$5, and $\$$10 bills. My answer: I had ...
1
vote
3answers
87 views

Exponential generating function for the number of binary strings of length $n$

I know that the generating function of the sequence counting the number of binary strings of length $n$ is $e^{2x}$. But my book doesn't explain why this is the case. Could you give me a little more ...
4
votes
2answers
91 views

No Adjacency Combinatorics Problem via Generating Function

I would like to find the generating function solution for the following combinatorics/probability problem. I have a combinatorial solution and the generating function deduced thereof. But I can not ...
0
votes
0answers
25 views

Enumeration of skew Ferrers diagrams revisited.

In M. P. Delest, J. M. Fedou, "Enumeration of skew Ferrers diagrams", Discrete Mathematics. vol.112, no.1-3, pp.65-79, (1993) http://dx.doi.org/10.1016/0012-365X(93)90224-H a generating function is ...
1
vote
1answer
85 views

Simplify a Combinatorial Sum $\sum_{k=0}^\infty {a\choose k}{b\choose c-k}{d-k\choose e}$

Is there a way to simplify $$\sum_{k=0}^\infty {a\choose k}{b\choose c-k}{d-k\choose e}$$ where $a,b,c,d,e$ are natural numbers? In particular, I would like to see the case for $a=45, ...
0
votes
1answer
21 views

Generating function of Language is rational

Let W be the set of all words over an alphabet $\Sigma$. Let $$L=\{w\in\Sigma^* | w\neq uvu',\text{ with }u,u'\in\Sigma^*,v\in W\}$$ I have to show that the generating function of L is rational. My ...
2
votes
1answer
64 views

Coefficients of a generating function

I need a bit of help. I was solving the form of the coefficients of the generating function $\sum_{n}n^m r^n$. Then I started building the indefinite sum $\sum n^m r^n \delta n$ trough recursive ...
2
votes
1answer
56 views

Transfer Matrix Method to determine the generating function

Let $G = (V,E,\Phi)$ be a weighted directed graph and $\mathcal{W}' : E \rightarrow \mathbb{C}$ the weighting. Let additionally $m = \# V$, $E_m$ the $m \times m$ identity matrix. Let $v,w \in V$ ...
8
votes
1answer
154 views

Finding closed form for a generating function with different powers of $x$ in parameter

I'm working on a math/programming puzzle that involves an integer series defined as having a recurrence relating values $a(n)$ to $a(\lfloor\frac{n}{2}\rfloor)$ and $a(\lfloor\frac{n}{4}\rfloor)$. ...
1
vote
1answer
26 views

“The well-known formulas that gives the relation between the generating functions of a sequence and the sequence of its 'tails'”

I'm reading a paper on Branching Processes and the Theory of Epidemics, and the fourth page (p. 262 of the book) the author refers to "the well-known formulas that gives the relation between the ...
3
votes
1answer
46 views

closed form for some binomial sum

I am trying to derive a closed form for the generating function of $a_n(x)=\sum_{k=0}^n \binom{n+k}{n}x^k, x>0, n\in\mathbb{N},$ i.e. for $G(z)=\sum_{n=0}^\infty a_n(x)z^n$. The only method I ...
1
vote
1answer
33 views

coefficient of operator for $B_{n,k}^{x^2}(x)$

We start with the following: $$ (x+z)^2 - x^2 = \sum_{n \geq 1} \frac{z^n}{n!} \frac{d^n}{dx^n}[x^2] $$ $$ (x+z)^2 - x^2 = z(2x+z) $$ $$ z^k(2x+z)^k = \sum_{n \geq k} Y^{\Delta}(n,k,x)z^n $$ Where ...
0
votes
1answer
28 views

Determining Probability Distribution from Probability Generating Function

I am trying to solve the following: The nonnegative, integer-valued, random variable X has generating function $g_{X(t)}=log(\frac{1}{1-qt})$. Determine $P(X = k)$ for $k = 0, 1, 2, . . .$, $E[X]$, ...
2
votes
4answers
48 views

Solve recurcion using generating function

I have got a problem with solving this equation using generating functions. $$ P_{n}=2nP_{n-1}-10n+5 $$ $$ P_{0}=5 $$ I started like that: $$ ...
1
vote
2answers
166 views

How was the equation re-written?

This question is a part of inhomogeneous recurrence relations (IHR). The actual question was Find a solution to $a_n - a_{n-1} = 3(n-1)$ where $n \ge 1$ and $a_0 = 2$. While going through the ...
0
votes
1answer
19 views

Generating function for $2n$ distinct balls to $n$ bins such that each bin will hold exactly two balls

Find the number of ways for having $2n$ distinct balls in $n$ distinct bins such that each bin will hold exactly two balls using a generating function The generating function (exponential) would ...
0
votes
2answers
41 views

Find coefficient of $X^{12}$

I need to find coefficient of $X^{12}$ in $({1-2X})^{19}$. What is the formula to solve it?I only know about $$\frac{1}{a-X}=\frac{1}{a}\sum_{r=0}^\infty \frac{X^r}{a^r}$$ ...
0
votes
1answer
61 views

Ways to have exactly $n$ nominees out of $2n$ voters

There are $2n$ voters, each write his name on a paper as the voter and the name of his nominee. How many ways there are such that there are exactly $n$ different nominees and each of the nominees ...
0
votes
2answers
27 views

Recursive equation in graph theory

How many vertex-colorings with 3 colors has the cycle $C_n$? How to build a recursive equation for the number of colorings over n? I know that a cycle has either 2 or 3 colors. 2 when n is even and ...