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.

1
vote
0answers
26 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
74 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
46 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
41 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
105 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
36 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
40 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
35 views

Generating functions question

How to transform $\sum_{n=2}^\infty n^2x^n$ to $\sum_{n=1}^\infty nx^n$
1
vote
1answer
49 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
13 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
51 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
83 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
49 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
51 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
89 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
61 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
103 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
166 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
54 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
66 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
75 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
84 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
51 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
56 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
41 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
28 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
47 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
75 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
36 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
29 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
69 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
41 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
109 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
51 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 ...
1
vote
2answers
60 views

Recursion Question using Generating Functions

Here is my question: Consider the recurrence, $$a_{n+1}=2a_n+(-1)^n$$ with initial condition, $$a_0=0$$ Find and prove a formula for $a_n$. I don't really know how to prove this formula I tried ...
3
votes
0answers
36 views

Voting Counting Problem With Generating Functions

50 people have voted in an election, in which they are two candidates, and 25 people have voted for one candidate, and 25 people have voted for the other. You don’t know this yet, and are counting the ...
0
votes
2answers
59 views

Find the power series representation of $\frac{1+x}{1-2x-x^2}$

My textbook presents the following steps for finding the power series representation of $\frac{1+x}{1-2x-x^2}$: $$f(x)=\frac{1+x}{1-2x-x^2}=\frac{\frac{1}{2}\alpha}{1-\alpha x} + \frac{\frac{1}{2}\...
0
votes
0answers
13 views

Understanding an Identity in Arthreya's “Branching Processes”

I'm currently reading from Chapter 1: The Galton-Watson Process in Arthreya's "Branching Processes," and I'm not sure that I'm understanding this identity correctly. We're given our generating ...
1
vote
2answers
47 views

Coefficient of two power series [closed]

How do I find the coefficient of $x^n$ in $\sum_{k = 0}^{\infty}\frac{(-x)^k}{k!}\sum_{j = 0}^{\infty}x^j$?
1
vote
0answers
26 views

Order type of growth rates of exponential generating functions of binary sequences

The exponential generating function of a sequence $a[n]$ is: $\displaystyle \text{EG}(a;x) = \sum_{n=0}^\infty a[n] \frac{x^n}{n!}$ My question is about exponential generating functions of binary ...
0
votes
0answers
25 views

Counting Number of Ways for a Ballot

50 people have voted in an election, in which they are two candidates, and 25 people have voted for one candidate, and 25 people have voted for the other. You don’t know this yet, and are counting the ...
0
votes
1answer
28 views

Determine the sequence generated by the following exponential generating functions:

a) $f(x)=3e^{3x}$ I have \begin{align}f(0)&= 3 \\ f(1)&=3e^3 \\ f(2)&=3e^6 \end{align} So would my sequence be $a_n=3e^{2n}$? Or by recurrence $a_n=a_{n-1}(e^3)$? Or should I find a ...
0
votes
1answer
44 views

Finding sum of a sequence composed of two other sequences

I am having this sequence: $a(n) = 2\cdot a(n-1) - a(n-2) + 2 \cdot a(n-3) + a(n-4) + a(n-5) - a(n-7) - a(n-8)$ with this generating function: $x \cdot (1 - x - x^3) / (1 - 2 \cdot x + x^2 - 2 \cdot x^...
2
votes
4answers
72 views

Generating function with tough restrictions

In how many ways can a coin be flipped $25$ times in a row so that exactly $5$ heads occur and no more than $7$ tails occur consecutively? For the heads, I think that it is $\binom{25}{5}$, but I do ...
3
votes
2answers
41 views

Finding the generating polynomial for this string-counting combinatorial identity

The combinatorial identity goes as follows: $$ \sum_{k=0}^\ell {n+k-1 \choose k} {n-k-1 \choose {\ell-k}} = {2n-1 \choose \ell } \ ,\ell \leqslant n-1 $$ Intuitively, the RHS counts all (0,1)-...
2
votes
2answers
69 views

Help Solving Recurrence Relation: $a_n = n^3a_{n-1} + (n!)^3$

I'm trying to find an explicit formula for the following recurrence relation: $a_0 = 1$, $\forall n \ge 1: a_n = n^3a_{n-1} + (n!)^3$ So far though, my attempts have been unsuccessful. My ...
5
votes
2answers
80 views

Identity involving product of two binomial coefficients

Emprically it looks like the following identity holds, but I haven't been able to prove it. Can anyone find a proof? $$ \binom{m+k}{k}\binom{n+k}{k}=\sum_{i\geq0}\binom{m}{i}\binom{n}{i}\binom{m+n+k-i}...
1
vote
1answer
38 views

Gen func “The number of partitions of n where each part occurs 2, 3, 5 times = number of partitions of n…”

The number of partitions of n where each part occurs 2, 3, 5 times = number of partitions of n with parts modulo 2,3,6,9,10 modulo 12 This is from Subbarao 1971 but I don't quite understand the ...
4
votes
2answers
77 views

Product between a power series and polynomial of finite degree

Consider the matrix $A_{n \times n}$ with its characteristic polynomial, being $a(z)=det(zI-A)$ of degree $n$: $ a(z)= a_nz^{-n} + ... + a_1z^{-1} +a_0 $ Consider now the product $P(z)=a(z)(zI-A)^{...