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

2
votes
1answer
41 views

Solving a system of recurrence relations with or without generating functions

I was given the following problem: Find the closed formula that determines the number of r-digits quaternary sequences (made of 0's, 1's, 2's and 3's) in which: (i) the number of 0's is even and ...
1
vote
1answer
24 views

Maple combstruct

How do I implement pointing in Maple with combstruct? I'm writing a symbolic generating function and I need to do something along the lines of A = Point(B) where Point would be a pointing operation, ...
1
vote
2answers
40 views

Infinite sum to fraction

I have the following infinite sum: $$\sum_{n=0}^{\infty}(n+1)^2 \cdot z^n$$ Could you help me how can I convert it to the fraction form? $$-\frac{z(z+1)}{(z-1)^3}$$ (when $|z| < 1$)
5
votes
0answers
129 views

Generating function for the number of surjections

Let $S_k^n$ be the number of possible surjections from a set of $k$ elements to a set of $n$ elements. We have $$\begin{align} &S_0^0 = 1,\qquad\forall k>0: S_k^0 = 0,\\ &S_n^n = ...
1
vote
2answers
182 views

Generating function for number of different tessellation checkered rectangle

Let $R_n$ be checkered rectangle sized $n \times 4, n \ge 1$. Let $a_n$ be number of different $R_n$ tiling with rectangles sized $1 \times 3$. $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ $ $\ \ \ ...
0
votes
1answer
51 views

What's the relation between Stirling numbers and the generating functions?

I just started studying higher combinatorics, but until now in the combinatorial sense I had only seen binomial theorem and coefficients. Therefore, I'm having a lot of difficulty in grasping the ...
1
vote
2answers
90 views

Solving the recurrence $a_{n+2} = 3a_{n+1} - 2a_n, a_0 = 1, a_1 = 3$ using generating functions

Solve the following recurrence using generating functions: $a_{n+2} = 3a_{n+1} - 2a_n, a_0 = 1, a_1 = 3$. My partial solution: We can rewrite $a_{n+2} = 3a_{n+1} - 2a_n$, as $a_{n+2} - 3a_{n+1} ...
1
vote
2answers
93 views

Recurrence relation about square of Fibonacci number

Prove that the square of the Fibonacci number satisfy the recurrence relation $a_{n+3}-2a_{n+2}-2a_{n+1}+a_n = 0$, and solve this recurrence relation with the correct initial conditions.
1
vote
1answer
16 views

How to prove the equality $ B_n(sx) =s^{n - 1}\sum_{j = 0}^{s - 1} B_n (x + \frac{j}{s}) $

Given the following equality: $$ B_n(sx) =s^{n - 1}\sum_{j = 0}^{s - 1} B_n (x + \frac{j}{s}) $$ where $B_n(x)$ - Bernoulli polynomial How to prove the equality? I tried to use generating ...
1
vote
1answer
32 views

Generating function for the set of $w$-free words.

Suppose $X$ is an alphabet and $w \in X^n$ is a word over it. Consider a set $P$ of $w$-free words over $X$ (a word is called $w$-free if it does not contain $w$ as a subword). I want to write a ...
3
votes
1answer
34 views

Number of ways to compute a product

Say there are two ways to compute the product $xyz$. Namely $(xy)z$ and $x(yz)$. Likewise, there are 5 ways to compute the product $wxyz$: $w(x(yz))$, $w((xy)z)$, $(wx)(yz)$, $(w(xy))z$, and ...
2
votes
1answer
116 views

Solution to a recurrence relation

Set $F_k(x) := \sum_{n\geq k} S(n,k)x^n$. Prove that $$F_1(x) = \frac{x}{1-x}, \space \space \space F_2(x) = \frac{x^2}{(1-x)(1-2x)} $$ Furthermore, show that the function $F_k(x)$ satisfy the ...
1
vote
1answer
29 views

System of recurrence relations with Taylor series expansion

