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
265 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
96 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
105 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
113 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
61 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
109 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
113 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
397 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
42 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
42 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
44 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
176 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
211 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
133 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
267 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
27 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
51 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
238 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
59 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
72 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
41 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
43 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
116 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
77 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
153 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 ...
1
vote
0answers
50 views

Simon Newcomb's problem

I am looking for an answer to the following problem. Let $S$ be the multiset $\{1^{d_1},2^{d_2},\dots,m^{d_m}$ $A_{S,k}$ is the number of permutations of $S$ with $k-1$ descents and no descent at the ...
1
vote
0answers
119 views

Question about ratios and combinatorics

In this question that I posted yesterday (11/15): I am solving a programming puzzle that consists of finding all the possible ways to build a brick wall of $48$" $\times$ $10$" (width $\times$ height ...
1
vote
0answers
172 views

To obtain the closed-form expression of CDF and PDF from the recurrence relation

Now I have a question, in which I need to find the probability mass function and the cumulative distribution function. But now I only have the recurrence relation. Here is the details: Assume ...
1
vote
0answers
250 views

binomial expansion of $(1+x)^n \left(\dfrac{1}{x} -1\right)^m$

Let $n$ and $m$ be positive integers with $n \gt m$. Can you show that the constant term of $${(1+x)^n}\left(\frac{1}{x} - 1\right)^m$$ is not equal to zero?
1
vote
0answers
106 views

Find $G(n)$ with $n \geq 1$

Let $G(1) = 0, \ G(2) = 1$, $G(2n+1) = 2 + G(n) + G(n+1)$ and $G(2n) = 1 + G(n), \ \ n \geq 1$ Find $G(n) $ P.S: This is little problem in my problem. I tried to solve by using generating function, ...