Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [generating-functions]

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.

2
votes
1answer
39 views

How to solve a recurrence relation with generating functions?

I don't really understand how to solve (with generating functions) for the recurrence relation of $$a_n = a_{n-1}+2(n-1)$$ with initial conditions of $a_1 = 2$ when $n \geq 2$ This is what I was ...
0
votes
2answers
59 views

Evaluate $\sum_{n=1}^N n {n \choose k}$ and get a closed form solution

Find a closed form of $\displaystyle\sum_{n=1}^N n {n \choose k}$. 1) Firstly, is it valid to simplify this equation to: $\sum_{n=k}^N n {n \choose k}$ because ${n \choose k} = 0$ for $n < k$? 2)...
0
votes
0answers
54 views

Evaluate $\sum_{n=1}^N {n \choose k} $ [duplicate]

Evaluate to get a closed form solution. I encountered this by rearranging the below equation which I also need some help solving: $\sum_{n=1}^N n {n \choose k} $ I'm not very good at solving ...
1
vote
1answer
19 views

Find the Recurrence relation for $q_n$ given the following condition:

Let $q_n$ denote the number of strings of length $n$ (formed from digits 0,1,2,3) which have even number of $2$'s. set up a recurrence relation for $q_n$.
0
votes
1answer
18 views

Using Generating Function to calculate number of ways to select committees

How many ways are there to select three committees from 10 people? The committees serve different purposes, someone has to be in every committee and everyone serves in exactly one committee. (Use the ...
0
votes
0answers
20 views

“Extra” step in counting the number of ways to have a domino tiling of a 4 by n rectangle?

The picture above explains a method for doing this via generating functions & finite state machines, but what I do not get is why we must record the number of dominoes used to make a state ...
-1
votes
1answer
77 views

How do you find the positive integer solutions of this equation with the conditions?

Compute the number of positive integers solutions of the following equation: $x_{1}+2x_{2}+3x_{3}+10x_{4}+2x_{5}=n,$ where $x_{1}\le 4$, and $3\le x_{2}\le 7$. I am using the generating functions ...
0
votes
1answer
57 views

How do you compute using generating functions? [closed]

Let $C_{0}=0$ and $C_{1}=1$ and define $C_{n}$ by $C_{n}=\sum_{k=0}^{n}C_{k}C_{n-k}\qquad\text{for}\quad n=2,3,\ldots\,$ Use generating functions to compute $C_{n}$.
0
votes
1answer
34 views

Recurrence relation with two variables.$(n+h_{n+1}) f(n+1,m) + f(n-1,m) + h_n f(n,m-1) + (m+1) f(n,m+1)=(1+m+(n-1)+ 2h_n) f(n,m) $

I have the following recurrence relation at hand: ( $n,m$ are integers) $$(n+h_{n+1}) f(n+1,m) + f(n-1,m) + h_n f(n,m-1) + (m+1) f(n,m+1)=(1+m+(n-1)+ 2h_n) f(n,m) $$ where $h_{n}= \frac 1{n+1}$. We ...
-2
votes
1answer
37 views

Find recurrence and generating function [closed]

Let $u_n$ be a probability that in $n$ Bernoulli trials number of success will be divisible by $3$ .Find reccurence for $u_n$ and it's generating function. As far as i get i know that $$u_n=\sum_k{n \...
0
votes
0answers
25 views

Number of ways of covering $m$ points by $n$ shapes?

Suppose $m$ points labelled $1,2,.....,m$ are on circumference of circle, find the number of ways of covering these $m$ points by $n$ shapes and no shapes touches any other shape. Shapes can be of ...
1
vote
1answer
29 views

Plain simple combinatorics formula vs. using polynomials for counting the number of balls which can be picked from a given set

I am really confused by the usage of polynomials for counting problem, for instance : Number of ways of picking $5$ balls from $5$ red, $5$ green, $5$ blue balls. Condition : At least one of ...
2
votes
1answer
37 views

Generating Functions - Mess with coefficients

Question: a) Find the coefficient of $x^n$ at the following generating function: $ne^{2x}$ b) Find the coefficient of $\frac{x^n}{n!}$ at the following generating function: $n \cos x$ My Approach: ...
0
votes
1answer
25 views

