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

5
votes
1answer
159 views

Complicated Multivariate Recurrence Relations For Generating Polynomials

I have the following multivariate recurrence relations all from the same system: First, suppose that $0\le k\le j\le m$, and let $N$ be an independent integer. Then we have for expressions $a(k,~ m,~ ...
2
votes
2answers
51 views

Prove that $\frac{1}{(1-x)^k}$ is a generating function for $\binom{n-k-1}{k-1}$

On my discrete math lecture there was a fact that: $\frac{1}{(1-x)^k}$ is a generating function for $a_n=\binom{n-k-1}{k-1}$ I'm interested in combinatorial proof of this fact. Is there any simple ...
0
votes
0answers
33 views

Closed form of generating function

Find the closed form of the generating function of the sequence $\frac{{n \choose r}}{n^r \cdot (r+3)}$ where $n$ tends to infinity. I tried to make a sort of infinite gp to use infinite gp sum ...
1
vote
1answer
51 views

Generating function of 1 over binomial

Is there any known function for which it holds $$f(x)=\sum_{n\ge m}\frac{x^n}{\binom{n}{m}}?$$ I arrived to this question trying to bound a series and I have no experience with generating functions.
1
vote
2answers
23 views

Sum with non unit increment

Let's consider the sum $$\sum_{i=4t+2} {\binom{m}{i}}$$. It's equivalent to the following $\sum_{s}{\binom{m}{4s+2}}$, but i got stuck here. How to evaluate such kind of sums? For instance, it's ...
1
vote
0answers
44 views

Generating function for reciprocals of Harmonic numbers?

Find an exponential generating function of reciprocal Harmonic numbers. $f(x)=\sum\limits_{n=1}^{\infty} \frac{1}{H_n}\frac{x^n}{n!}$ Also, it would be nice to see EGF or OGF for other reciprocals ...
1
vote
1answer
41 views

Hadamard's product of Fibonacci generating functions.

$F(s) = \frac{1}{1-s-s^2}=\sum_{n\geq0}F_ns^n$. I want to calculate $F(s) \circ F(s) = \sum_{n\geq0}F_{n}^2s^n$. I have tried using Binet"s formula, but problem remains unsolved.
4
votes
1answer
30 views

Is there a reference for the following generating function identities?

For the Motzkin and Schröder numbers respectively, we have the following identities: $$ Mk(z) = \sum_{n=1}^{\infty} \Bigg{(} -\frac{1}{2} \sum_{a=0}^{n+2} (-3)^{k} \binom{\frac{1}{2}}{a} \binom{ ...
1
vote
0answers
66 views

generating function and one recurrence sequence? [duplicate]

what is the generating function for sequence {$a_n$}$_{n \geq 0} $ which defined by $a_0=0$ and $a_n=\frac{1 \times 5 \times ... \times (4n-3)}{1 \times 2 \times ... \times n}$ $(n \geq 1)$. This ...
3
votes
2answers
131 views

How to calculate $(1+x)(1+x+x^2)\cdots(1+x+x^2+\cdots+x^n)$

I have a combinatorics problem and I've reduced it to finding coefficient that stands with $x^n$ in this polynomial, $$(1+x)(1+x+x^2)...(1+x+x^2+...+x^n)$$ But now I'm stuck. Can someone help me ...
0
votes
1answer
51 views

Find the coefficient of $x^{20}$ in $(x^{2}+⋯+x^{6} )^{5}$

I'm trying to find the coefficient of $x^{20}$ in $$(x^{2}+⋯+x^{6} )^{5}$$ My steps are $$=x^{10}(1+⋯+x^{4} )^{5}$$ $$=\left(\dfrac {1-x^5} {1-x}\right)^{5} x^{10}$$ $$= (1-x^5)^5 * (1-x)^{-5} ...
0
votes
1answer
51 views

Generating Functions - Extracting Coefficients

In many counting problems, we find an appropriate generating function which allows us to extract a given coefficient as our answer. In cases where the generating function is not one that is easily ...
0
votes
1answer
87 views

Kolmogorov backward equations for generating functions

The two-stage MVK model is a continuous time Markov model of cancer formation that describes the occurrence and growth of intermediate cells and malignant cells arising from a population of normla ...
4
votes
2answers
73 views

number of pairs formed from $2n$ people sitting in a circle

I am trying to understand the solution to the following problem: Suppose that $2n$ persons are sitting in a circle. In how many ways can they form $n$ pairs if no two adjacent persons can form a ...
0
votes
2answers
19 views

expand function, taylors series, combinatorics, generation functions

I have to expand $f(z)$ into a formal power series $f(z) = \sum\limits_{k=0}^\infty a_kz^k$ (for $z$ close to 0) $f(z)= \frac{z^3}{1-4z+3z^2}$ I know that: $\frac{1}{1-z} = \sum\limits_{k=0}^\infty ...
0
votes
0answers
34 views

$f(n)=3f(\frac{n}{3})+O(logn)$

I was asked to figure out the time complexity analysis for the following recurrence relation: $f(n)=3f(\frac{n}{3})+O(logn)$ I worked it out as O(nlgn), Would like to know if this is right or ...
9
votes
2answers
219 views

Counting sets by their connectedness

Let $U = \{u_1, u_2, \ldots , u_m \}$ where each $u_i$ is an $r$-subset of $[n]$ and $\,\bigcup u_i \!=\! [n]$. Construct the intersection graph of $U$. That is, let node $i$ correspond to $u_i$ and ...
1
vote
2answers
66 views

Solve recurrence relation using generating function

I'm trying to solve: $a_{n+1}-a_n=n^2$, $n\le0$ , $a_0=1$ using generating functions. Step 1) Multiply by $x^{n+1}$ $$a_{n+1}x^{n+1}-a_nx^{n+1}=n^2x^{n+1}$$ Step 2) Take the infinite sums ...
3
votes
2answers
94 views

Find a Generating Function for Ordered Rooted Ternary Trees

The Full Question If we let $T=$ the family of rooted ternary trees, $t_n =$ be number of trees in $T$ with $n$ nodes and $T(x) = \sum\limits_{n=0}^{\infty}w_nx^n$ be the generating function of $T$. ...
2
votes
0answers
28 views

Formal sum of product of all size k subsets of a set

Is there a nice way to use generating functions to represent the formal sum of all size-$k$ subsets of a set $S$? Here I want to represent a subset by the product of its elements. For example, if $S ...
1
vote
2answers
42 views

$F_{2n} = F_{2n-2}+2F_{2n-4}+\dots+n$ rigorous proof

Let $F_{n}$ be n-th fibonacci number($F_{0}$ = 0) and $g_{n} = F_{2n}$ if $n > 0$ $g_{0} = 1$. I want to prove that $g_{n} = g_{n-1}+2g_{n-2}+\dots +ng_{0}$. It's obviously seen from direct ...
0
votes
1answer
79 views

Solve $a_{n+1} - a_n = n^2$ using generating functions

The Full Question Using the method of generating functions, solve $a_{n+1} - a_n = n^2$ where $a_0 = 1$ My Research Scanned the website for similar answers, reviewed the following links: Solve the ...
1
vote
1answer
38 views

Applying Generating Function Approach to a $M/E_r/1$ queue

(This question is about Exercise 27 on page 55 from these lecture notes.) We consider a $M/E_r/1$ queue with arrival rate $\lambda$ and mean service time $r/\mu$. We let ...
0
votes
1answer
36 views

Counting unordered partitions on nested concentric disks

The idea is to think of each layer outside of the [core] as a rotatable disk and then only count a single member from each of the resulting equivalence classes, which I think can be done by requiring ...
1
vote
0answers
39 views

How to manipulate this summation in the easiest way possible?

$$ D = \sum_{k=c}^{n}\sum_{j=0}^{k-c}[{k-c \choose j}\ln^{k-c-j}(g(x))[\ln(g) f'(x) f_c^{(j)} X_{n,k(f\rightarrow g)^c} + f_{c}^{(j)} X_{n,k(f \rightarrow g)^{c}}' + \frac{d}{dx}[f_c^{(j)}] X_{n,k(f ...
1
vote
4answers
63 views

Sequence from generating function $\frac{1}{(1 - \frac{x}{3})^2}$

I know that for $$ \frac{1}{1 - \frac{x}{3}} $$ sequence would be $a_n = \frac{1}{3^n}$ for $n \geq 0$ ($\sum_{n \geq 0} \frac{1}{3^n} x^n$ ). How should I approach with that power of two?
0
votes
0answers
14 views

Recurrence relation involving ordinary generating function

Let $f_1,f_2,\ldots$ be a given infinite sequence of functions. Define the sequence of functions $F_1,F_2,\ldots$ by the recurrence relation $$F_n(x)=f_n(x)\sum_{k=0}^\infty F_{n+1}(k)x^k$$ or ...
1
vote
1answer
41 views

Find sequence for generating function $\frac{1}{(1-x)^{12}}$

I know that I should use partial fraction but is this really right approach, would not it be like 12 fractions? That power to 12 is something that is problematic for me. Can you give me some hint ...
0
votes
0answers
32 views
1
vote
0answers
16 views

Is there a way to express the reciprocal of the hypergeometric function 2F1(a,b;c;z) in terms of a b and c?

I'm trying to use generating functions to get the value of some coefficients, namely $\displaystyle\sum_{m\geq 0} f_{2m}x^m = 1 - \Big(\displaystyle\sum_{m\geq 0} u_{2m}x^m\Big)^{-1}\\$ and $u_{2m} ...
1
vote
2answers
71 views

Find sequence for given generating function $\frac{ \frac{3x}{2} + \frac{3}{2}}{ 3 - x }$

I have generating function $$A(x) = \frac{ \frac{3x}{2} + \frac{3}{2}}{ 3 - x }$$ and I need to find a sequence from it. This was my approach: $$ \frac{ \frac{3x}{2} + \frac{3}{2}}{ 3 - x } = ...
0
votes
1answer
26 views

If generating function of $\{ a_n \}$ is known what is the generating function of $\{ n a_n \}$

Generating function of $\{ a_n \}_{0 \leq n}$ is $$A(x) = \frac{1+2x}{1-2x}$$ then what is the generating function of ${n a_n}$ ? It is what I tried so far, $$A(x) = \frac{1+2x}{1-2x}$$ $$= ...
0
votes
1answer
163 views

Legendre polynomial and their generating function

I've evaluated the integral of (1-2rx + r^2)^-1/2 from -1 to 1 and got 2 And now I have to use this result to determine the values of all the integrals pn(x)dx from -1 to 1 Can anyone help Also the ...
0
votes
1answer
57 views

Manipulation of summations

this question branches off another question that can be seen here Now we begin be taking a look at the following expressions: $$ \sum_{k=1}^{n-l} \sum_{j-0}^m \frac{\ln(g)^{m-j}}{g^k} ...
2
votes
0answers
28 views

Link between partition function and ordered partition function

The partition function $p(n)$ measures the number of partitions of $n$, or the number of ways in which natural numbers can be summed to produce $n$, without regard to order. For example, the ...
2
votes
1answer
25 views

Find the coefficient on x^10 in the following generating function

$\ {(1 − x^{14})\over (1 − x)}$ My thought was: $\ (1-x^{14})\over (1-x)$ $\ = (1 - x^{14}) ∑ x^n$ $\ = ∑ [x^n - x^{n+14}]$ But I'm not sure if I'm on the right path?
2
votes
2answers
67 views

Find generating function for sequence

I am suppose to find generating function for sequence $(e_n)_0^\infty$ where $e_n$ is number of ways how to write a number $n$ as a sum of four natural odd numbers ($e_n$ is basically a number of ...
-2
votes
1answer
37 views

Transformations solving recurrence with generating functions

Why is $\sum_{n ≥3} a_{n-1} z^{n-1}$ equal to $(A(z) − 1 − z)$? $\sum_{n ≥3}a_{n-2} z^{n-2}$ equal to $(A(z) − 1)$?
2
votes
1answer
42 views

How Many Ways Are There to Roll $12$ Dice to Sum to $30$?

Notation $[x^k]f(x) =$ the coeffcient of $x^k$ in the power series expansion of $f(x)$ The Full Question If I roll a die numbered from $1$ to $6$ twelve times, how many ways can they sum to $30$? ...
1
vote
1answer
33 views

Generating function for set partitions

Let $k$ be fixed. For every $n$ denote by $p_{\leq k}(n)$ the number of partitions of the integer $n$, for which each part is at most $k$. a). Compute $p_{\leq 3}(5)$ b). Compute the generating ...
1
vote
2answers
27 views

Given a sequence ${a_k}, k=1,2,3…$, find the generating function for ${a_2k}$

This is a problem on an exam review sheet for a discrete mathematics course. Consider a generating function $$F(x)=a_0+a_1x+a_2x^2+...$$ Using operations on generating functions, obtain a ...
0
votes
0answers
10 views

Generating Function of Compositions of $n$ with $k$ parts [duplicate]

Notation $[x^n] =$ the coefficeint of $x^n$ The Full Question a) Find a closed form for the generating function C(x) for counting compositions of $n$ with $k$ parts, where each part is an odd ...
1
vote
1answer
84 views

how to solve generating function for odd number?

im working on this question and i don't know where to start the question is: a) Find a closed form for the generating function $c(x)$ for counting compositions with $k$ parts, where each part is ...
1
vote
1answer
51 views

Subset Sum Problem

I recently saw the following problem, and I'm exploring the possibility of generalising it in various directions. Consider a collection of $n$ cubic blocks with side lengths $1,2,\ldots,n$. It is ...
2
votes
2answers
33 views

Weak $k$-compositions with each part less than $j$

I am trying to figure out a problem from Richard Stanley's $\textit{Enumerative Combinatorics}$, which has to do with weak compositions of $n$ (sequence of nonnegative integers whose sum adds up to ...
1
vote
1answer
60 views

Permutations with odd-length cycles

I need to find - as a homework problem - the exponential generating function for the number of permutations of $n$ consisting of an even number of odd-length cycles. I can retrieve the exponential ...
0
votes
1answer
26 views

Simple generating functions without recurrence

I'm still getting to grips with generating functions. I think I can grasp how to form them when you have a recurrence relation, but what if you don't? Consider the sequence $\{a_n\}_{n\geq0}$ with ...
0
votes
1answer
57 views

How to solve this distribution problem with generating functions?

In how many ways can we distribute $6$ red balls, $7$ green balls and $8$ blue balls in $3$ different boxes such that each box has at least one ball of each color? I'd like to solve this problem ...
2
votes
1answer
44 views

Compositions of $n$ with $r$ odd parts and $s$ even parts

The problem I have been trying to figure out is as follows: Let $n-r=2k$. Show that the number $f(n,r,s)$ of compositions of $n$ with $r$ odd parts and $s$ even parts is given by ...
3
votes
1answer
62 views

Number of integer solutions with hard restrictions

In the jungle of posts on math.stackexachange related to this subject I have been searching quite a while now. I read some very useful posts however I can't solve my own problem. My version of the ...