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
35 views

Extracting Bernoulli polynomials from their generating function

The generating function for Bernoulli polynomials is $$ \frac{te^{tx}}{e^t-1} = \sum_{n=0}^\infty B_n(x) \frac{t^n}{n!}$$ The only way that I know of to get the coefficients out of this is to use ...
0
votes
1answer
23 views

Generating function of derangements

I am pretty new to the topic of generating functions and I would appreciate if someone could help me out with this problem I have. In the lecture we have proven the following generating function for ...
2
votes
1answer
24 views

Find generating functions for the Perrin and Padovan sequences

The Perrin sequence is defined by $a_0 = 3, a_1 = 0, a_2 = 2$ and $a_k = a_{k-2}+a_{k-3}$ for $k \ge 3$. The Padovan sequence is defined by $b_0 = 0, b_1=1, b_2=1$ and $b_k=b_{k-2}+b_{k-3}$ for ...
0
votes
0answers
15 views

Determine the number of partition of 20 into at most 5 parts.

Im stuck on these questions, I can kind of compute them on maxima, but I have to figure out why and how to get to a particular generating function or method. Determine the number of partition of 20 ...
2
votes
0answers
23 views

Asymptotic analysis of coefficients of ordinary generating functions with radius of convergence $1$ seems to always predict polynomial growth rate

Wikipedia gives the following formula for obtaining asymptotic information about the coefficients of an ordinary generating function from information about the generating function itself: if the ...
0
votes
0answers
18 views

how would i simplify this into an identity?

$$ B_{n,k}^{f\ln(g)} = B_{n,k}\left(\frac{d}{dx}[f(x)\ln(g(x))], \frac{d^2}{dx^2}[f(x) \ln(g(x)), \cdots, \frac{d^{n-k+1}}{dx^{n-k+1}}[f(x) \ln(g(x))]\right) $$ We know that: $$ B_{n,k}^{f\ln(g)} = ...
0
votes
0answers
29 views

Generating function of a_n * b_n

I've been searching for the answer yet no luck. Please let me know if this is a duplicate. Let $A(x) = \sum a_n x^n$, $B(x) = \sum b_n x^n$, $C(x) = \sum a_n b_n x^n$. I am looking for the closed ...
1
vote
2answers
44 views

Generating function for a sequence

Please provide a clue on how to solve the following problem: Find a closed form for the generating function for the sequence $\{a_n\}$, where $a_n = 1/(n+1)!$ for $n=0,1,2...$ I know this looks like ...
4
votes
0answers
68 views

Help finding a closed form

I have the following function: $$\frac{2e^x}{e^{2x}+1+2x}=\sum_{n=0}^\infty \varepsilon_n\frac{x^n}{n!}$$ I would like to find a closed form for the $\varepsilon_k$. One thing that I do know is that ...
0
votes
0answers
12 views

How do i take the inverse cauchy product of the following summation?

Well i start out by defining the following partial bell polynomial as: $$ B_{n,k}^u = \frac{n!}{k!} [t^n] \left(\sum_{m \geq 1} \frac{d^m}{dx^m}[u] \frac{t^m}{m!} \right)^k $$ Where $[t^n]$ is the ...
0
votes
2answers
72 views

Generating function and its closed form

Consider the inequality $x_1 + x_2 + x_3 + x_4 ≤n$ where $x_1,x_2,x_3,x_4,n ≥ 0$ are all integers. Suppose also that $x_2 ≥ 2$, that $x_3$ is a multiple of 4, and $1 ≤ x_4 ≤ 3$. Let $c_n$ be the ...
0
votes
0answers
46 views

Elusive closed form for card permutation problem

Does a closed form formula f(n) exist for the two rightmost columns? The two question marks are meant to be 0. The diagram is a summary of the numerical results from original question: Permutations ...
1
vote
0answers
28 views

Roll a dice till consecutive sixes - Generating Function

Consider the following experiment: A fair dice is thrown until two consecutive sixes are rolled. Let $X$ be the number of rolls of the experiment. I need to find the probability generating function of ...
2
votes
0answers
30 views

Multivariable generating functions

Let's consider a 2-variable generating function for the Dyck triangle numbers. Reccurence, satisfying to the triangle conditions is $d_{n, k}=d_{n-1, k-1}+d_{n-1, k}+d_{n-1, k-1}$, $d_{0, 0}=1$, ...
1
vote
0answers
33 views

Picking $3n$ subset with repetitions allowed from $\{A,B,C\}$ with conditions - is my generating function correct?

I'm trying to solve the following cominatorics problem: How many ways are there to choose $3n$ subset with repetitions allowed from set $\{A,B,C\}$ where $A, B$ are present at most $2n$ times each ...
0
votes
1answer
47 views

Closed form for nth term - generating functions

I think I am mostly confused about what the question is asking. I read that "closed form" means that it should not be represented as as infinite sum, so I am not sure what they are asking for. Would ...
3
votes
1answer
73 views

Is generating function having use in recurence relations containing division in subscripts?

It's well known that generating functions are great to solve recurence relations in form $$a_n = A*a_{n-1} + B*a_{n-2} + \dots$$ But i was wondering what happens if recurence relation contains ...
2
votes
1answer
50 views

Generating function for sequence $a_n = \lceil \sqrt{n} \rceil $

In one of books for discrete mathematics i came across sum to calculate $$\sum_{k=0}^n \lceil \sqrt{n} \rceil$$ which was fairly easy, but this sum intrigued me what is generating function for ...
0
votes
0answers
29 views
1
vote
0answers
63 views

Closed form of generating function $r^a$

Find the closed form of the generating function of $r^a$. in this question $r$ is the variable part and $r$ assumes the values $1,2,3,4,5,6,7 \ldots$ and $a \in \mathbb R_{\geq 0}$. I would appreciate ...
4
votes
1answer
139 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
46 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
31 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
votes
0answers
51 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
47 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 ...
0
votes
0answers
36 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
37 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
130 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
47 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
37 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
79 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
207 views

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
62 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
27 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
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
217 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
55 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
77 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
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
74 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
35 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
32 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
38 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
10 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 ...