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
2answers
47 views

Find the exponential generating function for the number of ways to distribute $r$ distinct objects into five different boxes

Find the exponential generating function for the number of ways to distribute $r$ distinct objects into five different boxes when $b_1<b_2\le 4$, where $b_1,b_2$ are the numbers of objects in boxes ...
0
votes
1answer
52 views

Partial fraction of a generating function

I am solving a recurrence relation $a_0 = a_1 = a_2 = 1, a_{n+3} = a_{n+2} − 2a_{n+1} − 4a_n$ for $n \ge 0$ I got a generating function for this sequence $f(x) = \frac{2x^2+1}{4x^3+2x^2-x+1} $ ...
2
votes
1answer
33 views

Determine the EGF for a set of partitions of partitions.

Given $a_{n}$ is the number of ways to partition elements of $[n]$ into non-empty sets, then further partition those sets into non-empty sets. I've already determined the egf for non-empty sets of $...
2
votes
2answers
86 views

How many combination of $3$ integers reach given number?

I have 3 numbers $M=10$ $N=5$ $I=2$ Suppose I have been given number $R$ as input that is equal to $40$ so in how many ways these $3$ numbers arrange them selves to reach $40$ e.g. $$10+10+10+...
3
votes
0answers
39 views

Why the moment-generating function, rather than the characteristic function?

I'm wondering why the moment-generating function is worth discussing (say, in basic probability courses, or in textbooks, rather than research), when the characteristic function appears to completely ...
0
votes
1answer
46 views

Not sure what I'm doing wrong with this recurrence problem

$r_{n} = 4r_{n-1} + 6r_{n-2} $ Using Generating Functions I have: We have $ R(x)= \sum^{\infty}_{i=0}r_nx_n $ $R(x) = \sum_{i=0}^{\infty} r_nx_n $. Then we multiply the relation on both sides by $...
3
votes
3answers
91 views

The number of words of length $n$ from specific alphabet with rule of creating.

Determination of the number of words of length n formed from the alphabet $\{ a, b , c, d \} $, where the letters $a , b $ are not adjacent. How to find out a recurrence and explicit formula for it ?
3
votes
2answers
41 views

Proving that $\sum_{n=1}^{\infty}S(n,n-2)x^n = \frac{x^3(1+2x)}{(1-x)^5}$

