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.

learn more… | top users | synonyms

0
votes
1answer
13 views

Show that $G_Y (s) = G_N (G_X(s))$ and $\mathbb{E}(Y ) = \mathbb{E}(N)\mathbb{E}(X_i)$ [on hold]

Suppose that $X_1, X_2, \ldots$ are independent identically distributed non-negative random variables with common probability generating function $G_X(s)$, and suppose that $N$ is an independent ...
2
votes
1answer
24 views

Easy way of seeing if swapping summation is ok? (Generating functional derivation of Bell numbers)

On page 21 of his book generatingfunctionology (available for free on the author's homepage), the author rearranges the summations in the following way: ...
1
vote
1answer
70 views

Using generating functions to answer how many bit strings of length N have no 000

The Problem I've been self-studying Introduction to Analysis of Algorithms by Sedgewick and Flajolet. I'm on the fifth chapter, and struggling with exercise 5.1: How many bit strings of length N ...
21
votes
1answer
222 views
+400

Odd digits of $2^n$

Let $u_{b}(n)$ be equal to to number of odd digits of $n$ in base $b$. For example: In base $10$, $u_{10}(15074) = 3$ In base $13$, $u_{13}(15610) = u_{13}([7, 1, 4, 10]_{13}) = 2$ What is the ...
2
votes
0answers
46 views

A recursion formula related to *Catalan numbers*

When I was working on a problem related to Catalan Number, I deduced the following recursion formula: \begin{equation} a_{l,r}=a_{l-1,r}+a_{l-1,r-1}+a_{l-1,r-2}+\ldots+a_{l-1,l-1},\\ where \quad r \ge ...
0
votes
1answer
38 views

How to solve the recurrence relation $T(n)=aT(n-1)+bn^c$ with $T(1)=1$

How to solve this recurrence relation? $ T(n)=aT(n-1)+bn^c \\T(1)=1,$ where a, b, c are constant. I want to solve it using generating function, but get stuck. Could anybody help me?
1
vote
1answer
52 views

Is there any mathematic meaning of generating function at some value?

Out of curiosity I am trying to learn some material about generating functions. Now I understand that if I will expand Fibonacci generating function, $f(x) = \frac{1}{1-x-x^2}$ I will get a series ...
4
votes
0answers
62 views

Dealing with a difficult sum of binomial coefficients, $\sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j} $

I am interested in finding an upper bound for the sum $$F(n)= \sum_{l=0}^{n}\binom{n}{l}^{2}\sum_{j=0}^{2l-n}\binom{l}{j}.$$ Ideally it should be possible to evaluate it exactly using some ...
0
votes
0answers
29 views

$e^{e-1}-e$ and a series involving Stirling numbers of second kind

First, using the generating function for the Stirling numbers of second kind ${m\brace n}$ $$\frac{(e^x-1)^n}{n!}=\sum_{m=n}^{\infty}{m\brace n}\frac{x^m}{m!},$$ multiplying by $e^x$, and integrating ...
0
votes
1answer
33 views

Use generating function to check how many solutions are to get balls from boxes and roll dices

In the box are 4 red balls, 5 blue balls and 2 yellow balls. How many possible solutions there are to get 7 balls from box to have at least 1 red ball and exactly 2 blue balls? I'm not sure I am ...
1
vote
0answers
28 views

Proof that two generating function are equals for the sequence which $n$-th number is:

I am not sure I am doing this exercise good 1) $p_n $ | all parts are pairs different and 2) $p_n $| all parts are not higher than $m$ I found these functions in book, first is: $$ ...
0
votes
0answers
14 views

Bounds on the heights of the minimal polynomials of the algebraic coefficients of linear recurrence relations

Given a linear recurrence relation $$ a_n=c_1a_{n-1}+c_2a_{n-2}+\cdots+c_ka_{n-k} $$ with characteristic polynomial $$ ...
1
vote
1answer
53 views

Substitution in a geometric series: $\sum_{n=0}^{N} x^n = \frac{x^{N+1} -1}{x-1}$

To find a formula for the sums of square of first n natural no, the following method is applied in generating functionology, we know $$\sum_{n=0}^{N} x^n = \frac{x^{N+1} -1}{x-1}$$ So we apply the ...
6
votes
3answers
248 views

Find the number of all subsets of $\{1, 2, \ldots,2015\}$ with $n$ elements such that the sum of the elements in the subset is divisible by 5

The problem is as in the question title. Only one addition - $n$ is not divisible by $5$. I already have a solution involving permutations, but recently I read about generating functions and I was ...
1
vote
1answer
23 views

Order of growth of sequence $f_{n} = 2f_{n-1} + f_{n-2}$

I'm currently stuck with the following problem. How do I calculate the order of growth of the following sequence: $f_{n} = 2f_{n-1} + f_{n-2}$ Assuming that $f_{0} =1$ and $f_{1} = 1$ I've got ...
1
vote
2answers
70 views

General solution for the series $a_n = \sqrt{(a_{n-1} \cdot a_{n-2})}$

