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
2answers
33 views

What's the number of natural solutions of the following equation :

$x_1 + 2x_2 + 3x_3 = n$ $x_1, x_2, x_3≥0$ Find a regression formula (or a recursive function, not sure how it's called in English) to calculate the number of solutions for all $n≥0$. Find the ...
2
votes
3answers
44 views

Understanding a formula for coefficients $a_n$ of the generating function$\sum_{n \ge 0} a_nx^n=\frac{1}{\sqrt{1-x}}$.

(HMMT 2019 Alge/NT 8) I am trying to understand the solution of this problem, but I don’t understand how the condition described in the title lead to $a_n=\frac{_{2n}C_n}{4^n}$ Does it have anything ...
1
vote
2answers
27 views

How to find a generating function that has only coefficients $a_n \equiv 0~(mod~k)$ from the generating function for $\{a_n\}$?

I am trying to work through a few problems, and one asks to sum over the Fibonacci numbers which are even-valued (it is the Euler Project problem #2). I realized that (if we index like $\langle 1, 2, ...
2
votes
1answer
33 views

Characterization of the geometric distribution

$X,Y$ are i.i.d. random variables with mean $\mu$ , and taking values in {$0,1,2,...$}.Suppose for all $m \ge 0$, $P(X=k|X+Y=m)=\frac{1}{m+1}$ , $k=0,1,...m$. Find the distribution of $X$ in terms of $...
0
votes
0answers
13 views

Multi-folds of Generating Functions

Stochastic Process Generating Function Practice I don't understand how $G_{N}(s) = G_{M}(G_{Y_i}(s))$. $N = Y_1 + Y_2 + Y_3 + ... +Y_M$, which to my understanding the main generating function should ...
0
votes
2answers
57 views

Solving a recurrence relation such that $\sum_{k=0}^\infty x_k = 1$

Question Let $x_0$ be arbitrary, $p \in (0,1)$ and assume the following holds: $$x_1=\frac{(1-p)^2(1+2p)}{p^3}x_0$$ $$x_2=\frac{(1-p)^3(1+3p-3p^3)}{p^6}x_0$$ and in general: $$ x_k(1-p)^3 + 3p(1-p)^2 ...
1
vote
1answer
29 views

Is it possible to “invert” an exponential generating function?

Consider the exponential generating function for a sequence $\mathbf{a}$, given by: $$\text{EG}_\mathbf{a}(x) = \sum_{n=0}^\infty a_n \frac{x^n}{n!}.$$ In order to find the sequence $\mathbf{a}$ ...
0
votes
1answer
27 views

Properties of the probability generating function

My understanding of PGF is that it is just an efficient way to find the properties of the distribution (mean variance etc) and represents the whole distribution, and there isn’t really any meaning to ...
41
votes
3answers
2k views

Expected maximum number of unpaired socks

Like all combinatoric problems, this one is probably equivalent to another, well-known one, but I haven't managed to find such an equivalent problem (and OEIS didn't help), so I offer this one as ...
0
votes
0answers
26 views

generating functions problem need help with compositions

We have $n$ letters sitting in a line. We break this line into three sublines. Within every subline, we choose two letters on which to place a single stamp. (The stamps are identical.) Let $b_n$ be ...
0
votes
0answers
33 views

Stirling Numbers of the Second Kind Ordinary Generating Function Identity

The ordinary generating function for the Stirling Numbers of the Second Kind are given by $$\sum_{n=0}^\infty{S(n,k)x^n}=\frac{x^k}{(1-x)(1-2x)...(1-kx)}$$ In a paper by Gessel, an alternative ...
0
votes
1answer
30 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_{n=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
1answer
62 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
47 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
31 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
25 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
63 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
63 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
39 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
56 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
29 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
49 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
49 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
47 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
73 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
53 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
57 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