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
0answers
26 views

partitions and generating functions ( combinatorics ) [on hold]

given partition, lets say the the ODD parts are : the biggest part, the 3th biggest part, the 5th biggest part etc and the EVEN parts are : the 2th biggest part, the 4th biggest part and so on . show ...
0
votes
1answer
25 views

Find number of nonnegative integer solutions to x+3y+3z=n, given n, using generating functions

For every $n,x,y,z\in \mathbb N$, where $x\ge{0}$ and $y,z \ge1$ Find the number of nonnegative integer solutions for $x+3y+3z = n$ I created a generating function for the problem: ...
0
votes
0answers
38 views

How to find the distribution from a given form of generating function

I have the generating function defined by F(x)= $\sum P(n,s) x^n$ . And the expression for F(x) is given by $F(x)= e^{\frac{a}{b}x} (1-x)^{b/s}$. Then how can i find p(n,s) function..? Can anybody ...
0
votes
1answer
47 views

probability generating function for multivariate distribution

I would like to ask how can we derive PGF of any multivariate distribution? and can anyone give an example of deriving the PGF of a multivariate distribution? That will be great. Thanks advance.
1
vote
2answers
116 views

a conjectured new generating function of narayana's sequence

In the 14th century ,an Indian mathematician T.V Narayana came up with a sequence now named after him.The sequence satisfies the recurrence $$a_{n}=a_{n-1}+a_{n-3}$$ Starting with $a_{0}=a_{1}=1$, ...
4
votes
1answer
144 views

conjectured new generating function of fibonacci numbers

I conjecture a new generating function for the fibonacci numbers $F_{n}$. Given, ...
1
vote
0answers
22 views

Generating function for writing an even number as a sum of at most k squares

I would like to find the exact number of ways in which $n$ can be represented as a sum of at most $k$ squares such that each term is less than or equal to say, $N$. A generating function for this ...
0
votes
1answer
31 views

Using generating functions to solve a distribution of distinct objects.

How many ways can $r$ distinct objects be distributed into $4$ distinct containers if there must be at most $1$ object in the first container? I think I have done this problem correctly. Can ...
0
votes
0answers
25 views

Writing the Equation to an Unknown Function?

I play a game that utilizes bombers to attack troops on a planet. The bombers takea percentage of the population depending on how many bombers were present in the battle. I was able to easily figure ...
0
votes
0answers
30 views

Recursion formula

I'm working on an exercise problem out of Algebra with Galois Theory by Emil Artin. I've arrived at the following recursion formula, $$ a_n = \sum_{i=1}^{n-1} a_ia_{n-i} $$ The hint in the book says ...
2
votes
2answers
85 views

A combinatorial identity No. 2

I have no idea how to simplify ( if possible at all ) this sum $$\sum_{k=0}^{n}(-1)^k\binom{x}{n-k}\binom{y-2x}{k}2^k$$ It would be fine if a 1-binomial expression formula would result.
1
vote
2answers
61 views

How to find an exponential generating function if we know a usual generating function? [duplicate]

Suppose we know a usual generating function of a sequence $a_0,a_1, a_2 \ldots :$ $$ f(x)=a_0+a_1 x+a_2 x^2+\cdots, $$ Question. It is possible to find an exponential generating function for the ...
-1
votes
6answers
70 views

Trivial Question : generating function

How does $ 1 + x + x^2 + x^3 + x^4 = \frac {1-x^5}{1-x} $ ?
2
votes
3answers
180 views

Generating Functions and closed form [closed]

I read somewhere that we can use generating functions to find closed form of a sequence. So what is the difference between a generating function and closed form of a sqeunce?
8
votes
1answer
140 views

Does $a_0=0, a_1=1, a_{n+2}=2a_{n+1}-3a_n$ ever return to 1 or -1 for $n>3$?

The sequence in question is the Lucas or Generalized Fibonacci sequence A088137. It's easy to write down its generating function $\frac{x}{1-2x+3x^2}$ and an explicit formula $a_n = ...
0
votes
1answer
21 views

Finding a moment generating function

I want to find $M(t)$ of $$f(x)= \begin{cases} e^{(-x-1)} & \text{for } x > -1 \\ 0 & \text{otherwise} \end{cases}$$ $e^{(-x-1)}$ I tried to do $$\int_{-1}^{∞ {}} e^{tx} ...
2
votes
0answers
33 views

What is the meaning of the cumulant generating function itself?

If we define the characteristic function for a random variable X as $\Phi(t)=<e^{itX}>$ then it seems like we can think of it as essentially a spectral decomposition that measures the ...
1
vote
1answer
43 views

Harmonic Generating Function

I have noticed an interesting generating function involving Harmonic Numbers. $$\sum_{n=1}^{\infty}H_nx^n=\frac{\ln(1-x)}{x-1}$$ But, I have not seen a generating function involving second-order ...
-1
votes
0answers
42 views

Finding distribution from PGF not in closed from.

