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

19
votes
0answers
451 views

Generating function solution to previous question $a_{n}=a_{\lfloor n/2\rfloor}+a_{\lfloor n/3 \rfloor}+a_{\lfloor n/6\rfloor}$

In attempting to answer this question, I reduced it to a seemingly simple generating functions question, but after days of work was unable to construct a proof. Since I do not have experience trying ...
7
votes
0answers
170 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
126 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*} ...
5
votes
0answers
131 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
34 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): ...
4
votes
0answers
84 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 ...
4
votes
0answers
136 views

Generating functions to solve number of integer solution problem

If I have $x_1 + x_2 + x_3 =10$ with $1\leq x_1 \leq 5, \; 2 \leq x_2 \leq 6, \;3 \leq x_3 \leq 9$ I know that I compute $(t^1+\dots + t^5)(t^2 +\dots + t^6)(t^3+\dots +t^9)$ and look at the ...
4
votes
0answers
130 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
76 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
243 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
212 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
30 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
44 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
52 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
50 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 ...
3
votes
0answers
127 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
124 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
49 views

Generating series - Finite groups of order $n$

I am wondering if something of interest can be said about one of the two series $$G_1(x)=\sum_{n=1}^{+\infty}{\mathcal{G}(n)z^n}$$ $$G_2(s)=\sum_{n=1}^{+\infty}{\frac{\mathcal{G}(n)}{n^s}}$$ where ...
3
votes
0answers
93 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 = ...
3
votes
0answers
129 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
162 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
576 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
33 views

Using Mellin transform for a certain function

In short, I want to use the Mellin transform to obtain the asymptotic behavior of the sequence $D_n = \frac{ [z^n] D(z)} {C_n}$ where $$ D(z) = \frac 1{2z}\sum_{p \ge 1}C_p \left( ...
2
votes
0answers
39 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
33 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
39 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
26 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
34 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
33 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
28 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
28 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
36 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
52 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
37 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
56 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
64 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
73 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
53 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
86 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
55 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
69 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
69 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
412 views

Counting distinct restricted integer partitions of $n$ into exactly $k$ distinct parts less or equal then $M$

How can I find the number of partitions of $n$ into exactly $k$ distinct parts, where each part is at most $M$? The number of partitions $p_k(\leq M,n)$ of $n$ into at most $k$ parts, each of size at ...
2
votes
0answers
66 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
47 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
188 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
106 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
46 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 ...
2
votes
0answers
287 views

Prove that sum is finite with the help of generating function

Please help me to prove that the following sum is finite $$ \sum_{j=2l-2}^{\infty}j!\, a_j^{(l)}, $$ here the generating function of $\displaystyle{a_j^{(l)}}$ is ...