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

0
votes
1answer
33 views

When does a closed form for the sequence enumerated by a generating function exist?

Are there any necessary and sufficient conditions on types of generating functions which guarantee the existence/nonexistence of a closed form for the sequence they enumerate? Generating functions ...
1
vote
2answers
89 views

Generating Functions for collection of balls

There are 10000 identical red balls, 10000 identical yellow balls and 10000 identical green balls. In how many different ways can we select 2005 balls so that the number of red balls is even or the ...
1
vote
1answer
21 views

Generating function which has no singularity

We can know the growth rate of coefficients from singularities of generating functions, but if a generating function which has no singularity at all, for example, the exponential function. What ...
0
votes
2answers
42 views

Get closed form of a series from its generating function

If we have the ordinary generating function of a series: $f(x) = \frac{1}{e^z -3}$ Can we get its closed form?
-1
votes
1answer
115 views

Identify the radius of convergence from ordinary generating function

Assume we have the ordinary generating function $f(x)$ of a series: $f(x) = \tan x$ Can we identify the radius of convergence for this series?
-2
votes
0answers
109 views

Prove that there exists a constant C such that $[z^n]\exp(z/(1-z)) = O(\exp(C\sqrt{n}))$ [closed]

Prove that there exists a constant C such that: $[z^n]\exp(z/(1-z)) = O(\exp(C\sqrt{n}))$ The bound of z is $|z|<\frac14$
-2
votes
2answers
100 views

Using generation functions solve the following difference equation

Using generation functions solve the following difference equation $$ a_{n+1} - 3a_{n+2} + 2a_n = 7n ; n\geq0; a_0 = -1; a_1 = 3. $$
2
votes
3answers
56 views

Find sequence function and general rule

the function $$a_{n+2}=3a_{n+1}-2a_n+2$$ is given, and $$a_0=a_1=1, (a_n)_{n\ge0}$$ multiplying everything by $$/\sum_{n=0}^\infty x^{n+2}$$ also adding $$\sum_{n=0}^\infty ...
0
votes
1answer
112 views

Prove that there exists a constant $C$ such that $[z^n]\exp(z/(1-z)) = O(\exp(C\sqrt{n})) $ [closed]

Prove that there exists a constant $C$ such that: $$[z^n]\exp(z/(1-z)) = O(\exp(C\sqrt{n})).$$ The bound of $z$ is $\vert z \vert<\frac14$
-1
votes
1answer
60 views

Identify the radius of convergence [closed]

For the ordinary generating function $f(z) = \frac{z^3 +1 }{z^3 -1}$, how can we identify its radius of convergence? And is this function meromorphic?
1
vote
0answers
38 views

Extracting coefficients from a transformed generating function

Let $G(z)=\sum_{k\geq 0} a_kz^k$ be a generating function such that $z^aG(1-z)=P(z)$, where $P(z)$ is a polynomial and $a$ is a positive integer. I'm interested in $P(z)[z^n]$, the coefficient in ...
0
votes
2answers
44 views

Combinatorics-Generating function

