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.

-3
votes
0answers
22 views

Probability of picking a Green ball? [on hold]

With an infinite number of bags S1, S2, S3, etc. S1 contains 3 yellow balls and 2 green ones. Each of the following bags contains 2 green and 2 yellow balls. We draw balls from S1 and put it in S2, ...
1
vote
0answers
39 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
25 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 ...
0
votes
0answers
7 views

to show how a relation containing summation of products leads to a compact relation using generating function

I have faced with the relation $$I_k(x,t)=\sum_{n=0}^{\infty}x^n\sum_{n_1+\dots+n_k=n}\prod_{j=1}^{k}p(n_j,t)\tag{1}\label{eq1}$$ in some books. In these books, it is said that the above relation ...
1
vote
1answer
34 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 ...
2
votes
0answers
33 views
+50

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
47 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
47 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
53 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
65 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
19 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
60 views

How can I get the sequence of the generating function $T(z)$ given that $T(z)=z+1+(z+1)T(z)^2$

given that $$T(z)=z+1+(z+1)T(z)^2$$, how can I get the sequence?
2
votes
2answers
82 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
17 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
21 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
60 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
39 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
33 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
78 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
34 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
42 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)(...
0
votes
0answers
11 views

Recursion for probability that all verticies in set are degree one

I am trying to come up with a probability that all given verticies in a set are degree one. Here is what I have so far. In $G_{n,p}$, fix a subset of verticies $A = \{ a_1,\dots,a_k \} $ such that $|...
1
vote
1answer
42 views

Generating function of even Fibonacci numbers

I am trying to prove the Fibonacci number identity $$\sum_{k = 0}^n {n \choose k} F_k = F_{2n}$$ with generating functions. If we let $$G(x) = \sum_{k \geq 0} \frac{F_k}{k!} x^k$$ be the exponential ...
3
votes
1answer
79 views

Sequences of $0$ and $1$

How many is sequences with length $4n$ which contain only $0$ and $1$. $0$ occurs $2n$ times and $1$ occurs $2n$ times. Moreover number of occurs $0$ before $n$'th occur of $1$ can't be bigger than $n$...
2
votes
0answers
18 views

Sums of trigonometric functions and polynomials

I have to calculate sums of the following forms $$\sum\limits_{k=1}^nP(k)f_m(kx),$$ where $P\in\mathbb{R}[X]$ and $f_m(x)=\sin^m(x)$ or $f_m(x)=\cos^m(x)$. This problem comes from consideration of ...
1
vote
3answers
43 views

Using a generating function for piggy bank problem

A piggy bank contains 45 loonies and 25 toonies. How many ways can the coins be divided so that Jamie gets no loonies, Julie gets no toonies but at least 10 loonies, and Brenda gets an odd number of ...
1
vote
1answer
43 views

Solution of a Combinatorics problem using Generating function

Q) There are $4$ types of coins 1 paisa, 5 paise, 10 paise, 25 paise. Using these coins we have to make 50 paisa, how many combinations can we make ? I want to know whether this problem can be solved ...
4
votes
2answers
75 views

Number of solutions to $x_1+x_2+\cdots+x_5=41$

Use a generating function to count the number of integer solutions to $x_1+x_2+\cdots+x_5=41$ that satisfy $0\le x_i\le20$ for all $i$, $x_i$ is even when $i$ is even, and $x_i$ is odd when $i$ ...
1
vote
0answers
27 views

Prove that the Legendre polynomial holds true using the generating function and a binomial expansion.

I tried using that $$P_{2n}(z)=\frac1{2^{2n}(2n)!}\frac{d^{2n}}{dz^{2n}}(z^2-1)^{2n} $$ but I am having trouble taking the derivative when $n$ is unknown and $z$ is $0$. Any help would be greatly ...
4
votes
1answer
101 views

Prove that $\sum_{n} t_n x^n = \frac{x^k}{(1-x^2)^k(1-x)} $

Let $t_n$ be a number of sequences $$ 1 \le a_1 < a_2 < ... < a_k \le n $$ such that $a_{2i}$ is even and $a_{2i+1}$ is odd. Prove that $$\sum_{n} t_n x^n = \frac{x^k}{(1-x^2)^k(1-x)} ...
1
vote
3answers
162 views

Number of ways to express sum.

Consider three sets of cards colored Blue, Red and Yellow. Each set has cards numbered $1-10$. The $4$ remaining cards are all indistinguishable cards numbered $0$. Card numbered $i$ has the ...
1
vote
2answers
48 views

Ways of constructing 10 unit high tower w/ infinite # blocks 1, 2, & 3 units high?

