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

9
votes
0answers
162 views

Specializations of elementary symmetric polynomials

Let $\mathcal{S}_{x}=\{x_{1,},x_{2},\ldots x_{n}\}$ be a set of $n$ indeterminates. The $h^{th}$elementary symmetric polynomial is the sum of all monomials with $h$ factors \begin{eqnarray*} ...
6
votes
0answers
59 views

A conjecture about “equiharmonic numbers” of Flajolet via Doron Zeilberger

While semi-randomly browsing, I came across this conjecture which Philippe Flajolet sent to Doron Zeilberger as a "gift" (the "gift" is here, so you can check to see if I have typeset it correctly): ...
6
votes
0answers
108 views

Generating Function for Associated Stirling Numbers $b(n,k)$

I am trying to identify or find the ordinary generating function (not the exponential generating function) for the Associated Stirling numbers of the Second kind, denoted $$b(1;n,k)=b(n,k)$$ These ...
6
votes
0answers
159 views

Generating Functions, Recursive Polynomials

At the CMFT international conference in Turkey (2009), the following open problem was given: Show that $$p_n(x):=\sum_{k=0}^n \frac{(n-k)^k}{k!}x^{n-k}$$ has only real simple zeros for every $n$. ...
5
votes
0answers
134 views

Generating function for the number of surjections

Let $S_k^n$ be the number of possible surjections from a set of $k$ elements to a set of $n$ elements. We have $$\begin{align} &S_0^0 = 1,\qquad\forall k>0: S_k^0 = 0,\\ &S_n^n = ...
5
votes
0answers
282 views

Formula for composition of formal power series with binomial coefficient

Let $f=\sum\limits_{n\geq 0}{f_n x^n}$ and $g=\sum\limits_{n\geq 1}{g_n x^n}$ be formal power series. The $x^n$ coefficient of $f(g)$ is $$ \sum\limits_{\mathbb{i} \in \mathcal{C}_{n}} {f_k ...
5
votes
0answers
104 views

Pairwise sums are equal

The distinct positive integers $a_1,a_2,...,a_n,b_1,b_2,...,b_n$ with $n\ge2$ have the property that the $\binom{n}2$ sums $a_i+a_j$ are the same as the $\binom{n}2$ sums $b_i+b_j$ (in some order). ...
5
votes
0answers
729 views

Asymptotics for the expected length of the longest streak of heads.

As Introduction to Algorithms (CLRS) describes, the problem is Suppose you flip a fair coin $n$ times. What is the longest streak of consecutive heads that you expect to see? The book claims ...
4
votes
0answers
29 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 ...
4
votes
0answers
37 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 ...
4
votes
0answers
49 views

How to compute this series?

I am stuck in computing this series (i.e, finding a closed-form formula): $$ \sum_{i=0}^k \binom{k}{i} \frac{2r^{i+1}(1-r)^{k-i+1}p^{k-i}v^i s^k}{(1-r)p^{k-i}s^i + r v^i s^{k-i}}, $$ where $r$, $p$, ...
4
votes
0answers
90 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 ...
4
votes
0answers
69 views

Number of non-negative solutions to an equation - check my work

I tried to solve the following question and would love someone to check my work. Let $\displaystyle x_1,x_2,x_3,x_4$ $100$ digits long numbers where every digit is $1$ or $2$. Find the number ...
4
votes
0answers
228 views

Extinction probability of binomial branching process tends to poisson one.

The folowing is stated and proved in the random graphs book by Luczak, Janson, Rucinski and this is on page 108 in the Giant component section. I can't understand why the conclusion follows from the ...
4
votes
0answers
160 views

Stirling numbers and Power Group Enumeration

The following question is a reference request concerning a derivation of the EGF for the Stirling numbers of the second kind by Power Group Enumeration / Burnside's Lemma, which is $$\sum_{n\ge 0} ...
4
votes
0answers
128 views

Find generating function For sequences

Can anyone out here help? The exercise says: "Find the generating function for each of the sequences below (the general term is given)" Now, the question is how do you find one for those: a) $U_n = ...
4
votes
0answers
159 views

