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
37 views

Integral of Legendre Polynomial

Determine the following integral $$\int_{-1}^{1}x^{2}P_{2n-1}\left(x\right) dx$$ Using the generating function and the fact that $\left(1-2rx+r^2\right)^{-1/2}=\sum^{\infty}_{n=0}P_{n}\left(x\right)...
1
vote
1answer
22 views

Closed form solution for generating function

The recursion formula for some probability $P_n(s)$ is $$P_{n+1}(s) = qP_n(s+1) + pP_n(s-1).$$ Define the generating function $$G(z,n) = \sum_{s=-\infty}^{\infty} z^s P_n(s)$$ and prove the ...
2
votes
1answer
32 views

Closed Form Solution to Exponential Recursion

Is there a closed form solution to the function $f_n=2^{f_{n-1}}$ where $f_0=2$ ? For instance, the first few values of the function are 2, 4, 16, 65536.
0
votes
0answers
21 views

Showing tat if $f(n) \sim cn^2$

I need to show that there is a constant $c$ such that if $f(n)$ is the number of solutions of $2x+3y+5z = n$ in nonnegative integers, then $f(n) ~ cn^2$ and find the value of $c$. What I tried was ...
1
vote
1answer
37 views

Giving a method for generating random numbers with a cumulative distribution function

So let's say I have a cumulative distribution function: $$F(x) = \frac{1}{2} (x + x^2) \space for \space 0 \lt x \lt 1$$ How do I find a method for generating random numbers from this function?
1
vote
2answers
54 views

Bernoulli Numbers and Tangent numbers.

Good evening. I am looking to see if there is a proof online to help guide me with the understanding that the Tangent Numbers, denoted $T_n$ and the Bernoulli numbers, denoted $B_n$ are related. It ...
1
vote
1answer
46 views

Generating function for the partition function [duplicate]

Could someone explain what is the reasoning behind the following equality? Or maybe direct me to a proof of the following equality? $$\sum_{n=0}^{\infty}p(n)x^n = \prod_{k=1}^{\infty}(1-x^k)^{-1}$$ ...
3
votes
2answers
38 views

Evaluate the sum $S=\sum_{k=0}^{n} \frac{(-1)^k}{k+1} {n \choose k}$ [duplicate]

The question is to evaluate $S=\sum_{k=0}^{n} \frac{(-1)^k}{k+1} {n \choose k}$ $\textbf{My Attempt:}$ I have considered the generating function $$ f(x)=\sum_{k=0}^{n} {n\choose k} x^k = (x+1)^n$$...
5
votes
2answers
77 views

Number of solutions of $x_1+2\cdot x_2+2\cdot x_3 = n$

I have to find number of solutions of $x_1+2\cdot x_2+2\cdot x_3 = n$. I guess it would be $[x^n](1+x+x^2 \dots)(1 + x^2 + x^4 \dots)^2$, but how to compute it? I know only that $\frac{1}{1-x} = 1+x+x^...
2
votes
0answers
39 views

Is there a closed form expression for this sum involving Stirling number of second kind

The expression I am trying to simplify is the following: $$f(x)=\sum_{n\ge k}S(n,k)(L)_{n}x^n$$ where $S(k,n)$ is the Stirling number of second kind for $k,n\in \mathbb{Z}^+,\ L\ge n$ and $(L)_n$ is ...
2
votes
0answers
51 views

Finding the Generating Function given a Complex Recurrence

I have the following recurrence relation: $G_0=0, G_1=1,$ $$\left(G+\frac{2}{3}\right)^n+\left(G+\frac{1+w_3}{3}\right)^n+\left(G+\frac{1+w_3^2}{3}\right)^n=0, n>1$$ where $w_3$ is the primitive $...
2
votes
1answer
40 views

Number of subsets $S$ of $[n]$ such that $\gcd(S)$ is coprime to $m$

Fix positive integers $m,n$. Is there a way to count the number of non-empty subsets $S$ of $[n] = \{1, \ldots, n\}$ such that $\gcd(S)$ is coprime to $m$? Can we come up with an expression for such a ...
4
votes
0answers
31 views

Functions that make a set of functions based on given conditions

Recently, I have been thinking about functions that make functions based on a set of conditions. Originally, I thought this is what generating functions were but after doing some research, I didn't ...
0
votes
1answer
12 views

Show that the following Legendre polynomials are equal

$P_{n}\left( -x\right) =\left( -1\right) ^{n}P_{n}\left( x\right)$ I understand that we could use the generating function and using the fact that $\left( 1+2rx+r^{2}\right) ^{-1/2}$ We could ...
2
votes
1answer
65 views

Find an egf for $\sum^{n}_{k=0} \binom{n}{k}$

The egf would be $\sum_{n = 0} [\sum^{n}_{k=0} \binom{n}{k}]\frac{x^{n}}{n!}$ = $\sum_{n = 0} \frac{n!}{k!(n-k)!}\frac{x^{n}}{n!}$ = $\sum_{n = 0} \frac{x^{n}}{k!(n-k)!}$ From here I'm a little stuck,...
0
votes
0answers
24 views

prove the equation by generating functions [duplicate]

Im studying a book about stochastic processes and it is mentioned in the book that the equation below is true and we can obtain it by generating functions can anyone prove it. Thanks a lot. $$\sum_{m=...
1
vote
1answer
53 views

Using generating functions to count

I have an assignment question that asks "use generating functions to calculate the number of integers between $100,000$ and $999,999$ the sum of whose digits is $k$" I am familiar with generating ...
3
votes
1answer
113 views

Can we characterize the probability generating function as a linear operator?

For a nonnegative integer-valued random variable $X$ with $\mathbb P(X=j)=p_j$, we define the probability generating function of (the distribution of) $X$ by $$P_X(s):=\mathbb E\left[s^X\right] = \...
0
votes
2answers
59 views

Evaluate the following sums using generating functions

I have two series that I'm supposed to evaluate using generating functions. (a) $0+1+2+3+4+ ...+ n$ (b) $0 + 3 + 12+...+3n^2$ I know how to evaluate (a) using walks in Pascal's triangle: the answer ...
1
vote
2answers
51 views

Reindexing Exponential Generating Function

I have an exponential generating function, and I need to double check what the teacher said, because I'm having trouble coming to the same result. Also, I need to verify what I am coming up with, and ...
5
votes
2answers
184 views

How many ways to choose $a<b<c<d<e$ from the set $\{1,2,3,\cdots,100\}$ such that $100<a+b+c+d+e<145$?

I would appreciate if somebody could help me with the following problem In how many ways can I choose a five number $a,b,c,d,e(a<b<c<d<e)$ from the set $\{1,2,3,\cdots,100\}$ such that $...
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
53 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
34 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
94 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
40 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
43 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
107 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
68 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
158 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
55 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 ...