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

2
votes
0answers
13 views

Determining probability generating function for waiting time to see first $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
2answers
45 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
36 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
35 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
35 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
68 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
70 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
86 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
16 views

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

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
17 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
83 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
51 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
150 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
32 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
46 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 ...
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
25 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
42 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
26 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
60 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
35 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
142 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
225 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
30 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
41 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
34 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
20 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
29 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
39 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
67 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
34 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
42 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} = ...
3
votes
1answer
97 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
42 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'$ ...