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

3
votes
0answers
19 views

A conjecture about “equiharmonic numbers” of Flajolet via Doron Zeilberger

While semi-randomly browsing, I came across this conjecture which Philippe Flajolet sent to Doron Zeilberger as a "gift" (the "gift" is here, so you can check to see if I have typeset it correctly): ...
1
vote
1answer
33 views

How to generate integer random numbers that equal to another random number?

I am running a simulation in Excel, and need to generate a group of integer random numbers summing up to another random integer, how can I possibly do it? For instance I have an integer random number ...
1
vote
1answer
6 views

Wiener algebra and generating function

Let $W^+$ be the algebra of function $f:\overline{\mathbb{D}}\mapsto \mathbb{C}$ such that $f(z)=\sum _{n\geq 0}c_nz^n, \forall |z|\leq 1,$ equipped with the norm $\|f\|_{W^+}=\sum _{n\geq 0}|c_n|$. ...
0
votes
2answers
27 views

Find a recurrence relation and solve it

Let $a_n$ be the nummber of ways that 4 people can throw $n$ eyes together with a die. Every person throw once. Now I want to find a generating function and compute $a_n$ for different $n$. To do ...
2
votes
1answer
32 views

Generating function for recurrence in two variables

Given characteristic polynomial for the recurrence in two variables (say $F(x,y)$) $$ (y^2-1)^x $$ and initial values can generating function for $F(x,y)$ be derived? I know how to do it for a ...
0
votes
1answer
32 views

Solve this recurrence relation

Solve the following recursions: $a_{n+1}=3a_n-a_{n-1}-1$ and $a_{n+1}=4a_n-a_{n-1}-1$. (These are to be solved separately, not simultaneously) I tried using generating functions but it got messy. Any ...
0
votes
0answers
13 views

generating function for the Hurwitz Zeta

we know from the digamma function $$ \Psi (z+1)= -\gamma -\sum_{k=1}^{\infty}\zeta(k+1)(-z)^{k} $$ my question is if there is a similar formula for $$ f(a)+ ...
1
vote
1answer
15 views

Construction of Probability Generating Function in Branching Process?

So I'm trying to construct a probability generating function for the following scenario: 1/5 of a rabbit population does not reproduce. 4/5 have 3 offspring each, and the probability of male or ...
2
votes
2answers
62 views

Use the generating function to solve a recurrence relation

We have the recurrence relation $\displaystyle a_n = a_{n-1} + 2(n-1)$ for $n \geq 2$, with $a_1 = 2$. Now I have to show that $\displaystyle a_n = n^2 - n +2$, with $n \geq 1$ using the generating ...
0
votes
1answer
55 views

Exponential generating function of partitions of set [n]

Find the exponential generating function of the partitions of the set [n], all of whose classes have a prime number of elements. The only thing I came up with was $$\sum\limits_{\textrm{t prime}} = ...
4
votes
4answers
176 views

The even-numbered coefficients of the Maclaurin series of $ \frac{1}{\cos(x)} $ are odd integers.

Let’s consider $ G(z) \stackrel{\text{df}}{=} \dfrac{1}{\cos(z)} $ as the exponential generating function of the sequence of Euler numbers. How can one prove that in the Maclaurin series of $ G $, $$ ...
2
votes
1answer
61 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
41 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
33 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
25 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
24 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
44 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)} = ...
2
votes
0answers
33 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
46 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
69 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
13 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
73 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 ...
1
vote
0answers
51 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
35 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
34 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
49 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
74 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
54 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
142 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
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
39 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
29 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
49 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
40 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
208 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
218 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 ...