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

Closed formula for ordinary power series generating function

To find the ordinary power series generating function of $\left\{\frac{1}{n+1}\right\}_2^\infty$, I tried to solve it like this, let $$\begin{align} f &= \frac{x^{n-2}}{n+1}, \text{ where }n \ge ...
1
vote
1answer
17 views

Sequence from generating function with integral

So, let $A(x)$ be the generating function of $a_0,a_1,\dots$ then what would be the sequence of the generating function: $$\int^x_0 A(t)dt$$ Since I am not much acquainted with integrals any help ...
1
vote
0answers
22 views

Finding the generating function of $H_{0}$ probability of hitting 0 in Markov Chain

Let $Y1 , Y2,...$ be independent identically distributed random variables with $\mathbb{P}(Y1 =1)=\mathbb{P}(Y1 =-1)=1/2$ and set $Xo=1,Xn =Xo+Y1+...+Yn$ for $n\geq1$. Define; $$H_o= inf\{n\geq0:Xn = ...
4
votes
2answers
50 views

Name for the following set of polynomials

I have the following set of polynomials defined by $$P_n(x) = \sum^n_{k = 0} \frac{n!}{k!} x^k, \quad x \geqslant 0.$$ The first few are \begin{align*} P_0 (x) &= 1\\ P_1 (x) &= 1+x\\ P_2 (x) ...
0
votes
1answer
28 views

Probability generating function of binomial distribution [duplicate]

In a population of $2n$ individuals there are $n$ infected individuals and $n$ uninfected. Suppose that $X$ of the n uninfected become infected, where $X \sim \mathcal B(n, p)$, and, then, given $X = ...
1
vote
1answer
38 views

Find new generating function, given an arbitrary generating function

In a discrete mathematics past paper, I am asked to find the generating function for the sequence $$\langle a_0, 0, a_2, 0, a_4, 0, \ldots \rangle,$$ given that $A(x)$ is the generating function for ...
0
votes
1answer
21 views

What is the $C$ constant in this generating function? (probability)

Let \begin{equation*} G(x)= C \frac{4x^4+x^5+1}{16-8x-4x^2}. \end{equation*} How am I supposed to calculate $C$? Out of $50$ experiments how many $0$'s do I get? $16-8x-4x^2$ can be written as: ...
0
votes
0answers
37 views

Computing an exponential generating function from the first few terms

The current question is related to this one, and this other one. I have a number sequence, and I want to find generating ...
5
votes
2answers
57 views

Find the generating function of this sequence

I need to find the generating function of the sequence $c_n = (a_0, a_1, a_2, \ldots)$, where: $$a_n = \begin{cases} 2^{n/2} & \text{if $n$ is even,} \\ 1 & \text{if $n$ is odd.} ...
4
votes
1answer
40 views

Variant Generating Function related to Euler Numbers

The generating function $$\frac{2e^x}{e^{2x}+1}=\sum_{n\ge 0}E_k\frac{x^k}{k!}$$ counts the number of alternating permutations of a set with an even number of elements. My question is this, if we ...
2
votes
2answers
36 views

How can I determine the sequence which has this generating function?

In a discrete mathematics past paper, I must find the first eight terms of the sequence whose generating function is $$\frac{x^2}{(1-x)(1-2x)}.$$ I have looked at both of the following posts: How ...
0
votes
2answers
49 views

Generating function - the number of ways to distribute 100 dollars to n people.

I am currently a district math student and am learning generating functions. I was working on a question for a while and still couldn't find an answer to it. Here is the question: Find the generating ...
2
votes
0answers
20 views

Using Mellin transform for a certain function

In short, I want to use the Mellin transform to obtain the asymptotic behavior of the sequence $D_n = \frac{ [z^n] D(z)} {C_n}$ where $$ D(z) = \frac 1{2z}\sum_{p \ge 1}C_p \left( ...
0
votes
1answer
33 views

partition of integers proof

For each partition $\sigma = (\lambda_1,\ldots,\lambda_k)$, define the weight function $w^∗(σ) = k$. Let $\Phi^∗P_n (x)$ be the generating function for $P_n$ with respect to $w^*$. Prove that for all ...
0
votes
2answers
68 views

Coefficient $x^{15}$ out of expression

We throw 4 dice. We are interested in the number of ways to get at most $k$. So we are looking for the coefficient of $x^k$ in the generating function. The generating function will look like this: ...
1
vote
1answer
52 views

transforming ordinary generating function into exponential generating function

I have seen a post here that says that you can convert an exponential generating function into an ordinary one with the aid of the Laplace transform. Is it possible to do the reverse transformation? ...
1
vote
2answers
95 views

Finding the PGF of $Z$ using conditional expectation.

I am working on this problem, where I am required to write down the pgf of $X$, as well as the pgf of $Y$ given $X=j$, and then using conditional expectation find the pgf of $Z$. So far, I have ...
1
vote
3answers
87 views

nth element of recurrence relation

I need to find explicit equation, that will give me n-th element of this recurrence: $$ a_0=0\\ a_1=3\\ a_{n+2}=a_{n+1} + 2a_{n} $$ I know, that I can use generating functions and difference ...
2
votes
1answer
42 views

Constant term of noncommutative $(X+Y+(XY)^{-1})^n$

As the title reads I am trying to find a formula for the constant term of the above noncommutative polynomal expression, $$[1](X+Y+(XY)^{-1})^{3n}\quad \bigg(\in \mathbb{C}\langle X^{\pm 1},Y^{\pm ...
1
vote
0answers
42 views

A question on generating function

How to find the generating function of $\binom{2n}{n}$?
4
votes
1answer
103 views

A convolution involving binomials

Given $$f(i)\gt0,\:g(i)>0,\:i =0,1,2,3,...\:$$and$$\sum_{i=0}^{\infty}f(i) = 1,\sum_{i=0}^{\infty}g(i) = 1$$Prove that, if$$\frac{g(l-k)f(k)}{\sum_{i=0}^{l}f(i)g(l-i)}=\binom{l}{k}p^k(1-p)^{l-k}\: ...
1
vote
1answer
32 views

Use generating function to find coefficient

Use a generating function to find the coefficient of $x^{22}$ in: $$\frac{1+3x}{(1-x)^8}$$ I know I need to use a binomial expansion on the lower term, but what about the upper term?
0
votes
1answer
17 views

Partitions of an integer where each summand appears at most four times

Find the generating function for the number of partitions of an integer (greater than zero), where each summand appears at most four times. Is it the following?
2
votes
0answers
39 views

A Mellin Transform of a generating function

I am trying to find the Mellin transform of the function $$ G(z) = \sum_{k \ge 1} C_k\left( 1- \exp \left( \frac{-z}{4^k} \right )\right), $$ where $C_k$ denotes the $k$-th Catalan number ($C_k = ...
2
votes
2answers
55 views

Understanding a Generating Function

This is from generating functionology by Herbert S Wilf. Here a rule is given as let f $\longleftrightarrow$ {$a_n$}$^{\infty}_0$ is a ordinary power series generating function and let k be a ...
1
vote
0answers
41 views

Standard deviation of a function

Good day! Im now dealing with some dilemma regarding on how to get the standard deviation of a function in a mathematical way. Using the function $$\frac{2}{π} \ln (n)$$ and some mathematics software, ...
2
votes
1answer
40 views

Exponential generating functions counting

How many $10$-digit numbers use only the digits $0, 1, 2$ with each digit appearing at least twice or not at all? I know I need the coefficient of $\frac{x^{10}}{10!}$ in: ...
0
votes
1answer
56 views

Generating function for set of binary strings of equal block length

Where blocks would be consecutive 0's or consecutive 1's. So 0000 would be a block of length 4. I'm not even sure how such a set would look? Would the following elements at least be in the set (so I ...
1
vote
1answer
20 views

Probability Generating Function Attempt

I am trying to find the PGF for the following distribution: $X_1$ has PMF: $\rho(x) = \frac{-p^x}{x\ln(1-p)},n\in \mathbb N$ Attempt: \begin{align*} \phi_{X}(s) &= E[s^x]\\ ...
1
vote
1answer
31 views

How to find a formula for these generating sequences?

It is given that $a_{0}=1$ , $b_{0}=0$ , $c_0=0$ $$ c_n= xc_{n-1}+x(x-1)a_{n-1}(3b_{n-1}+(x-2)a_{n-1}^{2})) $$ $$ b_n=xb_{n-1}+x(x-1)a_{n-1}^{2} $$ $$ a_n=xa_{n-1}+1 $$ where x is any constant. ...
3
votes
0answers
30 views

Probability Generating Function of Compound Poisson Process

Let $(N_t)_{t\ge 0}$ be a poisson process with intensity $\alpha > 0$. Let $(X_n)_{n \in \mathbb N}$ be iid real valued random variables that are independent of $N_t$. Let $Y_t = ...
0
votes
1answer
27 views

Prove that using generating function:For any $n ,k\in N$, the number of partitions of $n$ into parts

For any $n,k\in N$, the number of partitions of $n$ into parts, each of which appears at most $k$ times, is equal to the number of partitions of $n$ into parts the sizes which are not divisible by ...
2
votes
1answer
66 views

Proof regarding a probability generating function (Poisson)

Let $f(s)$ be the probability generating function ($pgf$) of a non-negative, integer valued random variable. It is also given that $f(1-p+ps)f(p) = f(ps)$. Prove that $f(s) = e^{\lambda(s-1)}$ for ...
2
votes
0answers
33 views

What are the combinatorial numbers appearing in these repeated derivatives?

Let $f$ be a $C^\infty$-function and define $g(x) = \exp(f(x))$. I am interested in the higher derivatives $g^{(1)}, g^{(2)}, \ldots$ of $g$. Let $\lambda$ be a partition of $n$, i.e. a tuple of ...
1
vote
2answers
53 views

Number of ways to throw at most 14 with 4 dice - generating functions

Determine the chance to throw at most 14 with 4 normal dice. I will set up the right generating function to determine the number of ways tot thow at most 14 with 4 normal dice and I need some help. I ...
2
votes
1answer
55 views

Find A closed form generating function $a(n)=C(N+7,4)$ for $n=0,1,2,…$ [closed]

Find a closed form generating function $a(n)=\binom{n+7}4$ for $n=0,1,2,\ldots$. So not really sure how to approach a combination when it used in generating functions?
0
votes
2answers
75 views

Find a closed form of the generating function for $a(n) =3n^2+4n+5$, $n=0,1,2,…$

Find a closed form of the generating function for $a(n)=3n^2+4n+5$ n=0,1,2,.... not sure how the constraint n=0,1,2,.... applies to this. Does this means that the coefficient must go up sequentially ...
3
votes
0answers
42 views

Coefficients of (generating) function

If I have the generating function \begin{equation*} A(x)= \frac{1}{(1-x^{10})\cdot(1-x^5)\cdot(1-x) }\,, \end{equation*} what is a clean way to find the coefficients of $x^{n}$. This coefficient ...
0
votes
2answers
34 views

Closed form for generating functions [closed]

I'm really not sure how to solve these type of questions could somebody lead me in the right direction? Find a closed form for these generating functions $$(a)\quad u_n = 3n^2+4n+5 \quad for ...
-2
votes
1answer
36 views

Expressing $\frac {x^n}{(1-x)^n}$ as a generating function [closed]

How did they get the following: $$\frac {x^n}{(1-x)^n} = \sum\limits_{m}{m-1 \choose n-1}{x^m}$$
1
vote
1answer
39 views

Evaluate $\sum\limits_{k=m}^n (-1)^k {n \choose k} {k \choose m}$

By using generating functions and snake-oil I got to Also what is the implication of $\sum \limits_ {k<={n}}$? I am told that this is equivalent to: But I'm not sure how to do that step, ...
1
vote
0answers
31 views

Generating Series and Recurrence Relation and Closed Form

We have the following recurrence relation: $b_n=2b_{n-1}+b_{n-2}$ and initial conditions $b_0=0, b_1=2$ I use the generating series method to solve as following: Let ...
2
votes
3answers
51 views

Generating function for $a_n= a_{n-1}+2a_{n-2}$+3

How do I find a generating function for $a_n= a_{n-1}+2a_{n-2}$+3 using sigma notation? with initial conditions $a_0$ =2 and $a_1$ = 2. I'm mainly confused by how to deal with the "+3" at the end. ...
0
votes
0answers
16 views

How to assemble rook polynomials?

I have a problem. I need to assemble a rook polynomial for the chessboard (6x6 boards). Black boards are 1, white boards are 0. ...
1
vote
1answer
26 views

Generation function $a_{n} = n$

I want to find the closed form of this  $\sum\limits_{n=0}^{\infty} {nx^{n}}$Is the following correct? $(\sum\limits_{n=0}^{\infty} x^n)^{'}= (1)^{'}+(x)^{'}+(x^2)^{'}+(x^3)^{'}+...=$ $0 + 1 +2x ...
2
votes
2answers
82 views

The value of ${\sum_{k=0}^{20}}(-1)^k\binom{30}{k}\binom{30}{k+10}$

$\newcommand{\b}[1]{\left(#1\right)} \newcommand{\c}[1]{{}^{30}{\mathbb C}_{#1}} \newcommand{\r}[1]{\frac1{x^{#1}}}$ The value of $$\sum_{k=0}^{20}(-1)^k\binom{30}{k}\binom{30}{k+10}$$ It is also the ...
3
votes
1answer
89 views

$\sum \limits_{n \geq 0}a_n \frac{x^n}{n!}=e^{x+x^2/2}$ implies $a_n \sim \frac1{\sqrt2} n^{\frac n2}e^{ -\frac n2+\sqrt n -\frac14 }$

Prove the following asymptotic formula for the exponential generating function coefficients of $e^{x+x^2/2}$: $\; \; a_n \sim \frac1{\sqrt2} n^{\frac n2}e^{ -\frac n2+\sqrt n -\frac14 }$ Stanley ...
2
votes
1answer
12 views

W/ generating functions, How many solutions are there to the equation $2a+3b+c=n$ for some integer $n \geq 0$ and $a, b, c \geq 0$?

The question is: How many solutions are there to the equation $2a+3b+c=n$ for some integer $n \geq 0$ and $a, b, c \geq 0$? Solve this by writing down the correct generating function. I have no idea ...
4
votes
1answer
66 views

What did i do wrong with this derivation?

$$ \cos(x) = \sum_{n=0}^\infty \frac{(-1)^n x^{2n}}{(2n)!} $$ Therefore \begin{align} \frac{1}{\cos(x)} &= \frac{1}{1-(\frac{x^2}{2} - \frac{x^4}{4!} + \frac{x^6}{6!} - \cdots)} \\ &= ...
3
votes
1answer
52 views

On the number of ways to make $50n$ cents out of pennies, nickels, dimes and quarters

Let $f(n)$ be the number of ways to make n cents out of pennies, nickels, dimes and quarters (1c, 5c, 10c, 25c). Prove that $f(50n) = an^3 + bn^2 + cn + 1$ for some constants $a, b, c.$ I have found ...