$X_1,X_2,\ldots,X_N$ are independent and identically distributed random variables. We have $X = e^{-Y}$, where $Y\sim\mathrm{Poisson}(\lambda_u)$, and $$Z =X_1+X_2+\cdots+X_N ,$$ where $N \sim ...
5
votes
1answer
94 views

How to evaluate this double infinite sum (Catalan number)

Let $C_n = \dfrac{1}{n+1}\binom{2n}{n}$. Is it possible to find the exact value of this infinite sum ? $$\sum_{n=1}^\infty \sum_{k=n}^\infty ...
2
votes
0answers
51 views

Sum taken over the specified set of integer: $\sum_{3 \mid n} a_n$

Let's consider a sum $$S_{m}=\sum_{ 3 | n}^{m} {a_{n}}$$ where the sum is taken over all the integers $3t$, where $0 \leq 3t \leq m$. Assume that $G(z)$ is a generating function of the sequence ...
0
votes
1answer
36 views

How to reconstruct distribution from the generating function

Suppose $$F(x)=\sum_n p(n)x^n$$ is a generating function, and we have the expression for $F(x)$ explicitly. Then how we can get the expression for $p(n)$ from this generating function?
2
votes
2answers
38 views

Closed form for multiplicative recurrence relation

In this StackOverflow question, I found an interesting recurrence relation: $$f(n) = \begin{cases} 1 & n \leq 2 \\ nf(n-1) + (n-1)f(n-2) & \text{otherwise.}\end{cases}$$ I plugged it into ...
1
vote
3answers
61 views

How can I find the generating function of this sequence?

I am preparing for a test and I came across this example: Find the closed form generating function of: $$\dbinom{50}{1}, 2\dbinom{50}{2}, 3\dbinom{50}{3},..., 50\dbinom{50}{50},0,0,0,0$$ I know ...
20
votes
1answer
387 views

What function satisfies $F'(x) = F(2x)$?

The exponential generating function counting the number of graphs on $n$ labeled vertices satisfies (and is defined by) the equations $$ F'(x) = F(2x) \; \; ; \; \; F(0) = 1 $$ Is there some closed ...
0
votes
3answers
66 views

generating function for $\frac{n!}{(2n)!}$ [closed]

How to construct generating function such that $$g(x) = \sum_{n=0}^\infty \frac{n!}{(2n)!} t^n $$
4
votes
1answer
49 views

Recurrence relation in terms of another sequence

How do I solve a recurrence of the form $$nd^{n-1}a_n+a_{n+1}d^{n+1}=b_n$$ for $a_n$, where $b_n$ is another (known) sequence and $d$ is a constant? My only idea was to use a generating function and ...
0
votes
1answer
54 views

Mountain of coins

Let a mountain of coins be an arrangement coins in rows such that the coins in each row form a single block, and that in all rows (except the bottom row) each coin touches exactly two coins from the ...
2
votes
1answer
41 views

Bernoulli Numbers generating function and Riemann Zeta function

I've been studying Bernoulli numbers and I came across this summation: $$ \sum_{n=1}^{\infty}\frac{B_n x^n}{n!} = \sum_{n=1}^{\infty}\frac{-n \zeta(1-n) x^n}{n!} = -\sum_{n=1}^{\infty}\frac{\zeta(1-n) ...
0
votes
0answers
47 views

Question on how to manipulate terms in this expression

sorry for the vague title, i dont know how else to express what i mean with this question. But what i need to do is find out which terms on the RHS of the expression are constants. It is clear that it ...
21
votes
1answer
401 views

What is the intuition behind generating functions? What makes them valuable?

I'm sorry if this question makes no sense. I have been reading generatingfunctionology and I have been able to solve the problems in the first chapters and I understand the mechanism I have to follow ...
1
vote
2answers
48 views

Find the Sum using bijection

Find the sum of $S=\displaystyle\sum_{i,j,k \ge 0, i+j+k=17} ijk$. I am looking for a solution that uses some bijection. I couldn't find any bijection. I am able to do the problem by other method by ...
4
votes
2answers
168 views

Find $a_{n,i,j}$ in the expansion $(x + D)^n = \sum\limits_{i,j} a_{n,i,j} x^i D^j.$

This is problem 47c. in Stanley's Enumerative Combinatorics Vol. 1. Background: Let $D$ be the operator $\frac{d}{dx}$. Part (a) asks to prove $$ (xD)^n = \sum\limits_{k = 0}^n S(n,k)x^k D^k $$ ...
0
votes
0answers
37 views

What will be Terms after repeating this step(Differentiation and multiplication) F times.

I was solving a probability problem and got stuck on the following situation, where each x_i is independent of others: $$f=(x_1+x_2+..x_k)^N$$ I'm interested in the expression obtained after ...
1
vote
0answers
71 views

Stirling number Combinatorics. Summation .

$$ \sum_{k=0}^n \left\{ {n\atop k} \right\} *(x)_k = x^n $$ is well known . What if the k-th term of LHS summation is divided by $q^k$ where $q$ is some positive constant, What about $$ ...
3
votes
1answer
56 views

finding the partial bell polynomial of $e^x$