A variation of this question has already been asked here, but I wish to solve via generating function. My question's answer is equivalent to the bijection... $$ card\left(\left\{\left[x_1\;x_2\;x_3\...
4
votes
2answers
60 views

Generating function for a combinatorics problem

I have this combinatorics problem: How many n strings are there of letters of english alphabet in which there are no consecutive z's? I want to solve this problem using generating functions ...
2
votes
1answer
69 views

Number of Motzkin trees with n nodes

I want to calculate $m_n$ - the number of different Motzkin trees (Trees where every node has zero, one or two nodes as children) that contain exactly $n$ nodes. The position of the children should ...
1
vote
1answer
78 views

100 prisoner and a light bulb probability question

I'm trying to solve the problem of 100 prisoners and light bulb using generating functions. The problem is a random prisoner out of 100 is sent a room with a light bulb in it each hour. How can you ...
1
vote
1answer
48 views

Borel Bivariate Generating Function

I want to prove the following statement: $$ \beta(t,x)=C(1+t,x)= \frac {C((1+t)x)} {1-xC((1+t)x)} $$ Where $C(x)$ is the generating function for the Catalan Numbers and $ \beta(x) $ is the Borel ...
0
votes
2answers
51 views

How to perform polynomial long division on 1/(1 - x)?

How do I perform polynomial long division on $\frac{1}{1 - x}$ to obtain the sequence $1 + x + x^2 + x^3 + \cdots$? In this video, the teacher went about it in the following way... $$ \require{...
1
vote
0answers
37 views

Szegő's method of finding the generating function of the Jacobi polynomials

In Orthogonal Polynomials (4th ed., Amer. Math. Soc. Colloq. Publ., vol. 23, 1975), Szegő starts off section 4.4 by giving the following integral representation of the Jacobi polynomials: $$P_n^{(\...
0
votes
2answers
26 views

combinatorics - generating functions

I need help making an OGF for $1 + x^i + x^{2i}+...+x^{ki}$. I already know how to verify that $1 +x +x^2+...+x^k$ can be written by $({1-x^{k+1}})/({1-x})$. I'm wondering if there is any correlation ...
1
vote
1answer
43 views

Create generating function: $(1, 1, -2, -2, 10, 3, -4, -4…)$

Find generating function (without using infinite series): a) (0, 1, 4, 9, 16, 25, 36...) b) (1, 1, -2, -2, 10, 3, -4, -4, 5, 5, -6, -6, 7...) (Only irregularity is the 10) Here's what I got:...
0
votes
2answers
68 views

How many ways to pay

Let $a_n$ be the number of ways in which you can pay $n$ amount with coins valued at 1, 2, 5, 10, 20, 50. Find the generating function for $(a_0,a_1,a_2,…)$. And find the value of $a_{23}$. Find ...
2
votes
2answers
35 views

Factorisation and roots of infinite polynomial

Recently, I’ve learned about generating functions. From my understanding you basically represent each “option” with a polynomial, and the resulting polynomials multiplied would give coefficients ...
0
votes
0answers
28 views

Generating of some binomial convolution looking sum

I have a sum as part of coming up as a generating function that is in the form of $\sum_{i=1}^a\sum_{k=1}^b \binom{a}{k}\binom{b-a}{i}(1-q)^{k+i}q^{b-i-k}(x^{b-i}y^{a-k})$, and would need a closed ...
1
vote
2answers
62 views

Generating function for special string 11100

Let $S$ be the set of $\{0,1\}$-strings that do not contain $11100$ as a string. Find the generating function of S where the weight of a string is its length. I tried this way : Consider all blocks ...
2
votes
0answers
37 views

Number of compositions in parts less equal two equals number of compositions in parts greater equal two.

Notations/Definitions: A composition of a natural number $n \in \mathbb{N}$ (I use $0 \notin \mathbb{N}$) is a sequence of natural numbers $n_1,n_2, ..., n_d \in \mathbb{N}$ such that $n_1+...+n_d = n$...
2
votes
2answers
82 views

Solving combinatorial problems with symbolic method and generating functions

I am trying to solve the following problems: a) Let $\mathcal{F}$ be the family of all finite 0-1-sequences that have no 1s directly behind each other. Let the weight of each sequence be its length. ...
1
vote
1answer
48 views

Domain limitations on generating function for Legendre polynomials

The generating function for legendre polynomials is $$\frac{1}{\sqrt(1-2ut+u^2)}=\sum_{i=0}^\infty u^iP_i(t)$$ where $P_i$ is $i^{th}$ legendre polynomial however for binomial expansion of left hand ...