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

-2
votes
2answers
32 views

want to check answer given in my book is correct or not [duplicate]

The problem is to find coefficient of $x^n$ using binomial theorem for rational index in the expansion of $$\frac{1}{1-x+x^2-x^3}.$$ In my book the answer is given as $$\frac14+\frac{n+1}{2}+\frac{(-...
3
votes
1answer
40 views

How to Multiply Two Infinite Series Correctly?

From my readings on the wikipedia, I was able to gather that the product of two infinite series $\sum_{i=0}^{\infty} a_{i}$ and $\sum_{j=0}^{\infty} b_{j} $ is outlined by the Cauchy Product. The ...
1
vote
2answers
59 views

Generating function for $\sum_{n=0}^{\infty} n^{p} x^n$

I am trying to derive the generating function for $H(x,p) = \sum_{n=0}^{\infty} n^p x^n$ I am trying to solve it with the following logic: (Edited now, trying a new framing) Base case: $$H(x,0) = \...
6
votes
2answers
62 views

Deriving sum of powers formula using generating functions

Just for fun I wanted to try to derive a formula for the sum of $p$-powers using generating functions, but without using any literature or websites for help. However I do need a small push or hint. ...
0
votes
0answers
27 views

Does the pgf uniquely determine the distribution? [on hold]

I know that the characteristic function of a random variable uniquely determines the distribution, but I'm just curious whether the probability generating function does so too(assuming that it exists)....
0
votes
0answers
30 views

Transforming generating functions into algorithms that generate combinatorial objects

I've stumbled upon this paper where they write about random sampling of combinatorial objects. For sampling to be proper one has to know some core numbers (probabilities). However, I'm not interested ...
1
vote
1answer
47 views

Probability generating function of some “random walk”

Let $S_n=\sum^n_{r=0}X_r$ be a left-continuous random walk on the integers with a retaining barrier at zero. More specifically, we assume that the $X_r$ are identically distributed integer-valued ...
1
vote
0answers
31 views

Question About Cauchy Product;

Is there a formula to multiply many series (More than two) using the Cauchy product? If there isn't, please tell me how I can write this formula $ \left( \frac{1}{a-e^x} \right) ^{n+1}$as the ...
0
votes
1answer
24 views

Is $G(\alpha s)/G(\alpha)$ a probability generating function

Suppose $G$ is a probability generating function. Let $\alpha\in [0,1]$, then is $\frac{G(\alpha s)}{G(\alpha)}$ necessarily a probability generating function?
0
votes
0answers
26 views

Deriving the sequence if the generating function is irreducible?

I am trying to better understand generating functions and how they can be derived / manipulated / etc. Right now I am operating on this identity, slightly modified from the answer here: For a ...
2
votes
1answer
57 views

How do I get a sequence from a generating function?

For example if I have the generating function $\frac{1}{1-2x}$ then it corresponds to the sequence $1 + 2x + 4x^2 + 8x^3 +~...$. I know how to start from the sequence and get the generating function, ...
0
votes
2answers
26 views

Finding the generating function of a recurrence relation in dependence of a variable

Given this inhomogeneous linear recurrence relation of 2nd order : $F_n = F_{n-2} + a$ for $n \geq 2$ with $F_1 = 1$ and $F_0 = 0$ How do I find the generating function of this recurrence ...
6
votes
0answers
136 views

Generalized Harmonic Number Summation $ \sum_{n=1}^{\infty} \frac{(H_{n}^{(2)})^2}{2^n}$

Prove That $$ \sum_{n=1}^{\infty} \dfrac{(H_{n}^{(2)})^2}{2^n} = \tfrac{1}{360}\pi^4 - \tfrac16\pi^2\ln^22 + \tfrac16\ln^42 + 2\mathrm{Li}_4(\tfrac12) + \zeta(3)\ln2 $$ Notation : $ \...
1
vote
1answer
44 views

What is the coefficient of the following

I got the question on a midterm and got it wrong. I'd like to know where I went wrong. We were supposed to find the coefficient of $x^{15}$ of$$(1-x^2)^{-10}(1-2x^9)^{-1}$$ My answer The only way to ...
0
votes
1answer
40 views

Elementary proof of MacMahon's generating function for plane partitions

Recall Macmahon's elegant and beautiful generating function for plane partitions $$ \sum_{n=0}^{\infty} pp(n) q^n = \frac{1}{(1 - q)^1(1 - q^2)^2(1-q^3)^3\cdots}= \prod_{j=1}^{\infty}\frac{1}{(1-q^j)^...
0
votes
1answer
24 views

Random walk - probability of first pass through zero.

In the proof that symmetric random walks end up regressing to the origin with probability $1$, I have found this didactic post on-line, where the power series of the probability mass function of the ...
1
vote
1answer
63 views

A Closed Form Lower Bound Approximating $p_{n,m,s} = n![z^n]\left(\sum_{k=0}^s\frac{z^k}{k!}\right)^m$

Here, I found $p_{n,m,s} = n![z^n]\left(\sum_{k=0}^s\frac{z^k}{k!}\right)^m = \sum\limits_{\substack{k_1 + \cdots + k_m=n\\0\leq k_i \leq s}} \frac{n!}{k_1!\cdots k_m!}$ as the number of ways to ...
0
votes
1answer
23 views

Solving Recurrence Relations with generating functions when the variable is in the function.

I'm studying for a midterm and couldn't figure out these three recurrences that I came across: $i_{n+1}=2ni_n+2i_n+2$ with initial condition $i_0=1$ $j_{n+1}=3j_n+1$ with initial condition $j_1=1$ $...
2
votes
0answers
65 views

Identity involving the Catalan numbers and binomial coefficients

Let $C_k := \frac{1}{k + 1} \binom{2k}{k}$ be the $k$-th Catalan number and let $K$ be a positive integer. I am looking for an identity or simplification of \begin{equation} \sum_{k = 0}^K C_k \...
0
votes
1answer
16 views

Generating functions in probability first pass through origin of a symmetric random walk

The proof of the eventual return to zero of a symmetric random walk was given here, but I am not comfortable with generating functions. In this book chapter an intermediate result depends on ...
0
votes
1answer
50 views

What is the ordinary generating function of this series?

I need this as part of a bigger proof. Does \begin{align} G_1 &\longleftrightarrow \Big\{\binom{n}{k}\Big\}_{2k=0}^r \notag \\ \implies G_1(z) &= (1 + z^2)^r \end{align} Help me prove this ...
1
vote
1answer
56 views

Finding the coefficient of $x^{50}$ in $\frac{(x-3)}{(x^2-3x+2)}$

First, the given answer is: $$-2 + (\frac{1}{2})^{51}$$ I have tried solving the problem as such: $$[x^{50}]\frac{(x-3)}{(x^2-3x+2)} = [x^{50}]\frac{2}{x-1} + [x^{50}]\frac{-1}{x-2}$$ $$ = 2[x^{50}]...
0
votes
1answer
39 views

Application of complex analysis and contour integral in generating functions

Normally generating functions are tools of discrete mathematics and integrals deal with continuous structures. A book offered the following formula without much explanation and I'm not able to ...
3
votes
2answers
104 views

How many positive integers from set $\{1,2…,10^{30}\}$ can't be represented as 2nd, 3rd, or 5th power of some positive integer?

An interesting problem I ran across. My guess is that it can be solved somehow using inclusion-exclusion principle. It would be a fun thing to learn how to do this, so I could use that knowledge in ...
7
votes
3answers
349 views

How can I rewrite recursive function as single formula?

There is following recursive function $$ \begin{equation} a_n= \begin{cases} -1, & \text{if}\ n = 0 \\ 1, & \text{if}\ n = 1\\ 10a_{n-1}-21a_{n-2}, & \text{if}\ ...
0
votes
0answers
23 views

Partition identity with generating functions

I'd like to show that: The number of partitions of $n$ such that parts appear 2,3 or 5 times is equal to the number of partitions of $n$ into parts congruent to $\pm 2$, $\pm 3$, $6$ mod $12$. The ...
0
votes
1answer
17 views

Help computing this product through the laguerre polynomial generating function

I don't understand generating functions very well and I was told in one of my questions that the coefficient of $t^N$ in the product between $$\frac{1}{(1-t)^2}\,\exp\left(-\frac{tx}{1-t}\right)$$ and ...
3
votes
2answers
43 views

Estimate growth of a recurrence convolution

Consider the following recurrence relation $$ a_{m+1} = (4 m + 1) \sum_{k=1}^m a_k a_{m-k+1}, \qquad a_1 = 1. $$ The first several values are $$ a_1 = 1,\; a_2 = 5,\; a_3 = 90, \; a_4 = 2665, \; a_5 = ...
0
votes
1answer
23 views

Can I express $\sum_{k,r} rV_rV_{k-1}x^k$ in terms of $u(x)\equiv \sum_kV_k x^k$?

I'm trying to solve a tough balls-in-bins problem by working with generating functions for the distributions of balls in bins at different times. So I have the probability that $k$ bins have some ...
1
vote
0answers
15 views

about minimal point in non- autonomous discrete system

Let $(X,d)$ be a compact metric space. In $(X,f)$, $x\in X$ is called minimal point if $N(x,U)=\{n|f^{n}(x)\in U\}$ is syndetic for every open set $U$ of $x$ i.e. there is $k\in N$ such that $\forall ...
1
vote
0answers
32 views

Moment Generating Function for $r$th central moment

When using moment generating functions, to find the $n$th raw moment ("$n$th moment about the origin"), you take the $n$th derivative of the MGF and evaluate at $t=0$. To find the $m$th central ...
1
vote
2answers
34 views

How do I compute the generating function for this number sequence?

I am trying to compute the generating function for the number sequence given by $a_n = (-1)^n$. I know that the solution is $A(x) = \frac{1}{1+x}$ but when I try to solve it using the procedure of ...
1
vote
2answers
51 views

Probability of N unrelated events, each with different probabilities, what is the chance X number of outcomes occur

Given the probability of N unrelated events, each with different probabilities, what is the chance X number of outcomes occur? Said specifically there are 8 unrelated contracts, what is the chance a ...
2
votes
3answers
55 views

Functions validity.

Why does writing a function differently make it valid for a originally invalid input? $e.g:$ $$f(x) = \frac{1} {(\frac1x+2)(\frac1x-3)} \implies x≠0$$ Which may alternatively be written as: $$f(...
0
votes
1answer
33 views

Solving this generating function to find the $n$th term in the sequence

I have been given the generating function $$f(x) = \frac{x^2+x+1}{1-x^7},$$ and I need to solve for a closed form of the $n$th term of the sequence g generated by this function. I have been trying to ...
0
votes
1answer
32 views

Finding the generating function to split $n$ into odd parts

I have been recently working with generating functions in my discrete mathematics course, and I was interested in one particular generating function. I want to find the generating function for the ...
1
vote
1answer
19 views

PGF of sum of $N$ random variables, where $N$ is a random variable itself.

Let's say $X_i$ (for $i = 1, 2, \ldots$) are independent r.v.'s that return $0$ or $1$, both with probability 0.5. Let's say $N$ is a geometric random variable with $P(N=n) = 0.5^n$ for $n=1, 2, \...
1
vote
3answers
65 views

What is the power series expansion at $x=0$ of the algebraic function defined by $(27x-4)y^3 + 3y + 1 = 0$?

Let $y$ denote the complex-valued algebraic function defined implicitly near $x=0$ by $(27x - 4)y^3 + 3y + 1=0$ and such that $y(0)=1$. What is the power series expansion of this function at $x=0$? ...
1
vote
0answers
31 views

Relation of relative numbers of (restricted) ways to distribute identical / distinct objects into distinct bins

If want to know if the following inequality holds for general values of $s \leq n \ll m$. $$\frac{C_0(n,m,s)}{C_0(n,m)} \leq \frac{p(n,m,s)}{m^n}$$ $C_0(n,m) = \binom{n+m-1}{m-1}$ is the number of ...
0
votes
4answers
55 views

Number of ways to write $n$ as sum of positive odd integers less than 10

Let $f(n)$ be the number of ways to write $n$ as sum of positive odd integers that each one of them is less than 10, without any importance to their order. For example: f(6)=4 as you can write it as 1+...
1
vote
0answers
31 views

Consistency in the definition of cross cumulants

Suppose that I have an $n\times 1$ random vector $X=(X_1,X_2,\ldots,X_n)'$. For $\xi=(\xi_1,\ldots,\xi_n)'\in\mathbb{R}^n$, we can define the familiar generating functions $$ M_X(\xi)=E\Big[\exp\Big(\...
3
votes
3answers
194 views

combinatoric sum (generating functions)

Given the generating functions: $f(x) = (1-x)^r = \Sigma_{i=0}^\infty a_i x^i$ $g(x) = \frac{1}{(1-x)^{r+1}} = \Sigma_{i=0}^\infty b_i x^i$ $h(x) = f(x) \cdot g(x) = \frac{1}{1-x}$ The factor of $...
4
votes
3answers
143 views

Problem solving a word problem using a generating function

How many ways are there to hand out 24 cookies to 3 children so that they each get an even number, and they each get at least 2 and no more than 10? Use generating functions. So the first couple ...
3
votes
4answers
85 views

Find a recursive formula to the given closed formula

I'm asked to find a recursive formula to this closed formula: $$f(n) = 2n + 3^nn$$ I tried to transform this formula to a formula that I might get using the Characteristic polynomial method. As I ...
1
vote
1answer
37 views

Using generating function to solve initial value problems

I have a hard exam coming up and something I've struggled with since week 1 of semester is initial value problems. How would I go about solving: (a) $u_{n} - 7u_{n-1} = 3 * 7^n : u_0 = 4 $ (b) $u_{n}...
1
vote
1answer
109 views

Proof using the product lemma

Let $S$ be the set of all finite subsets of $\mathbb N = \{1,2,3,...\}. $ We define a weight function $w$ where for a subset $X$ of $\mathbb N, w(X)$ is the sum of all the elements in $X$, with $w(\...
1
vote
0answers
39 views

The logarithmic integral $\int_2^x\frac{dt}{\log t}$ and Stirling numbers of the first kind

From the generating function for the function $x/\log(1+x)$, denoting $(A_n)_{n\geq 0}$ the corresponding sequence of coefficients, by integration of the function $1/\log(t+1)$ over $ \left( 1,x-1 \...
0
votes
1answer
20 views

Given a probability generating function what is the $r$th term

Given that pgf is $G(H(\xi))=\frac{1+\xi}{3-\xi}$. Where $H(\xi)=\frac{1}{2}(1+\xi)$ and $G(\xi) = \frac{\xi}{2-\xi}$. And that $G(H(\xi))$ is the pgf of some random variable $Y$. How does one get the ...
1
vote
0answers
48 views

Probability generating functions of coin tosses

I have just came across a weird definition for the probability generating function of a random variable $N$ that denotes the integer value for the $n^{\mathrm{th}}$ toss on which the coin turned out ...
0
votes
1answer
87 views

recursive generating functions

\begin{align} f(0) & = 1 \\ f(1) & = 1 \\ f(2) & = 2 \\ f(2n) & = f(n)+f(n+1), \;\;\;n\gt1 \\ f(2n+1) & = f(n-1)+f(n), \;\;\;n\ge1 \\ \end{align} I am trying to figure out ...