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.
3
votes
1answer
37 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 ...
0
votes
1answer
53 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 ...
0
votes
1answer
24 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 ...
4
votes
1answer
87 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 = ...
1
vote
2answers
84 views
In how many ways can you divide bonuses between employees?
How many ways are there to divide 33 000 USD between 22 employees of a company (including 1 president, 1 vice-chairman and 20 normal employees), if a normal employee can get 1000 or 1500 USD, whereas ...
3
votes
2answers
608 views
Keep getting generating function wrong (making change for a dollar) [duplicate]
Possible Duplicate:
Making Change for a Dollar (and other number partitioning problems)
I am working on the classic coin problem where I would like to calculate the number of ways to make ...
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
65 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 ...
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 ...
2
votes
1answer
28 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 ...
12
votes
6answers
827 views
Proving a binomial sum identity
Mathematica tells me that
$$\sum _{k=0}^n { n \choose k} \frac{(-1)^k}{2k+1} = \frac{(2n)!!}{(2n+1)!!}.$$
Although I have not been able to come up with a proof.
Proofs, hints, or references are all ...
1
vote
1answer
36 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
2answers
95 views
Is there a recursive formula for Euler's Totient function
I have been looking for a recursive formula for Euler's totient function or Möbius' mu function to use these relations and try to create a generating function for these arithmetic functions.
2
votes
1answer
67 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 ...
2
votes
2answers
62 views
Generating function of $a_n = \sum_{k = 0}^{\lfloor\frac{n}{2}\rfloor}{n \choose 2k}\frac{(2k)!}{k!2^k}$ is $e^{x+x^2/2}$?
I need to prove that the generating function of $a_n = \sum\limits_{k = 0}^{\lfloor\frac{n}{2}\rfloor}{n \choose 2k}\dfrac{(2k)!}{k!2^k}$ is $e^{x+x^2/2}$.
I tried it like this. I know that ...
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
3answers
103 views
Number of ways, powers of $2$ sum up specific values
Given the set $B=\{2^0,2^1, 2^2,...2^{n-1} \}$. Now you pick $n$ elements of $B$ with repetitions and sum the picked elements, e.g.
picking every element once this sums up to ...
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 ...
10
votes
7answers
4k views
Making Change for a Dollar (and other number partitioning problems)
I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the one quoted ...
7
votes
1answer
608 views
Equation about generating functions and subfactorial
Suppose $G_n(w)$ is a formal power series (really a probability generating function, see the following explanation) of variable $w$, try to solve out $G_n(w)$ for all $n\ge0$ from the ...
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 ...
0
votes
3answers
122 views
exponential generating functions containing an even/odd number of cycles
How to derive the exponential generating functions that having an even/odd number of cycles?
And how to define a bijection between them? Is there any example of this? Thanks in advance!
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 ...
6
votes
1answer
327 views
Generalizing Ramanujan's sum of cubes identity?
Ramanujan's sum of cubes identity is defined by the generating functions,
$$\begin{aligned}
\sum_{n=0}^\infty a_n x^n &= \frac{1+53x+9x^2}{R_1}\\
\sum_{n=0}^\infty b_n x^n &= ...
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
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 ...
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.
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
3answers
1k views
Number of cycles of all even permutations of $[n]$ and number of cycles of all odd permutations differ by $(-1)^n (n-2)!$
I'm trying to solve task 44 of the first chapter of Stanleys Enumerative Combinatorics (found here).
Show that the total number of cycles of all even permutations of $[n]$ and the
total number ...
2
votes
2answers
109 views
On the symmetric labelled structure of 2-regular graphs
Let $G$ be the symmetric labelled structure of 2-regular graphs (indexed by the number of vertices) then $G(x)=\frac{e^{-\frac{x}{2}-\frac{x^2}{4}}}{\sqrt{1-x}}$. Could you help me to solve this ...
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$.
...
26
votes
2answers
3k views
Why do engineers use the Z-transform and mathematicians use generating functions?
For a (complex valued) sequence $(a_n)_{n\in\mathbb{N}}$ there is the associated generating function
$$
f(z) = \sum_{n=0}^\infty a_nz^n$$
and the $z$-Transform
$$
Z(a)(z) = \sum_{n=0}^\infty ...
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
17 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$ ...
-1
votes
1answer
60 views
Fermat Last theorem on Poly-Euler numbers
The poly-Euler numbers, denoted as $E_{n}^{(k)}$, are defined by the following generating functions
:$${2\operatorname{Li}_k(1-e^{-x}) \over 1+e^{-x}}=\sum_{n=0}^\infty E_n^{(k)}{x^n\over n!}$$
The ...
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*}
...
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 ...
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
...
2
votes
2answers
64 views
Finding the Generating Function for $\sum_{n_1 +n_2 + \ldots + n_k = n} n_1 n_2 \cdot \ldots \cdot n_k$
I'm studying problem 2.6 (p. 65) in Herbert Wilf's generatingfunctionology (released by the author for free online). This problem actually has a solution already written in the back of the book (p. ...
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 ...
2
votes
1answer
116 views
Weak convergence and generating function
Let $X_n$ be a sequence of $\mathbb N_0$ valued random variables and denote by $g_{X_n}$ their generating function, i.e. $g_{X_n}(s) = \mathbb E[s^{X_n}] = \sum_{k=0}^{\infty} s^k \mathbb P(X_n=k)$.
...
4
votes
2answers
166 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
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 ...
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}$$
...