Find $a_n,b_n$ where $a_0=1,b_0=0$ for the following relations: $a_{n+1}=2a_n+b_n$ $b_{n+1}=a_n+b_n$ Using generating functions, the system is: $f(x)-a_0=2xf(x)+xg(x)$ $g(x)-b_0=xf(x)+xg(x)$ ...
1
vote
2answers
32 views

Find generating function of a sequence

Find generating function of a sequence $(1,1,2,2,2^2,2^2,2^3,2^3,...)$ Is it necessary to always look for a sub-sequence, e.g. $(1,2,2^2,2^3,...)$? This is a geometric sequence which generating ...
1
vote
1answer
30 views

Expand generating function $\frac{\exp{\frac{z}{1-z}}}{1-z}$

I know that the coefficients $[z^n]$ of the exponential generating function $\frac{\exp{\frac{z}{1-z}}}{1-z}$ are $\sum_{i=0}^{n}i!\binom{n}{i}^2$ but have trouble in proving it. I have done the ...
1
vote
1answer
24 views

Question about: How many partitions of $12$ have parts of size at most $5$?

If the parts are of size at most $5$, why are considering numbers greater than $5$? For example, why can $z_5$ take on $10, 15, \dots$?
1
vote
2answers
91 views

Evaluate sum using generating function

I'm trying to evaluate this sum: $$ \sum\limits_{s = 0}^{500} (-1)^s \binom{3000 - 2s}{2000} \binom{2001}{s}$$ As I think we need to use an expansion of $(1 -x)^n (1+x)^k$, but I've tried several ...
0
votes
1answer
27 views

Generating Functions of Binary Strings

I'm trying to learn generating functions and integer partitions and having particularly difficult time with this question: "This question is about binary strings where each block of 0s is followed by ...
-2
votes
1answer
35 views

Can you find the coefficient of x^r in a generating function if r is a negative number?

Find the coefficient of $x^8$ in $(x^2 + x^3 + x^4 + x^5)^5$. I pulled the $x^2$ out to make it $$\left[x^2(1 + x + x^2 + x^3)\right]^5$$ and then $$x^{10}(1 + x + x^2 + x^3)^5$$ But then ...
2
votes
0answers
29 views

Derivative of cumulative generating function at zero equals expectation value

Let $X$ be a random variable with values in $\mathbb{N_0}$. Then we can define the cumulative generating function of $X$ via $$ F_{X}: (-\infty, 0] \rightarrow \mathbb{R} \quad \quad t \mapsto ...
1
vote
1answer
29 views

Expression for recurrence relation $a_n$ using exponential generating functions

$a_0 = 2$, $a_n = na_{n - 1} - n!$ for $n \geq 1$. Let $$f(x) = \sum_{n \geq 0}a_n\frac{x^n}{n!}.$$ Multiplying each term in the relation by $\frac{x^n}{n!}$ and summing over values for which the ...
0
votes
2answers
39 views

Find the coefficient of $x^n$ in $\sqrt{1 - 8x}$.

We know from the extended binomial theorem that the OGF corresponding to the concise expression is $\sum_{k \geqslant 0}{1/2 \choose k}(-8x)^k$. And we need to find the coefficient $x^n$, which is ...
4
votes
3answers
142 views

$n$-words over the alphabet $\{0,…,d\}$ without consecutive $0$'s

I'm trying to solve the following problem in chapter 3 of Aigner's A Course in Enumeration: Let $f(n)$ be the number of $n$-words over the alphabet $\{0,1,2\}$ that contain no neighboring 0's. ...
1
vote
1answer
43 views

Generating function of Riemann zeta function

I want to know about the generating function of the Riemann zeta function which is related with the Laurent expansion at $z=0$. $f(z) := \dfrac{d}{dz} \log(\sin\pi z)$ $f(z) = \dfrac{1}{z} -2\sum ...
1
vote
0answers
31 views

If $G(s)=G(p+qs)e^{\lambda(s-1)}$ then $G(s)=e^{\lambda(s-1)/p}$

If $G_{n+1}=G_n=G$ where $G(s)=G(p+qs)e^{\lambda(s-1)}$, how can one conclude that $G(s)=e^{\lambda(s-1)/p}$ the G's above are generating functions, In this exercise one has independent variables ...
0
votes
0answers
18 views

