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

1
vote
0answers
12 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 ...
0
votes
0answers
9 views

Lower bound for a relative of the central binomial coeff

The central binomial coefficients $\binom{2m}{m}$ have g.f. $\frac{1}{\sqrt{1-4z}}$ and lower bound $\frac{4^m}{\sqrt{4m}} \le \binom{2m}{m}$. I'm interested in a related integer series $$T(2m, m) = ...
1
vote
0answers
27 views

Count the number of ways n different-sided dice can add up to a given number

I am trying to find a way to count the number of ways n different-sided dice can add up to a given number. For example, 2 dice, 4- and 6-sided, can add up to 8 in 3 different ways: ...
2
votes
1answer
38 views

Simplifying a generating function in two variables with two binomial coefficients

I'm trying to to make the below expression simpler, and it would be great if it could be expressed as something like $(x+y)^k$. $$ \sum_{i=0}^k\binom{n+1}i\binom{m+1}{k-i}x^iy^{k-i} $$ The number ...
2
votes
1answer
84 views

Why does convolution not maintain asymptotic equality of coefficients?

Assume I have four (generating) functions $f$, $f'$, $g$ and $g'$. If that is interesting, we can assume that they all share the same radius of convergence $\rho > 0$. In addition, we know that ...
4
votes
2answers
104 views

Difficult generating function

Define a beautiful number to be an integer of the form $a^n$, where $a\in\{3,4,5,6\}$ and $n$ is a positive integer. Prove that each integer greater than $2$ can be expressed as the sum of pairwise ...
4
votes
1answer
37 views

Generating functions and closed form solution for fibonacci sequence

Doing some extra practice problems and am having a hard time with this concept. Thanks!
3
votes
1answer
48 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
1
vote
2answers
48 views

Find a closed form for the generating function for this sequence

The sequence: $0, 0, 0, 1, 1, 1, 1, 1, 1, \ldots$ The book gives the answer of $\frac{x^3}{1-x}$ but I'm not sure how to get this answer. I understand the generating function of this sequence will be ...
4
votes
2answers
84 views

Is there a nice function representation of $\sum_{n=1}^\infty \zeta(2n+1)x^{2n+1}$

$$\sum_{n=1}^\infty \zeta(2n)x^{2n} = -\frac{\pi x}{2}\cot(\pi x) $$ Does $$\sum_{n=1}^\infty \zeta(2n+1)x^{2n+1}$$ have a nice function representation as well? From its graph, it looks like a ...
0
votes
0answers
47 views

generating function combinatorics solution

I am studying generating functions in combinatorics, and came across a problem that has already been posted here: Generating function and combinatorics =x^10(1-x^6)^10 * (1+x+x^2....)^10 I ...
3
votes
1answer
182 views

How to solve this recurrence Relation - Varying Coefficient

Sir,I have two questions related to this recurrence relation. It has been messing with me for long. Because of this I couldn't proceed my work for some time .This contains a polynomial term n+2 in ...
4
votes
1answer
92 views

Going from closed form to recurrence relation

If I had a closed form for a sequence that I suspect to represents a recurrence relation how would I determine the recurrence relation? In particular, I have the sequence $$a_n = ...
0
votes
1answer
26 views

Probability generating function for negative values of random variables?

What if we have negative integral values for a random variable?Then is it possible to write a probability generating function for it? All definitions I have seen so far is for non negative integer ...
0
votes
1answer
58 views

Partitions applications in physics

Is there any direct application of all developments related to partitions? I am specially interested in physics but cryptography or other mostly theoretical areas would also be a good answer. By ...
2
votes
2answers
65 views

Finding a Closed Form for a Recurrence Relation

I know that a general technique for finding a closed formula for a recurrence relation would be to set them as coefficients of a power series (i.e. a generating function). Then use properties of ...
4
votes
1answer
70 views

Closed form of $\sum_{k=0}^nk\binom{k}{3}\binom{2n}{k}$

Recently, I came across the following exercise on the course of discrete math Find a closed form for $\sum_{k=0}^nk\binom{k}{3}\binom{2n}{k}$ So I tried some of the usual techniques: Let ...
1
vote
1answer
46 views

Determine $x$ coefficient of $f(x)=( (x+1/x)^a+(x-1/x)^a)^b$

I'm trying to find the coefficients of $x$ from $f(x)=( (x+1/x)^a+(x-1/x)^a)^b$ where $a,b\in\mathbb{Z}^+$. I tried reading through some of Wilf's Generatingfunctionology, but I think I am still ...
1
vote
2answers
38 views

Generating function satisfying a second degree equation

