# Questions tagged [generating-functions]

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.

3,382 questions
Filter by
Sorted by
Tagged with
8 views

### Non recursive form of Binomial transform of Catalan numbers

My question has already been asked previously and it also has a solution: https://math.stackexchange.com/a/3618692/745043 which asks to make use of the binomial series to derive the non-recursive form ...
15 views

### Generating Functions for Networks

I am an undergrad and trying to learn about complex networks but I don't understand the intuition behind the generating functions for networks, I need some sources to read from that explains the ...
35 views

### Simple Generating Function Not Working the Way I Interpret it?

Suppose we let A be all sequences of zeros and ones, with generating function $F (z) = 1/(1 − 2z)$. Now suppose we can attach a single or double prime to each $0$ or $1$, giving $0′$ or $0′′$ or $1′$ ...
15 views

55 views

### Generating function for $\sum_{i=0}^{k} {n \choose i}$

I'm looking for ordinary generating functions for the above expression. If it doesn't exist, I'll be open to consider exponential generating functions as well. Edit: I'm actually trying to simplify ...
38 views

### Solving a recurrence relation using generating functions - power series form of the partial fraction?

I wanted to solve a recurrence relation of the form $$(a+2b+c)f_{n}=bf_{n+1}+bf_{n-1}+cf_{0}$$ I know how to get the solution using the characteristic equation method but I wanted to solve it using ...
80 views

### please help me. I have probability generating function as follows, how can get the mixture distribution of $X$ from it?

$$G_x (s)=\frac{s \cdot (1-q(1-α+α \cdot s))}{(1-q \cdot s)(1-α+α \cdot s)}$$ Or, in another way, how can I say that a random variable follows a certain distribution with a certain probability and ...
38 views

### Proving relation between exponential generating functions whose coefficients count certain types of graphs

Let's there be two exponential generating functions: $A(x)=\sum^\infty_{n=1}\frac{a_n}{n!}x^n$ $B(x)=\sum^\infty_{n=1}\frac{b_n}{n!}x^n$ Sequence ${\{a_n\}}^\infty_{n=1}$ defines number of all ...
20 views

Carleman matrices are useful to express the composition of two functions. Recall that the Carleman matrix of a function $f$ is an infinite matrix whose $i,j$ element is $\frac{1}{j!}\frac{{\rm d}^j}{{\... 1answer 25 views ### getting probability mass function$f(k)$from probability generating function$G(s)$? I have the probability generating function$G(s)$as following. How can I get the mentioned probability-mass function$f(k)$from it? $$G(s)=\frac{1+\alpha(1+\mu)-\alpha(1+\mu)s}{(1+\mu-\mu s)(1+\... 1answer 24 views ### Determine the number of ways to color a 1-by-n chessboard with the colors red, blue, green and orange. Determine the number of ways to color a 1-by-n chessboard, using the colors red, blue, green and orange if an even number of squares is to be colored red and an even number is to be colored green. ... 2answers 61 views ### Evaluating 8th derivative of (e^x-1)^6 at x=0 8 distinct objects are distributed into 7 distinct boxes. Find the number of ways in which these objects can be distributed to exactly 6 boxes. I have solved this question quite easily using method of ... 2answers 36 views ### Using generating function to solve non-homogenous recurrence relation The given recurrence relation is:$$ a_{n} + 2a_{n-2} = 2n + 3 $$with initial conditions:$$ a_{0}=3a_{1}=5$$I know$$G(x) = a_0x^0 + a_1x^1 + \sum_{n=2}^{\infty} a_nx^n $$and$$ a_{n} = -... 0answers 57 views ### Closed form for a recurrence relation Let$\{y_n\}$be a sequence of positive reals satisfying the following recursive formula: $$y_{n+1} = \frac{1}{3} \left(y_n + \frac{2}{y_n}\right).$$ Now, I am interested in finding out a closed form ... 0answers 57 views ### Find asymptotics given equation satisfied by generating function. I'm interested in a sequence of numbers whose ordinary generating function obeys the equation: $$F(z) = 1-z^2+z(F(z))^3.$$ Is there some (relatively simple) way to get a good upper bound on the ... 1answer 66 views ### How to find the coefficient of$x^k$in$(x+1)(x+2)\cdots(x+N)?$We are given$n,k$and$n$can be very large ($10^9-10^{14}$) but k is relatively small ($k<=2000$). I tried using sum and product of reciprocal of roots but it fails at the first step itself due ... 1answer 40 views ### Recurrence relation for increasing sequence of numbers If$x_1, x_2, \dots, x_n$is sequence of non-negative integers (of any length including the empty sequence) then$s_k$is the total number of such sequences such that$x_i \in [k]$and$x_i \leq \frac{...
I am trying to prove the equivalence of the following two statement: $(a_i)_{0}^{\infty}$ and $(b_i)_{0}^{\infty}$ are infinite sequences of numbers, such that their elements are related in the ...