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
0answers
8 views

Non recursive form of Binomial transform of Catalan numbers

My question has already been asked previously and it also has a solution: https://math.stackexchange.com/a/3618692/745043 which asks to make use of the binomial series to derive the non-recursive form ...
0
votes
0answers
15 views

Generating Functions for Networks

I am an undergrad and trying to learn about complex networks but I don't understand the intuition behind the generating functions for networks, I need some sources to read from that explains the ...
1
vote
1answer
35 views

Simple Generating Function Not Working the Way I Interpret it?

Suppose we let A be all sequences of zeros and ones, with generating function $F (z) = 1/(1 − 2z)$. Now suppose we can attach a single or double prime to each $0$ or $1$, giving $0′$ or $0′′$ or $1′$ ...
0
votes
0answers
15 views

Hadamard product of a generating function and a sequence

I have a series $\{g_n\}$ whose values are hard to compute, but I calculated a generating function for it (I know the square root is unconventional, but it results in a nice exponential function): $$ \...
-2
votes
1answer
45 views

What is the distribution of $Y$? [closed]

please help me . what is distribution of Y?
1
vote
1answer
57 views

Generating Functions Combinatorial argument

Show that any number of partitions of $r+k$ into $k$ parts is equal to the number of partitions of $$r+\binom{k+1}{2}$$ into $k$ distinct parts for $r \geq k$. I would like to see a proof for this,...
3
votes
1answer
45 views

Finding generating series

I am not able to figure out this problem based on Combinatorics - How many integer compositions of n, where $n ≥ 0$, are there where every part is even, and there are at least three parts? How should ...
-1
votes
0answers
38 views

Theorem about the Inverse Function [closed]

Let function $A(x) = a_1x + a_2x^2 + a_3x^3 + ...$ such that A(0)=$a_0$=0, and $a_1\ne$ 0, then there are functions $B(t) = b_1t + b_2t^2 + b_3t^3 + ...$, B(0)=0 and $C(u) = c_1u + c_2u^2 + c_3u^3 + .....
-2
votes
0answers
26 views

Composition of two generating functions

