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
2answers
79 views
A classical problem in combinatorics/probability
I read this problem in Cognition and Chance by Raymond Nickerson (the problem is stated not discussed)
...
13
votes
3answers
380 views
Solving a difficult recursion via generating functions
I have been trying to solve the recurrence:
\begin{align*}
a_{n+1}=\frac{2(n+1)a_n+5((n+1)!)}{3},
\end{align*}
where $a_0=5$, via generating functions with little success. My progress until now is ...
5
votes
3answers
176 views
$n$-ary trees with $k$-internal nodes - Catalan numbers
It is known that the Catalan numbers count the number of binary trees with $k$-internal nodes. I was thinking of how to count ternary trees or in general $n$-ary trees with $k$ internal nodes and got ...
0
votes
1answer
25 views
Probability density function for the normalised sum of N random variables
I was wondering what the PDF looks like for Z= (1/N)*SUM(z_1+...+ z_n), where each z_i is computationally represented by RAND(). What is the behaviour of the PDF as N -> infinity?
0
votes
1answer
26 views
Generating functions of partition numbers
I don't understand at all why:
\begin{equation}
\sum\limits_{n=0}^\infty p_n x^n = \prod\limits_{k=1}^\infty (1-x^k)^{-1}
\end{equation}
Where $p_n$ is the number of partitions of $n$. Specifically ...
5
votes
1answer
66 views
+50
Umbral calculus with negative indices (and powers)
Can we do umbral calculus with negative indices (and powers)? Can we write $a_{-n} \equiv a^{-n}$ or $L[a_{-n}] = a^{-n}$ where $L$ is a linear functional and $n$ need not be negative?
The common ...
6
votes
1answer
521 views
Equation about generating functions and subfactorial
Suppose $G_n(w)$ is a formal power series (really a probability generating function, see the following explanation) of variable $w$, try to solve out $G_n(w)$ for all $n\ge0$ from the ...
1
vote
1answer
28 views
Moment generating Function: sample mean
Let $\bar{X_{n}}$ be the sample mean of a random sample of size n from a distribution which has a pdf of:
f(x) = ${e^{-x}}$, for x> 0; 0, other wise.
a) show that the mgf of ...
2
votes
1answer
51 views
Weak convergence and generating function
Let $X_n$ be a sequence of $\mathbb N_0$ valued random variables and denote by $g_{X_n}$ their generating function, i.e. $g_{X_n}(s) = \mathbb E[s^{X_n}] = \sum_{k=0}^{\infty} s^k \mathbb P(X_n=k)$.
...
2
votes
2answers
73 views
Question about generating function coefficients
Find coefficient of $x^{18}$ in $(1+x^3+x^6+x^9+\cdots)^6 $
Normally, to to this I would look for a pattern that follows the following basic expansions in this powerpoint: ...
2
votes
3answers
54 views
Solving recurrence equation using exponential generating functions
The recurrence is
$ a_n = (n-1) a_{n-1} + (n-2)a_{n-2} $
I tried using exponential generating functions and have problems with it (the second term mostly)
Further can this be solved without ...
2
votes
3answers
66 views
Finding a coefficient using generating functions
I need to find a coefficient of $x^{21}$ inside the following expression:
$$(x^{2} + x^{3} + x^{4} + x^{5} + x^{6})^{8}$$
I think the only way (using generating functions) is to express the ...
2
votes
5answers
83 views
Deriving Closed Form for a Recursion via Generating Functions
Consider (1) $a_{n+2} = 2a_{n+1} - a_n + 4n3^n$ with $a_0 = a_1 = 1$.
Using generating functions and setting $A(x) = \sum a_nx^n$ we obtain
$$\begin{align*}&\quad\sum a_{n+2}x^{n+2} = ...
1
vote
4answers
81 views
Finding generating function for the recurrence $a_0 = 1$, $a_n = {n \choose 2} + 3a_{n - 1}$
I am trying to find generating function for the recurrence:
$a_0 = 1$,
$a_n = {n \choose 2} + 3a_{n - 1}$ for every $n \ge 1$.
It looks like this:
$a_0 = 1$
$a_1 = {1 \choose 2} + 3$
$a_2 = {2 ...
0
votes
1answer
21 views
Calculating coefficient of generating function with Coin
The problem I'm currently looking over requires use of generating functions to solve the following:
If a coin is flipped $25$ times with eight tails occurring, what is the probability that no run of ...
0
votes
1answer
70 views
Solve the following recurrences using generating functions.
Solve the following recurrence using generating functions to find a formula for $A_n$ in terms of $n$.
$A_0 = 1$, $A_1 = 1$, and for $n\geq 2$, $A_n = A_{n-1} + 2A_{n-2} + 4$
2
votes
1answer
20 views
Finding the coefficient in the closed form of the generating function
I try to solve the recursion $a_n=5a_{n-1}+5^n$ with $a_0=1$ with generating function, but I could not find the coefficient of $x^n$ in the closed form
\begin{eqnarray*}
...
2
votes
2answers
36 views
Using Generating Functions (again) to Solve Recurrences
Consider the recursion $a_n = 2a_{n-1} + (-1)^n$ where $a_0 = 2$
Then $A(x) = \sum a_n x^n$ = $2 + \sum a_n x^n$ shifting the index of summation. The only next move I can think of is to now ...
19
votes
6answers
617 views
How are we able to calculate specific numbers in the Fibonacci Sequence?
I was reading up on the Fibonacci Sequence when I've noticed some were able to calculate specific numbers. So far I've only figured out creating an array and counting to the value, which is incredibly ...
1
vote
1answer
35 views
Computing the probability of rolling a sum of 18 on 4 six-sided dice
The following PDF gives an explanation on page 11. Unfortunately I do not know how to reproduce it here.
http://web.mit.edu/~qchu/Public/TopicsInGF.pdf
In short, I am not sure how the symmetry ...
2
votes
0answers
16 views
Bivariate generating functions and diagonal like recurrences
I'm trying to solve recurrences of the type
$$a(n,m) = \sum_{k=0}^{m} a(n-k,k), \qquad a(n,0)= a(0,m)=1 \qquad (A_0)$$
with the help of generating functions, but I get stuck quite early on.
If I ...
5
votes
1answer
107 views
Combinatorial puzzle
Let $\pi$ be a set of ordered pairs of natural numbers, $\pi = \lbrace (n_1,n_2) \dots (n_k ,n_{k+1})\rbrace$ (a "set of pairs").
Let $\cup \pi$ be the set $\lbrace n_1 n_2 \dots n_k ...
2
votes
2answers
42 views
New to generating functions - how do I get the function from the sequence defined by $a_n= n$ for $n\geqslant 0$?
I'm given: $a_n= n$ for $n \geqslant 0$.
I'm quite good at recursive generating functions, but I haven't came across a simpler one like this, so I'm sure I'm just overlooking something really basic.
6
votes
2answers
222 views
Lines in the plane and recurrence relation
I am trying to solve the following problem from Cohen's Basic Techniques of Combinatorial Theory:
A collection of $n$ lines in the plane are are said to be in general position if no two are ...
0
votes
0answers
19 views
How to find the generating function of the system of equations?
Let $B(z)=\sum_{i=0}^\infty b_iz^i$,$A(z)=\sum_{i=0}^\infty a_iz^i$, $C(z)=\sum_{i=0}^\infty c_iz^i$, $D(z)=\sum_{i=0}^\infty d_iz^i$, how to find $D(z)$ from the relations
$$\begin{align} ...
1
vote
2answers
48 views
Number of partitions of a set into even classes
Suppose I have a set containing $n$ elements and I consider the number of partitions of it in which all the constituent classes are even. I let $R_n$ denote this number ($R_0=1$) and proceed as ...
-2
votes
1answer
155 views
Find a closed form for a generating function and recurrence
Find a closed form for the generating function $R(x) = \sum_{n=0}^\infty r_nx^n$, where $r_n$ is given by the recurrence $r_n = 3r_{n-1} + 5r_{n-2} + 6n$
for $n \geq 2$ and initial conditions $r_0 = ...
-2
votes
1answer
122 views
From a Generating Function find $R(x)$ as an infinite product of Quotients
Let $r(n)$ be the number of partitions of $n$ so that no multiple of $3$ appears as a part. For
example, $r(8) = 13$.
Let $R(x) =\sum_0^\infty r(n)x^ n $ be the generating function for $r(n)$.
Find ...
-2
votes
1answer
147 views
Find a form for $Q(x)$ as an infinite product of polynomials
Let $q(n)$ be the number of partitions of $n$ so that no part appears three or more times. For example, $q(8) = 13$
Let $Q(x) = \sum\limits_{n=0}^\infty q(n) x^n$ be the generating function for ...
1
vote
3answers
40 views
Coefficients of series given by generating function
How to find the coefficients of this infinite series given by generating function.$$g(x)=\sum_{n=0}^{\infty}a_nx^n=\frac{1-11x}{1-(3x^2+10x)}$$
I try to expand like Fibonacci sequences using geometric ...
-1
votes
0answers
41 views
Finding the counting function [closed]
I'm running into a problem determining what's going on here:
There are n types of food that include bread, pizza, candy, burgers, sandwiches, pasta, etc. If George takes bread, he will have to ...
0
votes
1answer
43 views
Proving a Probability Generating Function satisfies a partial differential Equation
We have N animals grazing in a field. The animals graze independently, and periods of grazing and resting alternate for the animals. If an animal is resting at time t, the probability it begins ...
2
votes
3answers
68 views
Solving functional equation for generating function
Find the functional equation for the generating function whose coefficients satisfy $$
a_n = \sum_{i=1}^{n-1}2^ia_{n-i}, \text{ for } n\ge 2, a_0 = a_1 = 1
$$
This is what I've tried so far:
$$
...
2
votes
1answer
38 views
Finding functional equation for generating function
I'm given
$$
a_n = \sum_{i=2}^{n-2} a_ia_{n-i} \quad (n\geq 3), a_0 = a_1=a_2 = 1
$$
and I need to find the functional equation for the generating function satisfying the above equality. I obtained ...
4
votes
0answers
64 views
Finding the number of 5-node labeled connected graphs via generating functions
Problem: Find the number of ways to connect a graph having 5 labeled nodes so that each node is reachable from every other node.
I have solved this problem using principle of inclusion and exclusion ...
2
votes
2answers
64 views
Functional equations and generating functions
The problem asks to find the functional equations for the generating functions whose coefficients satisfy
$$
a_n = \sum_{i=0}^{n-1} a_i a_{n-1-i}\,\, (n\geq1), a_0 = 1
$$
There's an example that's ...
6
votes
3answers
69 views
Combinatorics: Generating Function related to compositions of a number
My goal is to find the coefficients of the generating function for the following situation:
The number $f(n)$ is the sum over all compositions of $n$ into $3$ parts of the product of those parts.
Fo ...
5
votes
3answers
99 views
How to prove it? (one of the Rogers-Ramanujan identities)
Prove the following identity (one of the Rogers-Ramanujan identities) on formal power series by interpreting each side as a generating function for partitions:
...
6
votes
2answers
120 views
Simplify $\frac{1}{1 + \sqrt{2}} + \frac{1}{\sqrt{2} + \sqrt{3}} + \frac{1}{\sqrt{3} + \sqrt{4}} + \cdots+ \frac{1}{\sqrt{24} + \sqrt{25}}$
Simplify$$\frac{1}{1 + \sqrt{2}} + \frac{1}{\sqrt{2} + \sqrt{3}} + \frac{1}{\sqrt{3} + \sqrt{4}} + \cdots + \frac{1}{\sqrt{24} + \sqrt{25}}.$$
I know you can solve this using generating functions but ...
2
votes
2answers
48 views
Generating functions. Number of solutions of equation.
Let's consider two equations
$x_1+x_2+\cdots+x_{19}=9$, where
$x_i \le 1$
and
$x_1+x_2+\cdots+x_{10}=10, $ where $ x_i \le 5$
The point is to find whose equation has greater ...
1
vote
1answer
68 views
Exponential generating function for permutations with descent set whose least element is even
Let $E(n)$ be the number of permutations $w\in S_n$ such that the least element of the set $Des(w)\cup \{n\}$ is even, where $Des(w)$ is the descent set of $w$. I need to find the exponential ...
6
votes
3answers
71 views
Solve recursive equation $ f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1$
Solve recursive equation:
$$ f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1$$
$f_0 = 0, f_1 = 1$
What I have done so far:
$$ f_n = \frac{2n-1}{n}f_{n-1}-\frac{n-1}{n}f_{n-2} + 1- [n=0]$$
I ...
2
votes
3answers
76 views
Generating function for the solutions of equation $ 2x_1 + 4x_2 = n$
Let's denote $h_n$ as the number of soulutions of the following equation:
$$ 2x_1 + 4x_2 = n$$
where $x_i \in \mathbb N$.
Find generating function of the sequence $h_n$ and calculate $h_{2000}$.
...
1
vote
2answers
65 views
Solving Another Recursion Using Generating Functions
I am trying to find a closed form for
$$
Y(n) = Y(n-1) -2Y(n-2) + 4^{n-2} \text{ with initial conditions } Y(0) = 2,Y(1) = 1
$$
using generating functions. However, I am still not entirely ...
2
votes
2answers
65 views
Using Generating Functions to Solve Recursions
I have the recursion $A(n) = A(n-1) + n^2 - n$ with initial conditions $A(0) = 1$. I attempted to solve it using generating functions and I'm not quite sure I have it right, so I thought I might ask ...
0
votes
0answers
29 views
Use of Generating function
Given an $n$-element array $A[1\ldots n]$, let $T$ be the number of $(i,j)$ such that $A[i]>A[j]$. Use the generating function to compute the average of $T$.
Someone please help me. Thanks.
2
votes
1answer
52 views
How to solve this kind of problems?
For $[z^n]\frac{z^k}{1-z^k}$ we can get $[z^n]\frac{z^k}{1-z^k}=\left(
\begin{array}{ccc}
n-1\\
k-1\\
\end{array}
\right)$
But $[z^n](z\frac{1-z^r}{1-z})^k=?$
How to ...
0
votes
1answer
36 views
Generating function from recursion with division by index $n$
I've got stuck in my homework, and I don't really know if I should look for another solution or I just don't have enough knowledge to do it. So I need to find generating function (as in title) for:
$$ ...
2
votes
1answer
73 views
Coefficients of Generating Functions
This problem is from Stanley's Enumerative Combinatorics: Volume 1. page 115 here for those desirous of context (prettier conTeXt).
Anyway, it asks for fixed $j,k\in \mathbb{Z}$ to show that ...
3
votes
2answers
74 views
Finding coefficient of generating function
Find the coefficient of $x^{52}$ in $$(x^{10} + x^{11} + \ldots + x^{25})(x + x^2 + \ldots + x^{15})(x^{20} + x^{21}+ \ldots + x^{45})$$
One thing I tried doing was factoring out $x^{10}, x, ...
