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

Exponential generating function for number of 10 length sequences built from the alphabet, with some restrictions

I've got the following homework question. If anybody could possibly point me in the right direction, that would be great: Suppose X is a sequence with 10 terms built from 26 letters {a, b, c, ..., ...
0
votes
1answer
31 views

Genereting function

Let $p(n)$ denote the number of unrestricted partitions of $n$. How do I explain that the generating function $f(x)$ of $p(n)$ is $$f(x)=\prod_{n=1}^\infty \displaystyle\frac{1}{1-x^n} $$ Thanks a ...
2
votes
2answers
71 views

number of solutions to $x_1 + x_2 + x_3 + x_4 + x_5 = 31$ via generating function?

I will be very happy to understand how to solve this problem with generating function: How many solutions are there to the equation $$x_1 + x_2 + x_3 + x_4 + x_5 = 31$$ where $x_i$ is a nonnegative ...
0
votes
1answer
34 views

Higher-Order Approximation of Catalan-Numbers

I have a question considering the higher-order approximations of the Catalan-Numbers, following the book Analytic Combinatorics by Flajolet and Sedgewick. First we set $$ C_n = \frac{1}{n+1} ...
1
vote
2answers
113 views

Kind of basic combinatorical problems and (exponential) generating functions

I have a pretty straightforward combinatorical problem which is an exercise to one paper about generating functions. How many ways are there to get a sum of 14 when 4 distinguishable dice are ...
5
votes
2answers
297 views

Applications of generating functions to number theory

I am familiar (at least at a cursory level) with the extensive role generating functions play in the theory of partitions. What are some other prominent applications of generating functions to number ...
1
vote
1answer
28 views

Computational complexity of expanding a MacLaurin/Taylor Series

What methods exist to computationally determine the first $k$ coefficients of a function (possibly polynomial or rational polynomial function)? How do Mathematica/MatLab/Maple/etc. solve this ...
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
99 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
83 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
47 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
65 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
69 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
65 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
169 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 ...