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
1 vote
1 answer
36 views

Combinatorics - rewriting generating function as power series

I have been working on the following question: Find a recurrence relation for the number of regions created by $n$ mutually intersecting circles on a piece of paper (no three circles have a common ...
Mai's user avatar
  • 19
1 vote
0 answers
47 views

How to come up with the generating function of an elliptic curve?

Having watched the otherwise splendid Numberphile video with Edward Frenkel explaining the Langlands program, two mysteries remained completely open to me: Given the equation $y^2 + y = x^3 - x^2$ how ...
Hans-Peter Stricker's user avatar
3 votes
2 answers
711 views

How to put 6 rooks which they wont' attack each other?

We're presented with the following chessboard, and we aim to determine the number of arrangements in which 6 rooks can be placed without threatening each other. It's crucial to note that rooks cannot ...
Ariana's user avatar
  • 371
1 vote
0 answers
78 views

Counting the number of possible sequences increasing by no more than one

Count the number of sequences of integers $a_1, a_2, \dots, a_n$ such that $$ a_1 = 0 \quad\text{and}\quad 0 \leq a_{i+1} \leq a_i + 1 \quad\text{for}\quad 1 \leq i < n. $$ At first, I was ...
Email's user avatar
  • 29
2 votes
0 answers
127 views

When a sequence satisfies $a_n= \sum_{i=1}^{n-1} f_i(n) a_i+ g(n)$?

Question Given a sequence $a_n$ when it is possible to express such sequence as a "linear recurrence relation with not constant coefficients"? i.e. when $$ a_n= \sum_{i=1}^{n-1} f_i(n) a_{i} ...
Marco's user avatar
  • 1,852
5 votes
0 answers
263 views
+50

Generating functions in countable commutative monoids

Let $f: \mathbb{N}_0 \rightarrow \mathbb{C}$ be a function. The power series of $f$, if it exists, is defined as the sum $\sum_{n \in \mathbb{N}_0}^{} f(n)q^n$ where $q \in \mathbb{C}$. Note that for ...
Tian Vlašić's user avatar
1 vote
4 answers
130 views

difficulty for deriving the series representation of $f(x)=\frac{1+x^3}{(1+x)^3}$

I was given the generating function $f(x)=\frac{1+x^3}{(1+x)^3}$ and I was asked to find $a_9$. I attempted to break it down into two parts: $$f(x)=\frac{1}{(1+x)^3}+\frac{x^3}{(1+x)^3}$$ For the ...
Ariana's user avatar
  • 371
-4 votes
0 answers
25 views

Find the generating function of this infinite sequence [closed]

Find the generating function of this sequence: 2,4,7,2,1,1,1,1,1,1,…
Student's user avatar
  • 23
2 votes
1 answer
46 views

Does the moment generating function exist?

Suppose $\nu$ is a probability measure on the positive integers $\{1,2,3\dots,\}$, and let $\pi_{a}$ and $\pi_b$ be Poisson distributions on the positive integers with parameter $a,b$ respectively, ...
JY0's user avatar
  • 71
-6 votes
0 answers
62 views

Generating function for the following binomial coefficients [closed]

I'm interested in the following sum: $\sum_{n=0}^{\infty}{n \choose k}x^k$ I know that if the binomial coefficient gets replaced by ${n+k \choose k}$ the generating function looks like $(1-x)^{-k}$ ...
Haimu Wang's user avatar
0 votes
0 answers
117 views

Generating function of modified Bessel function of first kind

I am doing some analytical work in the field of wind turbine wakes. The wake is often described as a 2D Gaussian function. When I integrate this 2D Gaussian function over a circle of an arbitrary size ...
Karim Ali's user avatar
0 votes
1 answer
81 views

Creating a generating function for weak compositions

As far as I know, generating functions are just formal power series, with each $x$ term being a placeholder for the coefficient that I actually care about. This is simple(?) for certain problems, like ...
Hat's user avatar
  • 317
2 votes
1 answer
82 views

Integral representation for reverse Bessel polynomials

$\DeclareMathOperator ZZ$Series solutions to partly invert $e^x(x^2+a)$ and $e^xx(x+a)$ exist when more general quadratic-exponential equations are reduced. Using the reverse Bessel polynomials $p_n(x)...
Тyma Gaidash's user avatar
1 vote
1 answer
87 views

Understanding Transfer Principle About Formal Power Series

The theorem I am referring to is from "The Concrete Tetrahedron" by Kauers and Paule, which states: Theorem 2.8 (Transfer Principle) Let $a(z) = \sum_{n=0}^{\infty} a_nz^n$ and $b(z) = \sum_{...
faceclean's user avatar
  • 7,139
3 votes
1 answer
352 views

$z_2+z_3+z_4+z_5=n$ satisfing $i\not\mid z_i$

In multiple choice test had a problem: How many positive integer solutions of $z_2+z_3+z_4+z_5=n$ satisfing $i\not\mid z_i$ Answer: A. $\displaystyle\sum_{k=2}^n \left\lfloor\dfrac{{k\choose 2}}{5}\...
hxthanh's user avatar
  • 1,457
0 votes
1 answer
63 views

What's the generating function of the recurrence relationship $(n+1)a_{n+1} = 3a_n + 1$

I was playing around with this interesting recurrence relationship $(n+1)a_{n+1} = 3a_n + 1$ with $a_0 = 1$, but I couldn't get the final answer $f' = 3f + \frac{1}{1-x}$. I have attempted with two ...
HackBear's user avatar
2 votes
1 answer
46 views

Expected value and variance of the random binary number generator

Problem from an old exam: The random number generator $X$ produces random numbers following a Poisson distribution with parameter $\lambda$. Unfortunately, these numbers are too small, so we decided ...
Michał's user avatar
  • 703
2 votes
1 answer
72 views

Proving Bertrand's Ballot Theorem using Generator Functions

As a learning exercise, I am trying to understand if it is possible to prove (the famous) Bertrand's Ballot Theorem (https://en.wikipedia.org/wiki/Bertrand%27s_ballot_theorem) specifically using ...
Uk rain troll's user avatar
0 votes
0 answers
56 views

Finding the Intersection of two known integer sets

The two sets I am hoping to intersect are the set of triangle numbers and quarter-squares. From those linked resources I have the generating function for both sets. $$f_{A000217}(x) = \frac{x}{(1-x)^3}...
Brandan's user avatar
  • 41
2 votes
0 answers
76 views

What is the most efficient way to find the coefficient before the $n$-th term in this generating function?

I am calculating the square of the Pascal matrix (i.e. the infinite lower triangular matrix with entries $A_{nk}={n\choose k}$) using the theory of Riordan arrays, and have obtained (or so I believe) ...
Daigaku no Baku's user avatar
1 vote
1 answer
63 views

Generating function for 'inversions' in max-heap

Problem from an old exam: A full binary tree of height $n$ has $2^n-1$ vertices. We randomly insert all numbers $1, \ldots, 2^n-1$ into it (each permutation is equally likely). An error is defined as ...
Michał's user avatar
  • 703
1 vote
1 answer
74 views

Generating function for number of inversions

Problem from an old exam: Let $X_n$ be the number of inversions in a random permutation $\pi:\{1, \ldots, n\} \rightarrow\{1, \ldots, n\}$. (Each of the $n$! permutations is equally likely.) Find the ...
Michał's user avatar
  • 703
2 votes
3 answers
278 views

Find explicit formula for generating function

I'm given the following recurrence: $a_0 = 3, a_n = 2a_{n-1} - 7$ for $n \ge 1$. I did the following steps: $$A(x) = \sum_{n=0}^\infty a_nx^n$$ $$a_n = 2a_{n-1} - 7$$ $$\sum_{n=1}^\infty a_nx^n = 2\...
popcorn's user avatar
  • 197
0 votes
2 answers
50 views

getting wrong solution to system of recurrences

i have been stuck on this question for hours now and would really appreciate any help. So i have the following system of recurrences $$a_n=1+a_{n-1}, b_n = 1+b_{n-1}+2a_{n-1}, a_1=b_1=1, n\geq 2.$$ ...
eagle I 's user avatar
0 votes
1 answer
41 views

Integer partitions with summands bounded in size and number

This book says it's easy, but to me, it's not. :( As for 'at most k summands', in terms of Combinatorics, by using MSET(), $$ MSET_{\le k}(Positive Integer) = P^{1,2,3,...k}(z) = \prod_{m=1}^{k} \frac{...
David Lee's user avatar
  • 133
0 votes
1 answer
37 views

Generating function given a recurrence relation

In this case I'm here again, now with a problem regarding generating functions. Now, I am asked to find the generating fuction $f(x) = \sum_{n = 0}^{\infty}a_nx^n$ such that $a_n = \frac{a_{n-3}}{n} \...
Daniel C.'s user avatar
  • 1,227
1 vote
0 answers
58 views

Exponential generating function of binomial coefficients in pascal's triangle

Does there exist any closed form formula for the following exponential generating function: $$ F_k(x) = \sum_{n=0}^{\infty} \frac{\binom{2(k+n)-1}{n}x^n}{(k+n)!} $$ The coefficients in the numerator ...
user270610's user avatar
1 vote
0 answers
36 views

Connecting generating functions for binomial and negative binomial distributions

The generating function for the binomial distribution can be expressed as: $((1-p)+p)^r=\sum\limits_{k\ge 0} \binom{r}{k}(1-p)^k p^{r-k}$ $=\sum\limits_{k\ge 0} \text{ probability of $k$ failures when ...
Terence C's user avatar
  • 303
0 votes
1 answer
72 views

Distribution of the sum of points for non-standard dice

Question from my last exam: A cubic die is called fair if its sides are labeled with integers, and each side has an equal probability of landing face up. When multiple fair dice are rolled, the ...
Michał's user avatar
  • 703
2 votes
1 answer
52 views

Correct another Hermite polynomial generating function

This is a companion question to another one that I posted here yesterday. In the acclaimed encyclopedia of special functions by Ismail and Van Assche published in 2020 the following generating ...
user12030145's user avatar
  • 1,036
1 vote
0 answers
49 views

Generating Function for Modified Multinomial Coefficients

The multinomial coefficients can be used to expand expressions of the form ${\left( {{x_1} + {x_2} + {x_3} + ...} \right)^n}$ in the basis of monomial symmetric polynomials (MSP). For example, $$\...
Bear's user avatar
  • 51
7 votes
1 answer
87 views

Correct Hermite polynomial generating function

In the acclaimed encyclopedia of special functions by Ismail and Van Assche published in 2020 the following generating function is given for Hermite polynomials (p. 77, eq. (3.8.48)), without source: $...
user12030145's user avatar
  • 1,036
1 vote
0 answers
46 views

What is the difference between counting plane tree and binary tree by Catalan numbers? [duplicate]

Problems: Prove that the number of plane trees with $(n+1)$ vertices is $n-th$ Catalan number $C_n$. For this problem: I have found a solution in a post on Mathstack Prove that number of non-...
Tung Nguyen's user avatar
  • 1,208
4 votes
1 answer
313 views

Why do Bell Polynomial coefficients show up here?

The multinomial theorem allows us to expand expressions of the form ${\left( {{x_1} + {x_2} + {x_3} + {x_4} + ...} \right)^n}$. I am interested in the coefficients when expanding ${\left( {\sum\...
Bear's user avatar
  • 51
1 vote
1 answer
89 views

Expanding series to obtain desired words using generating functions

I am working on analytic combinatorics by myself. According to theorem, $$W\bigg(z,\frac{az}{1+az},\frac{bz}{1+bz},\frac{cz}{1+cz}\bigg)=\bigg(1-\frac{az}{1+az}-\frac{bz}{1+bz}-\frac{cz}{1+cz}\bigg)^{-...
user avatar
1 vote
2 answers
178 views

Value of $\sum_{k=0}^n \binom{n}{k}^2$ using analysis.

I'm trying to solve this following question: By deriving $f(x) = x^n (1+x)^n$ $n$ times, determine the value of $\sum_{k=0}^n\binom{n}{k}^2$. My attempt on this was to express $f(x)$ in 2 ways: $f(x)...
Sewshley's user avatar
  • 135
0 votes
2 answers
56 views

Alternating hockey stick sum $\sum_{m=k}^M (-1)^m \binom{m}{k}$

I'd like to calculate the following sum efficiently $$S(k, M) = \sum_{m=k}^M (-1)^m \binom{m}{k}$$ I've tried to use generating functions and write $$ S(k,M) = \sum_{m=k}^M [x^k] (-1-x)^m = [x^k] \...
ploosu2's user avatar
  • 8,445
2 votes
1 answer
103 views

Finding a exponential generating function

I'm trying to find a generating function of a series expression, any suggestions would be appreciated. $S=1+\alpha(x-\alpha t)a+[\alpha^2(x-\alpha t)^2+2\alpha\nu(x-2\alpha t)]a^2/2!+[\alpha^3(x-\...
maverick005's user avatar
6 votes
1 answer
224 views

Computing Asymptotic Expansion of Coefficients of Implicitly Defined Power Series

Background: I've been studying the text "Analytic Combinatorics" (amazing book!) and related papers in an effort to intuit the methods therein. My tangentially related background in spectral ...
random precision's user avatar
2 votes
1 answer
103 views

Finding $ \sum_{k=0}^n (-1)^k A_k {n \choose k}, ~\text{if}~ (1+x+x^2)^n=\sum_{k=0}^{2n} A_k x^k$

Finding $S=\sum_{k=0}^n (-1)^k A_k{n\choose k}$, if $(1+x+x^2)^n=\sum_{k=0}^{2n} A_k x^k.$ \begin{align} (1+x+x^2)^n &= A_0+A_1x+A_2x^2+\dots+A_nx^n+\dots+A_{2n}x^{2n} \\ (1-1/x)^n &= {n \...
Z Ahmed's user avatar
  • 43.1k
1 vote
1 answer
68 views

Finding a value using generating functions

In a certain exercise I have been asked to find the value of $\sum_{k\geq0}{n+k\choose2k}\cdot2^{n-k}$. I think that the approach written in the following paragraph seems one of the possible "...
Daniel C.'s user avatar
  • 1,227
3 votes
0 answers
95 views

Infinitely many Ramanujan-type sum of cubes and unimodular matrices?

Ramanujan's sum of cubes identity is defined by the generating functions (easily calculated by Wolfram), \begin{aligned} \sum_{n=0}^\infty a_{n} x^n &= \frac{1+53x+9x^2}{1-82x-82x^2+x^3} = 1,135,...
Tito Piezas III's user avatar
1 vote
2 answers
99 views

Coefficient of polynomial of $x^k$

Consider a polynomial of power n: $P(x)=1+x+x^2+\dots+x^n$ How do I find coefficient of $x^k$, where $0\le k\le 3n$ of the polynomial $P^3(x)$? I have tried plugging in different values of $n$ to find ...
JavaGamesJAR's user avatar
1 vote
1 answer
93 views

Property of functions over generating functions

I know that if $f(x)=g(\frac{x}{1-x})$, then $f(\frac{x}{1+x})=g(x)$ when $f(x)$ and $g(x)$ are function. When I read about generating functions , I saw that "Generating functions are not ...
user avatar
1 vote
1 answer
75 views

Is there a function $f$ such that $f(-x)=\sum_{k=0}^{+\infty}{\frac{f(k)}{k!} x^k}$?

You can rewrite this as the requirement that $(-1)^k f^{(k)}(0)=f(k)$ but I do not feel this helps much. I also saw some similarities with Ramanujan's master theorem/interpolation formula but I also ...
user146125's user avatar
0 votes
2 answers
140 views

Definite integral of $x\sin^n(x)$, recurrence relations, $\zeta(3)$

This is my first ever post on this website, so bear with me. I'm trying to find a general solution to the following integral: $$\int_{0}^{\pi/2}x\sin^s(x)dx$$ With respect to "$s$" So ...
Jofo's user avatar
  • 9
6 votes
2 answers
514 views

Provide a closed formula based on the generating function $\frac{x}{1+x+x^2}$

Recently, when I self-learnt Discrete Mathematics and Its Applications 8th by Kenneth Rosen, I did only the even-numbered exercises which the author offers the detailed description instead of the odd ...
zg c's user avatar
  • 166
0 votes
0 answers
76 views

Generating function problem

Using generating functions, find the number of ways to divide $n$ coins into $5$ boxes that meet the condition that the number of coins in boxes $1$ and $2$ is an even number that does not exceed $10$,...
Tiago's user avatar
  • 53
0 votes
2 answers
79 views

Ordinary generating function for Lah's numbers $L(n,k)$

I'm studing signed Lah's numbers $L(n,k) = (-1)^n\frac{n!}{k!}\binom{n-1}{k-1}$. It's easy to show that exponential generating function for the sequence $\{L(n,k)\}_{n\geq0}$ is equal to $$ \sum\...
Orel_Algebraist's user avatar
0 votes
0 answers
55 views

Given the generating function for the sequence $a_n$, can we find the generating function for $a_na_{n+1}$?

Given $f(x) = \sum_{n \geq 0} a_nx^n$, can we find a function $g(x) = \sum_{n \geq 0} a_na_{n+1}x^n$? When we solve the recurrences of the form $a_na_{n+1} = h(n)$, it is normal to define $b_n = (-1)^...
hellofriends's user avatar
  • 1,436

1
2 3 4 5
89