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

4
votes
1answer
85 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
21 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
50 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
58 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
64 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
33 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
37 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
66 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
78 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
27 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
122 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
53 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
107 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
39 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
81 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
35 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
16 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
61 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
124 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
64 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
193 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
48 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
55 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
40 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 ...
4
votes
2answers
164 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
33 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
39 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
159 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
56 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
162 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 ...
3
votes
1answer
58 views

Are there further transformation principles similar to the Inclusion-Exclusion Principle (IEP)?

This question is motivated by the elaboration of the question Combinatorial Proof of Inclusion-Exclusion Principle (IEP). Let's consider the following two aspects: 1.) IEP transforms at least ...
1
vote
1answer
31 views

Expressing the generating function defined by $b_n = \sum_{k=0}^{n} 3^k\cdot a_k$

The title is probably somewhat unclear, sorry if it is.. Let $F$ be the generating function of the sequence $(a_n)_{n=0}^{\infty}$ Use $F$ to express the generating function for ...
1
vote
1answer
66 views

Probability of getting SUCCESS AND FAILURE at number n-1 and n trial

In a sequence of Bernoulli trials let $u_n$ be the probability that the combination SF occurs for the first time at the trials number n-1 and n. To find the generating function I wrote the following ...
0
votes
0answers
31 views

Finding a generating function to solve a linear equation

I need to find a generating function to solve a linear equation. This is the linear equation: $$X_1+X_2+X_3+X_4+X_5 = 3n+1$$ All numbers are natural numbers which can be divided by 3 with no remainder ...
0
votes
0answers
36 views

Are generating functions ever analytic for logarithmic series?

Given a series $s_n = \ln(n) f(n)$ where $f(\cdot)$ is an elementary analytic function which does not involve the logarithm. More precisely $f$ can have simple poles but no branch cuts or essential ...
2
votes
1answer
26 views

Generating function - zeros when $n\in \mathbb{N}_{odd}$

It is given that $a_n$ is generated by the following function: $${1+6x} \over {(1+5x)(1-x)}$$ What is the generating function of: $$\left\{ {\matrix{ {{a_n},\mathbb{N}_{even}} \cr ...
0
votes
0answers
29 views

Extracting a Singularity - Generating Functions and Hankel Integration

I have a general question regarding the process of singularity analysis of generating functions. The aim of singularity analysis is to find a general correspondence between a function's behavior close ...
0
votes
0answers
32 views

Generating function counting quaternay sequence.

I have the following problems: $1.$ Calculate the number of the n-digits Quaternary sequence containing even $"2"$ and $"1"$ and at least one $"3"$. (When a sequence is made by the digits $1,2,3,4$) ...
1
vote
1answer
31 views

Proving that a moment generating function converges pointwise

I have found a moment generating function $M_n$ given by $\cfrac{(1-e^t)e^{\frac tn}}{n(1-e^{\frac tn})}$ if $t\ne 0$ and 1 if $t =0$ How do I prove that $M_n$ converges point-wise to the moment ...
0
votes
2answers
45 views

Generating function(really simple????)

With $X_n$ as a discrete random variable that takes the values $1,2,\dots,n$ with equal probability $\frac1n$. I want to: Evaluate the probability generating function of $X_n$!!! $G_{X_n}= ...
1
vote
1answer
30 views

How is this step completed?

User Did, did this step in his answer to my previous question: $$\sum_{k=0}^n{n\choose k}(zp)^kq^{n-k}=(q+pz)^n.$$ How is it done? Is it simply an identity, or something more?
1
vote
1answer
23 views

Generating functions for $n*2^n$ & the seq a0+a1+a2+…

1) What is the generating function of $a_n = n2^n, n\geq0$? My answer: $f(x) = \sum a_nx^n = \sum n2^nx^n = \sum n(2x)^n$, but I have no idea where to go from here. 2) Let the sequence $s_n = a_0 + ...