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

Generating Functions to design nonstandard dice

Define a nonstandard die as a $6$-sided die that is equally likely to come up on each side, but has a different set of numbers than the usual $1,2,3,4,5,6$ on its sides. A standard die will be the ...
0
votes
1answer
29 views

Generating functions which are prime

Sorry for strangely worded title. The intended meaning is the generating functions which are not divisible by other generating functions, not functions for generating prime numbers. With this out of ...
1
vote
2answers
46 views

Sum with Generating Functions

Find the sum $$\sum_{n=2}^{\infty} \frac{\binom n2}{4^n} ~~=~~ \frac{\binom 22}{16}+\frac{\binom 32}{64}+\frac{\binom 42}{256}+\cdots$$ How can I use generating functions to solve this?
0
votes
1answer
32 views

generating function for a power sequence

The question is short: I don't understand how should I solve this. Problem wants the G(x) of this: 1,4,9,16,... I can solve this one but I cannot connect these two to each other: 1,2,3,4,...
1
vote
1answer
25 views

Find the generating function

I'm trying to find the generating function for this sequence: $$0,0,3,0,9,17,33,65,129,257...$$ What I know so far: $$0\cdot x^0 + 0\cdot x^1 + 3\cdot x^2 + 0 \cdot x^3$$ and ...
3
votes
2answers
77 views

What sequence does $\frac{1}{1-s-s^4}$ generate?

When attempting to find an easy answer to this question What is the coefficient of $x^{11}$ in the power series expansion of $\dfrac 1{1-x-x^4}$? I'd think of $\frac{1}{1-x-x^4}$ as of a ...
1
vote
1answer
23 views

Generating function for $l_{n+1} = 3l_n+1$.

I have the sequence $l_{n+1} = 3l_n+1$ for $l_0 = 0$ or $1$ (This just shifts the sequence one index back or forward.) The first terms are $(0),1,4,13,40,121,364,\ldots$ So I am looking for an ...
1
vote
1answer
30 views

Finding the generating funcrtion associated with a sequence

I'm having a little trouble understanding this type of question: Find the generating function for this sequence. $$ 0,0,1,0,16,32,64,128,256,512...$$ I'm pretty new to this concept of generating ...
2
votes
1answer
40 views

Find number of solutions of this equation using generating function

I'm given an equation $x_1 + x_2 + x_3 + x_4 + x_5 = 24$, with a restriction that all of $x_i > 1$ and 2 of them are odd, the rest are even natural numbers. I can solve this using the following ...
3
votes
2answers
120 views

how to prove a combinatorial identity

I've encountered with following identity: $$\sum\limits_{n=0}^\infty\binom{a+bn}{n} \left(\frac{z}{(1+z)^b}\right)^n=\frac{(1+z)^{1+a}}{1+(1-b)z}$$ Is it correct? how to prove it?
0
votes
0answers
48 views

Expansion of $(6 + 3x + x^2)^n$

In the role playing game Exalted, there is a dice mechanic whereby you have a certain number of 10-sided dice in a dice pool and when you roll them, each die showing a 7, 8, or 9 count as one success ...
0
votes
0answers
23 views

What kind of generating function adapts well both argument shift and multiplicativity?

I have encountered a sequence which involves both some multiplicative arithmetic functions and argument shifts and does not seem to fit neither into Dirichlet nor Lambert kind of generating function. ...
0
votes
1answer
74 views

Dirichlet series generating function of a sequence

To find the dirichlet series generating function of the following sequence $\left\{\sum_{n/d}d^q\right\}_{n=1}^\infty$ The series is like this $\frac{1^q}{1^s} + \frac{1^q+2^q}{2^s} + ...
0
votes
0answers
26 views

Substitutions in Probability Generating Functions

I have a probability generating function: $$G_{i,j}(x,y)=\sum_{i,j}p(i,j)x^i y^j.$$ I was wondering what is the intuition beyond setting $G(y)=G_{i,j}(1,y)$? Does it represent anything special? I ...
4
votes
1answer
40 views

How to determine the generating function?

So I have $$\overset{*}{F} = \overset{*}{F}_{n-1} + \overset{*}{F}_{n-2} + g(n)$$ where $\overset{*}{F}$ is NOT a Fibonacci number for $n \geq 2$. $g(n)$ is any function $g: \mathbb{N} \to ...
1
vote
1answer
46 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 ...
4
votes
1answer
28 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
30 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
72 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
61 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
45 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
22 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
45 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 ...
6
votes
2answers
85 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.} ...
5
votes
1answer
57 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
43 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
63 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 ...
0
votes
1answer
38 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
72 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: ...
2
votes
2answers
116 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
106 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
96 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
56 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
votes
1answer
56 views

A question on generating function

How to find the generating function of $\binom{2n}{n}$?
4
votes
1answer
120 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
36 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
25 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
53 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
63 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
44 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
45 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
69 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
27 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
44 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
38 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
29 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
78 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
38 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
61 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
63 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?