Card game probability

Suppose the following solitaire with a standard deck. I turn four cards visible on the board and on each turn, I remove those suits that appears more than once in the board. Then I fill the board such ...
4
votes
0answers
80 views

The importance of generating series

What follows is a very nebulous question. I just seek for some help in understanding a "technique" which has proven itself very powerful. I noticed that very often generating series appear in ...
4
votes
0answers
176 views

Combinatorics: Distributions with several constraints - potential generating sequences?

This seems to be a "stars and bars problem" - however I am unsure how to apply a constraint. Furthermore, I would like to understand how this would be done in both counting as well as generating ...
4
votes
0answers
298 views

Generating function for product of binomial coefficients

In general, if $a(n)$ is an integer sequence with generating function $A(t)$ and $b(n)$ is an integer sequence with generating function $B(t)$, it is not easy to find the generating function $C(t)$ ...
4
votes
0answers
242 views

What is the exponential generating function of the inverse matrix of an integer triangle?

Let ${Z}$ denote an integer triangle (like Pascal's), ${Z}_{n,k}$ for $0\leq k \leq n$ and let $f$ be an exponential generating function for polynomials $p_{n}(x)$ with $[x^k]p_{n}(x)= Z_{n,k}$. ...
3
votes
0answers
21 views

Writing a generating function

I came across the following question and it's a bit different from what I'm used to... Write a generating function for each of the following: 1) You are making an Easter basket with at most two ...
3
votes
0answers
76 views

A recursion formula related to *Catalan numbers*

When I was working on a problem related to Catalan Number, I deduced the following recursion formula: \begin{equation} a_{l,r}=a_{l-1,r}+a_{l-1,r-1}+a_{l-1,r-2}+\ldots+a_{l-1,l-1},\\ where \quad r \ge ...
3
votes
0answers
48 views

How to show that two probability generating functions are equal?

From Grimmett's Probability and Random Processes: Let $G_a(s) := \sum_0^\infty a_is^i$ where $a = \{a_i : i \geq 0\}$ is a real sequence. Uniqueness. If $G_a(s) = G_b(s)$ for $|s| < R'$ ...
3
votes
0answers
47 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 = ...
3
votes
0answers
65 views

What happens to the exponential generating function if the sequence is “stretched”?

Consider a real-valued sequence $(a_0,a_1,a_2,....)$ and the "$n$-stretch"-transformation, which inserts $n$ zeros between each element, for example $n=2$ would represent the transformation ...
3
votes
0answers
155 views

Generating Functions - Number of numbers with sum of digits $\leq 7$

How many natural numbers with $n$ digits are there, where the sum of their digits is $\leq 7$? So I said the following: For the first digit (MSB) we can't have a zero, and all the other $n-1$ ...
2
votes
0answers
26 views

Generating function for the Josephus Problem?

According to the Wikpedia article on the Josephus problem, the general solution is by dynamic programming. However, since there seems to be an explicit recurrence rule for the problem, should there ...
2
votes
0answers
37 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
50 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
0answers
57 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 ...
2
votes
0answers
55 views

A limit about $\prod_{k=0}^\infty\frac1{1-x^k}$

