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

7
votes
3answers
339 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
21 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
0answers
10 views

generating functions for catastrophe theory

I am studying Thom's theorem in catastrophe theory and am having a hard time understanding what the "generating functions" actually do. How exactly are they used to classify generic caustics? 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
41 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
22 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
14 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
32 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
47 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
48 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
31 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
18 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
26 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
47 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 $...
3
votes
3answers
139 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
83 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
36 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
108 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 ...
0
votes
1answer
34 views

Finding a generating function from an expression

Series representations: $$ \frac{1}{2(1-x)^3}+\frac{1}{4(1-x)^2}+\frac{1}{8(1-x)}+\frac{1}{8(1+x)}=\sum_{n=0}^\infty x^n\left(7+(-1)^n+8n+2n^2\right). $$ I'm trying to figure out to to turn this ...
3
votes
1answer
41 views

Find a generating function for $a_r=(r-1)^2$

Problem Find a generating function for $a_r=(r-1)^2$ My Solution $$g(x)=1+x+x^2+x^3+\cdots=\frac{1}{1-x}$$ $$g'(x)=1+2x+3x^2+4x^3+\cdots=\frac{1}{(1-x)^2}$$ $$x\times g'(x)=x+2x^2+3x^3+4x^4+\...
1
vote
0answers
28 views

Find an ordinary generating function whose $a_r = 3r + 7$

Problem Find an ordinary generating function whose coefficient $a_r = 3r + 7$. My Solution $$g(x)=1+x+x^2+x^3+\cdots=\frac{1}{1-x}$$ $$7\times g(x)=7+7x+7x^2+7x^3=\frac{7}{1-x}$$ $$g'(x)=0+1+...
0
votes
0answers
25 views

Explicit form of a generating function.

Let $q \geq p$ be natural numbers both larger than or equal to two. Let $u(z):=z^p+z^{p+1}+...+z^q$ and $p(z)=\frac{z u'(z)}{1-u(z)}$. Since $p(z)$ is rational, one can write (by the theory of ...
1
vote
0answers
34 views

Vandermonde-type convolution with geometric term

Is there a closed-form solution to the following sum? \begin{align*} f(r, s, n) = \sum_{k=0}^{n}c^k\binom{r}{k}\binom{s}{n-k} \end{align*} I know this corresponds to find the coefficient of $x^n$ of ...
3
votes
1answer
131 views

Inequality with analytic functions on the unit ball

Let $g(z) = \sum_{n\geqslant 0} a_nz^n$ be an analytic function where $a_n$ only take values in $\{0,1\}$ (not sure if it is a necessary condition, it is just the case I'm considering). Let $\{n\...
3
votes
1answer
199 views

Conditional probability generating function - Binomial

I'm working on the following problem: Y = $X{_1}+X{_2}+X{_3}+...+X{_N}$ $N\overset{d}{\sim}Bi(n,p) $ and $X_i\overset{d}{\sim}Bi(m,q)$ $N, X_1, X_2 $ are independent $a)$ Find $...
1
vote
0answers
19 views

Determining the E.G.F from an Umbral Type Recurrence Formula

Suppose I have the recurrence formula $$\left(A+\frac{2}{3}\right)^n+w_3^2\left(A+\frac{1+w_3}{3}\right)^n+w_3\left(A+\frac{1+w_3^2}{3}\right)^n=0; A_0=1, A_1=-\frac{1}{3}$$ where $w_3=\exp(2i\pi/3)....
0
votes
1answer
25 views

Generating Normals with specific means and variances

Suppose I wish to generate normals $X, Y, Z$ with the correlation matrix R but with means $0, 1, 2$, and variances $4, 16, 25$, respectively. How would you do this? The only way I know of doing ...
1
vote
3answers
28 views

Complicated partial fraction expansion

I'm reading the book generatingfunctionology by Herbert Wilf and I came across a partial fraction expansion on page 20 that I cannot understand. The derivation is as follows: $$ \frac{1}{(1-x)(1-2x).....
0
votes
2answers
35 views

A function that satisfies the $n$-th derivative where $x=0$ is $\frac{1}{n}$ [closed]

Is there a function that satisfies $f^{(n)}(0)=\frac{1}{n}$ for every positive integer $n$?
2
votes
3answers
87 views

Inclusion–Exclusion Identical Computers Problem

Find the number of ways to distribute 19 identical computers to four schools, if School A must get at least three, School B must get at least two and at most five, School C get at most four, and ...
0
votes
1answer
32 views

Coefficient of $x^n$ in binomial expansion

I want to find the coefficient of $x^n$ in $G(x)$ where $ G(x) = \frac{1}{1-x^{a_1}}\times\frac{1}{1-x^{a_2}}\times\dots\times\frac{1}{1-x^{a_k}}$ how do I approach this? It would be helpful if it ...
3
votes
2answers
60 views

Multiplying A Coefficient by an Indexed Multiplier using Generating Functions

If I have a particular exponential generating function, $$G(x)=\sum_{n=0}^\infty a_n\frac{x^n}{n!}$$ then what would be the generating function for $$H(x)=\sum_{n=0}^\infty (n+1)a_n\frac{x^n}{n!}$...
4
votes
4answers
140 views

Find a generating function for the number of strings

The string $AAABBAAABB$ is a string of ten letters, each of which is $A$ or $B$, that does include the consecutive letters $ABBA$. Determine, with justification, the total number of strings of ten ...
1
vote
0answers
17 views

How would you write the OGF for the sequence {hk}

Write the ordinary gen. function for the sequence. So trying to work this out. I ended up with (1+x)^7. But I am not sure if this is correct. Thanks for any help.
4
votes
2answers
58 views

Counting numbers of fruit baskets

Suppose you have $10$ apples, $12$ bananas, and $8$ peaches, and you want to divide them into $3$ baskets containing $10$ fruit each. In how many ways can you do this, if the fruit of each type is ...
2
votes
3answers
146 views

A combinatorial task I just can't solve

Suppose you have $7$ apples, $3$ banana, $5$ lemons. How many options to form $3$ equal in size baskets ($5$ fruits in each) are exist? At first I wrote: $\displaystyle \frac{15!}{7!3!5!} $ But its ...
0
votes
0answers
78 views

Coefficients of powers of the generating function of the Fibonnaci numbers

How to find the coefficent of $x^M$ in $$( x + x^2 + x^3 + x^5 + x^8 + x^{13} + x^{21} + \ldots )^n$$ where $n$ is a positive integer and the exponents are the Fibonacci numbers?
1
vote
1answer
39 views

Finding a generating function for $\{(n+2)C_{n+1}\}^\infty_{n=0}$

I'm trying to come up with a generating function for $\{(n+2)C_{n+1}\}^\infty_{n=0}$ where $C_n$ is the $n$th Catalan number. I know we can write $(n+2)C_{n+1} = 2(2n+1)C_n$. I also tried to follow ...
0
votes
0answers
56 views

Coefficient of generating function in two variables

I have a generating function $$\sum_{m,n} P(m,n)y^{m}x^{n} = \prod(1-yx^t)^{-1}$$ where $t \in \{1,2,3,5,8,...\}$ i.e. Fibonacci set with single 1. For now, I have a naive script to calculate ...
1
vote
1answer
68 views

Luis Suarez goalscoring record.

Problem: The $2013-14$ season was a short-lived ray of hope in an otherwise long dark night for the world’s greatest football team. The team played $38$ league games and the main contributing ...
1
vote
3answers
33 views

Use generating functions to determine the number of ways

Use generating functions to determine the number of different ways $12$ identical action figures can be given to $5$ children so that each child receives at most $3$ action figures So far I have come ...