Hey I'm searching a general solution for this recursive series: $a_n = \sqrt{(a_{n-1}\cdot a_{n-2})}$ $\forall n \geq 2$ $a_0 = 1$, $a_1 = 2$
1
vote
1answer
40 views

Making an infinite generating function a finite one

If we have some generating function $G(x)$ that generates terms indefinitely, is there a way to translate it to be a finite generating function? For example if I only want to generate the first $k$ ...
5
votes
1answer
66 views

A combinatorial expression is equal to a binomial coefficient squared

Problem: Prove for all natural numbers the following identity: $$\sum_{r=0}^{n}\frac{(2n)!}{(r!)^2((n-r)!)^2}=\dbinom{2n}{n}^2$$ I have just been successful in interpreting the LHS of the above as ...
0
votes
0answers
18 views

how to use and make sense of generating function method to solve coupled master equation?

I am trying to solve a two dimensional continuous time and discrete state master equation. The master equation is linear and looks as follows, $\frac{\partial P_A(x,y,t)}{\partial t} = k_{11} ...
3
votes
3answers
48 views

Finding the number of sequences with $0 \leq a_m \leq 3m$

Problem: Let $\alpha, \beta$ be non-negative numbers. Suppose the number of strictly increasing sequences $a_0, a_1, a_2 \cdots a_{2014}$ satisfying $0 \leq 3m$ is $2^{\alpha}(2\beta+1)$. Find ...
0
votes
1answer
24 views

How to solve non-homogeneous recurrences?

I am trying to find a way to solve non-homogeneous recurrences by solving the homogeneous and non-homogeneous parts separately. I can use generating functions for the whole thing, but I want to learn ...
2
votes
1answer
37 views

Catalan numbers derivation (quadratic part)

When deriving the Catalan numbers using generating functions, eventually you reach the step: $C(x) = 1 + xC(x)^2$ which means $xC(x)^2 - C(x) + 1 = 0$ Which, through the quadratic formula, means ...
2
votes
1answer
57 views

How to derive sequence from generating function?

If you are solving a problem and you encounter a generating function that you haven't seen before, is there a way to derive its underlying sequence representation? For example I came across ...
2
votes
1answer
44 views

Sum of squares using generating functions

I tried using generating functions to solve the sum of squares formula based on the recurrence $a_n = a_{n-1} + n^2$ with $a_0 = 0$. $$G(x) = \sum_{n=0}^{\infty} a_n x^n \\ G(x) - 0 = ...
1
vote
1answer
26 views

Bijection for Rook placecement and Stirling number of 2nd kind

Say we have an nxn chessboard from which the squares below the diagonal are removed to obtain a new board $C_n$. The board $C_3$ is shown below. Let the number of ways to place k non-attacking ...
1
vote
0answers
39 views

OEIS A249665 generating function

I'm stuck at finding the general term of the sequence $$1, 1, 1, 2, 6, 14, 28, 56, 118, 254, 541, 1140, 2401, 5074, \ldots$$ According to OEIS, Colin Barker conjectured the recurrence relation to be ...
5
votes
1answer
170 views

Do two permutations in $S_n$ generate a transitive subgroup of $S_n$?

On page 139 of Flajolet and Sedgewick's Analytic Combinatorics we read: "To two permutations $\sigma,\tau$ of the same size, associate a graph $G_{\sigma,\tau}$ whose set vertices is $V=[1\ldots n],$ ...
3
votes
3answers
42 views

How to properly set up partial fractions for repeated denominator factors

I was just trying to solve a problem that had the following item which I needed to split into separate generating functions: $$\frac{x}{(1-2x)^2(1-5x)}$$ I had assumed I needed to split it into: ...
1
vote
1answer
32 views

Finding the expectation and variance from a probability generating function

I need some help with the following question. I managed to get the p.g.f., and can get the expectation and variance in the normal ways, but need a helping hand in deducing them through the use of the ...
3
votes
1answer
31 views

Derivation of Catalan numbers

Trying to go through the proof. Let $C_n = \sum_{k=0}^{n-1} C_k C_{n-1-k}$ with $C_0 = 1$. $$ G(x) = \sum_{n=0}^{\infty} C_n x^n \\ G(x) = \sum_{n=0}^{\infty} (\sum_{k=0}^{n-1} C_k C_{n-1-k}) x^n \\ ...
0
votes
1answer
34 views

Is my generating function correct so far for this recurrence?

Trying to teach myself generating functions. Recurrence: $a_n = 18a_{n-1} - 80a_{n-2}$ where $a_0 = 1$ and $a_1 = 9$. Attempt at using generating functions: $$G(x) = \sum_{n=0}^{\infty} a_nx^n \\ ...
0
votes
1answer
26 views

Combinatorics problem using generating exp functions 2

Calculate the number of sequences of length n that are made of $1, 2, 3, 4$ so that the digits $1,2$ shows an even number of times, And the digit $3$ shows at least 1 time. I've been given a clue to ...
1
vote
1answer
48 views

Combinatorics problem using generating functions 1