How to find the sequence given the exponential generating function [closed]

I am trying to learn combinatorics by myself and I am currently stuck on this question. Let $ω$ denote a root(complex ) of the equation $z^2 + z + 1 = 0$. What sequence is $e^x + e^{\omega ...
0
votes
0answers
17 views

Deriving mean through MGF for discrete uniform distribution

The MGF of a discrete uniform distribution is given as $$M_X(t) = \frac{e^t(1-(e^t)^k)}{k(1-e^t)}$$ Looking for $E(X)$, I am computing $$M_X'(t) =\frac{(k(e^t-1)-1)e^{(kt+t)}+e^t}{ k(e^t-1)^2}$$ ...
2
votes
3answers
68 views

Derive $\sum_{s=r}^{\infty} \binom{m}{s} \binom{s}{r}(-1)^s=0 $ using an identity $(1 + x)^ m (1 + x)^{ -(r+1)} = (1 + x)^{ m-r-1}$

To prove: $$\sum_{s=r}^{\infty}\binom{m}{s} \binom{s}{r}(-1)^s=0 $$ Use the identity: $$(1 + x)^ m (1 + x)^{ -(r+1)} = (1 + x)^{ m-r-1}$$ I have trouble understanding the hint, could somebody ...
0
votes
1answer
33 views

Generating function of number of assignments with constraints

Suppose I have $N$ boxes on a ring. Each box can be assigned number $0$ or $1$. Neighboring boxes can not have both $1$. so the assignment $0000$ is allowed, but the assignment $0110$, $1001$ etc are ...
0
votes
1answer
28 views

Generating function from recurrence relation of binomial distribution

Hello i have given recurrence like this : $$p_{n,k}=(1-q)p_{n-1,k-1}+qp_{n-1,k}$$ my question is how to get (step by step) generating function from this recurrence? we know that it's some king of ...
2
votes
1answer
76 views

A Fibonacci convolution

A Fibonacci convolution. Recall that $$F(x)=\sum_{n=0}^\infty F_n x^n =\frac{x}{1-x-x^2} =\frac{1}{\sqrt{5}} \left(\frac{1}{1-\Phi x} -\frac{1}{1-\bar{\Phi}x}\right).$$ (a) Prove that $\displaystyle ...
0
votes
0answers
14 views

Why is the count for labelled sets just 1 in the EGF $e^x = \sum 1 \cdot \frac{x^n}{n!}$?

I have been reading up on species theory and generating functions and I haven't been able to get my head around this. Shouldn't the count for labelled sets still be $n!$ since we are still labelling ...
1
vote
4answers
55 views

Number of Non negative integer solutions of $x+2y+5z=100$

Find Number of Non negative integer solutions of $x+2y+5z=100$ My attempt: we have $x+2y=100-5z$ Considering the polynomial $$f(u)=(1-u)^{-1}\times (1-u^2)^{-1}$$ $\implies$ $$f(u)=\frac{1}{(1-...
1
vote
1answer
54 views

Number of integral solutions $x_1 + x_2 + x_3 = 10$

$x_1 + x_2 + x_3 = 10, \ \ 0 \leq x_1 \leq 10 , \ 0 \leq x_2 \leq 6 , \ 0 \leq x_3 \leq 2 $ $[x^{10}] (1 + x^1 + x^2 + ... + x^{10})(1 + x^1 + x^2 + ... + x^{6})(1 + x + x^2)$ $[x^{10}] \Large (\...
2
votes
1answer
26 views

Sequence from a generating function?

Find the sequence $a_n$ if its generating function is $$A(x) = \prod_{n=1}^{\infty}(1-q^nx)$$ Well, i need to find the expansion of A(x) in terms of powers of x. For that I take the log of both the ...
0
votes
0answers
26 views

Finding the probability generating function of $Z= mY + n$ where $Y$ is random variable and $m,n$ are positive integers

Let $G_Y(s)$ be the probability generating function of $Y$. The probability generating function of $Z$ is defined as: $$G_z(s) = E(s^Z)$$ $$= E(s^{mY \ +\ n})$$ $$= E(s^{mY}s^n)$$ $$= s^{n} \ E((s^{...
0
votes
1answer
46 views

Exponentiate generating functions as formal power series

In my discrete math class, we are studying generating functions. We learned that $$ e^x = \sum_{i = 0}^{\infty} \frac{x^i}{i!}, $$ which is certainly an identity in calculus. However, in the ring of ...
1
vote
1answer
39 views

What is the coefficient of $ x^{i}$ in the product $ \ \large \prod_{i \geq 1} \frac{1}{1-x^i}\prod_{i \geq 1} \frac{1}{1+x^{2i-1}}$?

What is the coefficient of $ x^{i}$ in the product $ \ \large \prod_{i \geq 1} \frac{1}{1-x^i}\prod_{i \geq 1} \frac{1}{1+x^{2i-1}}$? Answer: $\ \large \prod_{i \geq 1} \frac{1}{1-x^i}\prod_{i \geq ...
0
votes
0answers
27 views

Generating Function for partition of r into distinct parts

My combinatorics class is learning about generating functions and partitions of numbers into summands. One exercise we are working on for tomorrow's lecture to better understand the concept is to find ...
0
votes
0answers
34 views

Advanced Discrete Math Generating function Problem

I am suppose to prove that the number of partitions of $n$ in which each part appears $2$, $3$, or $5$ times equals the number partitions of $n$ in to parts which are congruent to $2$, $3$, $6$, $9$, ...
0
votes
0answers
43 views

Expected value and variance of random variable on some terms(dates?)

I have a exercise that sounds like this: Find the expected value and the variance of the random variable X with natural values in terms of: a)generating function P b)generating function Q Excercise ...
1
vote
1answer
38 views

Constrained combinatorial question: 2 types of balls divided into k groups with limits

Let's say we have two types of balls, black and white. There are $B$ black balls and $W$ white balls, s.t. $B + W = N$ where $N$ is the total number of balls. We want to divide these $N$ balls ...
1
vote
2answers
64 views

Finding generating function for $ h_{n} = h_{n-1} + \binom{n+1}{3} + n$

Let $h_{n}$ denote the number of regions into which a convex polygonal region with $n + 2$ sides is divided by its diagonals, assuming no three diagonals have a common point. With this is the initial ...
0
votes
0answers
36 views

Generating functions for number of ways to take k servings of food

A hungry math major visits the school's cafeteria and wants to know the number of ways sk to take k servings of food, including at least one main course, an even number (possibly zero) of side ...
1
vote
1answer
50 views

Solve generating function of $\left(1+x+x^2+…+x^{200}\right)*\left(1+x^2+x^4+…+x^{200}\right)$

So i want to find the coefficient of $x^{200}$ of the above generating function because I have the equation $2a+b=200$ and I want to find how many tuples(?) can give me that. So I started using the ...
1
vote
4answers
104 views

Solve recurring sequence using a generating function

I have the sequence $a_n=3a_{n-1}-3a_{n-2}+a_{n-3}$, $\forall\ n \ge 3$, with $a_0=2$, $a_1=2$, $a_2=4$ being the known terms, and I want to find a non-recursive equation for $a_n$ using a generating ...
0
votes
1answer
38 views

labelled rooted tree with odd degree

Let $F(z)$ be the exponential generating function for labelled rooted trees with every vertex having even out-degree and let $H(z)$ be the exponential generating function for labelled rooted trees in ...
0
votes
0answers
13 views

Determine C, the generating functions GX(s), GY (s), GZ(s) and the probability mass function for the random variable Z = X + Y .

Consider two independent random variables X and Y . Random variable X can take only even values 0, 2, 4, . . ., and for any integer k it takes value 2k with probability P[X = 2k] = $C/4^k$ , where C ...
1
vote
1answer
48 views

Generating function of $(1+x)^n*(1+x+x^2)$

I have this generating function $$(1+x+x^2)^3*(1+x)^3$$ and i try to find $x^6$ and $x^9$ so i tried to simplify the 1st part $(1+x+x^2)^3$= $(1-x^3)^3*(1-x)^-3$ and it gives me $1+$$\frac{3!}{1!2!}x+...
1
vote
1answer
35 views

Combinatoric meaning of $a_n=5a_{n-1} - 6a_{n-2}$

I've solved the following recurrence relation: $a_n=5a_{n-1} - 6a_{n-2}$ using generating functions, to be: $a_n=3^n-2^n$. It is possible to give a meaning to $3^n-2^n$, and that is: Consider the ...
1
vote
1answer
26 views

Solve for the coefficient of an even generating function

Using a generating function, find the number of ways to select 10 candies from a huge pile of red, blue, and green lollipops if the selection has an even number of blue lollipops. I started, but I ...
0
votes
3answers
69 views

solving $f(x)=\frac x{1-x^2}+2(1+x)f(x^2)$ without power series expansion

My question concerns the title equation $f(x)=\frac x{1-x^2}+2(1+x)f(x^2)$, which arose through the use of generating functions for a simple recurrence. Assuming $f: R\rightarrow R$ is analytic, the ...
0
votes
1answer
57 views

Is there any difference between these two solutions for finding generating function?

Consider the following question. Find the generating function for the number of integer solutions to the equation $c_{1}+c_{2}+c_{3}+c_{4}=20$ where $-3\leq c_{1}, -3 \leq c_{2}, -5\leq c_{3}\leq 5,...
0
votes
0answers
21 views

Find generating function: summation from $0$ to infinity of $i(5^i)$

I know the generating function of the summation from $0$ to infinity of $nx^n$ is $= \frac{x}{(1-x)^2}$ So would this be something like $\frac{5}{(1-5)^2}$?
0
votes
1answer
33 views

Generating Function of 3(5^n)-2n

I am unsure as to whether or not I solved this generating function correctly. $a_n = 3(5^n) − 2n$ and the generating function is given by $$ \begin{split} &=3\sum 5^n - 2 \sum n\\ &=3(1+5+5^2+...
2
votes
1answer
59 views

Finding the generating function of 1/(n+1)!

I seem to be stuck on this question. Or rather, not sure if I solved it correctly. So I know that $$\frac{1}{(n+1)!}=\frac{1}{(n+1)}*\frac{1}{(n)!}$$ Therefore, I can change $\frac{1}{(n+1)}$ to $...
2
votes
1answer
67 views

differentiating the generating function of the Legendre equation

I need to differentiate the generating function $$G(x,t)=\sum a_n(x)t^n$$ w.r.t. x in order to solve $$\tfrac{d}{dx}[(1-x^2)\tfrac{dG}{dx}]+\tfrac{d}{dt}[t^2\tfrac{dG}{dt}]$$. But I don't ...
0
votes
0answers
14 views

We divide a group of people into subgroups A, B, and C, and ask each subgroup to form a line.

We divide a group of people into subgroups A, B, and C, and ask each subgroup to form a line. We also require that A have an odd number of people, and that B have an even number of people. How many ...
1
vote
1answer
44 views

Expectation and Variance using generating function with dependent variables

Suppose $X\sim\operatorname{Po}(\lambda)$ and $Y\sim\operatorname{Po}(\mu)$. Given $Z=X+Y$ , find the $\mathbb{E}[Z]$ and $\operatorname{Var}[Z]$ by first finding the generating function of $Z$. I'...
2
votes
2answers
50 views

How does the notation of PGF read in plain English?

How does the above notation of PGF read in plain English? Is it $\alpha$ to the power $X$? What does it even mean?
1
vote
3answers
42 views

Generating functions (index shifting)

I am going through old exam questions for my upcoming exam, but got stuck on a question since I don't really understand the solution. The question I have a problem with (in boldface): (b) Let ...
1
vote
1answer
134 views

Combinatorics Problem - Tiling to cover length $n$

Suppose you have $4$ types of tiles: blue dominoes, blue monominoes, red dominoes and red monominoes. Find the generating function for the number of ways of lining up tiles to cover length n such that:...