I was wondering if anyone could give a hint on how to prove this expression, I have been stuck on it for hours. Thanks in advance! Proving that $$\sum_{n=1}^{\infty}S(n,n-2)x^n = \frac{x^3(1+2x)}{(...
1
vote
1answer
31 views

How to use a generating function to work out an infinite sum

I have the infinite sums: $$\sum_{k=0}^\infty k^2a^k \quad \text{and}\quad \sum_{k=0}^\infty ka^k$$ where, $\left\lvert a \right\rvert<1$. I was able to find the answers to the infite sums here, ...
0
votes
0answers
31 views

Combinatorics Composition of generating fuctions

I can follow through the whole problem except I don't understand how to get $A(x)$. Can you run me through how to get $A(x)$? This is my attempt, $3$ represents the options: poisonous, slightly ...
1
vote
1answer
42 views

Alternating sign odd number generating function.

I have a sequence that I'm trying to find both an ordinary generating function for as well as a closed form without a floor function. The sequence $$\{1,1,-1,3,-3,5,-5,7,-7,9,-9,11,-11,\}$$ is ...
2
votes
1answer
106 views

Finding Probability generating function from moment generating function

I have been trying to solve a master equation and now finally when I solved it using the method of moment generating function. I don't know how to convert it into a corresponding probability function. ...
2
votes
0answers
67 views

Taylor series for multivalued complex functions (and their use in combinatorics)

As far as I know, it is considered to be a "fact" that by the Generalized Binomial Theorem, the complex function $\sqrt{1 + z}$ has the following Taylor expansion at $z = 0$: $$\sqrt{1 + z} = \sum_{n \...
0
votes
4answers
51 views

Determine the generating function $f(x)$, of the recurrence relation..

Determine the generating function of the recurrence relation $a_n=3\cdot2^{n-1}-a_{n-1}$ for $n\geq2 , a_1=0$ So $a_0x+(3\cdot2-a_1)x^2+(3\cdot4-a_2)x^3 \ldots $ and what to do next?
1
vote
0answers
66 views

A generalized version of inclusion exclusion principle using a binomial identity

I'm trying to find a way to derive a generalized inclusion exclusion principle for the number of elements which are in the intersection of at least $s$ sets from $A_1,A_2,...,A_n$ using this identity: ...
0
votes
1answer
30 views

Show that in a Galton-Walton Branching Process, $\phi_n'(s)\to0$ for every $s\in(0,1)$ if $p_0>0$

Let $Z_n$ be the Galton Watson Branching Process. Let $Z_n=\sum_{k=1}^{Z_{n-1}}X_{k,n}$ where $X_{k,n}\sim X$ are iid progeny distribution. If $p_0=P(X=0)>0$ then show that $\forall s\in(0,1)$ we ...
2
votes
2answers
157 views

proof that the binomial sum is equal to 1

I'm trying to prove the following identity: let $k$ and $s$ be positive integers and let $k\ge s\ge 1$ $$\sum_{i=0}^{k-s} (-1)^i{s-1+i \choose s-1}{k \choose s+i} = 1$$ I've tried to use a ...
1
vote
1answer
22 views

Troubleshooting Textbook: Using Generating Functions for Non-Homogenous Recurrence

I am learning about Generating Functions to solve non-homogenous linear recurrences, and I can't seem to get the right solution, no matter what I do. Also, the example I have to work off of in the ...
1
vote
2answers
55 views

Solving Recurrence with Generating Function

I have the following recurrence: $r_n = 4r_{n-1} + 6r_{n-2} \text{ where } r_0 = 1 \text{ and } r_1 = 3$ Next, I write my generating function, $R(x)$: $$ \begin{align} R(x)*(1 - 4x - 6x^2) &= ...
1
vote
1answer
29 views
1
vote
1answer
54 views

Generating Function: Why is $G(0)=P(X=0)$?

$G$ is the generating function: $$G(s)=E\left[s^X\right]=\sum_{i=0}^{\infty}P(X=i)s^i$$ But the textbook claims that $G(0)=P(X=0)$. Why? $$G(0)=\sum_{i=0}^{\infty}P(X=i)(0)^i=0$$ but this is not $P(X=...
1
vote
1answer
38 views

expressing a natural number as a sum of three natural numbers and finding the sum of their product

I have three natural numbers $a, b, c$ such that $a + b + c = n$ and I'm looking for $\sum abc$. So far I've figured out that the generating function for $p(n,3)$ might be $\frac{x^3}{(1-x)(1-x^2)(1-...
0
votes
1answer
18 views

Trouble with integer partition proof

I am reading Keller & Trotter: Applied Combinatorics, pg. 155, and I am having trouble with an intermediate step in a proof. The proof deals with integer partitions: And the part I can't ...
1
vote
1answer
44 views

A Finite Combinatorial Sum

It can be proved by induction or telescoping sum that $$\sum_{i=0}^n {2i\choose i}\frac{1}{2^{2i}}=(2n+1){2n\choose n}\frac{1}{2^{2n}}.$$ However, without knowing the right hand side in advance, I ...
2
votes
1answer
25 views

Arrangements with no anomalous neighborhoods

How many ways can $8$ boys and $20$ girls be ordered such that for each boy at position $i$, there is no neighborhood (of $2n+1$ points with $n > 0$) consisting of positions $j \in [i-n,i+n]$ that ...
3
votes
1answer
58 views

Find closed formula for $a_{n+1}=(n+1)a_{n}+n!$

$a_{n+1}=(n+1)a_{n}+n!$ where a0=0 and n>=0. To get the closed form, I'm trying to find an exponential generating function for the above recurrence, but it doesn't seem to be very nice. Am I going ...
3
votes
1answer
58 views

Find closed formula for the recurrence $a_{n}=na_{n-1}+n(n-1)a_{n-2}$

$a_{n}=na_{n-1}+n(n-1)a_{n-2}$ where a0 = 0, a1=1, and n >= 2. I found an exponential generating function for this recurrence, but cant seem to find the closed form because the generating function ...
0
votes
1answer
28 views

Proof gone wrong: Probability Generating functions.

I'm trying to proof something but I'm getting a different answer than my textbook and I don't know where I've gone wrong. The question concerns a random discrete variable $Y$ taking on values in $\...
0
votes
1answer
36 views

Generating function question with an inequality and finding the closed form.

Consider the inequality $x1+x2+x3+x4 ≤n$ where $x1, x2, x3, x4, n ≥ 0$ are all integers. Suppose also that $x2 ≥ 2$, $x3$ is a multiple of 4, and $1 ≤ x4 ≤ 3$. Let cn be the number of solutions of the ...
0
votes
1answer
48 views

A volunteer coordinator has 30 identical chocolate chip cookies to distribute to six volunteers.

Use a generating function (and computer algebra system) to determine the number of ways she can distribute the cookies so that each volunteer receives at least two cookies and no more than seven ...
0
votes
0answers
30 views

Weighted Q-binomial Coefficients

A possible identity popped up in a project for college, and if features q-binomial coefficient, which can be interpreted as the generating function for the number of Ferrer's boards fitting into a $k\...
2
votes
0answers
56 views

A limit about $\prod_{k=0}^\infty\frac1{1-x^k}$

If $$\sum\limits_{n = 0}^\infty {{a_n}{x^n}} = \prod\limits_{k = 0}^\infty {\frac{1}{{1 - {x^k}}}} ,$$ Prove $${a_n} < \exp \left\{ {\sqrt {\frac{{2\pi }}{3}n} } \right\}$$ and $$\mathop {\lim }\...
1
vote
2answers
35 views

Convolution formula proof- Random discrete varaiables [closed]

Let X, Y be discrete random variables and take values at $1, 2, · · · , n, · · · $ $f_{X}(t)=\sum_{k=0}^{k=inf} P(X=k)x^{k}$ is the probability generating function. and this result was given below $...
3
votes
2answers
28 views

Solve the recurrence relation $a_n = 2a_{n-1} + 2^n$ with $a_0 = 1$ using generating functions

Here is what I have so far, or what I know how to do, rather: I am given this equation: $a_n = 2a_{n-1} + 2^n$ with $a_0 = 1$ So, with the $2a_{n-1}$, I know I can do the following. We change the $...
2
votes
0answers
24 views

Finding a generating function for a sequence with two recurrence equations

The sequence $a_{n}$ is defined as follows: $a_{0}$ = 0 , $a_{1}$ = 1 $a_{2n} = a_{n}$ $a_{2n+1} = a_{n} + a_{n+1}$ let the generating function $F(x)$ be defined as $F(x) = \sum_{n=1}^{\infty} a_{...
1
vote
1answer
23 views

Find $G_a(x)$ for $a_n={4^{3n-5}\over3^{2n+4}}$

I don't really know where to begin on this one. I haven't gotten very far but I feel like with a few hints I should at least be able to start solving this.
1
vote
1answer
30 views

Find $G_a$ in the following case ${a_n}={1\over{(n-1)(n+1)}}$ for $n\ge 2$

We briefly covered generating functions in class and most of the situations we covered we were given a recurrence to find a generating function for. I haven't gotten very far but I do believe $$G_a(x) ...
0
votes
1answer
29 views

To find the Generating function for the given case

$$a_{n} = \frac{4^{3n-5}}{3^{2n+4}}$$ I was just able to reach till $a_{n}$ = ($\frac{64}{9}$) $a_{n-1}$ Don't know how to proceed further
2
votes
1answer
34 views

To calculate generating function

If $a_{n}$ = $\frac {1}{(n-1)(n+1)}$ for $n\ge2$ What are we supposed to do with $a_{0}$ and $a_{1}$? How can I find the generating function without using $a_{0}$ and $a_{1}$?
1
vote
1answer
20 views

Is $\sum_{n,m \geq 0} F_n^m x^n y^m$ a rational generating function?

I am curious if the generating function defined by: $$ F(x,y)=\sum_{n=0}^{\infty} \sum_{m=0}^{\infty} F_{n}^m x^n y^m$$ where $F_n$ is the $n$th fibonacci number, is a rational function. That is, Is ...
0
votes
4answers
44 views

How does $\frac4{1-x^3}=\sum_{n\ge 0}4x^{3n}$ equal $4x^0+0x^1+0x^2+4x^3+0x^4+0x^5+4x^6+0x^7+0x^8+\ldots$?

I've been searching through the internet and through SE to find something to help me understand generating functions, but I haven't found anything that would solve my problem with them. I understand ...
2
votes
1answer
99 views

Function that produces sequence 112123123412345…

I'm trying to find a function/formula for $a_n$ such that it produces the sequence $112123123412345$ and so on. I know that one possible way to do this is to find a function like $n-b_n$ where $b_n$ ...
12
votes
3answers
279 views

Words built from $\{0,1,2\}$ with restrictions which are not so easy to accomodate.

We assume a ternary alphabet $V=\{0,1,2\}$ and are looking for a generating function describing the number of words of $V^*$ fulfilling certain restrictions. The words I am interested in do not ...
1
vote
1answer
51 views

Formula for a geometric series weighted by binomial coefficients (sum over the upper index):$\sum_{i=0}^L {n+i\choose n}\ x^i =\ ?$

The binomial sum is $$\sum\limits_{i=0}^n {n\choose i}\ x^i = (1+x)^n,$$ where $\displaystyle{n\choose i}=\frac{n!}{(n-i)!i!}.$ Is there a corresponding formula when you sum over the upper index of ...
0
votes
0answers
11 views

Generating function for recurrence raised to powers

Well, there are many recurrence relations as $ \displaystyle a_n^{k_n} = \sum_m {f(a_m^{k_m})}$ So, I was thinking if there is a method(a particular kind of generating functions which deals with ...
1
vote
2answers
73 views

Help with finding the generating function of this language?

I've simplified this a bit so that I can just get help with the basic steps. Say we have a language of all words over $\{a,b,c,d\}$ where the only letters allowed to commute are $ab$. I need help ...
11
votes
1answer
216 views

Does the functional equation $p(x^2)=p(x)p(x+1)$ have a combinatorial interpretation?

A recent question asked about polynomial solutions to the functional equation $p(x^2)=p(x)p(x+1)$. Subsequently, Robert Israel posted an answer showing that solutions are necessarily of the form $p(x)=...
2
votes
1answer
99 views

Probability Generating Function homework question

Hello Everyone i have attempted this question as a homework problem and i have a solution and wondering if anyone can confirm if this is correct. The question is: A monkey repeatedly types in any of ...
4
votes
1answer
43 views

How to simplify this equation regarding pronic numbers for integer solutions

A pronic number is a number that can be expressed as the product of two consecutive positive integers. For instance, $42 = 6 \cdot 7$ is a pronic number. I've become interested in solving for the ...
0
votes
0answers
23 views

When can a function be represented by an infinite nested radical, a la a Taylor series?

Given a (let's say analytic) real function $f(x)$, when can $f(x)$ be represented as an infinite nested radical depending on $x$, constructed from some sequence? For example, the third and fourth ...