I got this problem in an exercise list: Let $G(x)$ be the generating function of the numeric sequence $(C_n; n \geq 0)$ satisfying the recurrence equation: $$C_n = \sum_{k=0}^{n-1}C_kC_{n-k-1}, ...
2
votes
1answer
70 views

Quadradic recurrence relation

There is an method to solve recurrences of the form $a_{n+1} = (a_n + c)^2$? I am particularly interested when $c = 1$. I tried to use generating functions but I got stuck with. Let $G(x) = \sum_{k ...
4
votes
1answer
85 views

Generalization of Fibonacci using Generating Functions

I have been trying to work through the beginning of Generating Functionology. In the first chapter, the author mentions that it is possible to using generating functions to solve for a Fibonacci-like ...
3
votes
1answer
42 views

A bijection defined on the set of configuration of lamps

Consider $n$ lamps clockwise numbered from $1$ to $n$ on a circle. Let $\xi$ to be a configuration where $0 \le \ell \le n$ random lamps are turned on. A cool procedure consists in perform, ...
2
votes
1answer
30 views

Asymptotic approximation for the r-associated Stirling numbers of the second kind

It is well know that for fixed $k$ the asymptotic approximation for the Stirling numbers of the second kind is given by $\frac{k^n}{k!}$. Does such simple asymptotic expression also exist for the ...
6
votes
4answers
127 views

The number of permutations of $\{1,2,\ldots,n\}$ that have exactly one ascent (rise).

Sloane's OEIS A000295 counts the number of $n$-permutations with exactly one ascent. For example $a(3)=4$ because we have: $1\wedge32$, $21\wedge3$, $2\wedge31$, $31\wedge2$ where I have marked the ...
1
vote
1answer
29 views

Products of n exponential generating functions

So I am using exponential generating functions and have a question about taking the product of more than 2 exponential generating functions. I know that the product of 2 exponential generating ...
3
votes
2answers
46 views

Generating Function for the number of ways representing positive integer with odd numbers

I had an exam and this question struck me out of nowhere, making me sad :) Let $f(n)$ denote the number of possibilities representing $n$ using odd positive single-digit numbers $[1,3,...,9]$ For ...
2
votes
1answer
55 views

Generating function for picking j balls without replacement from an urn

In an urn, each balls is labeled with one of $\{0,1,2,...,k\}$. For each $i\in{0,1,2,...,k}$, there are exactly $n_i$ balls labeled $i$. Let $f(x)=\sum\limits_{i=0}^k n_ix^i$. Let ...
0
votes
2answers
109 views

Combinatorics: Binary Strings

Are the these 2 binary generation expressions equal? If so, how do I simplify my answer to match the solution's? Question: The set of binary strings where the length of each block of 0s is divisible ...
0
votes
1answer
27 views

Prove equilvalence of generating series with compositions.

weight function: w(c1, ..., ck) = c1 + ... + ck and w(ci) = ci, 1<=i<=k Could someone explain to me what the N notation stand for? My take would be that the left N notation represents a set ...
0
votes
1answer
40 views

How many ways you can make change for an amount N using A and B monets.

I encountered a quite interesting problem. The question is: How many ways you can make change for an amount N using monets of value A and B, knowing that GCD(A,B)=1. Any idea how to solve this? It ...
4
votes
4answers
82 views

Find a generating function for $\sum_{k=0}^{n} k^2$

Find a generating function for $\sum_{k=0}^{n} k^2$ I know my solution is wrong, but why? My solution: If $F(x)$ generates $\sum_{k=0}^{n} k^2$ then $F(x)(1-x)$ generates $k^2$. ...
1
vote
2answers
36 views

Probability Generating Functions with Three Dice

Three identical dice are thrown. The dice are fair, that is, for all three dice the probability of turning up face $j$ is $1/6$, $1 \le j \le 6$. Let $X_1,\ X_2,\ X_3$ be the independent random ...
0
votes
0answers
19 views

Generating Function that relates Bessel's first kind with $p=0$ and Legendre polynomial

Well the objective of the problem is to prove: $$e^{tx} \cdot J_0\left(t\sqrt{1-x^2}\right) = \sum_{n=0}^{\infty}\frac{P_n(x)}{n!}t^n ,$$ without using integral expressions as done here by Graham ...
4
votes
1answer
63 views

Extracting a coefficient from a generating function

Background: I am working on an exercise relating to Skolem $k-$subsets with index $k$ in Goulden and Jackson's Combinatorial Enumeration text and they broke it down to finding the coefficient of $x^n$ ...
2
votes
5answers
126 views

Find a closed form for $\sum_{k=0}^{n} k^3$ [duplicate]

Find a closed form for $\sum_{k=0}^{n} k^3$. I would appreciate ideas for approaching questions like this in general as well. Thanks.
1
vote
1answer
44 views

