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

1
vote
1answer
27 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
52 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
2answers
52 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 ...
3
votes
2answers
54 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
15 views

Using Laplace transform to solve the pde resulting from solving simple birth process differential equations using generating function method [on hold]

Using Laplace transform to solve the pde resulting from solving simple birth process differential equations using generating function method $$\frac\partial{\partial t} G(z,t)+\lambda z(1-z)\; ...
0
votes
0answers
14 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
79 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
61 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
50 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
2answers
113 views
+150

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
24 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
45 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
30 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
26 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
44 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
162 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 ...
1
vote
0answers
58 views

Coefficient of $x^{2m}$ in algebraic identity [closed]

How to calculate coefficient of $x^{2m}$ in each part of the following algebraic identity: $$ \frac{(1-x^2)^n}{(1-x)^n}=(1+x)^n $$ And from here to get identity of binomial coefficients in form of: ...
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
40 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
23 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 ...
4
votes
0answers
41 views

How to compute this series?

I am stuck in computing this series (i.e, finding a closed-form formula): $$ \sum_{i=0}^k \binom{k}{i} \frac{2r^{i+1}(1-r)^{k-i+1}p^{k-i}v^i s^k}{(1-r)p^{k-i}s^i + r v^i s^{k-i}}, $$ where $r$, $p$, ...
1
vote
1answer
18 views

Generating function for a bin that has either no elements or 2 only?

What is the generating function for a bin that has either zero elements or 2 only? We start with: $(1+x^2)$ which if it had an $x$ it would translate to $\frac {1-x^3}{1-x}$ So I thought maybe I ...
1
vote
1answer
25 views

generating function as english statement

An ordinary enumerator is given as $(1+x+x^2)^p$. This is being understood as follows: There are 2 each of p kinds of objects.The ordinary enumerator for selecting none (or) one (or) both the ...
3
votes
3answers
57 views

Fountains of Coins and Fibonacci Numbers

I recently came across a problem in Herbert Wilf's Generatingfunctionology book that I can't come up with an elegant solution to and can't find any solutions online. The problem statement begins on ...
0
votes
2answers
45 views

Please help to find the formula for a relation

I'm trying to find the formula for the following relation: $ x_1 + x_2 + x_3 + x_4 = n $ where: $ 0 \leq x_1 \leq 3$ $ 0 \leq x_2 \leq 3$ $ x_3 \geq 0 $ $ x_3 \geq 0 $ Let $a_n$ be the ...
1
vote
2answers
49 views

Please help to find term's coefficient in the following example

I trying find the number of all solutions in the following: $ x_1 + x_2 + x_3 + x_4 + x_5 = 24 $ where: 2 of variables are natural odd numbers 3 of variables are natural even numbers none of ...
1
vote
0answers
33 views

Partition Generating Function (Truncation)

Let $P(x)=\sum_{n=0}^{\infty} p_nx^n$ be the partition generating function, and let $P^*(x)=\sum_{n=0}^{\infty} p^*_nx^n$, where $$p^*_n = \binom{\text{number of partitions of }n}{\text{into an even ...
7
votes
1answer
139 views

Partition Generating Function

a) Let $$P(x)=\sum_{n=0}^{\infty} p_nx^n=1+x+2x^2+3x^3+5x^4+7x^5+11x^6+\cdots$$ be the partition generating function, and let $Q(x)=\sum_{n=0}^{\infty} q_nx^n$, where $q_n$ is the number of ...
2
votes
3answers
38 views

Generating Functions with composition

For a nonnegative integer $n$, a composition of $n$ means a partition in which the order of the parts matters. Consider the generating function $$C(x) = \sum_{n=0}^{\infty} c_nx^n,$$ where $c_n$ is ...
5
votes
0answers
221 views

Formula for composition of formal power series with binomial coefficient

Let $f=\sum\limits_{n\geq 0}{f_n x^n}$ and $g=\sum\limits_{n\geq 1}{g_n x^n}$ be formal power series. The $x^n$ coefficient of $f(g)$ is $$ \sum\limits_{\mathbb{i} \in \mathcal{C}_{n}} {f_k ...
0
votes
2answers
29 views

Generating Functions or Counting?

Alice has two bags. Each bag has $4$ slips of paper with the numbers $1$ through $4$ on them. Betty also has two bags, each with $4$ slips of paper with positive integers on them. They decide to play ...
1
vote
2answers
38 views

Generating Functions with Fibonacci

a) Let \begin{align*} F_{\text{even}}(x) &= F_0x^0 + F_2x^2 + F_4x^4 + F_6x^6 + F_8x^8 + \cdots \\ &= x^2 + 3x^4 + 8x^6 + 21x^8 + \cdots \end{align*} be the generating function whose ...
2
votes
3answers
33 views

Generating Functions Partitions

Let $U(x)=\sum_{n=0}^{\infty} u_nx^n$, where $u_n$ is the number of partitions of $n$ into at most two parts. For example, $u_4=3$ because $4$ can be partitioned into at most two parts as $4$, $3+1$, ...
0
votes
1answer
19 views

Strong fixed points and generating function

For a permutation $\sigma\in S_n$ we say i is a strong fixed point, if $\sigma(j)<\sigma(i)$ for $1\leq j<i$ and $\sigma(j)>\sigma(i)$ for$ i<j\leq n$ i) Show a strong fixed point is a ...
2
votes
0answers
28 views