If $A(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + ...$ $and$ $B(x) = b_1x + b_2x^2 + b_3x^3 + ...$ are generating functions, where $b_0=0$, then $A(B(x))=a_0 +a_1b_1x+(a_1b_2 +a_2b_1^2)x^2 +(a_1b_3 +...
3
votes
3answers
88 views

Expansion of generating function $\frac{1}{ \sqrt{1-12x+4x^2 } }$

I came across this generating function $$\frac{1}{ \sqrt{1-12x+4x^2 } }$$ How exactly does one expand this series? I have read through some notes, it seems like we need to factorize the denominator, ...
3
votes
0answers
80 views

Ordered Factorization of positive integers with two prime factors

The bottom of this page provides a solution to the number of ordered factorizations of a positive integer with two prime factors: https://mathworld.wolfram.com/OrderedFactorization.html i.e. if $n = ...
0
votes
0answers
20 views

How can i find the lattice-point enumerator of some polytope?

Let $$P=\{(x_1, x_2, \cdots ,x_5)\in \mathrm{\Bbb R^5} \mid x_i\ge 0,\, x_1+x_2\le 1,\, x_2+x_3\le 1,\, x_3+x_4 \le 1,\, x_4+x_5 \le 1\}$$ The lattice-point enumerator of $P$ is $$L_P(t)=\#\{(x_1, ...
1
vote
0answers
55 views

Generating function for $\sum_{i=0}^{k} {n \choose i} $

I'm looking for ordinary generating functions for the above expression. If it doesn't exist, I'll be open to consider exponential generating functions as well. Edit: I'm actually trying to simplify ...
0
votes
0answers
38 views

Solving a recurrence relation using generating functions - power series form of the partial fraction?

I wanted to solve a recurrence relation of the form $$(a+2b+c)f_{n}=bf_{n+1}+bf_{n-1}+cf_{0}$$ I know how to get the solution using the characteristic equation method but I wanted to solve it using ...
0
votes
0answers
80 views

please help me. I have probability generating function as follows, how can get the mixture distribution of $X$ from it?

$$ G_x (s)=\frac{s \cdot (1-q(1-α+α \cdot s))}{(1-q \cdot s)(1-α+α \cdot s)} $$ Or, in another way, how can I say that a random variable follows a certain distribution with a certain probability and ...
0
votes
1answer
38 views

Proving relation between exponential generating functions whose coefficients count certain types of graphs

Let's there be two exponential generating functions: $A(x)=\sum^\infty_{n=1}\frac{a_n}{n!}x^n$ $B(x)=\sum^\infty_{n=1}\frac{b_n}{n!}x^n$ Sequence ${\{a_n\}}^\infty_{n=1}$ defines number of all ...
1
vote
0answers
20 views

Carleman matrix for sum of two functions

Carleman matrices are useful to express the composition of two functions. Recall that the Carleman matrix of a function $f$ is an infinite matrix whose $i,j$ element is $\frac{1}{j!}\frac{{\rm d}^j}{{\...
0
votes
1answer
25 views

getting probability mass function $f(k)$ from probability generating function $G(s)$?

I have the probability generating function $G(s)$ as following. How can I get the mentioned probability-mass function $f(k)$ from it? $$G(s)=\frac{1+\alpha(1+\mu)-\alpha(1+\mu)s}{(1+\mu-\mu s)(1+\...
1
vote
1answer
24 views

Determine the number of ways to color a 1-by-n chessboard with the colors red, blue, green and orange.

Determine the number of ways to color a 1-by-n chessboard, using the colors red, blue, green and orange if an even number of squares is to be colored red and an even number is to be colored green. ...
0
votes
2answers
61 views

Evaluating 8th derivative of $(e^x-1)^6$ at $x=0$

8 distinct objects are distributed into 7 distinct boxes. Find the number of ways in which these objects can be distributed to exactly 6 boxes. I have solved this question quite easily using method of ...
1
vote
2answers
36 views

Using generating function to solve non-homogenous recurrence relation

The given recurrence relation is: $$ a_{n} + 2a_{n-2} = 2n + 3 $$ with initial conditions: $$ a_{0}=3$$ $$a_{1}=5$$ I know $$G(x) = a_0x^0 + a_1x^1 + \sum_{n=2}^{\infty} a_nx^n $$ and $$ a_{n} = -...
0
votes
0answers
57 views

Closed form for a recurrence relation

Let $\{y_n\}$ be a sequence of positive reals satisfying the following recursive formula: $$y_{n+1} = \frac{1}{3} \left(y_n + \frac{2}{y_n}\right).$$ Now, I am interested in finding out a closed form ...
3
votes
0answers
57 views

Find asymptotics given equation satisfied by generating function.

I'm interested in a sequence of numbers whose ordinary generating function obeys the equation: $$F(z) = 1-z^2+z(F(z))^3.$$ Is there some (relatively simple) way to get a good upper bound on the ...
2
votes
1answer
66 views

How to find the coefficient of $x^k$ in $(x+1)(x+2)\cdots(x+N)?$

We are given $n,k$ and $n$ can be very large ($10^9-10^{14}$) but k is relatively small ($k<=2000$). I tried using sum and product of reciprocal of roots but it fails at the first step itself due ...
2
votes
1answer
40 views

Recurrence relation for increasing sequence of numbers

If $x_1, x_2, \dots, x_n$ is sequence of non-negative integers (of any length including the empty sequence) then $s_k$ is the total number of such sequences such that $x_i \in [k]$ and $x_i \leq \frac{...
0
votes
1answer
23 views

Proof of equivalence of two statements about relationship between two generating functions

I am trying to prove the equivalence of the following two statement: $(a_i)_{0}^{\infty}$ and $(b_i)_{0}^{\infty}$ are infinite sequences of numbers, such that their elements are related in the ...
2
votes
1answer
63 views

Exponential generating function with Stirling numbers

I want to prove in particular this result- $$ \newcommand{\gkpSII}[2]{{\genfrac{\lbrace}{\rbrace}{0pt}{}{#1}{#2}}} \sum_{k \geq 0} \gkpSII{2k}{j} \frac{\log(q)^k}{k!} = \frac{1}{\sqrt{2\pi}} \...
0
votes
0answers
37 views

Find the generating function of $S_n$(Please check my idea)

$Q)$ Let the $S_n$ be the number of the positive roots $(x,y,z)$ of the $x+2y+3z=n$, $n \geq 6$ (I.e. $x>0, y>0$ and $z>0$) Find the generating function $g(x)$ of $S_n + S_{n+1} + S_{n+2}$ ...
2
votes
1answer
103 views

Closed formula for the sum $a^1+a^4+a^9…$

I'm wondering if there is a closed formula for the sum $a^1+a^4+a^9...$ and more generally $a^{1^n}+a^{2^n}+a^{3^n}...$ for real $a$ and $n$ such that $|a|<1$ and $n>1$.
2
votes
2answers
84 views

Generating Function for sum of N dice [or other multinomial distribution] where lowest N values are “dropped” or removed

I came across this interesting question on another StackExchange sub that has not been answered after a couple of years. After searching Meta for protocol and finding this post, I think it's ...
6
votes
1answer
183 views

Find two-index Inverse relations

Solve the following system of $ mn$ equations $$ a_{p,q}=\sum_{i=0}^m \sum_{j=0}^n i^p j^q b_{i,j}, p=0 \ldots m, q=0 \ldots n. $$ where $b_{i,j}$ are unknowns. Of course, for small $m,n$, it is ...
0
votes
0answers
24 views

Ring of formal power series in two real variables

Generating functions for e.g. integer partitions are elements of the ring of formal power series $\mathbb{C}[[q]]$. But if I have a generating function in two variables, say $q$ and $u$, what is the ...
0
votes
0answers
31 views

Interpreting combinatorics in the language of generating functions

Recently I've been trying to make sense of generating functions by trying to create an interpretation for it, so far I've made interpretation of addition, multiplication, division and derivative and ...
7
votes
1answer
98 views

Show that the formal power series $ Q(x)=\frac{x}{1-e^{-x}}$ has the property that the coefficient of $x^n$ in $Q(x)^{n+1}$ is always $1$

When I am looking up the Wikipedia page for the definition of Todd class, it says that the formal power series defined by $$ Q(x)=\frac{x}{1-e^{-x}}=1+\frac{x}{2}+\frac{x^2}{12}-\frac{x^4}{720}+\cdots$...
0
votes
2answers
44 views

Modifying generating functions to work for cases with distinct objects

A committee is made of three people. If there are two men and three woman to choose from, how many committees have one man and two women? Since there is exactly two distinct kinds of people, we must ...
0
votes
0answers
39 views

Find an exponential generating function

Find an exponential generating function for the number of selected object arrangements of five different types, with a maximum of five of each type.
2
votes
3answers
40 views

Generating functions to calculate finite permutations

Ok, so suppose, I roll a seven sided die (has an extra side of 0) three times to find how many ways I get a sum of nine, I need take coefficent of $ x^9$ in this, $$ S=(1+x+x^2 + x^3 + x^4 + x^5 + x^...
0
votes
1answer
280 views

Number of strings with one element as the most common element

Consider the number of strings formed from the set $\{1,2,3,4,5\}$ of length $n$. What is the number of strings in which the number of occurrence of $1$ is greater or equal to the number of occurrence ...
0
votes
0answers
15 views

Number of $r$ permutations of $n$ objects of which there are $n_i$ objects of kind $ob_i$

Number of $r$ permutations of $n$ objects of which there are $n_1$ objects of kind $\text{obj}_1$ , $n_2$ objects of kind $\text{obj}_2$, $n_3$ objects of kind $\text{obj}_3$. We are limiting the ...
1
vote
2answers
58 views

Proving $n$-th term formula of Fibonacci sequence using generating function

I am trying to get the formula $F_n = \frac{\phi^n - \psi^n}{\phi - \psi}$ using generating functions. I managed to find that $G_F(x) = \frac{1}{1 - x - x^2}$ then I used partial fraction ...
1
vote
2answers
47 views

What is the number of $6$ digit positive integers whose sum of the digits is at least $52$?

What is the number of $6$ digit positive integers whose sum of the digits is at least $52$? My kind of approach was: I thought to use Multinomial Theorem concept here. So my primary aim was to find ...
1
vote
1answer
58 views

Combinatoric question about coefficients

What is the coefficient of $x_1x_2x_3x_4x_5x_6$ in the product : $\prod_{i=1}^6 (x_1+x_2+x_3+x_4+x_5+x_6-x_i)?$ I tried with Generating function but didn't succeed. Thx.
1
vote
0answers
72 views

calculating coefficients of generating functions.

how many ways are there to collect $\$24$ from $4$ children and $6$ adults if each person gives at least $\$1$, but each child can give at most $\$4$ and each adult at most $\$7$? answer: $$(x+x^2 + x^...
2
votes
0answers
69 views

On Logarithmic Derivative transformation

I am curious about a certain transformation called the logarithmic derivative that seems to appear a lot in different cool ideas, for example: The use in generating functions for recursions of the ...
4
votes
1answer
58 views

Interested in a closed form for this recursive sequence.

Consider the following game: you start with $ n $ coins. You flip all of your coins. Any coins that come up heads you "remove" from the game, while any coins that come up tails you keep in ...
2
votes
1answer
29 views

generating functions for the sequence $\{\frac{k(k-1)}{2}\}$ and ${(k+1)(k+2)}$

For the following two sequences: (1) $\{(k+1)(k+2)\}$, (2) $\{\frac{k(k-1)}{2}\}$, I am trying to obtain the generating functions for both of them. I am going through a text finite difference ...
1
vote
1answer
21 views

Generating function for partitions of a number in which no odd number appears twice

What is the generating function for partitions of a number in which no odd number appears twice? Note: twice means that the odd number can't appear three times or more either.
2
votes
2answers
87 views

If we pick a sequence of numbers $(a_k)$ at random, what is the expected radius of convergence of $\sum_k a_k x^k$?

Suppose we pick a sequence of positive integers independently and identically distributed from $\mathbb{N}^+$: call it $(a_k)=(a_0,a_1,a_2,a_3,\ldots)$. If we consider the corresponding generating ...
0
votes
0answers
17 views

Does the order of generating functions imply the order of coefficients?

Suppose that we have two generating functions $f(z)=\sum_{n \ge 0} f_n z^n$ and $g(z)=\sum_{n \ge 0} g_n z^n$ with non-negative coefficients. Assume that the radius of convergence is $\infty$ for both ...
1
vote
0answers
21 views

Resolving an integral equal to the exponential generating function involving the Riemann zeta function

It is well-known that $$-\gamma-\psi\left(1-x\right)=\sum_{n=1}^{\infty}\zeta\left(n+1\right)x^{n}$$ Using the OGF to EGF integral transformation, then $$\frac{1}{2\pi}\int_{-\pi}^\pi (-\gamma-\psi(1-...

1
2 3 4 5
68