Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
7 views

Methods for Determining Closed Form of Polynomial Numerator of a Rational Generating Function

Good morning. I have the following; Let $$\beta_k(x)=\sum_{k=0}^\infty{b(r;n,k)x^n}$$ Here, $b(r; n,k)$ are called Associated Sterling Numbers of the Second Kind, and are the number of ways to ...
1
vote
0answers
17 views

Find the generating function for number of quadrangulations

I have this homework to solve, I've got some ideas but not sure it's the right direction. A set of chords of a convex $2n$-gon is a quadrangulation if no two chords intersect and all faces are ...
4
votes
2answers
45 views

Choosing $r$ things from a set containing $l$ things of one kind, $m$ things of a different kind, $n$ things of a third kind,…

Here is a statement from a textbook that I'm referring to: From a set containing $l$ things of one kind, $m$ things of a different kind, $n$ things of a third kind and so on, the number of ways of ...
1
vote
1answer
29 views

Using generating functions to determine conditional probability of five heads in a row

My question is about a method to approach counting in MATHCOUNTS States #29 2019 by using generating functions. Here is the problem: Chris flips a coin 16 times. Given that exactly 12 of the flips ...
1
vote
1answer
23 views

If $e^{x/2(t+1/t)}=\sum\limits_{n=-\infty}^\infty I_n t^n$ then $I_n=\sum\limits_{k=0}^\infty \frac{\left(x/2\right)^n}{(n+k)!k!}$