MGF Proof: Laplacian Distribution of 1 is difference of 2 Exponential Distributions

Here's the question I'm working on: Show by using moment generating functions that if $X$ is the Laplacian distribution of 1, $L(1)$, then $X$ is defined as $Y_1 - Y_2$, where $Y_1$ and $Y_2$ are ...
2
votes
2answers
46 views

How to find the sum $\sum_{i = 0}^{\infty}\frac{F_i}{7^i}$?

How to find the sum $\sum_{i = 0}^{\infty}\frac{F_i}{7^i}$? $F_i$ - $i$-th Fibonacci number My solution: I think that that's right to use generating functions. For Fibonacci number the generating ...
0
votes
1answer
46 views

Closed Form Generating Function for sum of natural numbers

I need to find a Closed Form Generating Function for a sequence whose $n$-th term is the sum of the first $n$ natural numbers, i.e: $$f(x) = \sum_{i=1}^{n}\frac{n(n+1)}{2}x^n$$ and am having ...
0
votes
0answers
17 views

Find generating function

Let $\mathcal{T}(z)$ and $\mathcal{S}(z)$ are the generating functions of the sequences $\{t_n\}, \{s_n\}$. And $\mathcal{T}(z)\mathcal{S}(z) = 1$. How to find $\{s_n\}$ and $\mathcal{S}(z)$ if it is ...
-1
votes
1answer
22 views

2-dimensional moment generating function of (X, logX) [closed]

I'm having trouble with starting and completing this question: $X$ is a Gamma-distributed random variable, $X\sim\Gamma(k,\theta)$. What is the (two-dimensional) moment generating function of $(X, ...
1
vote
1answer
38 views

Generating function of (-3)^n

Given the sequence $a_n$, where $n$-th element is $a_n = (-3)^n$ I have the generating function $$A(t) = \sum_{n=0}^{\infty} (-3)^nt^n $$ The problem now is to simplify the obtained expression. I ...
1
vote
1answer
58 views

Generating function of Catalan numbers.

I have the generating function $\hat{\beta}(z)=\sum_{k=0}^\infty C_k z^k$ where $C_k$ are Catalan numbers. Now, for $|z|<1/4$ we've $$\hat{\beta}(z)=\sum_{k=0}^{\infty} z^k \int x^{2k}\sigma(x) dx ...
1
vote
1answer
30 views

Solution to closed form of a Generating function

Can anyone give me the closed form of the generating function $$\Sigma ^\infty_{r=2} r.4^r.x^r$$ I am trying to solve recurrence relation using generating functions and this is one of the terms. I ...
4
votes
1answer
133 views

Leningrad Mathematical Olympiad $1991$

A finite sequence $a_1, a_2, ..., a_n$ is called $p$-balanced if any sum of the form $a_k+a_{k+p} + a_{k+2p}+...$ is the same for any $k = 1, 2, 3, ..., p$. For instance the sequence $a_1 = 1$, ...
3
votes
2answers
66 views

Can one do anything useful with a functional equation like $g(x^2) = \frac{4x^2-1}{2x^2+1}g(x)$?

I got $$g(x^2) = \frac{4x^2-1}{2x^2+1}g(x)$$ as a functional equation for a generating function. Is there a way to get a closed form or some asymptotic information about the Taylor coefficients ...
0
votes
0answers
39 views

Suppose $X\sim\mathrm{Poisson} (N)$ where $N\sim\mathrm{Poisson}(\lambda)$, What is the P.G.F of $X+N$?

I have tried conditioning on $N$ and I obtained that: $$G_X(Z) = \exp\left(\lambda\left(e^{Z-1}-1\right)\right).$$ I then used the property that states that $G_{X+N} = G_X(Z)*G_N(Z)$. But I was ...
0
votes
1answer
49 views

Prove that if a sequence with $50$ members is $p$-balanced for $p=3,5,7,11,13, 17$, then all its members are equal zero.

