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
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
56 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
33 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
35 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
52 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
60 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
81 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
22 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
72 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
43 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
48 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
63 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
56 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
14 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
164 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
59 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
66 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
30 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
86 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 ...
1
vote
1answer
42 views

Easy generating functions task from concrete mathematics book

This question might seem very novice, but i'm not sure about the solution. We have domino puzzle of size $2 \times\ n$ and we get 4 points for every vertical block and 1 point for horizontal block, ...
0
votes
2answers
25 views

Help with finding the generating function (with a constant )

How do you get the generating function from this formula: $8(1+x)^{7}$ I have the following formula for $(1+x)^{n}$ : $n\choose 0$ + $n \choose 1$$x^1$ + $n \choose 2$$x^2$+... +$n \choose ...
0
votes
2answers
42 views

How to find the coefficient of $x^8$ in the following:

I need to find the coefficient of $x^8$ in the following using generating functions: $$\frac{(1+x)^2}{1-3x} $$ I attempted to write out three different generating functions adding together to give ...
2
votes
1answer
43 views

Techniques for solving recurrence relations using generating functions

How does one extract coefficients from generating functions that involve exponents. Things like $A(z) = 1+A(z^2)$ or $A(z)= 1+A(z^2)+A(\sqrt z)$?
2
votes
1answer
79 views

Differentiate $P_{x_n}(z) = \prod_{i=1}^n\frac{1+z+z^2+…+z^{i-1}}{i}$ twice to calculate the variance of involutions.

Use the Probability Generating Function for Involutions: $P_{x_n}(z) = \prod_{i=1}^n\frac{1+z+z^2+...+z^{i-1}}{i}$ To Calculate the Variance of Involutions where: $Variance \space X_n = ...
5
votes
2answers
72 views

Closed form of generating function consisting of power of two binomials

Let $g(x)$ be infinite formal power series and $$g(x) = (1 + x)(1 + x^2)\cdots(1 + x^{2^k})\cdots$$ Show that $(1 - x) g(x) = 1$. My book gives following proof: Using a fact that $(1 - x^k)(1 + ...
3
votes
1answer
86 views

A generating function that produces $\{n^n\}_{n=0}^{\infty}$

I am trying to find a generating function that produces the sequence $$ 1, 2^2, 3^3, 4^4, 5^5,\cdots,n^n $$ so that $$ F(x) = \sum_{n=0}^{\infty}n^n\frac{x^n}{n!} $$ Does anyone know of such a ...
2
votes
3answers
68 views

How would one go by manipulating known generating functions to get the following:

$$\sum_0^\infty(n+1)(2n+1)x^n$$ I know the following, which is what I am assuming I must manipulate. I have the answer to the closed form, but I do not understand how to get there. Please, no answers ...