If $$\sum\limits_{n = 0}^\infty {{a_n}{x^n}} = \prod\limits_{k = 0}^\infty {\frac{1}{{1 - {x^k}}}} ,$$ Prove $${a_n} < \exp \left\{ {\sqrt {\frac{{2\pi }}{3}n} } \right\}$$ and $$\mathop {\lim ...
2
votes
0answers
24 views

Finding a generating function for a sequence with two recurrence equations

The sequence $a_{n}$ is defined as follows: $a_{0}$ = 0 , $a_{1}$ = 1 $a_{2n} = a_{n}$ $a_{2n+1} = a_{n} + a_{n+1}$ let the generating function $F(x)$ be defined as $F(x) = \sum_{n=1}^{\infty} ...
2
votes
0answers
28 views

Diagonalizing some very well behaved non-symmetric matrices

Suppose the matrices $A_N$ which in dimension $N$ have non-zero elements given by $(A_N)_{i,i+1}=i$ and $(A_N)_{i+1,i}=N-i$, for $i=1,...,N-1$ For example, $A_4=\left[ \begin {array}{cccc} ...
2
votes
0answers
36 views

Derivative of cumulative generating function at zero equals expectation value

Let $X$ be a random variable with values in $\mathbb{N_0}$. Then we can define the cumulative generating function of $X$ via $$ F_{X}: (-\infty, 0] \rightarrow \mathbb{R} \quad \quad t \mapsto ...
2
votes
0answers
37 views

What does this generating function terminology mean?

I am reading Zeilberger's paper on repeated coin tossing (winning or losing a dollar each time), and I came upon the following: If you factor a break-even sequence (i.e. with sum $0$) according ...
2
votes
0answers
98 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 ...
2
votes
0answers
56 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 ...
2
votes
0answers
41 views

generating function question, method?

Write a closed formula for the generating function of the sequence $a_n=(2n+3)(-1)^n$ So first I try $A(z)=\sum_{z=0}^\infty (2n+3)(-1)^nz^n$ $=\sum_{n=0}^\infty [2(n+1)+1](-1)^nz^n$ ...
2
votes
0answers
84 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
0answers
42 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 ...
2
votes
0answers
60 views

Generating function for recurrence in two variables

Given characteristic polynomial for the recurrence in two variables (say $F(x,y)$) $$ (y^2-1)^x $$ and initial values can generating function for $F(x,y)$ be derived? I know how to do it for a ...
2
votes
0answers
61 views

Asymptotic analysis of coefficients of ordinary generating functions with radius of convergence $1$ seems to always predict polynomial growth rate

Wikipedia gives the following formula for obtaining asymptotic information about the coefficients of an ordinary generating function from information about the generating function itself: if the ...
2
votes
0answers
37 views

Generating function of a_n * b_n

I've been searching for the answer yet no luck. Please let me know if this is a duplicate. Let $A(x) = \sum a_n x^n$, $B(x) = \sum b_n x^n$, $C(x) = \sum a_n b_n x^n$. I am looking for the closed ...
2
votes
0answers
42 views

Multivariable generating functions

Let's consider a 2-variable generating function for the Dyck triangle numbers. Reccurence, satisfying to the triangle conditions is $d_{n, k}=d_{n-1, k-1}+d_{n-1, k}+d_{n-1, k-1}$, $d_{0, 0}=1$, ...
2
votes
0answers
373 views

Formal sum of product of all size k subsets of a set

Is there a nice way to use generating functions to represent the formal sum of all size-$k$ subsets of a set $S$? Here I want to represent a subset by the product of its elements. For example, if $S ...
2
votes
0answers
41 views

Don't understand why this generating function needs to be taken to the power $-1$

I'm given the following recursive formula for a sequence: $u_{n+1}=u_n+\sum_{k=1}^{n-1}u_ku_{n-k}\ (n\ge1),\ u_0=0,\ u_1=1$ Since $u_0=0$ we can rewrite: $u_{n+1}=u_n+\sum_{k=0}^{n}u_ku_{n-k},\ ...
2
votes
0answers
58 views

Transforming Exponential to Ordinary Generating Functions

I am looking for a particular ordinary generating function, if it exists for the Associated Stirling Numbers of the second kind $$b(1;n,j)=b(n,j)=\sum_{k=0}^j(-1)^k\binom{n}{k}S(n-k,j-k)$$ Where ...
2
votes
0answers
72 views

How to solve this tough recurrence relation?

For solving a related probability problem, I'm required to solve the following recurrence relation:- $q(r,b,L)=\frac{b}{r+b}q(r,b-1,L)+\sum_{k=1}^{L}\frac{r}{r+b}\times\cdots \times ...
2
votes
0answers
89 views

Correctness of counting with product of generating functions

In generating functions we can related the coefficients of the generating function with as sequence. $$f(x) = \sum^{\infty}_{n=0}f_nx^n$$ and the sequence that corresponds to it: $$( \ f_0 \ , \ ...