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,573
questions
0
votes
0
answers
17
views
generating function of recursion with a hyperbolic function
I am looking to solve a recursion for a certain sequence $\{a_n\}_{n \geq 1}$ through its generating function
$$f(x)=\sum_{n\geq 1} a_n x^n\tag{1}\label{1},$$
which after plugging-in the specific ...
- 137
3
votes
1
answer
59
views
Definite integral $\int_{-1}^1 \frac{\mathrm{d}x}{\sqrt{1-2xt+t^2}\sqrt{1-2xs+s^2}}$ related with Legendre polynomials generating function
Recently, as a math tutor, I was thinking how one could introduce to students the famous Legendre polynomials. One standard way is by the Generating function
$$\frac{1}{\sqrt{1-2xt+t^2}} = \sum_{l=0}^\...
- 2,943
3
votes
2
answers
95
views
How to show this recursion for $\Big(\frac12(1+\sqrt{1-4x})\Big)^m$?
Let $a_n$ be the coefficients of the generating function $((1+\sqrt{1-4x})/2)^3$, i.e.,
$$
\left(\frac{1+\sqrt{1-4x}}{2}\right)^3 = \sum_{n \ge 0} a_nx^n.
$$
It is known, that $a_n$ satisfies the ...
- 247
1
vote
1
answer
42
views
How to solve recurrence of a two-sided sequence with generating functions?
Given a two-sided sequence
$$...,a_{-2},a_{-1},a_0,a_1,a_2,..$$
with recursion
$$a_n=\frac12(a_{n-2}+a_{n+1}), n\neq0$$
and initial condition
$$a_0=1$$
let
$$G(z)=\sum_n a_n z^n$$
be its generating ...
- 81
5
votes
1
answer
95
views
Recursive relation for power series coefficients
I wish to find a recurrence relation involving the coefficients of the power series of $\mathrm{exp}(x^2/2 + x^3/3)$. This happens to be an exponential generating function and so via a combinatorial ...
- 8,937
0
votes
0
answers
21
views
Generalizing a Result From Polyas Problem Book in Analysis about differentiation of power series
Within the classic book Problems in Analysis by George Polya and Gabor Szego in the section on operations and differentiation of power series, problem 48 states the following:
"Suppose that $f(x)$...
- 111
1
vote
1
answer
84
views
Solving a recursion formula involving products of compositions of an integer
I have the following recursive formula that I want to solve in order to find a general, non-recursive expression for arbitrary $S_N$ (real positive number). Here it is:
\begin{equation*}
S_{N+1} = \...
- 137
1
vote
1
answer
55
views
Using generating functions prove that $\sum_{k=r}^{2n-1} k2^k \binom{2n-k-1}{n-1} = n2^r \binom{2n-r}{n}$
Inspired by the question: How to prove? $\sum_{k=r}^{2n-1}k2^k{2n-k-1\choose n-1}=n2^r{2n-r\choose n}$.
Using generating functions prove that
\begin{equation*}
\sum_{k=r}^{2n-1} k2^k \binom{2n-k-1}...
- 582
1
vote
0
answers
43
views
Solve recurrence relation with kronecker-delta using generating function
Assume the following recurrence relation
\begin{equation}
a_{n}=(n-1) a_{n-1} + \lambda(\delta_{n,0}-\delta_{n-1,0})
\end{equation}
where $\lambda$ is a real parameter and $n\ge 0$.
Using the the ...
- 37
2
votes
1
answer
60
views
Does an exponential or any generating function exist for a sequence which consists of every $4$^th Hermite polynomial?
I know that it exists for the Hermite polynomials an exponential generating function:
$$\sum_{n=0}^\infty H_n(x)\frac{t^n}{n!} = e^{2xt-t^2}$$
however, what happens if the sequence plugged into the ...
- 176
-1
votes
0
answers
59
views
Can the Function $p(t, r) = e^{r \sin \left( \frac{(2t+1) \pi}{2} \right)}$ Be Used to derive a Prime Generating Function?
I am exploring a mathematical function related to prime numbers and have written a Python script to test it. Here is the function and the code I've used:
Math Functions:
Sum of Divisors Function:
$$ ...
1
vote
1
answer
76
views
Prove that $\sum_{k} \binom{l}{m+k} \binom{s+k}{n} (-1)^k = (-1)^{l+m} \binom{s-m}{n-l}$ using generating functions
This is an identity from Concrete Mathematics (5.24).
Use generating functions to prove that
\begin{equation}
\sum_{k} \binom{l}{m+k} \binom{s+k}{n} (-1)^k = (-1)^{l+m} \binom{s-m}{n-l}
\label{...
- 582
2
votes
0
answers
38
views
what type of polynomials are these? similar to laguerre polynomial generating function.
I'm studying polynomials generated as coefficients of this generating function:
$$ [x^n]f(x) = [x^n] \frac{\cos(t\frac{1-x}{1+x})}{(1-x^2)^{\frac{1}{4}}}$$
This is kind of similar to Laguerre ...
- 79
3
votes
0
answers
50
views
Reference on polynomial attached to permutation group
Let $G$ be a permutation group acting on $n$ objects. Let $C(g)$ be the set of cycles of an element $g\in G$, and define $l(c)$ to be the length of a cycle $c$. Now set
$$T(G) = \sum_{g\in G}\sum_{c\...
0
votes
0
answers
24
views
Using Symbolic Method to derive generating function for rooted trees using their line graph
It is well known that the line graph of any tree $T$ on $n$ vertices is a block graph of size $n-1$ where each vertex is contained in at most $2$ blocks.
If we now consider a rooted tree with root $r$,...
- 1,323
0
votes
1
answer
70
views
how to calculate the number of valid positions here?
I have an $N \cdot M$ board with some of it's tiles being forbidden meaning they act as a barrier/hole in the board (meaning if you have two rooks and you don't want the rooks to threaten each other ...
- 73
1
vote
0
answers
41
views
Generating function for A140717
Let $T(n, k)$ be A140717 (i.e., triangle read by rows: $T(n,k)$ is the number of Dyck paths $d$ of semilength $n$ such that sum of peakheights of $d$ - number of peaks of $d$ equals $k$ ($n \geqslant ...
1
vote
1
answer
73
views
Understanding proof of Lah numbers exponential generating function
Lah numbers satisfy $L(n, k) = \frac{n!}{k!}\binom{n-1}{k-1}$. In my Professor's lecture notes I found:
Lah numbers have the following exponential generating function:
$$\sum_{n=k}^{\infty} L(n, k) \...
- 29
5
votes
2
answers
169
views
can you help me to see how the expansion $\big(\frac{a}{1+a}\big)^1+\big(\frac{a}{1+a}\big)^2+\big(\frac{a}{1+a}\big)^3+...$ end up with a?
Assume that $f(a)= \frac{a}{1-a}=a+a^2+a^3+...+..$
I want to find what $f(\frac{a}{1+a})$ is.
We can easily obtain it by: if $f(a)= \frac{a}{1-a}$, then $f(\frac{a}{1+a})= \frac{\frac{a}{1+a}}{1-\frac{...
- 51
3
votes
1
answer
85
views
Generating Functions Tiling Problem
I am asked to consider a $1 × n$ rectangle $R_n$ whose vertices are
$(0, 0),(0, 1),(n, 0),(n, 1)$. First, I am asked to derive a closed form for the amount of ways $R_n$ can be covered with tiles of ...
- 43
0
votes
1
answer
44
views
Proving identities for $\cos(x\sin\theta)$ and $\sin(x\sin\theta)$ involving Bessel functions.
I'm working on this exercise about Bessel functions:
Suppose $x>0$ and $\theta\in\mathbb{R}$. Show that
$$\cos(x\sin\theta) = J_0(x)+2\sum_{n=1}^{+\infty}J_{2n}(x)\cos(2n\theta)$$
$$\sin(x\sin\...
- 145
3
votes
1
answer
63
views
Producing generating function for Smirnov words from general form using variables a and b
Suppose we have an alphabet ${\mathcal{A}}$ of size ${m}$. Its generating function (using the variable ${z}$ to mark length) is simply ${A(z) = mz}$, as ${\mathcal{A}}$ contains ${m}$ elements of ...
user1379473
1
vote
2
answers
108
views
proof using combinatorics
A child has a set of $96$ distinct blocks. Each block is one of $2$ materials (plastic, wood), $3$ sizes (small, medium, large), $4$ colours (blue, green, red, yellow), and $4$ shapes (circle, hexagon,...
- 85
1
vote
3
answers
72
views
Show that the constant term of a generating function is not null
Given a positive integer $n$, is there a standard/simple argument to show that the constant term of the following generating function:
$$\frac{\left(\frac{x^{2n}-1}{x-1}\right)^{2n}}{x^{n(2n-1)}}$$
is ...
- 2,201
0
votes
1
answer
67
views
Infinite product of generating functions
I once saw this amazing problem from some combinatorics book. (I forgot the book name) It is about using generating function to count the number of solutions.
$a_1+2a_2+4a_3+8a_4+\cdots=n$($n \in \...
- 406
10
votes
3
answers
344
views
Can you do better than partial fraction decomposition?
Consider the function $f_3(x)=\frac1{(1-x)(1-x^2)(1-x^3)}$. We can think of computing some sort of partial fraction decomposition for $f_3(x)$. For example,
$$f_3(x)=\frac{1/6}{(1-x)^3}+\frac{1/2}{(1-...
- 433
2
votes
0
answers
22
views
Find the generating function $\mathcal{B} = \sum_{n=0}^{\infty}\left(\sum_{i+j+k=n}a_{i+j}a_{j+k}a_{k+i}\right)X^n.$
Consider a sequence $\{a_n\}$, the ordinary generating function for it is given by $\mathcal{A} = \sum_{n=0}^{\infty}a_nX^n$. Then
$$\mathcal{A}^2 = \sum_{n=0}^{\infty}\left(\sum_{i+j=n}a_i a_j\right)...
- 829
1
vote
0
answers
41
views
How to find $\lim_{n \to \infty} \sum_{k=2}^{n-2} \zeta(k) \zeta(n-k) x^{k-1} = x^{-1} - \psi_{0}(-x) - \gamma$ from generating function of $\zeta()$?
In equation (130) of this page, the identity $$\lim_{n \to \infty} \sum_{k=2}^{n-2} \zeta(k) \zeta(n-k) x^{k-1} = x^{-1} - \psi_{0}(-x) - \gamma \label{1} \tag{1} $$ is stated. Here, $\zeta(\cdot)$ is ...
- 7,336
3
votes
1
answer
122
views
Combinatorial expression for coefficients of $(x+y)^m (x-y)^n$
Is there a simple combinatorial expression for the coefficients of $x^hy^b$ in the polynomial $(x+y)^m (x-y)^n$, for any $m,n$?
I tried using induction but I was not able to obtain reasonable formulas....
- 1,348
1
vote
1
answer
78
views
Number of arbitrary bracket strings (with n open brackets) which turns into correct ones when adding k closing brackets
There are sequences (strings) of brackets containing exactly $n$ opening brackets. How many of them turn into correct bracket sequences (i.e. with matching brackets) when adding $k$ closing brackets ...
- 132
0
votes
2
answers
52
views
"Distinguished" rise (ascent) in permutation. What exactly does it mean? [closed]
The text 'Analytic Combinatorics' by Flajolet & Sedgewick says that
(p.209 quote)
[Rises and ascending runs in permutations]
A rise(ascent) in a permutation $\sigma = \sigma_1\sigma_2....\sigma_n$ ...
- 203
1
vote
0
answers
33
views
Lognormal distribution and Galton Watson process
I have been studying a Galton Watson process that creates random binary trees with probability of survival $p_{s}$ and offspring distribution $p(k)=p_{s}\delta(k-2)+(1-p_{s})\delta(k)$. I'm ...
- 41
1
vote
2
answers
105
views
Find number of solutions for integer equation: way to simplify calculations?
Find number of solutions of the equation:
$$
x_1 + x_2 + x_3 + x_4 + x_5 + x_6 = 20,
\quad 0 \leq x_i \leq 8,
\quad x_i \in \Bbb Z
$$
The answer $(27237)$ can be found with generative polynomial:
$$
...
- 132
0
votes
0
answers
61
views
Find number of solution to an equation using generating functions [duplicate]
I need to find the number of integer solution to $x_1+x_2+x_3+x_4=30$ such that $x_i\geq0$ and $x_1\leq5, x_2\leq10, x_3\leq15, x_4\leq21$
I was able to come up with the generating functions for each ...
- 463
0
votes
1
answer
60
views
Can the gamma function be generalized to quaternions and how? [duplicate]
The gamma function is a generalization of the operator !n. The question is: Can the concept of the gamma function be generalized to quaternion analysis and the use of quaternions, and how?
4
votes
1
answer
135
views
Sum of reciprocal Bernoulli numbers
What is sum of the Bernoulli numbers? discusses the sum of the Bernoulli numbers, using divergent sum methods since the Bernoulli numbers grow exponentially. This exponential growth makes it so that ...
- 9,045
0
votes
1
answer
44
views
How the modified Bernoulli numbers relate to the ordinary Bernoulli numbers
The modified Bernoulli numbers are defined as the numbers $b_k$ whose generating series is
$$\frac 1 2\log\left(\frac{\sinh \frac t 2}{\frac t 2}\right) = \sum_k b_k t^k.$$
(I use a slightly different ...
- 9,852
1
vote
1
answer
41
views
Generating function of $P_{11}^{2n}$
I am studying Markov chains and I am interested in calculating the generating function ($U(s)$) of $P_{11}^{2n}$, where
$$
P = \begin{pmatrix}
0 & 1-\alpha & \alpha & 0 \\
...
- 797
1
vote
0
answers
33
views
Can Zeckendorf's theorem be proven using generating functions?
First, I state Zeckendorf's theorem.
Zeckendorf's theorem states that every positive integer can be represented uniquely as the sum of one or more distinct Fibonacci numbers in such a way that the sum ...
- 829
1
vote
1
answer
85
views
Deriving the generating function for the Catalan triangle
I'm hoping for help in deriving the two-variable generating function for the Catalan triangle, also known as a truncated version of Pascal's triangle. There are a few variations floating around, so to ...
- 2,287
2
votes
0
answers
69
views
writing regular expression for exactly once $111$ in binary strings for finding Generating functions
I am looking for the regular expression for binary strings consisting of $1$ and $0$ and containing $111$ exactly once to find their generating functions. For example, $101100001110,000111000,01010111,...
user1351065
-1
votes
2
answers
57
views
Question regarding generating function. [closed]
In my text book there's an example (Please see image attached) related to generating functions which uses quadratic formula to get the roots then it's transformed into a form which I can't get my head ...
6
votes
2
answers
394
views
Why are Probability Generating Functions important?
I am trying to learn more about Probability Generating Functions. Here is my basic understanding:
For a discrete random variable $X$, the probability generating ...
- 719
2
votes
4
answers
113
views
Solve recurrence relation $2a_n=a_{n-1}+2^n$ using generating functions
Solve $2a_n=a_{n-1}+2^n$, $a_0=1$, for all $n \geq 1$
Here is my attempt:
Let $G(x) = \sum_\limits{n=0}^\infty a_n x^n$, then we have
$$2 \underbrace{\sum_\limits{n=1}^\infty a_n x^n}_{G(x)-a_0 x^0} = ...
- 783
0
votes
2
answers
85
views
Expand $\sqrt{1-4x}$ into an infinite power series
I'm reading the book Math Girls. At one time (p. 131), a closed form was obtained for generating function $C(x)$ like below.
$$C(x)=\frac{1-\sqrt{1-4x}}{2x}$$
To facilitate further deduction, the ...
- 283
2
votes
1
answer
115
views
Solving the non-linear recurrence $d_i + 2 i d_{i-1} = e_{i+1}$ (via generating functions)
I've been studying the recurrence $$d_i + 2i d_{i-1} = e_{i+1} =: (-2a)^{i+1}e^{-a^2} \quad\quad\quad a \in \mathbb{R}$$
attempting to solve for the sequence $(d_i)$. (The $d_0$ case is defined ...
- 143
0
votes
1
answer
60
views
Counter example to the identity theorem for two generating functions
I want to give an example of two generating functions $\psi_{X_+}$ and $\psi_{X_-}$ for random variables $X_+$ and $X_-$ with values in $\mathbb{N}_0$ which coincide on infinitely many points $x_i\in(...
- 1,241
2
votes
0
answers
53
views
Countable system of differential equations
I'm interested in solving the following countably infinite system of ODEs
\begin{equation}
\frac{d}{dt}H_{n,k}\left(t\right)=\left(-p\right)nH_{n,k}\left(t\right)+\left(-q\right)nH_{n,k+1}\left(t\...
- 358
-1
votes
2
answers
60
views
closed form expression for the generating function $\sum_{n=0}^\infty \binom{m+n}{n} x^n$ [closed]
How to find the closed form expression for the generating function:
$$
\sum_{n=0}^\infty \binom{m+n}{n} x^n\quad
\mbox{where}\ m\ \mbox{is a}\ positive\ integer\ ?.
$$
- 35
0
votes
1
answer
85
views
Generating function and currency
We assume that we have a country's currency that contains three coins worth 1, 3, and 4. How many ways can we get an amount of $n$ using these three pieces?
In others words what is the number of ...
- 35