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

-1
votes
0answers
42 views

Generating function for $a_0=0,$ $a_n=\frac{1 \times 5 \times … \times (4n-3) }{1 \times 2 \times … \times n}$

What is the generating function for the sequence $\{a_n\}_{n \geq 0}$, defined by $a_0=0$ and $a_n=\frac{1 \times 5 \times ... \times (4n-3)}{1 \times 2 \times ... \times n}$ for $n \geq 1$. ...
1
vote
1answer
37 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
21 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 ...
0
votes
0answers
24 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
36 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
28 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
65 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
126 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 ...
1
vote
0answers
28 views

How to express power series with even powers [closed]

Please have a look at the question above. for i), I tried to express the second urn as 1/2 (f(x)+f(-x)), but I could not get the algebra right. Can any one please help? Thanks in advance
0
votes
1answer
42 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
31 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
69 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 ...
-1
votes
2answers
190 views
+50

one recurrence relation with generating function

what is generating function for {$a_n$}$_{n \geq 0} $ sequence that 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)$. ...
4
votes
2answers
60 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
0answers
25 views

dot diagram prove

I have to prove theorems using dot diagrams. a.- $P_n(k) = p_n(k-n)$ b.- $p_n(k) = p_{n-1}(k) + p_n(k-n)$ c.- The number $P_n(k)$ of partitions of $k$ into exactly $n$ parts is equal to the number ...
0
votes
2answers
17 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 ...
1
vote
0answers
33 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
209 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
48 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
71 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
27 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
41 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
71 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
30 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
0answers
19 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
37 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
9 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
39 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
31 views
1
vote
0answers
11 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
70 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
24 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
121 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
49 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} ...
1
vote
0answers
46 views

Expression for $n~ \mathrm{mod}~ m$

I have found generating function for the sequence $\left(n \operatorname{mod} m\right)_{n \geq 0}$ (where $n \operatorname{mod} m$ denotes the remainder of $n$ modulo $m$): it is $F(x) = ...
2
votes
0answers
20 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
56 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
32 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
38 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
26 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
26 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
8 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
63 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
49 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
24 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
49 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
24 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
50 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 ...