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

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
24 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
57 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
54 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
27 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
34 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
47 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 ...
2
votes
0answers
55 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} ...
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
92 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
277 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
49 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
212 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 ...
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
41 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
21 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 ...
1
vote
3answers
93 views

Calculate $a_n = \binom{n}{2} + \binom{2}{n}$

Calculate $a_n = \binom{n}{2} + \binom{2}{n}$ Could you give me a hint how to start solving this equation? How can I expand $\binom{2}{n}$? Definition of $\binom{a}{b}=\frac{a \cdot (a-1) \cdots ...
0
votes
1answer
33 views

Calculate coefficients of power series

Calculate the coefficients of the power series expansion of $f(z)=\frac{2}{\sqrt{1-3z}}+\frac{1}{(1-z)(1-2z)}$ Could you check if I understood the task and calculated it correctly? ...
0
votes
1answer
54 views

Find a generating function with Fibonacci

$$G(x) = \sum_{n=1}^\infty na_n x^n $$ Hello. I need to find a generating function for the summation above, where $a_n$ is the Fibonacci sequence. I have found the generating function for the ...
2
votes
3answers
69 views

Solve $a_n=2 a_{n-1} - a_{n-2} + 2^n$ using generating function

I'm preparing to an exam and trying to solve $a_n=2 a_{n-1} - a_{n-2} + 2^n$, where $a_0=0$ and $a_1=1$. This is my approach: Let $A(z)=\sum_{n \geq 0} a_{n+2} z^{n+2}$, then: $$\sum a_{n+2} ...
1
vote
0answers
44 views

Hermite's identity for sum of floor function

In Hermite's 1884 paper "Sur quelques conséquences arithmétiques des formules de la théorie des fonctions elliptiques", volume 5 of Acta Mathematica, pages 310-315, he proves what is often called ...
3
votes
1answer
73 views

number of permutations of [n] for which all cycles have even length

I'm looking to find the number of permutations of [n] for which all cycles have even length, call that number $f_n$. I've seen here: Number of permutations of a specific cycle decomposition that the ...
1
vote
0answers
39 views

exponential generating function for the number of ways to arrange marbles in a line

Say we have red, green, and blue marbles that we are arranging in a line of length n. We need to use an even number of blue marbles, at least two red marbles, and at most two green marbles. I am ...
1
vote
1answer
44 views

alternating sum of squares using a generating function

say we have the alternating sum of squares $f_n=\sum_{k=0}^n(-1)^kk^2$=-1+4-9+16-25+... Any ideas how to derive this in terms of n using a generating function? I know that it can be derived by seeing ...
0
votes
2answers
42 views

What does this binomial sum equal?

I'm trying to evaluate this sum: $$\sum_{k=0}^n {n \choose k}{{2n+1}\choose k}$$ I thought I could work with generating functions of the two binomials. I know $$\sum_k\binom{n}k{}x^k=(1+x)^n$$ is the ...
5
votes
1answer
112 views

Finding Divisibility of Sequence of Numbers Generated Recursively

I have the following generating function: $$E(x)=\frac{2e^x}{e^{2x}+1+2x}=\sum_{n=0}^\infty {E_n}\frac{x^n}{n!}$$ which generates a sequence of integers below $$\{1, -1, 3, -15, 93, -725, 6815, ...
1
vote
0answers
76 views

How to prove this equality about Eulerian numbers?

I want to prove the following equality where $A(k,m)$ is the Eulerian number : $$\forall k\ge0,\sum_{k=0}^{\infty}n^k x^k = \frac{\sum_{m=0}^{k-1}A(k,m)x^{m+1}}{(1-x)^{k+1}}$$ I previously proved ...
0
votes
1answer
35 views

Dice rolls-Generating Functions

Let $d_n$ be the number of ordered sequences of die rolls (i.e., sequences of integers from $1$ to $6$) that add up to $n$. For example, $d_4=8$, because a total of $4$ can be rolled in $8$ ways: ...
5
votes
2answers
118 views

Find a sum $S = \sum\limits_{t \in E} \sum\limits_{x \in E} (t + x)(t + x^2)…(t+x^{2p})$

I am solving a problem that has already a plan for the solution. As a subproblem I have to find the value of $$S = \sum\limits_{t \in E} \sum\limits_{x \in E} (t + x)(t + x^2)...(t+x^{2p})$$ where ...
2
votes
2answers
52 views

How many ways can you collect six dollars from $8$ people if $6$ people give $0$ or $1$ dollars and $2$ people each give $0$, $1$, or $5$ dollars?

I must use a generating function to solve this question: In how many ways can you collect six dollars from eight people if six people give either $0$ or $1$ dollars and the other two people each ...
1
vote
2answers
49 views

Generating function to find the number of ways to put marbles in a basket

Write a generating function for the number of ways to make a basket of $n$ marbles, if you need to use at least one orange marble , an even number of yellow marbles, at most 2 green marbles, and any ...
0
votes
0answers
24 views

Additive combinatorics, moments, generating functions, Cauchy's formula and asymptotics

Let $A, B$ be finite sets of positive integers, let $$f(z) = \left(\sum_{a \in A} z^a\right)\left(\sum_{b \in B} z^b \right) = \sum_{m \geq 0} r_{A, B}(m) z^m,$$ where $r_{A, B}(m)$ is the number of ...
0
votes
3answers
129 views

How to fit $\sum{n^{2}x^{n}}$ into a generating function?

I do have somewhat of a reasoning for this. $$S = 1 + x + x^{2} + x^{3} +.. + x^{n} $$ Denoting the derivative of $S$ as $T$ $$T = 1 + 2x + 3x^{2} + 4x^{3} +... + nx^{n-1}$$ $$xT = x + 2x^{2} + ...
2
votes
2answers
29 views

Number of equivalence classes of permutations which are equivalent if neighboring even(odd) numbers can be interchanged

Let $S_8$ be the set of all permutations of $1,2,\dots, 8$. For example $\sigma=(8,5,4,3,1,2,6,7)$ is a permutation . We define the equivalence relation $\sim$ on $S_8$ such that if two odd (or even) ...
1
vote
0answers
36 views

Searching for a generating function of a probability mass function

I am looking for a a family of probability mass functions $f_n$ with the following recurrence: $$ f_{n}(k)=qf_{n-1}(k)+p\sum_{i=1}^{k-1}f_{n-1}(i)f_{n-1}(k-i). $$ In addition, we have $q=1-p$ and $ ...
0
votes
3answers
42 views

Using generating functions to solve a recurrent relation

I have one question on my Discrete Math homework that involves using generating functions, and I'm at a complete loss for how they work. The question asks: "Use the generating function method to ...
2
votes
1answer
22 views

Generating function with G'(1) and G''(1) reducing to 0/0 = undefined

My question is about an analysis of an algorithm in D. E. Knuth's book The Art of Computer Programming, Vol. 1. More specifically, it is about section 1.2.10, equations 20 to 22. First we have a ...
3
votes
1answer
57 views

In how many ways can we select $r$ crayons from six different colors (red, yellow, blue, green, purple, orange), with an odd number of red and yellow?

I need to make a generating function for the following: In how many ways can we select $r$ crayons from six different colors (red, yellow, blue, green, purple, orange), with an odd number of red and ...
4
votes
1answer
75 views

How many numbers between $0$ and $999,999$ are there whose digits sum to $r$

How many numbers between $0$ and $999,999$ are there whose digits sum to $r$ In generating a function for the answer, here is what I came to. We have a maximum of 6 number slots to use to sum to r. ...