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.

Filter by
Sorted by
Tagged with
0
votes
1answer
32 views

Expected Number of Rolls Until the sequence 6,6,5?

I've seen the recursive expected value approach to solving this problem but I am interested in how to solve this from a generating function perspective. Let E be the expected number of rolls, and X ...
0
votes
0answers
20 views

Exponential generating function of the sequence $\{na_n\}_n$ given a recursively defined sequence $\{a_n\}_n$

Find the exponential generating function of the sequence $\{na_n\}_{n\in\Bbb N}$ where $\{a_n\}_{n\in\Bbb N}$ is given by $a_0=-2,a_n=4a_{n-1}+3^n,n\ge 1.$ My attempt: Let $f(x)=\displaystyle\sum_{n=...
1
vote
1answer
32 views

Computing a power series

I came a across this power series during the resolution of a problem, $$\sum_{n = 0}^{\infty} \frac{(-1)^n}{(2n)!}x^n$$ but I haven't been able to crack it, it seems to be some sort of exponential ...
0
votes
0answers
46 views

Taylor series of $\frac{1}{1-x}$ centered at $x = 1$

I learnt taylor series recently and saw a video of blackpenredpen in which he found taylor series of a polynomial at $x = 1$. So, I was trying to find taylor series of $\frac{1}{1-x}$ at $x = 1$. Here'...
1
vote
2answers
45 views

Solving the differential equation $f''=f'+f$, where $f$ is an exponential function meant to give a term of Fibonacci series

I'm currently working through the H.S. Wilf's book generatingfunctionology, which is about generating functions, and have reached page 40 (or page 45 on the pdf) where the book is starting to deal ...
1
vote
1answer
21 views

Extracting $P_0$ from generating function

I have the following generating function for stochastic process $$\sum_n z^n p_n=\left[1-\frac{(1-z)}{\Lambda(t)}\right]^{n_0},$$ and I want to extract the probability $p_0(t)$ but I am confused how I ...
2
votes
1answer
25 views

OGF for unlabeled objects and EGF for labeled objects?

A few days ago I asked a question about the difference between the definition of classes of structures and combinatorial classes. I have been told that a combinatorial class refers to "unlabeled ...
0
votes
0answers
27 views

Partitions into distinct even summands and partitions into (not necessarily distinct) summands of the form $4k-2,k\in\Bbb N$

Prove that the number of ways to partition $n\in\Bbb N$ into distinct even summands is equal to the number of ways of partitioning $n$ into (not necessarily) distinct summands of the form $4k-2,k\in\...
2
votes
0answers
51 views

Solving Functional Equation from an Ordinary Generating Function

I was working with a friend on his CS homework, and one of his problems involved the following sequence: $$T(1) = 1; T(n) = T(n - 1) + T\left(\left\lfloor\frac{n}{2}\right\rfloor\right) \text{for } n &...
2
votes
2answers
84 views

How to solve this nonlinear recurrence relation?

I'm trying to solve the following recurrence relation (all values are real): $$g(n+1) = \frac{a_n + g(n)}{k\cdot g(n)}$$ With: $a_n,g(n) > 0$ for all n, and $g(0)$ is arbitrary. $k \in \mathbb{N}\...
0
votes
1answer
52 views

Generating function of $f(n) = C_n - \sum_{k=1}^{n-1}\binom{n}{k}f(n-k)$

I have combinatorially found this recurrence for a class of Dyck paths: $$f(n) = C_n - \sum_{k=1}^{n-1}\binom{n}{k}f(n-k)$$ where $C_n$ is the $n$-th Catalan Number. Now I want to write the generating ...
0
votes
1answer
63 views

Recurrence relation to solve

I have one problem that can be transformed into recurrence relation shown below, I guess $a_{n} = O(n)$. But I cannot solve the analytic form of $a_{n}$, can anyone help me on this? $$(n-2)a_{n+1}-(n-...
0
votes
0answers
21 views

Connection between generating functions with special polynomials

I was learning special function (ODE II course) where I encounter various kind of special polynomials like Legendre, Bessel's, Hermite and Laguerre. And many of their properties (specially recursive ...
0
votes
0answers
36 views

Is it possible to find the value of a polynomial from the generating function?

Suppose I've to find $H_4(0),$ where $H$ represents the Hermite polynomial. I've only been provided with the following relation : $$e^{-t^2+2tx}=\sum_n H_n(x)\frac{t^n}{n!}$$ My first step is to ...
2
votes
0answers
102 views

Is there a closed form for $\sum_{k=0}^n \binom{n}{k}^2p^k(1-p)^{n-k}$?

I have come accross the following sum \begin{align} s_n=\sum_{k=0}^n \binom{n}{k}^2p^k(1-p)^{n-k}. \end{align} Can we obtain some closed-form expression with respect to $p$ for this summation? I found ...
2
votes
1answer
37 views

"Matching coefficients" in generating functions approach

Here (https://austinrochford.com/posts/2013-11-01-generating-functions-and-fibonacci-numbers.html), it is proved (by generating functions) that the nth Fibonacci number is $$F_n=\frac{1}{\sqrt{5}}(\...
-1
votes
2answers
53 views

Solving non-homogeneous recurrence relations [closed]

Find $g_{n}$ if $g_{n+2}-6g_{n+1}+9g_{n}=3\times 2^n + 7\times (3)^n$ given $g_{0}=1,g_{1}=4$. How can I proceed to solve these kind of recurrence relations? I cannot show any work since I haven't ...
1
vote
0answers
59 views

Is $\frac{1}{x(1+x)}$ a well-defined generating function?

Is this a well-defined generating function? $$\frac{1}{x(1+x)}$$ We know that $\:\frac{1}{(1+x)} = \sum_{n \ge0}(-1)^nx^n$,$\:$ hence the notation $\frac{1}{x}\sum_{n \ge0}(-1)^nx^n \:$ would act as ...
1
vote
1answer
74 views

Find the generating function of $f(n) = \sum_{k = 0}^n \binom{n}{k} (-1)^{n-k}C_{k}$

I want to find the generating function of $f(n) = \sum_{k = 0}^n \binom{n}{k} (-1)^{n-k}C_{k}$, where $C_k$ is the $k$-th Catalan number. So, using the definition of an ordinary generating function: $$...
0
votes
1answer
73 views

How to solve $x(x-1)(x-2)(x-3)(x-4)(x-5)....(x-999)$? [closed]

How to solve $x(x-1)(x-2)(x-3)(x-4)(x-5)....(x-999)$? I'm calculating the probability of $1000$ multicast group having different address. Multicast address space is $2^{28}$. So I tried to calculate ...
2
votes
2answers
92 views

Understaing Concept of Generating function.

I can easily understand the generating function of sequence such as $a_n = n+1$ or something, but cannot understand generating function for some object. There are 2 examples (with photos): What does &...
2
votes
1answer
54 views

Show that $\sum_{k=1}^n \binom{n}{k}k^2=n^2\cdot \:2^{n-2}+n\cdot \:2^{n-2}$.

Let $n$ be a positive integer. Show that $\sum_{k=1}^n \binom{n}{k}k^2=n^2\cdot \:2^{n-2}+n\cdot \:2^{n-2}$. I have that $$(1+x)^n = \sum_{k=0}^n {n \choose k} x^k$$ and I'm wondering if I can use ...
2
votes
1answer
68 views

Demonstration for the equal number of odd and unequal partitions of an integer

I'm having some problems trying to resolve one exercise from The art and craft of problem solving by Paul Zeitz. What this problem asks you is to prove that $F(x)$ is equal to 1 for all $x$, where $$F(...
0
votes
0answers
20 views

Generating function of a symbolic sequence

I am trying to construct generating function of the next sequence $R_i$ $\mathbf{R}_1=1+A_{1,1} b_{1,1}$ $\mathbf{R}_2=1+A_{1,1} b_{1,1}+A_{2,1} b_{1,2}+A_{1,2} b_{2,1}+A_{2,2} b_{2,2}+A_{1,2} A_{2,1}...
0
votes
0answers
48 views

How to find $\sum_{n=1}^{\infty} a_{2n} x^n$ from $\sum_{n=1}^{\infty} a_{n}x^n$?

Suppose that we have some sequence $(a_n)_{n\ge 1}$ and its generating function $\displaystyle f(x)=\sum_{n=1}^{\infty} a_{n}x^n$. How can I find the generating function of $(a_{2n})_{n\ge 1}$ from ...
1
vote
0answers
57 views

How do I use generating functions?

So, I have been taking an introductory combinatorics class and over the past semester we had, not surprisingly, occasionally used generating functions to solve problems. Now, I am capable of ...
1
vote
1answer
76 views

Binomial Coefficient

If $b_n=\sum_{k=0}^{n}(-1)^k\binom{n}{k} a_k \forall n\in\mathbb{N_0},$ then prove that $a_n= \sum_{k=0}^{n}(-1)^k\binom{n}{k} b_k \forall n\in\mathbb{N_0}.$ My Working: let $f(x)=a_0+a_1x+a_2x^2+\...
1
vote
1answer
40 views

Find the general term in the sequence with generating function

Let $a_n$ be the sequence defined by $$a_0 = 1,$$ $$2a_{n+1}=\sum_{i=0}^n\binom{n}{i}a_ia_{n-i}$$ I want to find the general term. I have noticed that $$\sum_{i=0}^n\binom{n}{i} = 2^n$$ but don't know ...
0
votes
0answers
15 views

A `recursive convolution' equation

Immediate problem I have a finite sequence of $k +1 \in \mathbb{N}$ numbers $(a_{i})_{0 \leq i \leq k}$ satisfying the recurrence relation $$ a_0 = -1, \qquad a_{i+1} = -\sum_{j=1}^{i} a_{j}\frac{1}{(...
0
votes
2answers
34 views

Consider $5$ dice with six sides, three of which are labeled $1$ and three of which are labeled $2$. How many ways are there to get a sum of $9$?

Consider $5$ dice, each with six sides, three of which are labeled $1$ and three of which are labeled $2$. How many ways are there to get a sum of $9$ from rolling these five dice? I'm learning about ...
2
votes
0answers
65 views

Alternating sum of binomials divided by a polynomial of the index

I'm working with a sequence of $k$ by $k$ matrices $M^n$ whose entries satisfy $$M^n_{ij} = \binom{j-1}{i-1} \sum_{l=0}^{j-i} \binom{j-i}{l} (-1)^{l} (\frac{1}{i+l})^n, \quad n \in \mathbb{N}$$ I've ...
0
votes
0answers
67 views

Solve generating function for $a_n$

I am not sure how to solve questions like this. I am aware of both recurrence relations and generating functions and how two of these concepts work, but I find it hard to combine them. I would really ...
0
votes
1answer
76 views

Find the coefficient of $x^n$ in $(x^2 +x^3 +x^4 +\cdots)^5$

I have got stuck on this question, though I realise that I have probably got really close to an answer. This is how I approached it: \begin{align*}f(x) &= (x^2+x^3+x^4+\cdots)^5\\ &= x^{10}(1 +...
0
votes
0answers
11 views

Solving recurrence of functions with changing input.

I'm trying to solve the following recurrence relation: $$Z_n(h) = Z_{n-1}(h+k) + Z_{n-1}(h-k), $$ with $Z_1(h)$ some given function. I was thinking about all kinds of techniques to solve this, but ...
1
vote
1answer
77 views

Finding a closed-form formula to a recurrence with summation of past terms

I'm trying to find a closed form formula for the following recurrence problem but I'm having some difficulty: \begin{align} g(n) &= -\frac{1}{n+1} - \sum_{i=1}^{n} \frac{1}{n+1}g(i) \\ &= \...
1
vote
2answers
35 views

Recurrence relations in the generating function of binary partitions

Let $b(n)$ denote the number of binary partitions of $n$, that is, the number of partitions of $n$ as the sum of powers of $2$. Define \begin{equation*} F(x) = \sum_{n=0}^\infty b(n)x^n = \prod_{n=0}^\...
6
votes
4answers
217 views

Coefficient extraction

I want to show: \begin{equation*} [z^n]\frac{1}{(1-z)^{\alpha + 1}} \log \frac{1}{1-z} = \binom{n + \alpha }{n} (H_{n+\alpha} - H_{\alpha}). \end{equation*} where $[z^n]$ means the $n$-th ...
0
votes
2answers
41 views

Generating function and integer sequence that arise from this function

I am looking for the power series arising from the generating function $f(x)$ that solves the following equation: $\alpha^{2}x^{3}+3\alpha x^{2}f(x)+3xf(x)^{2}=\beta$ for some $\alpha,\beta\in \mathbb{...
1
vote
0answers
31 views

random number selection and generating function

Suppose a number is chosen randomly between $\{0,1, \cdots 99 \}$. Let X denote the sum of the digits of the selected number. I am interested in the p.m.f of X. Here is my approach: Let $u =\{0,1, \...
1
vote
1answer
22 views

Ways of Changing 85/90 dollars

The number of ways of changing 85 dollars with 1,5,10 and 20 dollar bills should be the coefficient of $x^{85}$ in $(1+x+x^2+\ldots+x^{85})(1+x^5+\ldots+x^{85})(1+x^{10}+\ldots+x^{80})(1+x^{20}+\ldots+...
2
votes
1answer
45 views

Generating function on Lehman's Mathematics for Computer Science

I am reading Lehman's Mathematics for Computer Science. In chapter 16 Generating Functions.enter image description here I couldn't see how $1-x-x^2 = (x-r_1)(x-r_2)$. Shouldn't it be $1-x-x^2 = -1(x-...
1
vote
1answer
49 views

Number of different suits among some randomly chosen cards

A standard deck of cards has 4 suits, with 13 cards per suit. 2 different colored decks (red and blue) are shuffled together to form a single 104-card deck. Red suits are distinct from blue suits. ...
1
vote
2answers
98 views

Showing the formal identity $(1-x+x^2)(1-x^2+x^4)(1-x^4+x^8)\cdots =\frac{1}{1+x+x^2}$

How to show this formal identity (or you can assume $|x|<1$)? $$(1-x+x^2)(1-x^2+x^4)(1-x^4+x^8)\cdots =\frac{1}{1+x+x^2}$$ I can show that the latter is $$=1-x+x^3-x^4+x^6-x^7+\cdots$$ but how to ...
1
vote
0answers
38 views

Non-crossing Partition

I'm trying to solve following problem, and I got stuck. Let be $[n]=\{1,...,n\}$. Def. A partition $\pi$ of $[n]$ is called non-crossing, if $a$ and $b$ belong to one block and $x$ and $y$ to another, ...
5
votes
0answers
320 views

Converting $ \int_0^{\infty} \frac{e^{-\varepsilon s} \, (s+s^2)^{\beta}}{\log^{\gamma}((1+s)/s)} \, ds$ to a sum?

Could anyone shed some light on how to convert the following integral to a sum? $$ I=\int_0^{\infty} \frac{e^{-\varepsilon s} \, (s+s^2)^{\beta}}{\log^{\gamma}((1+s)/s)} \, ds; \qquad\,\,\varepsilon,\...
1
vote
0answers
79 views

Solving homogeneous linear recurrence relation with double non-constant coefficients

I have the following recurrence relation -an eigenvalue problem- \begin{equation} (N+1-r) \, a_{r-1} + \frac{(m(r+1))!}{(m r)!} a_{r+1}=C_1 a_{r} \quad r\geq 1, \end{equation} with boundary conditions ...
2
votes
1answer
88 views

Closed form for the recursion $g(i,j) = g(i-1,j) + g(i,j-1)$

Consider the function $g$ defined by $$ g(i,j) = \begin{cases} i \, & \text{ if $\,j = 1$} \\ j \, & \text{ if $\,i = 1$} \\ g(i-1,j) + g(i,j-1) \, & \text{ otherwise } \end{cases} $$ I ...
2
votes
0answers
79 views

Lyndon words over the binary alphabet that begin with "00"

Lydon words over the binary alphabet are strings of $1$s and $0$s such that all rotations of the word are strictly lexicographically later. I've been looking at Lyndon words of length $n$, which are ...
1
vote
1answer
49 views

Find coefficient in this expression

I want to find the coefficient of $x^{21}$ in this expression: $(x^3+x^4+x^5+\ldots +x^{10})^4$. The first thing I did was $(x^3+x^4+x^5+\ldots +x^{10})^4=(x^3)^4(1+x+x^2+\ldots+x^7)^4$. So the ...
2
votes
1answer
127 views

Generating Function of Riordan numbers

I would like to find generating function of $f(n)$, where $f(n)$ is defined as following: $$f(n)=\sum_k^n \binom{n}{k}(-1)^{n-k}C_k\text{.}$$ With $C_k=\frac{1}{k+1}\binom{2k}{k}$($C_k$ is the $k^{th}$...

1
2 3 4 5
78