How to simplify $F(x)=\sum_{n}^{\infty}\sum_{k}^{\infty}{n-k-1\choose k}x^n$?

This generating function is equivalent to $$\sum_{n}^{\infty}F_n x^n=\dfrac{x}{1-x-x^2}$$ where $F_n$ is a fibonacci number. To show this, I need to simplify the above generating function with ...
2
votes
1answer
65 views

Generating functions over $\mathbb{Z}$

Let $(a_n)_{n \in \mathbb{Z}}$ be a sequence such that both limits $\lim_{n \to \infty} a_n$ and $\lim_{n \to -\infty} a_n$ exists. Consider recursive relation $$ 2b_n - \frac{1}{2}(b_{n-1} + b_{n+1}) ...
2
votes
1answer
44 views

Number of nodes with an even number of children in an ordered tree (AKA Plane Planted Tree)

I am looking for verification for my attempt at the solution. I have found that my answer disagrees with an answer I found here: Extract Coefficients From A Function Problem at hand: For a plane ...
1
vote
2answers
50 views

How to translate $\sum_n \frac{x^n}{a_n}$ into a generating function

Is there any way to translate $\sum_n \frac{x^n}{a_n}$ into a generating function of type $A(x)$ or into any combination involving $A(x)$? This question comes from a treatment I'm giving to equation ...
10
votes
1answer
203 views

Prove that $\exp(\log(\frac{1}{1-x})) = \frac{1}{1-x}$

I am trying to prove this directly by comparing the coefficients in the two series rather than using formal calculus. Here is what I have so far, but I think I made a mistake: \begin{align*} ...
2
votes
0answers
50 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 ...
0
votes
0answers
56 views

$\sum_{k=1}^{n}\dfrac{(-1)^{k+1}}{k}{n\choose k}=\sum_{k=1}^n\dfrac{1}{k}$

If $n$ is a positive integer, then the above identity holds. I tried to solve this question using generating function. $$A(x)=\sum_n\left(\sum_{k=1}^n\dfrac{1}{k}\right)x^n=-\dfrac{\log(1-x)}{1-x}$$ ...
2
votes
1answer
41 views

Number of ways to fill a bag of weight $N$ with fruits - Generating series question

How many ways are there to fill a bag (maximum of weight $N$) with watermelons, apples, and grapes, where the number of apples has to be at least the number of watermelons? The weights are given as ...
5
votes
3answers
194 views

Harmonic Numbers series I

Can it be shown that \begin{align} \sum_{n=1}^{\infty} \binom{2n}{n} \ \frac{H_{n+1}}{n+1} \ \left(\frac{3}{16}\right)^{n} = \frac{5}{3} + \frac{8}{3} \ \ln 2 - \frac{8}{3} \ \ln 3 \end{align} where ...
2
votes
1answer
35 views

does this sequence of functions converges uniformly to Dirichlet function?

Let $r_{1},r_{2},...$ a sequence that includes all rational numbers in $[0,1]$. Define $$f_n(x)=\begin{cases}1&\text{if }x=r_{1},r_{2},...r_{n}\\0&\text{otherwise}\end{cases}$$ this sequence ...
1
vote
2answers
42 views

Generating functions for sequences

I would like to know more about constructing generating functions for certain type of sequences defined differently over certain ranges of $n$, and would appreciate any references. For example, if ...
2
votes
1answer
163 views

Generating function for vertices distance from the root in a planar tree

I need you help to solve this problem: Consider a planar tree with $n$ non-root vertices. Give a generating function for vertices distance $d$ from the root. Proof that the total ...
1
vote
1answer
35 views

Generating function for this series

The question is: find the generating function for $(f_0,f_1,f_2,...)$ where $f_{n} = f_{n-1}+ 2f_{n-3}$ and $f_0 =0$ and $f_1 = f_2 = 1 $ I have solved this and reached G(x) = $(x-2)\over(2{x^3} + x ...
0
votes
1answer
58 views

Is there a closed form expansion for $(2^k + 1)^{k+1}$?

Is there a way to express $(2^k + 1)^{k+1}$ expanded... The first few values for $k+1=2,3,4,5,6,\ldots$ are: $ k+1=2: 1+2^{2 k}+2^{1+k} $ $ k+1=3: 1+3\ 2^k+3\ 2^{2 k}+2^{3 k} $ $ k+1=4: 1+2^{4 ...
1
vote
2answers
165 views

Generating function for planted planar trees

I need your help to solve this problem : Give a generating function for planted planar trees with all degrees odd. Show that the number of such trees with $2k+1$ non-root vertices is ...