Shifting trick in double series show that if $\displaystyle e^{x/2(t+1/t)}=\displaystyle\sum\limits_{n=-\infty}^\infty I_n t^n$ then $\displaystyle I_n=\sum\limits_{n=0}^\infty \frac{\left(x/2\right)^...
0
votes
3answers
36 views

Find the sum of the following A.G.P

Find the sum of: $1×2+ 2×3x+ 3×4x^2...$ I tried the problem and I am getting answer as $\frac{(2-x)}{(1-x)^2}$ which I think is wrong Can Someone please tell the correct answer so that I can find my ...
0
votes
1answer
61 views

How many ways to split a convex polygon to squares?

If $a_0 = 0$ and $a_1 = 1$, and $a_n$ stands for the number of ways to split a convex polygon with $n+1$ angles to squares, is given by $$a_n = \sum_{k+l+m = n }a_ka_la_m$$ Now, using generating ...
2
votes
1answer
61 views

Half of the binomial theorem

The binomial theorem states that the generating function $\sum_{k=0}^n {n \choose k} x^k$ is equal to $(1+x)^n$ for any $n$. For a given $n$, let $$B(x)=\sum_{k=0}^n {2n+1\choose k} x^k.$$ That is, ...
1
vote
1answer
37 views

Extracting coefficients from 2-D generating function for recurrence relation

We want to extract the coefficients for a recurrent relation from the 2-dimensional generating function $$G(x,y)=\frac{y^{n-1}(1-y)x}{xy^n-x-y+1}$$ where $n$ is a strictly positive integer constant. ...
0
votes
0answers
10 views

Offspring generating function in Branching process.

Find the extinction probability for a branching process with offspring distribution $a =(1∕6, 1∕2, 1∕3)$. Solution The mean of the offspring distribution is $\mu = 0(1∕6)+ 1(1∕2)+ 2(1∕3)...
0
votes
0answers
12 views

problem on translation in quantum mechanics [duplicate]

$$\lim_{N\to \infty} \left(1-\frac{x}{N}\right)^N=\exp(-x)$$ Can anyone give a proof for it, I see a similar result in quantum mechanics ( Momentum as a generator of translation ). The textbook does ...
0
votes
1answer
48 views

Finding the $m^\text{th}$ term of an expression?

How to find the $m^\text{th}$ term for the following expression: $$ \left.\frac{\partial^m}{\partial s^m}e^{a s^2}\right|_{s=0}$$ Is there any analytical approach? I computed first few terms ...
1
vote
2answers
55 views

Generalized central binomial coefficients convolution

It is well-known that \begin{align*} \sum_{i=0}^n \binom{2i}{i}\binom{2n-2i}{n-i} = 4^n, \end{align*} where one might use combinatorial arguments or generating function technique to prove this. Now I ...
0
votes
0answers
32 views

Probability mass function (for y)

The probability mass function of a random variable $Y$ is given by $$f(y) = \frac{a^{(y-3)}}{(e^a)(y-3)!} \quad \text{for } y = 3,4,\dots\text{ and } a > 0$$ Derive the cumulant generating ...
0
votes
1answer
33 views

Generating functions with power series

How to find the series expansion for generating function $\frac {1} {1-2x-x^2}$? I have got so far $$\frac {1} {1-2x-x^2}=-\frac {1} {2\sqrt2} (\frac {1} {1-\sqrt2+x} -\frac {1} {1+\sqrt2+x})$$ $\...
0
votes
1answer
28 views

Number of solutions by generating functions

**Q4 Find the number of ordered triples $(x, y, z)$ of nonnegative integers satisfying the conditions: (i) x ≤ y ≤ z; (ii) x + y + z ≤ 100. (RMO 2003 INDIA)** My approach to the problem is through ...
1
vote
1answer
27 views

Recurrence Relation with generating function

We have the generating function $$1/(1−2x−x^2)=\sum_{n=0}^{\infty}a_nx^n$$ Show $$a_n^2 + a_{n+1}^2 = a_{2n+2}$$. I am thinking of finding a 2 × 2 matrix A and the text gives a hint of $$A^{n+2}= \...
-1
votes
1answer
29 views

Using generating functions, find the number of solutions of the equation

so I've searched a lot about this and I've seen a few solutions but I didn't understand any of them. I have this equation which I'm meant to use generating functions to find the number of solutions ...
0
votes
0answers
11 views

Convergence for trivariate power series

Consider a trivariate power series $F(z,x,y)=\sum_{n=0}^\infty\sum_{h=0}^\infty\sum_{k=0}^\infty\alpha_{n,h,k}z^nx^hy^k$ such that $F(\rho,2,2)<\infty$ for some $\rho>0.$ Is it true that $$\...
3
votes
1answer
46 views

$L^2$ norm of the first derivative of Legendre polynomials

Recently I have encountered a question while studying the orthogonal properties of Legendre's polynomial $$ \int_{-1}^{1} P_{n}^{\prime}(x) P_{n}^{\prime}(x)=n(n+1), n\geq1 $$ I have tried the ...
0
votes
0answers
24 views

Is this the correct generating function to determine the number of ways to choose k objects from n objects when the ith object appears at least 2i

Find the generating function to determine the number of ways to choose k objects from n objects when the ith object appears at least 2i times for 1 ≤ i ≤ n. So if the generating function for one ...
2
votes
1answer
41 views

Generating function for number of distinct coordinates in integer lattice.

I'm looking for the value of the generating function $$f_{k, n}(x) = \sum_{y \in [n]^k}{x^{\# \text{distinct coordinates of y}}} = \sum_i{a^{(k, n)}_ix^i}$$ For example, for $k = 1$, we have $$f_{1, ...
0
votes
0answers
49 views

Generating function / combinations for a sum with restrictions

So the general story is "we draw identical marbles (with replacement) and place them randomly in 3 different bins" (generic stars / bars), we continue drawing until a bin has exactly 10 marbles. I ...
2
votes
4answers
54 views

How prove with using mathematical induction $\prod_{i=0}^n 1+q^{2^i} = \frac{1-q^{2^{n+1}}}{1-q}$?

Prove the identity \begin{align} \prod_{i=0}^n \left(1+q^{2^i}\right) = \frac{1-q^{2^{n+1}}}{1-q} \end{align} for each nonnegative integer $n$. To begin with, I cannot verify the equality itself. ...
3
votes
1answer
79 views

Does $e^x e^x$ really equal $e^{2x}$?

I'm trying to prove the well-known identity $$\sum_k {n \choose k} = 2^n$$ with exponential generating functions (egf's). The idea is to note that the egf of the left hand side and the right hand side ...
0
votes
1answer
19 views