$$ \left(e^{x+z} - e^x\right) = \sum_{n=1}^\infty \frac{z^n}{n!} \frac{d^n}{dx^n}[e^x] $$ $$ \left(e^{x+z}-e^x\right)^k = \sum_{n \geq k} Y^{\Delta}_{e^x}(n,k,x)z^n $$ Where: $$ Y^{\Delta}(n,k,x) = ...
6
votes
4answers
383 views

How to solve this recurrence $K(n)=2K(n-1)-K(n-2)+C$?

The recurrence is $K(n)=2K(n-1)-K(n-2)+C$ where $C$ is a constant. What I have tried is substituting $2K(n-1)$ as we do in fibonnacical recurrences. It didn't gave me a fruitful expression! Can ...
1
vote
1answer
53 views

Better closed form for generating function $\sum \binom{n}{2k} x^k$

I have a power series $F_n(x) = \sum_k \binom{n}{2k} x^k$, which has a closed form of $F_n = \frac12 \left((1 + \sqrt{x})^n + (1 - \sqrt{x})^n\right)$. $$\begin{align} (1 + \sqrt{x})^n + (1 - ...
2
votes
2answers
51 views

How many solutions exists for this equation? [duplicate]

$$x_1 + x_2 + x_3 + x_4 = 28$$ I tried to solve it with generating functions. Is it correct to get to the form of $${(1 + x + {x^2} + {x^3} + ....)^4}$$ and this equals to: $${(1 - x)^{ - 4}}$$ ...
0
votes
1answer
22 views

Finding probabilities from probabilty generating function

Given that I have a probability generating function for $Q$ given by $\dfrac{4s^{2}}{9-3s-2s^{2}}$, I want to find $P(Q = n)$ for $n \geq 2$. I understand that I could actually use the definition of ...
1
vote
1answer
17 views

How to find the generating function from recurrence relation $t_n=(1+c~q^{n-1})~p~t_{n-1}+a +b+nbq, ~~n\ge 2$?

How to find the generating function $T(z)=\sum_{n=0}^{\infty} t_n~z^n$ from the recurrence relation $$t_n=(1+c~q^{n-1})~p~t_{n-1}+a +b+nbq,\qquad n\ge 2.$$ given that $$t_1=b+(1+c~p)(a~q^{-1}+b),$$ ...
4
votes
2answers
63 views

Determining probability generating function for event “$SS$”

Given a sequence of Bernouilli trials, we have $P(S) = \frac{2}{3}$ with $0<p<1$. The event "SS" occurs on the $i$-th trial if we observe an $S$ on the $i$-th trial following a $S$ on the ...
1
vote
3answers
64 views

How to solve this combinations with repetitions problem using generating functions?

Find the number of solutions to : $$x_1 + x_2 + x_3 + x_4 + x_5 = 10$$ where none of the variables can be the number $3$. I can solve this with Inclusion-Exclusion Principle, but I really love ...
1
vote
0answers
51 views

How to Evaluate this Summation to Find a Closed Form

While taking the incomplete Bell Polynomil of $x^a$ i found out that: $$ B_{n,k}^{x^a}(x) = x^{ak-n} \sum_{m=0}^k \frac{(am)!(-1)^{k-m}}{m!(k-m)!(am-n)!} $$ Now, what i am wondering is, what is the ...
1
vote
1answer
37 views

Determining Probability Generating Function from Probability Mass Function and Convergence

I am trying to solve the following: Suppose $X_{nk}, k=1,2,\ldots,n, n≥ 2$ are i.i.d. random variables $$P(X_{nk}=0)=1-\frac{1}{n}-\frac{1}{n^2}\\P(X_{nk}=1)=\frac{1}{n}\\P(X_{nk}=2)=\frac{1}{n^2}$$ ...
1
vote
1answer
39 views

Deriving Probability Density Function from Probability Generating Function for Random Sum

I am trying to solve the following: Let $X_{i}$~$Geometric(q) i=1,2,...,N$ with $q=1-p, 0<p<1$. $N$~$Geometric(p)$. Define $Y=\sum_{i=1}^{N}X_i$ and assume each $X_i$ is i.i.d. and ...
5
votes
2answers
78 views

Generating functions of bills

Using generating functions, find the number of ways to make change for a $\$$100 bill using only dollar coins and $\$$1, $\$$5, and $\$$10 bills. My answer: I had ...
1
vote
3answers
90 views

Exponential generating function for the number of binary strings of length $n$

I know that the generating function of the sequence counting the number of binary strings of length $n$ is $e^{2x}$. But my book doesn't explain why this is the case. Could you give me a little more ...
4
votes
2answers
93 views

No Adjacency Combinatorics Problem via Generating Function

I would like to find the generating function solution for the following combinatorics/probability problem. I have a combinatorial solution and the generating function deduced thereof. But I can not ...
0
votes
0answers
30 views

Enumeration of skew Ferrers diagrams revisited.

In M. P. Delest, J. M. Fedou, "Enumeration of skew Ferrers diagrams", Discrete Mathematics. vol.112, no.1-3, pp.65-79, (1993) http://dx.doi.org/10.1016/0012-365X(93)90224-H a generating function is ...