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

8
votes
0answers
133 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*} ...
7
votes
0answers
177 views

Does $A193201$ count the partitions of $n$ of arbitrary dimension?

By my count, these sequences match for $n=0\ldots6$, where partitions that are the same after relabeling dimensions are considered equivalent (i.e., the dimensions are unordered). For example, for ...
6
votes
0answers
55 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): ...
5
votes
0answers
238 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
94 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 ...
5
votes
0answers
141 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$. ...
4
votes
0answers
42 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
59 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
108 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
139 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
79 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
89 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). ...
4
votes
0answers
264 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
221 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
43 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
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 = ...
3
votes
0answers
60 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 ...
3
votes
0answers
59 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
138 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 ...
3
votes
0answers
127 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} ...
3
votes
0answers
136 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$ ...
3
votes
0answers
165 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 ...
3
votes
0answers
611 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 ...
2
votes
0answers
38 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
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 ...
2
votes
0answers
31 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
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
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 ...
2
votes
0answers
42 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
39 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
38 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
107 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
32 views

Link between partition function and ordered partition function

The partition function $p(n)$ measures the number of partitions of $n$, or the number of ways in which natural numbers can be summed to produce $n$, without regard to order. For example, the ...
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

Is there a systematic relation between the generating functions for the rows vs that for columns of infinite sized Carleman-matrices?

(Roughly related, but generalizing, of this earlier question) Background: The first part of the following(the column-wise-focus) is also described in Eri Jabotinski's 1953-treatize Representation of ...
2
votes
0answers
47 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
59 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
71 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 \ , \ ...
2
votes
0answers
80 views

Partitions of 200 into at most 6 parts.

I'm working on a partition problem, and I got an answer that is simply staggering, and I was hoping for someone to verify whether my answer is correct. The question was simply to determine the number ...
2
votes
0answers
60 views

Do asymptotically equivalent coefficients survive convolution at least in Θ?

This is a follow-up question to this one where I asked if asymptotic equivalence of coefficients carried over after convolution, resp. why this was not the case. Answerer Daniel Fischer proposed that ...
2
votes
0answers
106 views

Puzzle with character order

Suppose I have 3 letters a, b, c and I want to find the minimum length of a string that uses all the double combinations of the aforementioned letters. How should I do it or how are such problems ...
2
votes
0answers
57 views

Deriving combinatorial coefficients for a series related to the binomial series (but with a third index)

I have a problem that reminds me a lot of the binomial coefficients, and I'm wondering how to compute future elements with a nice formula, in the same way that $\binom{n}{k}$ is used as a symbol ...
2
votes
0answers
71 views

Find the sum of exponentails of squares $\sum_{r=1}^n e^{-\alpha r^2}$

I would like to find $$a_n =\sum_{r=1}^n e^{-\alpha r^2},\qquad \alpha\in\mathbb{R}$$ I tried to solve the equivalent recursion $$a_n=a_{n-1}+e^{-\alpha n^2}\quad(n>0),\qquad a_0=0.$$ with an ...
2
votes
0answers
73 views

Question about generating functions with trig

Consider there recurrence relation $$a_n=\frac{5}{4} a_{n-1} \cos{(\pi\cdot a_{n-1})}.$$ I am trying to find the generating function $A(x)=\sum_{n=1}^\infty a_nx^n.$ I've tried the following: ...
2
votes
0answers
69 views

Distributing problem using generating functions

For $r\in\mathbb{Z^*}$, let $a_r$ denote the number of ways to distribute $r$ identical objects into $3$ identical boxes, $b_r$ be the number of distributions so that the boxes are to be non-empty, ...
2
votes
0answers
48 views

Sequence of Ratios

Let $\{a_n\}_{n\ge 0}$ be a positive real sequence and define $$r_n=\frac{a_{n+1}}{a_n},\quad n\ge 0$$ Suppose that we know the formal power series of $a_n$, i.e. we know the following: ...
2
votes
0answers
197 views

Number of distributions of $r$ distinct objects into $n$ different boxes

Find an exponential generating function for the number of distributions of $r$ distinct objects into $n$ different boxes w/ exactly $m$ nonempty boxes I'm not sure about the solution, but this is ...
2
votes
0answers
117 views

Given a generating function for $\sum a_n z^n$, what is the generating function of $\sum a_n^2 z^n$

Given a generating function $G(z)$ for $\sum_{n=0}^{\infty} a_n z^n$, what could be said about the generating function of $\sum_{n=0}^{\infty} a_n^2 z^n$, what algebraic form should it have? For ...
2
votes
0answers
47 views

Generating Function for rational sequence

I'm trying to compute the generating function for the function defined for $1\le N < \beta$, $C_N = \frac{\beta}{N(\beta-N)}$. I think my math so far is correct, but I don't know how to solve the ...