In how many ways can you divide $n$ different balls into $5$ different boxes so that the two last boxes has an even number of balls. I've been given a clue to show that: $\sum_{n=0}^\infty {x^{2n} ...
1
vote
0answers
23 views

Get the probability generating function of $X$ from $Y$

For $X\in $Bin($n,p$) and $Y|X=k \in$Bin($k,p$), I have to show using the pgf that $Y \in$Bin($n,p^2$). I have been shown that the pgf of $Y$ can be written as, $$ ...
1
vote
0answers
22 views

Mean value theorem applied to the numerator in the result of the generating function

I am looking at the generating functions and I have stumbled upon the following result: $$Q(S)=\frac{1-P(s)}{1-s}$$ where $P(s)=p_0+p_1s+p_2s^2+...$ and $Q(s)=q_0+q_1s+q_2s^2+..$ and $P\{X=j\}=p_j$ ...
7
votes
1answer
61 views

What is the significance of this identity relating to partitions?

I was watching a talk given by Prof. Richard Kenyon of Brown University, and I was confused by an equation briefly displayed at the bottom of one slide at 15:05 in the video. $$1 + x + x^3 + x^6 + ...
1
vote
0answers
13 views

let $\mu$ = $E[V]$ where V is a typical family resulting from one individual, then prove that $E[X_n] = \mu^2$

I used the fact that $G_{v}^{'}(1) = \mu$ , $G_v(1) = 1$ and $G_n(z) = G_{n-1}(G_v(z))$ I then got the following: $E[x_n] = G_{v}^{'}(1) = \frac{d}{dv} G_{n-1}(G_v(1))$ which i simplified to: ...
24
votes
5answers
2k views

When the product of dice rolls yields a square

Succinct Question: Suppose you roll a fair six-sided die $n$ times. What is the probability that the product of the rolls is a square? Context: I used this as one question in a course for ...
1
vote
4answers
65 views

Derive the following generating function

$$\frac{1}{(1-x)^3} = \sum_{n=0}^\infty \binom{n+2}{2}x^n$$ I am not sure how to begin. $$\frac{1}{1-x} = \sum_{n=0}^{\infty} x^n$$ $$\frac{1}{(1-x)^2} = \sum_{n=0}^{\infty} nx^{n-1}$$ Then ...
3
votes
1answer
73 views

Closed form of a generating function $\sum _{n=1}^\infty x^{n^2}$

I am looking for a closed form of the expression $$F(x) = \sum _{n=1}^\infty x^{n^2} $$ The question arose when I attempted to prove Lagrange's four square theorem via generating functions. It ...
3
votes
2answers
99 views

Ordinary generating function of powers of 2

Is there a good closed form expression for the generating function of the formal power series $$ A(z) := \sum_{n=0}^\infty z^{2^n} = z + z^2 + z^4 + z^8 + z^{16} + \cdots. $$ Is there a tractable way ...
8
votes
4answers
178 views

Generating functions - deriving a formula for the sum $1^2 + 2^2 +\cdots+n^2$

I would like some help with deriving a formula for the sum $1^2 + 2^2 +\cdots+n^2$ using generating functions. I have managed to do this for $1^2 + 2^2 + 3^2 +\cdots$ by putting $$f_0(x) = ...
3
votes
2answers
81 views

Infinite recurrence relation which depends on subsequent sequence values

I'm trying to solve a problem and I have it reduced to solving the following recurrence relation which goes "backwards" as the value of $p_i$ depends on subsequent values. $p_i\in [0,1]$ $p_i = 0 (i ...
1
vote
2answers
58 views

Counting Polar Bears

My class is starting to work with generating functions, and I've been working on a problem related to the counting of polar bears. Suppose that there is this bar that polar bears really like to get ...
0
votes
1answer
21 views

Extracting the coefficient

So I have found the following through a series of differential equations and exponential generating functions: $[\displaystyle\frac{x^n}{n!}](\displaystyle\frac{1}{2}x^2 + x + 1)e^x$. I got this in ...
3
votes
2answers
22 views

Generating Functions To Deal With

I've been working on producing a closed-form generating function for the coefficients $a_n = \binom{n}{2}.$ I was wondering what might be a good procedure to start on this. I get that ...
0
votes
1answer
39 views

Use geometric progression formula to expand generating function into a power series?

I am a software engineer and I am studying combinatorics on my own to enhance my learning. I have been finally starting to get the hang of generating functions, but the following problem below has me ...
3
votes
2answers
61 views

Count the number of 10 digit numbers with given condition

PROBLEM: Count the number of 10 digit numbers with digits from $\{1, 2, 3, 4\}$ and no two adjacent digits differing by $1$. I am able to provide a solution using recursion but it is a very ...
2
votes
1answer
24 views

Formation of generating function with negative integer conditions

I am having problems understanding the logic in solving the following question: Find the generating function for the number of integer solutions to the equation : $c_1 + c_2 + c_3 +c_4 = 20$ ...
2
votes
1answer
29 views

Generating function, finding coefficient (decomposing)

I just started learning about generating functions, and there is a problem that I have the solution to, but I'm wondering if there is a better general method to solve problems of that kind. If I want ...