5 pirates find 3000 gold coins. In how many ways they can distribute them, if the captain gets at least 500 and not more then 2000 coins. the rest get at least 150 but not more then 1000 coins.(each ...
3
votes
2answers
98 views

Deriving a (tricky, I think?) recurrence relation

I'm having trouble trying to derive a recurrence relation for a problem I'm looking at. "Let $h_n$ be the number of ways of packing a bag with $n$ fruits (either apples, oranges, bananas, or pears), ...
0
votes
1answer
60 views

Differences Exponential and Ordinary Generating Functions

I am trying to understand conceptually the differences between ordinary generating functions (OGF$=1+x+x^2+\ldots$ ) and exponential generating functions (EGF$=1+x+\frac{x^2}{2!}+\ldots$ ) when it ...
1
vote
1answer
34 views

relation between multivariate probability generating function and univariate ones

Suppose I have two independent integer random variables $X_1$, $X_2$ (with constraint that $X_1+X_2\le N,0\le X_1\le N,0\le X_2\le N$), with probability generating functions $g_1(z)$, $g_2(z)$. Now I ...
4
votes
1answer
97 views

Proving a combinatorial identity “directly”

This is a homework problem. In the first part of the problem, I managed to use a combinatorial problem to prove the following identity: $\Sigma_{k=0}^{n}(-1)^k {2n-k \choose k} 2^{2n-2k} = 2n+1$ But ...
2
votes
1answer
32 views

Show that a function is a probability generating function

I'm doing past papers in order to revise for exams in June and my university irritatingly doesn't provide any mark schemes and I'm very stuck on a question. The question says: Let ...
0
votes
1answer
36 views

multivariate probability generating function

Suppose I have three random variables $X_1$, $X_2$ and $X_3$, with probability generating functions $g_1(z)$, $g_2(z)$ and $g_3(z)$. Now I have a joint-distribution $P(X_1-X_2,X_1-X_3)$, whose ...
1
vote
2answers
74 views

Use generating functions to find the number of partitions of $n>1$ that have an odd number of even parts $k=1,…,10$

Here are some examples where we find $f(n)$ - the number of partitions that satisfy our condition: $\boldsymbol{2} = (1+1) \rightarrow \boldsymbol{f(2)=0} $ $\boldsymbol{3} = (1+1+1) = ...
1
vote
2answers
53 views

Coefficients of this generating function

For the first part of a problem, I solved the generating function to be $F(x) = \frac{x^3}{(1-x)^2}$ Now it's the easy part that has me a little confused. What would the coefficients be in this case? ...
0
votes
0answers
62 views

Alternating permutation exponential generating function

A permutation pi is alternating if pi_1 > pi_2 < pi_3 > pi_4 <….Let a(n) be the number of alternating permutations of size n. (a) Find a recurrence relation for a(n). (b) Evaluate the ...
0
votes
1answer
82 views

Round table exponential generating function

Let $r(n)$ be the number of different ways to seat $n$ people around a round table. Find the exponential generating function for $r$. I believe $r(n)$ is just equal to $n!/n = (n-1)!$. So then I ...
0
votes
2answers
47 views

Ordinary generating functions

Let's define the sequence $a_n$, $n \geq 0$ by making $a_0 = 0$ and $a_{n+1} = 2a_n + n$ for $n \geq 0$. Show that if $F(x) = \sum_{n=0}^{\infty} a_nx^n$ is the generating function of the sequence, ...
0
votes
0answers
23 views

probability in graphs - degree distribution

I am reading this paper on networks which employs probability in analyzing graphs. Suppose that a graph has $n$ vertices. Furthermore, if each vertex has a probability $p_k$ of having $k$ neighbors, ...
1
vote
1answer
53 views

Find the probability generating function

I have an exercise of this type that I just can not solve "Are $x$ and $y$ be independent random variables, $X$-Poisson($a$), $Y$-Poisson($b$). Find the probability generating function of the random ...
1
vote
2answers
47 views

Help me manipulating with exponential generating function (recurrence relation)

I have recurrence relation $f_0=0, f_1=1$ $$f_n = \frac{2n-1}{n}f_{n-1} - \frac{n-1}{n}f_{n-2} + 1$$ $$nf_n = nf_{n-1} + (n-1)f_{n-1} - (n-1)f_{n-2} + n$$ I tried to solve it using ordinary ...
0
votes
1answer
42 views

Generating functions of form $\sum_{n=0}^\infty a_n x^{kn}$

Let's consider generating function $$F(x) = (1+x)^r = \sum_{n=0} \binom{r}{n} x^n$$ And another generating function $$G(x) = (1+x^2)^r = \sum_{n=0} \binom{r}{n}x^{2n}$$ Please note those 2 functions ...
0
votes
1answer
39 views

Hi guys, can anyone help with this recurrence relation problem?

I'm going through practice questions for my exams but this question has left me confused: The Bessel functions of integer order, Jn(x), are described by the generating function: Derive the ...
1
vote
2answers
74 views

Generating functions for compositions

Let $g(n)$ be the number of compositions of n where each part is an odd number. Let $h(n)$ number of compositions of $n$ where each part is either 1 or 2. Using the ordinary generating functions ...
1
vote
0answers
26 views

Deriving recurrence relations, very stuck!

Going through past papers for my exams and cannot figure this one out, does anyone know how to do these? The Bessel functions of integer order, Jn(x), are described by a generating function of the ...
2
votes
2answers
32 views

Ordinary Generating functions for $b_n$

Problem Let $f(x)$ be a ordinary generating function for the sequence $ \{\ a_0, a_1, a_2... \}\ $ Find the ordinary generating function for $b_0 = b_1 = 0, b_2 = 1$ $b_n = a_n$ for $n \geq 3$. Also ...
2
votes
1answer
30 views

Some help with generating functions

Problem Let $f(x)$ be the ordinary generating function for the sequence $ \{\ a_0 , a_1, a_2,... \}\ $. Find the ordinary generating sequence for the following sequence: $$b_n = a_n + c \ \ \ , n \in ...
0
votes
1answer
46 views

Counting Balls / Elementary Generating Functions

I have a quiz tomorrow in an elementary combinatorics class, and I'm trying to understanding these generating function problems. For some reason, I can't see to figure out how to set these two up. ...
0
votes
2answers
49 views

Ordinary generating functions problem

Problem Find the ordinary generating function for each of the following sequences. In each case the sequence is defined for all $n \in \mathbb{N}_0$. $$a_n = n$$ I'm having a very hard time ...
0
votes
2answers
41 views

Problem understanding notation

I'm learning about generating functions and in the opening explanations my book (and various sources) claim: $$a_n = 1 \forall n \in \mathbb{N}_0, \ \ \ f(x) = \frac{1}{1-x}$$. I read this as: ...
2
votes
1answer
64 views

Compositions - Fruit Salad

I'm asked to find $s(n)$ which is the number of ways to make a fruit salad with $n$ pieces of fruit, given that we must use strawberries by the half-dozen, an odd number of apples, between 2 and 7 ...
3
votes
1answer
67 views

Question about generating function of kind of fibonacci partial sum

$F_n$ here is $n$-th fibonacci number We know that $$\sum_{n=0}^\infty \left(\sum_{k=0}^n F_kF_{n-k}\right)x^n$$ is a generating function of multiplying two G.F: $a_n =\langle F_n \rangle$ and $b_n = ...
0
votes
2answers
47 views

Obtaining a linear recurrence from differential equation

I need some guidance with the following problem. I have a sequence $L_0,L_1,\ldots$ whose ordinary generating series satisfies $$L(x) = \sum_{n=0}^{\infty} L_n \frac{x^n}{n!} = \frac{1}{2-e^x}.$$ ...
0
votes
1answer
60 views

Definite integral involving bessel functions of first and second kind

Is there any standard solution of the integral: $\lim_{\epsilon \to 0} \int_{\epsilon}^{a} J_m(k_1\rho)Y_m(k_2\rho)\rho \, d\rho$. where the integer $m\geq0$ and $a<\infty$
0
votes
0answers
15 views

Derive a formula for a number of set divisions

Let $D(n;a_1,\ldots,a_m)$ be the number of divisions n for factors of the size belonging to the set$\{a_1, a_2,\ldots, a_m\}$. Show that: $1/(1-t^{a_1})(1-t^{a_2})\ldots(1-t^{a_m})$ is a generating ...
1
vote
1answer
49 views

Inclusion-exclusion principle: finding the number of solutions

Given the equation $\begin{cases} x_1+x_2+x_3+x_4 =18\\ 0\leq x_i\leq 7 \text{ with } x_i \in \mathbb{N} \text{ and } 1\leq i\leq 4 \end{cases}$ how do I calculate the number of solutions with the ...
4
votes
4answers
167 views

What is the number of compositions of the integer n such that no part is unique?

I want to find the generating function for the number of compositions (ordered partitions) of n such that no part is unique ( equivalently, every part appears at least twice). For example: there are ...
1
vote
1answer
61 views

Finding the coefficient of a generating function

Given $f(x) = x^4\left(\frac{1-x^6}{1-x}\right)^4 = (x+x^2+x^3+x^4+x^5+x^6)^4$. This is the generating function $f(x)$ of $a_n$, which is the number of ways to get $n$ as the sum of the upper faces of ...
2
votes
1answer
37 views

Show uniqueness of decimal representation using generating funcions.

I have to show using generating functions that decimal expansion of non-negative integer is unique. So I created generating function: $$ \prod_{k=0}\sum_{i=0}^9 {x^{i \cdot 10^k}} $$ I have to show ...
3
votes
1answer
67 views

Solving a recurrence for a random walk revisited

I previously asked about the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < ...
3
votes
2answers
87 views

a manipulation of Fibonacci recurrence

Let $F_n$ be the Fibonacci number, and we know $F_{n+2} = F_{n+1} + F_{n} $ with $F_0 =1,F_1 = 1$ And this can be manipulated to $F_{n+6} = 4F_{n+3} + F_n$ if we let n be a multiple of 3, we can ...
0
votes
1answer
32 views

Taking the derivative of a generating function and trying to find the $n^{th}$ derivative

When we are working with a generating function of a given sequence, when we take the derivative, we normally multiply by $x$ to shift the series back due to the derivative causing a shift in the ...
2
votes
3answers
82 views

Find closed formula $f(n)$ from generating function

I'm asked to find a closed formula for $f(n)=6f(n-1)-9f(n-2)$ for $n>1$ with $f(0)=-1. f(1)=0$, using the ordinary generating function $F(X)$. I found $F(X)=-1/(1-3x)^2$ but from there I don't ...
4
votes
1answer
87 views

Recurrence for random walk

I have the following recurrence which I get when trying to solve a random walk problem given a positive integer $x$. $p_i = \dfrac{p_{i-1}}{2} + \dfrac{p_{i+2}}{2}$ if $0< i < x$ $p_i = 1$ if ...
3
votes
3answers
68 views

Calculate $\sum_{n\geq 0}\frac{H_n}{10^n}$

Question is like in the title and my attempt is Let have sequence $$a_n = <\frac{H_0}{10^0},\frac{H_1}{10^1},\frac{H_2}{10^2},\dots>$$ where $H_n$ is n-th harmonic number. And we have to ...