generating function question, method?

Write a closed formula for the generating function of the sequence $a_n=(2n+3)(-1)^n$ So first I try $A(z)=\sum_{z=0}^\infty (2n+3)(-1)^nz^n$ $=\sum_{n=0}^\infty [2(n+1)+1](-1)^nz^n$ ...
9
votes
3answers
233 views

Quadratic Equation Recurrence?

So I was playing around with the following: Let $f_0(x) = x^2 - bx + c$. If $f_n(x)$ has roots $p$ and $q$ with $p > q$, then let $f_{n+1}(x) = x^2 - px + q$. The recurrence relation is rather ...
0
votes
2answers
38 views

How many ways to distribute $n$ objects into $r$ boxes so that each box have at least $1$ (but no more than $k$) objects?

Example: How many ways are there to distribute 15 fruits to 6 people so that each person has at least 1 fruit but no more than 3? I understand how to do it when we need to make sure that at least ...
0
votes
2answers
39 views

elementary counting and specify the generating function

Let $k\geq1$, and let $b_n$ be the number of words $\omega=v_1 \cdots v_n$ over the alphabet $\Sigma=\{1,\dots k\}$ such that $v_i\neq v_{i+1}$ for $1\leq i\leq n-1$. I have to show with elementary ...
-1
votes
1answer
63 views

Generating function [closed]

Let f(n,m) the number of der path from (0,0) to (n,m) $\in \mathbb{N}^2$ wich consists the steps (0,1), (1,0) and (1,1)and set f(0,0) to 1. Let $a_i = \sum_{n+m=i}f(n,m), i\geq 0$ i) Show that: ...
1
vote
1answer
66 views

Coefficient of operator and how to do it

This question stems from this $$ \frac{1}{x+z}- \frac{1}{x} = \sum_{k=0}^\infty \frac{z^k}{k!}\frac{d^k}{dx^k}[\frac{1}{x}] $$ Now, i need to find the Bell Polynomial of $\frac{1}{x}$, $$ ...
0
votes
1answer
28 views

Can this recurrence relation be solved with generating functions?

I have this recurrence relation, $$a_{n+1}=\frac{n+2}{n}a_n$$ with $a_1=1$. I've already solved this using a substitution approach by letting $a_n=\dfrac{(n+1)!}{(n-1)!}b_n$. This means ...
0
votes
1answer
33 views

Binary tree bijection

I've been studying for an up coming exam in combinatorics and I came across something interesting by accident. We have the two combinatorial constructions: $$\mathbb{U}\cong SEQ(\mathbb{ZU})$$ And ...
1
vote
1answer
41 views

Explanation of Generating Functions Simplification

Given the problem: What is the coefficient of $x^{2005}$ in the generating function $G(x) = \frac{1}{(1-x)^2(1+x)^2}$? The solution posted starts with: Let $\frac{1}{(1-x)^2(1+x)^2} = ...
2
votes
0answers
79 views

Question from Wilf's generatingfunctionology on ordered representations of $n$ as a sum of $k$ distinct integers.

This is a question from Wilf's generatingfunctionology, Chapter 2, Exercise 21(a) and (b) (p. 71 in the 3rd edition). (a) Let $T$ be a fixed set of nonnegative integers. Let $f(n,k,T)$ be the ...
3
votes
0answers
40 views

How to show that two probability generating functions are equal?

From Grimmett's Probability and Random Processes: Let $G_a(s) := \sum_0^\infty a_is^i$ where $a = \{a_i : i \geq 0\}$ is a real sequence. Uniqueness. If $G_a(s) = G_b(s)$ for $|s| < R'$ ...
0
votes
2answers
38 views

How to find a formula of this generating sequence?

It is given that $I_0=0$ and $S_0=0$ $$I_n=I_{n-1}+1$$ $$S_n=3S_{n-1}+5I_n$$ How to come up with a formula for $S_n$?
0
votes
0answers
32 views

Question about the coefficient of operator

Note that the "coefficient of" operator is an operator that takes the coefficient of the power series. We start with the following: $$ \frac{1}{f(x)+z} - \frac{1}{f(x)} = \sum_{k=0}^\infty ...
2
votes
3answers
49 views

Expansion of Generating Functions

If you roll $10$ dice, how many ways can you get a total sum of top faces of $25$? I understand how to write the generating function of $(x+x^2+ \dots +x^6)^{10}$ and the fact that you need to find ...