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
272 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 ...
6
votes
0answers
99 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
93 views

Sum-Product Generating Functions

Let $A_n$ be a family of sequences $\{a_i\}_{i=1}^n$ of length $n$. I'll refer to sequence elements of $A_n$ as $a$. Then define $$G(z):=\sum_{a\in A_n}\prod_{i=1}^n(z+a_i).$$ Here's one possible ...
5
votes
0answers
106 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
115 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
71 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
81 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
200 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
182 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
44 views

Geometric Generating Functions

Let $p(t) = t^3 + Ft^2 + Et + V$, where $F,E,V$ are the number of faces, edges, and vertices of a cube, respectively. Factor $p(t)$ and explain your results in terms of generating functions. A hint ...
3
votes
0answers
51 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 ...
3
votes
0answers
40 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
65 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
110 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
118 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
402 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
69 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} ...
2
votes
0answers
58 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
43 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
57 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
60 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
60 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
43 views

Number of nodes with even offspring

I've been working on a combinatorics assignment, and while the last few questions had clever solutions which didn't involve functional equations and the use LIFT, I fear I'm at my end. Given a ...
2
votes
0answers
45 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
44 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
285 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 ...
2
votes
0answers
178 views

What is the closed form of generating function of a power law?

I want to know if there is a "closed form" of the following generating function, $G_n(x) = \sum_{n=0}^{\infty} P_n x^n$ where, $P_n = C(n_0 + n)^{-\gamma}$ where $C$ is a normalization constant, ...
2
votes
0answers
128 views

Help on Generating function - Analysis of Median of three - Quick Select

I am trying to find out the average case analysis of median of 3 - quick select. The recurrence relation is \begin{equation} C_{n,j} = 1 + \sum_{k=1}^{j-1}\pi_{n,k}C_{n-k,j-k} + \sum_{k=j+1}^{n} ...
2
votes
0answers
90 views

Proving generating functions equality

What do you use to prove the following equality (and possibly more general ones of the kind)? \begin{align*}\sum_{r,s,t} \frac{q^{r^2+rs+s^2+st+t^2}}{(q)_r (q)_s (q)_t} z_1^{r+s} z_2^{s+t} = ...
2
votes
0answers
214 views

Generating Function of Integer Partition Such that at Least One Part is Even

I've been having a few issues coming up with a generating function for an integer partition such that at least one part is even. What I have got so far is: The generating function with no ...
2
votes
0answers
52 views

Which type of counting problems are solved by hypergeometric function as generating function?

Which type of counting problems are solved by hypergeometric function as generating function? would you mind giving some examples such as relating counting with hypergeometric function as generating ...
2
votes
0answers
134 views

Asymptotics of shifted Catalan numbers

I am trying to understand a lemma from a paper (most of the proof was omitted), and I've got it melted down to the following: Let $B_n$ denote the $n$-th Catalan Number. In a sufficiently small ...
2
votes
0answers
269 views

Deep understanding on exponential generating function

In spite of having done some exercises, I still find it harder to understand exponential generating function deeply than ordinary generating function. Could someone explain it "deeply"? Or are there ...
1
vote
0answers
47 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 ...
1
vote
0answers
39 views

Extracting coefficients from a transformed generating function

Let $G(z)=\sum_{k\geq 0} a_kz^k$ be a generating function such that $z^aG(1-z)=P(z)$, where $P(z)$ is a polynomial and $a$ is a positive integer. I'm interested in $P(z)[z^n]$, the coefficient in ...
1
vote
0answers
28 views

Deriving recurrence relations, very stuck!

Going through past papers for my exams and cannot figure this one out, does anyone know how to do these? The Bessel functions of integer order, Jn(x), are described by a generating function of the ...
1
vote
0answers
21 views

Dirichlet series expansion?

When an analytic function $f(x)$ is given, we can easily obtain the coefficient of $x^n$ in a power series expansion of it. I'd like to know if there exists something similar for Dirichlet series. Is ...
1
vote
0answers
52 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: ...
1
vote
0answers
257 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 ...
1
vote
0answers
62 views

Finding Generating Series for Number of “words” in an Alphabet

Question: Find the generating series with the property that for each non-negative integer $n$, the coefficient of $x^n$ is the number of "words" of length $n$ coming from the alphabet $\{{a,b,c}\}$. ...
1
vote
0answers
75 views

Whats wrong in following attempt to write Hermite polynomials in terms of hypergeometric function?

Let's have Hermite polynomials: $$ e^{2tx - t^{2}} = \sum_{n = 0}^{\infty}H_{n}(x)\frac{t^{n}}{n!}. \qquad (1) $$ I need to write it in terms of confluent hypergeometric Kummer function for index $n = ...
1
vote
0answers
42 views

Text Generating Functions: Do they exist?

This is a little far out question, but just curious: is it even possible to have a non-high-degree-polynomial function (as in polynomial regression function) that could generate a sentence of say, 10 ...
1
vote
0answers
43 views

Need Help with Interpreting this Answer

Generating Functions help I'm not quite sure how to go from the reciprocal function to the coefficient of $x^{100}$; could anyone help me out? I have an exam on this in 2 days, and I'm still ...
1
vote
0answers
45 views

Closed form of an inhomogeneous non-constant recurrence relation

I try to find a closed form for the $f_k$'s (at least for $f_1$) satisfying the following recurrence relation for any fixed $n>0$: $f_0 = 0$, $f_n = 0$, and $f_k = \frac{n}{2k}(f_{k-1} + f_{k+1} + ...
1
vote
0answers
59 views

Solving a recurrence involving binomials.

Does anybody know how to solve the following recurrence? Maybe with generating functions? Any hint? $t(n) = 1 + \frac{1}{2^{n-1}} \sum_{i=0}^{n-1} {n \choose i} t(i)$
1
vote
0answers
117 views

Generating Function for edge-rooted labelled trees

Let $T_v(z)$ be the (exponential) generating function for vertex-rooted (non-plane) trees. Im trying to construct the generating function $T_e(z)$ for edge-rooted trees from this. I know the ...
1
vote
0answers
78 views

Is there a generic approach to Generating Function of periodic sequences?

Recently I read on wiki (see here): "Any periodic sequence can be constructed by element-wise addition, subtraction, multiplication and division of periodic sequences consisting of zeros and ones." ...
1
vote
0answers
158 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 ...
1
vote
0answers
36 views

Variance & Expectation

$X$ is a random variable with values in the set of natural numbers and the Generating function G. In Addition: $t(n) = P(X>n)$. Let $F$ be the generating function of the sequence $\{t(n): n \ge ...
1
vote
0answers
88 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 ...