Stack Exchange Network

Stack Exchange network consists of 175 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.

1
vote
0answers
59 views

Relation between generating function of a sequence and reciprocal sequence

Stating that for a sequence $\{a_n\}$ its generating function is $f(x)=\sum_{n=0}^\infty a_n x^n$. I am interested in finding out its relationship with generating function of the sequence $\{b_n=1/a_n\...
0
votes
1answer
24 views

Consider the map ψ:C[x, y]→C[t] defined by f(x, y)⇝f(t^2, t^3). Prove that its image is the set of polynomials p(t) such that dp/dt(0)=0

So it is as the title says written here again for ease of reading: Consider the map $ψ:C\left[x, y\right]\to C\left[t\right]$ defined by $f(x, y) \mapsto f(t^2, t^3)$. Prove that its image is the set ...
3
votes
0answers
40 views

Calculate $\sum_{|S|=k}(n-|\cup S|)^m$ where $S$ is a subset of $X=\{\{a_1,a_2\},\{a_2,a_3\},\cdots,\{a_{n-1},a_n\},\{a_n,a_1\}\}$

Let $x_i=\{a_i,a_{i+1}\}\ (1 \leq i \leq n-1)$, $x_n=\{a_n,a_1\}$ and $X=\{x_1, \cdots, x_n\}$. Given $n,m$ and $k$, I'd like to ask how to calculate $\sum_{|S|=k}(n-|\cup S|)^m$ where $S$ is a subset ...
5
votes
1answer
109 views

Counting Necklaces

Suppose we have a necklace with $n$ beads. Each bead is either red or blue. I'd like to ask how to count the number of necklaces $f(n,m,k)$ satisfying the following requirements: 1) There are exactly ...
0
votes
1answer
71 views

Allan Gut Inter. Course on probability First Edition Chap 3 Problem 2

I need help with this problem. Does anyone know how to approach it? The distribution of the nonnegative, integer-valued random variable X has the following properties: For every n>=1: $P(X=2n)=\frac{...
3
votes
0answers
54 views

What distribution has the probability generating function $\mathbb E[s^X]=\left(\frac{1-\delta P}{1-sP}\right)^{\frac{1-s}{\delta-s}}$?

Is it possible to obtain the probability mass function for the discrete random variable $X$ associated with the following probability generating function? $$ \mathbb E[s^X]=\left(\frac{1-\delta P}{1-...
2
votes
1answer
73 views

Lattice Paths with moves $(1, 0)$, $(1, 1)$, and $(1, -1)$

Find a closed formula for the generating function that counts the number of lattice paths from $(0, 0)$ to $(n, 0)$ which never dip below $y=0$ and consist of the moves $(1, 0)$, $(1, 1)$, and $(1, -1)...
0
votes
2answers
51 views

Generating function problem with expectation.

Let $X$ be an integer valued random variable such that $$E\left[X(X-1)\ldots(X-k+1)\right]=\begin{cases}\binom{n}{k}k!&,\text{ if } k=0,1,2,\ldots,n \\ 0&,\text{ if }k>n\end{cases}$$, then ...
2
votes
2answers
52 views

Number of $n$-permutations with $r$ inversions modulo $k$

So I am reading "Introduction to Enumerative and Analytic Combinatorics" and there is the following problem: 27 on page 220: Let $k \leq n-1$. How many $n$-permutations are there for which the ...
1
vote
0answers
47 views

How to construct a function with these hypotheses?

I want to construct a function $f:[0,1]×[0,1]\rightarrow [0,1]$ such that $f(0,t)=t$ $f(1,t)=2t-1$ $ \forall$ $ t\geq \frac{1}{2}$ $f(s,t)=0$ $ \forall $ $0 \leq t \leq \frac{s}{2}$ $f(s,\frac{s}{2}...
0
votes
3answers
56 views

How do I find the generating function formula for the sequence defined by the recurrence: [closed]

$ a_0 = 1, a_1 = 0, a_2 = 8, a_3 = -7 $ $ a_n = 6a_{n-2} - 8a_{n-3} + 3a_{n-4} $ $ (n \geqslant 4) $
0
votes
1answer
79 views

Probability mass function from a generating function

I have the generating function $G_x(\theta) = \frac{\alpha-1}{\alpha-\theta^2}$ and I am trying to determine the probability mass function. I believe I need to determine the Taylor series expansion ...
0
votes
2answers
58 views

Find generating function of $ a_n=2a_{n-1}-3a_{n-2}+4n-1 $

I have to find generating function of $ a_n=2a_{n-1}-3a_{n-2}+4n-1 $ where $a_0=1$ and $a_1=3$. I'm currently stuck at the form: $f(x) = \sum_{n=0}^\infty a_nx^n = 1 + 3x +2x\sum_{n=2}^\infty(a_{n-1}...
1
vote
1answer
42 views

Find closed form of composition.

Consider $f(z) = \frac{1-a}{1-az}$, where $a \in(0,1)$ . Now we want to find $f(f\dots(f(z)\dots)$. It will begood if there is a closed form of it. I've consider first step : $f(f(z)) = \frac{1 - a}{...
0
votes
1answer
51 views

Generating function for a special binary string

Let $S$ be the set of binary strings consisting of a (nonempty) block of $0$s followed by a (nonempty) block of $1$s, such that if the block of $0$s has odd length, then the block of $1$s has even ...
2
votes
2answers
52 views

Finding the generating function of a sequence for $n$ pennies

Let $a_n$ count the number of different ways you can pay a sum of n pennies with 1p and 2p coins. Find the generating function and closed formula for $a_n$. I have attempted this question, finding $...
0
votes
1answer
68 views

How to find the generator of the following ideals?

How to find the generator of the following ideals $\cal a=${$F\in \mathbb Q[X]:F(i)=0$} in $\mathbb Q[x]$, $\cal b=${$F\in \mathbb Q[X]:F(\sqrt 2i)=0$} in $\mathbb Q[x]$? $\cal c=${$F\...
0
votes
0answers
23 views

How to find closed-form formula of $b_n = \sum_{j+k=n} a_{j,k}$

I’ve tried to use generating functions (GF) on this ‘convolution’-looking type of recurrence relation to find a closed-form formula for $b_n$ $$ b_n = \sum_{j+k=n} a_{j,k} $$ But any definition of ...
5
votes
2answers
134 views

How to solve this recurrence relation using generating functions: $a_n = 10 a_{n-1}-25 a_{n-2} + 5^n\binom{n+2}2$?

How can we solve the following recurrence relation using GF? $a_n = 10 a_{n-1}-25 a_{n-2} + 5^n {n+2 \choose 2}$ , for each $n>2, a_0 = 1, a_1 = 15$ I think that most of it is pretty ...
0
votes
1answer
85 views

How can I determine the sequence generated by this generating function: $B(x)=(x+3)^2 + \frac{x}{(1-3x)^6}$?

How to find the sequence that is generated by this GF? $B(x)=(x+3)^2 + \frac{x}{(1-3x)^6}$ We know that $\frac{1}{(1-ax)}$ is generated by $\sum_{i=0}^n a^n x^n$
2
votes
1answer
258 views

Number of unlabeled rooted trees with n vertices and k leaves

I know that we can write the corresponding multivariate generating function as follows: $\sum y^kx^n$ such that $n$ is the number of vertices and $k$ is the number of leaves. Then we can obtain $f(x,y)...
2
votes
2answers
212 views

Find a generating function for which $A(n)={n \choose 2}$

In the book I'm using, $A(x)$ denotes the formal power series (generating function), $A(x) = \sum a_ix^i$. I'm really stuck on this problem. Thanks for any help. My attempt after the given hint: $$\...
1
vote
1answer
29 views

Linear recursion with constant coefficients that fullfil $a_n = 3^n + 7^n$ for $n \in \mathbb{N}_0$

Let $a_n = 3^n + 7^n$ for $n \in \mathbb{N}_0$ I know that the generating function of $a_n= 3^n+7^n = A(x) = \frac{1}{1 - 3x} + \frac{1}{1 - 7x}.$ The exponential generating function $$A(x) = \...
0
votes
1answer
42 views

Exponential generating function $A(x) = \sum_{n=0}^{\infty}\frac{a_n}{n!}x^n$

Let $a_n = 3^n + 7^n$ for $n \in \mathbb{N}_0$ I know that the generating function of $a_n= 3^n+7^n = A(x) = \frac{1}{1 - 3x} + \frac{1}{1 - 7x}.$ But how can one calculate the exponential ...
0
votes
2answers
58 views

Generating function $3^n + 7^n$ for $n \in \mathbb{N}_0$

Let $a_n = 3^n +7^n$ for $n \in \mathbb{N}_0$ How can one calculate the generating function of the sequence $(a_n)_{n\in \mathbb{N}}$? Is that correct? If yes, how can one find that out? In our ...
2
votes
0answers
27 views

Moment Generating Function exercises: Knowing that $M_{X}(0)=1$ and $M´_{X}(0)= EX$

Hi guys, Any help with letter b of this exercise from Casella´s Book? I could finish the letter a). But I cant move in letter b). Any help? Thanks
1
vote
0answers
23 views

Find the number of ways to choose $k$ objects from a set of $n$ objects arranged in a circular order such that no two consecutive elements are chosen

Find the number of ways to choose $k$ objects from a set of $n$ objects arranged in a circular order such that no two consecutive elements are chosen. I could think of a combinatorial solution- ...
0
votes
0answers
21 views

Find generating function created by $10n$ for $n=0,1$ . $(-2)^n$ for rest even numbers. $0$ for rest odd number.

$an=$ { $10n$ for $n=0,1$ $(-2)^n$ for rest even numbers $0$ for rest odd numbers } My solution: $$A(Z)=0+10z+0+(-2)^3z^3+0+(-2)^5z^5+0+...(-2z)^{n-1}$$ or $$...(-2z)^{2n-1}$$ Not sure which ...
0
votes
1answer
53 views

Find generating function created by $a_n=2^{n+3}$, for $n\geq3$,$ a_0=1$, $a_1=\frac{5}{2}$ $a_2=3$

I hope title is understandable, wasn't sure on how to translate this task from my language. Below is my solution to this problem, is logic behind it correct? $$A(z)=\sum_{n=0}^{\infty}a_nz^n=1+\frac{...
0
votes
1answer
31 views

Find the generating function for the number of integer solutions to $x_1 + x_2 + x_3 + x_4 = r$ with $1 \le x_1 \le x_2 \le x_3 \le x_4$

Find the generating function for the number of integer solutions to $x_1 + x_2 + x_3 + x_4 = r$ with $1 \le x_1 \le x_2 \le x_3 \le x_4$. The textbook has showed me the solution, so I do know how to ...
0
votes
0answers
30 views

for characteristic function $\phi$, prove that $1-|\phi(2u)|^2\le 4( 1-|\phi(u)|^2 )$

I know that, If $X$ and $Y$ are two independent random variables then $$\phi_{X+Y}(u) =\phi_{X}(u)\cdot\phi_{Y}(u)$$ and $ \phi_{-X}(u)=\overline{\phi_{X}(u)}$ How to proceed further?any steps to ...
0
votes
0answers
31 views

Generating functions and algebricity

I study Generating Functions and i see the example 5.1a p.p 9 in paper below. i can't understand the author how solved it? can you help me? Paper: "SOME APPLICATIONS AND TECHNIQUES FOR GENERATING ...
0
votes
0answers
22 views

Computing coefficients of the generating function counting trees with forbidden members

How can I compute the coefficients $r^{(n)}_p$ with a Python code using the following equations? \begin{equation}\label{10} r^{(n)}(x)= S^{(n)}(x)-\frac{1}{2}\left[ (S^{(n)}(x))^2-S^{(n)}(x^2)\right] ...
1
vote
1answer
60 views

Almost all trees are cospectral (Allen Schwenk's 1973 article)

I am currently working on the following article: https://www.researchgate.net/publication/245264768_Almost_all_trees_are_cospectral. There are a few things that I don't understand, and since the ...
1
vote
0answers
42 views

For a p.g.f, of $X, f_X(s)$, is $s$ really “just” a dummy variable?

The p.g.f, $f_X(s)$ of a random variable $X$ is given by $$ f_X(s) = \sum_{x = 0}^\infty P(X = x)s^x$$ Usually, it's said the $s$ is just a dummy variable, but having been exposed to the result that ...
0
votes
0answers
32 views

Why is this series given by this Taylor expansion?

So I am doing some graph theory stuff and I know that, given $4$ axes that I can walk along in both directions, the number of reached points after $n$ steps is: $$ N(n) = \sum_{k=0}^{\mathrm{min}(4,n)...
5
votes
3answers
196 views

Generating function for the number of graphs with $k$ connected components

There are $$b_n = \frac{(n-1)!}{2}$$ ways to form a cycle on $n$ labelled vertices, for $n\geq 3$. The exponential generating function for this sequence is $$ f(x) = \frac{1}{2}\sum_{n\geq 3} (n-1)! \...
1
vote
0answers
69 views

Probability generating function of simple birth process

Question: Suppose that $(X_t)_{t \geq 0}$ is a $(1,(\lambda_n)_{n \geq 0})$ simple birth process with $\lambda_n = (n+1)\lambda$. Show that $$\phi(t) := \Bbb E[z^{X_t}]= ze^{-\lambda t}+ \int_0^t \...
0
votes
1answer
73 views

An efficient approach to combinations of pairs in groups without repetitions?

Before I start, I need to admit that I am not a mathematician and if possible would need this explained in laymen terms. I appreciate your patience with this. The problem: A class consisting of n ...
0
votes
3answers
46 views

Collecting 20 dollars from different people

In how many ways can I collect a total of $20$ dollars from $4$ different children and $3$ different adults, if each child can contribute up to $6$ dollars, each adult can give up to $10$ dollars, and ...
0
votes
3answers
72 views

Finding coefficient of $x^{100}$

What will be solution of this function for coefficient of $x^{100}$? $$\displaystyle\frac{1}{\left ( 1-x^{10} \right )(1-x^{20})(1-x^{50})}$$ My solution: $[x^{100}] \ \ \ \ \ \ \ \ \  \ $$\...
-2
votes
1answer
43 views

Kids eating candy [closed]

Determine how many ways I can distribute 80 candies to 3 kids, such that: The first kid receives an arbitrary number of candies (possibly 0). The second kid receives an even positive number of ...
0
votes
1answer
33 views

Find generating function for the following conditions:

$a_n=$ $2^{n+1}$ for $n:3|n$ $a_n=$ $0$ for the rest So theres what I tried to do: $$\sum_{n=0}^{\infty}a_nz^{n}=2*z^0+0*z^1+0*z^2+2^4z^3+0*z^4+0*z^5+2^7z^6+...2^{k+1}z^k$$ $$2^{k+1}z^k=b^k$$ $$\...
2
votes
2answers
34 views

Finding the closed form of a generating function

Given that $k$ is a positive integer and $f(x)$ is the generating function of the sequence $(b_0,b_1,b_2,...)$ where $b_n = {n \choose k}\;\, \forall \;n$, show that: $$f(x)=\frac{x^k}{(1-x)^{k+1}}$$ ...
1
vote
2answers
65 views

How to convert $\frac{1}{(1-x)(1-x^3)}$ into a sum of multiple fractions?

What I mean is, that one can convert $\frac{1}{(1-x)^2(1-x^2)}$ into the following sum: $\frac{1}{8}(\frac{1}{1+x}+\frac{1}{1-x} +\frac{2}{(1-x)^2} + \frac{4}{(1-x^3)})$ But I can't seem to do the ...
0
votes
1answer
25 views

Showing a probabilistic inequality using probability generating function

Let Y~Poisson($\lambda$) be a random variable. Use $G(z)$ to show that: $\mathbb P(Y\geq2\lambda)\leq e^\lambda 2^{-2\lambda}$, where $G$ is the probability generating function of Y, defined as $G(z)=\...
1
vote
2answers
50 views

Solve the recursion given by $f(n) = 2f(n-1) + \frac{(-1)^n}{n!}$ using generating functions.

Assume that $f(0) = 0, f(1) = -1$. $g(x)$ is $f(n)$'s generating function, I got to the expression: $ g(x) = \frac{e^{-x}-1}{1-2x} $ But am now stuck, since I can't find a power series for the ...
0
votes
1answer
65 views

Find the coefficient of $x^{24}$ in the power series of $e^{2x}(e^x-1)$.

I tried to work through the problem algebraically, and got to $\frac{2^{24}}{24!}(2^{24}-1)$, but comparing with the Taylor series generated for the function by Wolfram Alpha, it seems to be incorrect....
1
vote
1answer
63 views

Number of non-negative integer solutions for $x+y+z = n^2$

What is the number of solutions for $x+y+z = n^2$ for $x,y,z$ non-negative integers? I thought to use generating functions. I know that the generating function for $x_1+x_2+...+x_k= n$ when $x_i \in ...
0
votes
1answer
60 views

Range of one-dimensional lattice paths of a given length

How many lattice paths in $\mathbb{Z}$ of length $n$ with steps in $\{-1,0,+1\}$ visit $m$ distinct points? Notice that this is just the number of lattice paths $P$ such that $\max P - \min P + 1 = m$...