Unique generating function for a sequence

For an infinite sequence $\{a_n\}$, is the generating function unique to that sequence? Can I say for example that $\frac{x}{1-x-x^2}$ is the g.f. of the Fibonacci sequence $F_n$ with initial ...
16
votes
3answers
1k views

How do I prove this combinatorial identity

Show that $${2n \choose n} + 3{2n-1 \choose n} + 3^2{2n-2 \choose n} + \cdots + 3^n{n \choose n} \\ = {2n+1 \choose n+1} + 2{2n+1 \choose n+2} + 2^2{2n+1 \choose n+3} + \cdots + 2^n{2n+1 \choose ...
0
votes
0answers
18 views

Issue w/ extracting coefficients from generating function using IDTFT

This q will make use of these 3 DTFT pairs... $$ \require{extpfeil}\Newextarrow{\xleftrightarrow}{15,15}{0x2194} \begin{array}{rcl} \alpha x_1[n] + \beta x_2[n] & \xleftrightarrow{\mathscr{F}} &...
1
vote
0answers
44 views

drawing unique elements with replacement

I have a situation where I will draw a random number of balls from an urn with $r$ red balls and $b$ blue balls, with $N=r+b$. The number drawn is $k$, and I know the distribution $k$ comes from. ...
0
votes
3answers
47 views

Probability generating function of exponential distribution

The exponential distribution is given by: $$PDF: \lambda e^{\lambda x}$$ And the formula for probability generating function is given by: $$G(z) = \sum_{x=0}^\infty p(x)z^x$$ where $p(x)$ is a ...
1
vote
1answer
46 views

Extracting coefficients from two-dimensional generating function

We have the two-dimensional recurrent series $F(r+1,s+2) = F(r,s) + F(r,s+1) + F(r,s+2)$ and the boundary conditions $F(r,0)=1$, $F(0,s)=0$ for all $s>0$ and $F(0,0)=1$ and $F(r,1)=r$. This series ...
3
votes
0answers
72 views

Proving a property of a solution to a set of nonlinear polynomial equations

Consider the following system of equations for $R_{i}(\lambda)$ \begin{align} R_1 &= \frac{\lambda}{4}(1 + R_3 + 2 R_2 R_1) \tag{1.1}\\ R_2 &= \lambda \left[q + \left(\frac{1}{2} - q\right)...
1
vote
2answers
54 views

Multiplying two generating functions

I am trying to complete exercise 10 from here. It says to find $a_7$ of the sequence with generating function $\frac{2}{(1−x)^2} \cdot \frac{x}{1−x−x^2}$. I wrote down the first $7$ numbers of both ...
1
vote
0answers
52 views

Summation Formula for Tangent/Secant Numbers

I came across the following expressions: $$\begin{align} \widehat{S}_{2n} &:= \sum_{1 \leq k_1<\cdots<k_n \leq 2n} \prod_{\ell=1}^n (k_\ell-2\ell)^2, \\ \widehat{T}_{2n+1}&:=\sum_{1 \...
0
votes
1answer
11 views

how is the abs val of excess of p(n|odd # of parts) OVER p(n|even #of parts) = p(n|distinct odd parts?)

A question in The Elementary Theory Of Partitions asks the reader to show that the absolute value of excess of the number of partitions $n$ with an odd number of parts over the number of those with an ...
1
vote
1answer
54 views

Generating function of recurrence relation $T(n) = T(n-1) + (n-1)$

Generating function of recurrence relation $T(n) = T(n-1) + (n-1)$ I've been trying to get the closed form for this recurrence by using generating function, and got to the following $$ G(x) - xG(x) -...
2
votes
2answers
71 views

Find $f^{(22)}(0)$ for $f(x)=\frac{x}{x^{3}-x^{2}+2x-2}$

Find $f^{(22)}(0)$ for $f(x)=\frac{x}{x^{3}-x^{2}+2x-2}$ I know that I should use Taylor's theorem and create power series. However I don't have idea how I can find $a_{n}$ such that $f(x)=\sum_{n=1}^...
0
votes
2answers
22 views

Stirling Number Generating Function Relationship

In "Generatingfunctionology" by Herbert Wilf, there is a section where he derives explicit formulas for Stirling numbers. (Please see images below). I'm wondering how he arrives at the relationship ...
0
votes
2answers
62 views
2
votes
2answers
86 views

What is the generating function of $z^3 + 2z^5 + 5z^7 + 14 z^9+\dots$?

What is the generating function of $z^3 + 2z^5 + 5z^7 + 14 z^9+\dots$ ? The generating function can be written as follows: $$A(z)=\sum_{i>2}^{\infty} a_i z^{2i+1},\text{where } a_i \text{ is the ...
0
votes
1answer
26 views

Galton Watson process - Extinction probability

Let $(Z_n)_{n≥0}$ be a Galton Watson Process with offspring distribution $(p_n)_{n≥0}$ satisfying: $p_0,p_2>0,$ $p_1∈[0,1)$ and $p_n=0$ otherwise. Find the extinction probabilty q. My attempt: ...
1
vote
0answers
24 views

Asymptotics of Generating Coefficients along a Ray

Suppose I have a multidimensional array of numbers $a(n_1,\ldots,n_r)$, for $n_1,\ldots,n_r\in\mathbb N\cup\{0\}$. I can form the generating function $$A(x_1,\ldots,x_r)=\sum_{n_1,\ldots,n_r\geq 0}a(...
1
vote
2answers
63 views

Generating function of $\frac{h(x)}{(1-x)^2}$

If $h(x)$ is the generating function for $a_r$, what is the generating function of $$\frac{h(x)}{(1-x)^2}$$ Let $h(x)$ be written as $$h(x) = \sum_{r} a_r x^r $$ Consider more simply $$\frac{h(x)}{...
1
vote
1answer
43 views

Recurrence relation of partioning $n$ into exactly 3 parts:

I wanted to find a recurrence relation for partitioning an integer $n$ into exactly $3$ parts To be clear, I know the formula $P(n,k)=P(n-1,k-1)+P(n-k,k)$, but I want to derive a relation involving ...
0
votes
1answer
38 views

Result on partitions with distinct odd parts

Let $pdo(n)$ be the number of partitions of n into distinct odd parts. Then $p(n)$ is odd if and only if $pdo(n)$ is odd. I am well aware that a proof of this is available here but I want to do it ...
0
votes
1answer
94 views

Find the generating function to determine the number of ways to choose k objects from n objects when the ith object appears at least n + i times

Find the generating function to determine the number of ways to choose k objects from n objects when the ith object appears at least n + i times for 1 ≤ i ≤ n. the generating function for picking k ...
1
vote
0answers
35 views

Solution of generating function does not make sense

Consider the generating function $$G(x,t) = \sum_{n=0}^N P_n(t) x^n,$$ with $G(1,t) = 1$ and $G(x,0) = x^m$. From a master equation, I obtained the following partial differential equation for $G$: $$\...
0
votes
0answers
36 views

How do we defined our prediction models to be generalized well enough to be applied to unseen dataset?

How do we define our prediction models to be generalized well enough to be applied to an unseen dataset? And if there is an outlier in the data do we need to keep it or remove it? Have to justify the ...
0
votes
1answer
33 views

Generating functions question

How to transform $\sum_{n=2}^\infty n^2x^n$ to $\sum_{n=1}^\infty nx^n$
1
vote
1answer
47 views

Find number of ways to split $1$ dollar into $5$, $10$, $20$, $50$ cents

Find number of ways to split $1$ dollar into $5$, $10$, $20$, $50$ cents I am going to use generating functions: $$n = [x^{100}] (1+x^5+x^{10}+\cdots)(1+x^{10}+x^{20}+\cdots)(1+x^{20}+x^{40}+\cdots)(...