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.
6
votes
1answer
527 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
1answer
142 views
Is there any way to solve recurrence equations with variable coefficients?
So far I have done some problems that are best solved using generating functions. These mostly contain variable coefficients.
A simple one is $H(n) = (n+2)H(n-2)$. I have found solutions to these ...
1
vote
1answer
30 views
Solving recurrence equation using generating functions
$$a_{0} = 0, a_{1} = 1, a_{2} = 2, a_{3} = 6$$
$$a_{n} = a_{n+3} - a_{n+2}$$
$\sum = a_{n}x^{n}$
$A(x) = \frac{A(X) - x - 2x^{2}}{x^{3}} - \frac{A(x) - x}{x^{2}}$
$A(x) = \frac{x^{3} + x - 1}{-x^{2} ...
1
vote
1answer
31 views
Finding a probability distribution given the moment generating function
The $n$-th moment ($n \geq 1$) of a random variable $X$ is given by: $m_n = \frac{2^n}{n+1}$. Find the probability distribution of $X$.
Here's my attempt at a solution: I expand the moment generating ...
1
vote
1answer
32 views
Moment generating Function: sample mean
Let $\bar{X_{n}}$ be the sample mean of a random sample of size n from a distribution which has a pdf of:
f(x) = ${e^{-x}}$, for x> 0; 0, other wise.
a) show that the mgf of ...
1
vote
1answer
76 views
Exponential generating function for permutations with descent set whose least element is even
Let $E(n)$ be the number of permutations $w\in S_n$ such that the least element of the set $Des(w)\cup \{n\}$ is even, where $Des(w)$ is the descent set of $w$. I need to find the exponential ...
1
vote
1answer
31 views
Generating function of a random variable
I've got the following problem:
Give the generating function of the random variable $X$ whose mass function is defined by:
$$f(m) = P(X=m) = (m+1) p^2 (1-p)^m,$$ where $m$ is a positive integer ...
1
vote
1answer
46 views
Is it possible to manipulate this series/generating function?
I have come across a generating function that is similar to another generating function.
First, some preliminaries. I call a closed form a function like $\frac{1}{1-x}$. In other words, a closed ...
5
votes
0answers
233 views
Construction of generating function from identity
I am trying to solve identity involving binomials and fibbonaci numbers by using generating functions:
$$\sum_{k=0}^n{n \choose k}{n+k\choose k}f_{k+1}=\sum_{k=0}^n{n \choose k}{n+k\choose ...
4
votes
0answers
66 views
Finding the number of 5-node labeled connected graphs via generating functions
Problem: Find the number of ways to connect a graph having 5 labeled nodes so that each node is reachable from every other node.
I have solved this problem using principle of inclusion and exclusion ...
4
votes
0answers
69 views
Number of Permutations with $k$-inversions and with a single clamped value
Let $S_n$ be the symmetric group. Recall that the number of inversions of a permutation $\sigma\in S_n$ is the number of ordered pairs $i<j$ with $\sigma(i)>\sigma(j)$. Now, call the number of ...
4
votes
0answers
119 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
133 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}$.
...
2
votes
0answers
31 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$ ...
2
votes
0answers
32 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 ...
2
votes
0answers
18 views
Bivariate generating functions and diagonal like recurrences
I'm trying to solve recurrences of the type
$$a(n,m) = \sum_{k=0}^{m} a(n-k,k), \qquad a(n,0)= a(0,m)=1 \qquad (A_0)$$
with the help of generating functions, but I get stuck quite early on.
If I ...
2
votes
0answers
47 views
Generating function for the number of choices $I,J\!\subseteq[n]$ such that $\max\,[n]\!\setminus\!(I\!\cup\!J) < \max I\!\cap\!J$
Suppose that each pair $I,J\!\subseteq[n]=\{1,\ldots,n\}$ for which
$$\max\,([n]\!\setminus\!(I\!\cup\!J)) < \max (I\!\cap\!J) \tag{1}$$ contributes $t^{|I|+|J|}$ to a generating function, and ...
2
votes
0answers
266 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
44 views
Understand variant kinds of generating functions?
I found there are various kinds of generating functions in Wikipedia. I would like to understand why (the purpose)and how these concepts were created.
For the "how" part, given a sequence $(a_n)$,
...
2
votes
0answers
118 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
106 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
81 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
186 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
98 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
48 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
107 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
176 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
53 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 &= ...
1
vote
0answers
42 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
24 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
56 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
35 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 ...
1
vote
0answers
26 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
85 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
453 views
Finding the Moment Generating function of a Binomial Distribution
Suppose $X$ has a $Binomial(n,p)$ distribution. Then its moment generating function is
$$
M(t) = \sum_{x=0}^x {n \choose x}p^x(1-p)^{n-x} \\
=\sum_{x=0}^{n} {n \choose x}(pe^t)^x(1-p)^{n-x}\\
...
1
vote
0answers
233 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
103 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, ...
0
votes
0answers
27 views
continued fraction
$[a_0,a_1,a_2,\cdots,a_n]:=1/(a_0 + 1/(a_1 + 1/(a_2 + \cdots + 1/(a_n)\cdots )))$
I am so curious that what is the shape of $ f_n(x) $ such that
$$ \sum_{n \geq 0} f_n(x) y^n = [-y,1] +[-y,y,1]x + ...
0
votes
0answers
20 views
How to find the generating function of the system of equations?
Let $B(z)=\sum_{i=0}^\infty b_iz^i$,$A(z)=\sum_{i=0}^\infty a_iz^i$, $C(z)=\sum_{i=0}^\infty c_iz^i$, $D(z)=\sum_{i=0}^\infty d_iz^i$, how to find $D(z)$ from the relations
$$\begin{align} ...
0
votes
0answers
32 views
Use of Generating function
Given an $n$-element array $A[1\ldots n]$, let $T$ be the number of $(i,j)$ such that $A[i]>A[j]$. Use the generating function to compute the average of $T$.
Someone please help me. Thanks.
0
votes
0answers
26 views
Number Theory----Show using generating functions that $P_{d,o}(n) = o(P(n))$ (or $PE(n)\sim PO(n)$)
Show using generating functions that $P_{d,o}(n) = o(P(n))$ (or $PE(n)\sim PO(n)$) by obtaining an upper bound for $P_{d,o}(n)$ of the form $exp(k+\operatorname{abslong})n$, where $k < ...
0
votes
0answers
27 views
Generating matrix for a normal distribution?
Could anyone tell me if there is some such thing as a Generating Matrix of a gaussian distribution ?
I mean, some matrix $G$ such that for any column vector $v = \begin{pmatrix}v_{1} & \dots ...
0
votes
0answers
34 views
is it right to subs m=-m into ordinary generating function to be z-transform?
i success convert exponential generating function into ordinary generating function
ordinary generating function = summation(p(x)*z^(-m),m=0..infinity) (Maple code)
substitute m=-m into this ...
0
votes
0answers
26 views
Where do Laguerre network derived from?
I know generating function of Laguerre and its pdf.
I would like to know whether others can derive to this network.
How to derive the laguerre network?
0
votes
0answers
189 views
Solving a recurrence relation with generating functions
I'm having trouble midway with solving this recurrence relation using generating functions:
$a_{k+2} - a_{k + 1} + 2a_k = 4^x$, with initial conditions $a_0=2, a_1=1$.
I'm not sure if this is ...
0
votes
0answers
94 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 ...
0
votes
0answers
35 views
The number of linear extensions of crown poset with $2n$ vertices
I'd like to get the number of linear extensions of crown poset with $2n$ vertices.
I know that the number of linear extensions of wall poset is given by Euler number, whose exponential generating ...
0
votes
0answers
187 views
What are the mathematical and “real world” applications of “quadratic maps”, a type of dynamical system?
If we suppose that we can get a generating function for any "quadratic map (as in dynamical systems)", what are the mathematical applications? Also, what are the "real world" applications of this? ...
0
votes
0answers
73 views
Is there any way to create (a closed form for) this power series/generating function?
There is a fairly simple pattern to it.
$$1 y + $$
$$(1 + 1x)y^2+ $$
$$(1+1x+1x^2 + 1x^3)y^3 + $$
$$(1+1x+\dots+1x^7)y^4 + $$
$$(1+1x+\dots+1x^{15})y^5 + $$
$$\dots$$
Does anyone know of a way ...
0
votes
0answers
129 views
Where can I find more information on the Hadamard Product (of Generating Functions)?
I've been messing around with generating functions, power series, and related series, and I've come across a simple method of using two "roots of unity filters" to calculate the Hadamard product. A ...