A finite sequence $a_1, a_2, ..., a_n$ is called $p$-balanced if any sum of the form $a_k+a_{k+p} + a_{k+2p}+...$ is the same for any $k = 1, 2, 3, ..., p$. For instance the sequence $a_1 = 1$, ...
1
vote
1answer
49 views

Exponential generating series of binomial coefficients: $\sum_{k=0}^\infty{ k \choose j}\frac{x^k}{k!} $

I'm wondering if anyone knows what it is? The exponential generating series I have in mind is $$ f_j(x) = \sum_{k=0}^\infty { k \choose j} \dfrac{x^k}{k!}. $$ Thanks!
1
vote
2answers
35 views

Finding combination using generating function

Q. Find the no of ways of inserting r dolllars using 1 dollar, 2 dollar and 5 dollar tokens,when order doesn't matter and when order doesn't matter. Ans. When order doesn't matter.. ...
0
votes
2answers
37 views

On partitions of integers

In an example in my textbook, I came across a question where it was asked to find the generating function for the number of partitions of ${n \in N}$ into summands that (a) cannot occur more than 5 ...
1
vote
1answer
48 views

On exponential generating function

In an example in my textbook, it is mentioned that the sequence generated by: ${f(x)= e^x + x^2}$ is: 1,1,3,1,1,1,1,... why is it that when $x^2$ is added to $\sum_{i=0}^{\infty} x^i/i!$ we would ...
1
vote
1answer
36 views

On partition of integers

I came across an example in my textbook where it was asked to find the generating function for the number of integer solutions of: ${2w+3x+5y+7z=n}$ where ${0\le w, 4\le x,y, 5\le z}$ The ...
0
votes
1answer
61 views

How to solve these recurrence relations by using generating function [closed]

First of all, I want to make an apology for my English for I'm not an English native speaker. I'm reading Discrete Mathematics and its Applications recent days, and I am stumped by these three ...
1
vote
1answer
62 views

Proving binomial summation identity using generating functions

An exercise for class requires me to prove the following identity using generating functions: $$\sum_{k=0}^{m/2} (-1)^k {n \choose k} {n+m-2k-1 \choose n-1} = {n \choose m}$$ for all $m \leq n$ and ...
-1
votes
2answers
96 views

Use generating functions to solve $a_n = 6a_{n-1} - 8a_{n-2} + 3 $ and… [closed]

Use generating functions to solve: $$a_n = 6 a_{n - 1} - 8 a_{n - 2} + 3$$ With initial condition: $a_0 = 1$ and $a_1 = 0$ $$a_n = 3 a_{n - 1} + 4 a_{n - 2}$$ With initial conditions: $a_0 = 1$ ...
10
votes
0answers
167 views

How to compute the coefficients of this generating function

Working on some combinatorial problem, I arrived at the following generating function $$K_m(x) = \sum_{n\geq 0}K_{mn}x^n ...
0
votes
0answers
10 views

Generating function of different laws

I want to understand how to deduce the expresion of a generating function of a Bernoulli law with parameter $p$ , a binomial $(n,p)$ and a poisson of parameter $\lambda $ For example i know how to ...
0
votes
1answer
18 views

A question about generating function related to weakly decreasing function

Let $f:[n]\to \mathbb{N}$, then there is a formula $\sum_{f(1)\ge f(2)\ge\cdots\ge f(n)\ge 0}q^{f(1)+f(2)+\cdots+f(n)}=\frac{1}{(1-q)(1-q^2)\cdots(1-q^n)}$ For the case $n=1$, since there is a single ...
1
vote
0answers
39 views

Using generating functions to find the coefficient

I was looking at an example in my textbook where it was asked to find in how many ways can a police captain distribute 24 rifle shells to four police officers so that each officer gets at least three ...
0
votes
0answers
85 views

Number of ways to roll a 6 sided dice - Generating Functions

In a graded assignment the question asks: Find a generating function for $ar$, the number of ways a roll of six distinct dice can show a sum of $r$ if: The first three dice are odd and the second ...