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.

1
vote
1answer
13 views

Can someone simplify this expression into Sterling numbers of the second kind

There was a question that was asked as below. How many different ways can you distribute m distinct objects into n distinct bins such that there are no bins with exactly one object. To solve this I ...
1
vote
1answer
27 views

Calculate coefficient $z^n u^j$ of power series in two variables

I'm trying to calculate $$[z^n u^j] \frac{1}{(1-zu)(1-z)} \log \left(\frac{1}{1-zu}\right),$$ where $[z^n u^j] \sum_{n=0}^\infty \sum_{j=0}^\infty F_{n,j} z^n u^j = F_{n,j}$. So I have to ...
0
votes
0answers
23 views

Show with generating functions that every positive integer has a unique decimal representation.

Question: Show with generating functions that every positive integer has a unique decimal representation. Attempt: I've come up with the following to represent the ones, tens, hundreds, so on: $(1+...
1
vote
1answer
53 views

Find the generating function for equation $2x_1+3x_2+5x_3+7x_4=n$ with restrictions and number of solutions for $n = 50$

Question: Find the generating function for the number integer solutions of the equation $2x_1+3x_2+5x_3+7x_4=n$, where $0 \leq x_1, 4 \leq x_2,4 \leq x_3,$ and $5 \leq x_4$, and find the number of ...
0
votes
2answers
60 views

How many solutions are there to the equation $x_1+x_2+x_3+x_4+x_5=30$ with restrictions using generating functions?

How many solutions are there to the equation $x_1+x_2+x_3+x_4+x_5=30$ where $a) 2 \leq x_1 \leq 4$, and $3 \leq x_i \leq 8$, for all $2 \leq i \leq 5$. $b) 0 \leq x_i$ for all $1 \leq i \leq 5$, ...
1
vote
3answers
81 views

How to expand $\frac1{(1-x)(1-x^2)(1-x^5)}$

How do I expand $$\frac1{(1-x)(1-x^2)(1-x^5)}$$ I need to find the coefficent of $x^9$, but I also want to be able to derive the general form. The only method I could thing of was to expand the $...
0
votes
1answer
26 views

In a probability generating function, what exactly is the parameter for G(z)?

For instance, given $\DeclareMathOperator{\P}{\mathbb{P}} \DeclareMathOperator{\E}{\mathbb{E}} G(z) = \E z^X$, what exactly is $z$? and also what does the generating function actually give you? ...
0
votes
0answers
34 views

Finding a generating function for the set of all integer partitions [duplicate]

I know that integers can be partitioned into the different ways to get that integer. For example: $$4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1$$ can be written as $$(4),(3, 1),(2, 2),(2, 1, 1), (1, 1, 1, 1)...
0
votes
0answers
22 views

Generating function in two variables

I am not familiar with generating functions. So please help here, I have the following equation. $$f(x, y)=f(x-1, y-2)+f(x,y-1)$$ Can there be a generating function for this? If so, what is it?
0
votes
1answer
25 views

Building a Generating Function to Represent an Integer Partition

From a Miklos Bona combinatorics textbook, I'm at an almost total loss. My professor recently discussed products of generating functions, so I suspected this problem might relate. The only strategy ...
1
vote
1answer
38 views

Find $a_n$ in terms of $b_n$ given $b_n = \sum_{k=0}^{n} {n \choose k} a_k$

Given sequences $a_n$ and $b_n$ satifying $$b_n = \sum_{k=0}^{n} {n \choose k} a_k$$ I am required to find $a_n$ in terms of $b_n$ My attempt: The generating fuction for $b_n$ will be \begin{align} ...
1
vote
2answers
55 views

Proving correspondence and partitions via generating functions, or at least I think so.

Let $A=\{2,6,10,14,\ldots\}$ be the set of integers that are twice an odd number. Prove that, for every positive integer $n$, the number of partitions of $n$ in which no odd number appears more than ...
-2
votes
1answer
46 views

Generating function into polynomail

i) Find a generating function expression of a sequence with terms $$d_n=\sum_{p=0}^n p^3$$ using operations on the geometric series $\sum_{n\geq 0} x^n$ ii) Derive a polynomial (in $n$) ...
0
votes
0answers
38 views

Wilf's generatingfunctionology 1.6.6

So, I was reading book on generating functions(https://www.math.upenn.edu/~wilf/gfology2.pdf), and I am not sure what was the reasoning behind setting $x=1/r$ in $(1.6.6)$, or rather is it just ...
0
votes
0answers
37 views

Finding an expression for the generating function of a sequence using algebraic operations

All done using geometric series $\sum_{n>0} ^{\infty} x^n$ a) Find expression for the generating function of the sequence with terms $q_n=n^4$. b) Find expression for the generating function of ...
0
votes
0answers
42 views

Simplifying $ \sum_{1\cdot m_1 + 2\cdot m_2 + \cdots + n \cdot m_n = n} \frac{1}{m_1 ! m_2 ! \cdots m_n !} t^{m_1 + \cdots + m_n} $

Does anybody know how to simplify the expression like the following? $$ \sum_{1\cdot m_1 + 2\cdot m_2 + \cdots + n \cdot m_n = n} \frac{1}{m_1 ! m_2 ! \cdots m_n !} t^{m_1 + \cdots + m_n} $$ This ...
1
vote
1answer
21 views

For which $c$ is $G$ a generating function?

Given $G(x)= c \ln(1-{x \over 2})$, $x \in \mathbb R$, for which $c \in \mathbb R$ is $G$ a probability generating function? I am aware of the definition of a generating function but I'm having a ...
2
votes
1answer
32 views

Solve $G(n)=a \, G(n-1)+b$ by generating functions

I'm having a lot of difficulty solving $$G(n) = a \, G(n-1)+b \hspace{5mm} \text{for} \hspace{5mm} n=2,3,...$$ and a given $a$ and $b$ by generating functions. I can find a general formula for the n-...
0
votes
1answer
59 views

Mathematically correct way of using the generator functions

Let $(F_n)_{n \in \mathbb{N}}$ be the Fibonacci sequence: $F_0=0$, $F_1=1$ and $\forall n \in \mathbb{N}: F_{n+2}=F_{n+1}+F_{n}$. Now let $$f(x):=\sum\limits_{n \in \mathbb{N}} F_n x^n$$ So we have ...
2
votes
3answers
53 views

Finding a particular coefficient in a polynomial

I'm trying to get the coefficient of $x^6$ of this polynomial product: $$x^2(1+x+x^2+x^3+x^4+x^5)(1+x+x^2)(1+x^2+x^4).$$ I know with infinite series, you can use the closed form solution of the ...
3
votes
2answers
44 views

Generating function for number of words with no k consecutive 0's?

I am trying to determine the generating function for the sequence $a_n$, where $a_n $ is the number of words of length n over the alphabet {0, 1, 2, ..., q-1} that do not contain the subword $0^k$. I ...
0
votes
0answers
18 views

Recurrence relation with forward and backward dependences

I'm trying to obtain a closed form corresponding to each term of the series given by: $f(m,n)=\delta f(m-1,n+1)+(1-\delta) f(m+1,n-1)$ $f(0,k)=1$, $f(k,0)=0, f(0,0)=0$ $\delta\in(0,1)$, $m,n\geq0$, ...
2
votes
1answer
40 views

Why does subtracting function with the same singularities make it analytic

When estimating asymptotics of a series from its generating function, we look for singularities (this makes sense to me) and then try to remove them (this also makes sense) by subtracting a function ...
0
votes
0answers
15 views

Obtaining generating function for recurrence “time”

I was working on some exercise questions in Chapter 2 of Karlin and Taylor's "A First Course in Stochastic Processes." I was stuck on question 2.12 to be specific. Regarding a 1-dimensional random ...
3
votes
1answer
59 views

Erdos Selfridge and some intuition regarding $f(x^2) - f(x)^2 = g(x^2) - g(x)^2$ and

The Erdos Selfridge problem asks that For any (multi)set $A$ of $n$ real numbers $\{ a_1, \cdots, a_n \}$, define the (multi)set $S_A = \{ a_i+a_j | i < j \}$. Find all positive integers $n$ ...
1
vote
1answer
20 views

Generating function: Collecting dollars from children and adults.

Here is the problem: 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 ...
2
votes
0answers
51 views

Generating function for seven constrained die rolls

Is it possible to get a generating function when you throw 7 distinct dice that gives a sum of r if the first 3 dice are odd and the last 3 are even . no mention of the 4th (middle die which can be ...
3
votes
1answer
50 views

Generating function problem, and distributing candy to kids.

Here is the problem: Determine how many ways I can distribute $80$ candies to $3$ kids, such that: $\bullet$ The first kid receives an arbitrary number of candies (possibly $0$). $\bullet$ The ...
17
votes
1answer
212 views

If $\sum_{n=1}^{\infty}\frac{1}{p(n)}\in\mathbb{Q}$, is $\sum_{n=1}^{\infty}\frac{n}{p(n)}\in\mathbb{Q}$?

Suppose $p(n)$ is a polynomial with rational coefficients and rational roots of degree at least $3$. If we know $$\sum_{n=1}^{\infty}\frac{1}{p(n)}\in\mathbb{Q}$$ are we able to infer that $$\sum_{n=...
0
votes
1answer
51 views

Finding a generating function

Suppose I have 4 numbers, $x_0,x_1,x_2$ and $x_3$, and the sum, $$x_0+x_1+x_2+x_3$$ I put the constraint that $x_0$ and $x_3$ are either 1 or 0, and $x_0$ and $x_3$ can be equal or between 0 to 3 (0,...
1
vote
5answers
67 views

About the identity $1=(1-x)(1+x+x^2+\cdots)$

I'm learning about generating function. I have trouble understanding why $$1=(1-x)(1+x+x^2+\cdots),$$ if in the second parenthesis it stop at any $k\in\mathbb N, x^k$ then an additional term $(-x)(x^...
1
vote
2answers
74 views

Coefficient of a generating function

I have the following generating function, $$f(x)=(1+x+x^2+x^3)^4$$ I want to find the $[x^5]$ coefficient, to do so I wrote, $$[x^5]f(x)=[x^5](1+x+x^2+x^3)^4=[x^5]\left(\frac{1-x^4}{1-x}\right)^4= [...
0
votes
0answers
20 views

How to Solve box balls with Generating Functions

I have a question that I thought of. There are two boxes. One box has an infinite number of balls, distributed so that there is $1$ ball labeled $1,$ $2$ balls labeled $2,$ and for any positive ...
0
votes
1answer
27 views

Using Generating Functions to Distribute Candies

Determine how many ways I can distribute $80$ candies to $3$ kids, such that: $\bullet$ The first kid receives an arbitrary number of candies (possibly $0$). $\bullet$ The second kid receives an ...
2
votes
4answers
55 views

How to get series coefficient for $\frac{1}{(1-x)^3}$?

I was trying to use generating functions to get a closed form for the sum of first $n$ positive integers. So far I got to $G(x) = \frac{1}{(1-x)^3}$ but I don't know how to convert this back to the ...
6
votes
2answers
99 views

Differentiating closed formulas in formal power series

In Herbert Wilfs' book gfology, the generating function is defined "formally" as If $\displaystyle f = \sum_{i \geq 0} a_i x^i$, and $\displaystyle g = \sum_{i \geq 0} b_i x^i $, we define ...
1
vote
2answers
29 views

If there are m items of one kind,n items of another kind and so on, then the number of ways of choosing r items of these items is

Please prove this result: If there are m items of one kind,n items of another kind and so on, then the number of ways of choosing r items of these items is =Coefficient of $x^r$ in $(1+x+x^2+...+x^...
0
votes
0answers
35 views

Find $f(n)$ such that $\sum_{k=1}^{n} k^{1.23}\sim f(n)$

Find $f(n)$ such that $\sum_{k=1}^{n} k^{1.23}\sim f(n)$. I tried to use generating functions. To proceed I need to calculate $\sum_{n\geq0} n^{1.23}x^{n}$ (or something asymptotically similar, ...
4
votes
2answers
76 views

Number of ways to pay (generating functions)

I've just started learning generating functions. Let $a_n$ be the number of ways in which you can pay $n$ dollars using 1 and 2 dollar bills. Find the generating function for $(a_0, a_1, a_2, \ldots)$...
4
votes
3answers
99 views

Find the generating function for sequence $1,2,4,0,8,24,120,184,312,56,568,1592,…$

I'm having trouble finding a generating function for the sequence that has a closed form. The sequence can be deduced using two powers, with alternating negative and multiples of three as shown: ...
0
votes
2answers
46 views

Truncating a generating function

It is true that the generating function for the number of ways to partition an integer $n$ into a sum of ones is \begin{align} f(x) = 1 + x + x^2 + x^3 + \cdots \end{align} But I don't see how the $1$ ...
1
vote
0answers
48 views

Find all strings that satisfy certain conditions

Find all strings $w \in \{0,1,2\}^n$ such that 1) each number occurs at least once 2) $0$ does not occur as the first digit, $1$ does not occur as the second digit and $2$ does not occur as ...
2
votes
2answers
45 views

Solve $2a_{n-2} = a_n + a_{n-1}$ using generating function

Need to solve: $$2a_{n-2} = a_n + a_{n-1}$$ with: $a_0 = 0$ and $a_1=1$ I get: $$f(x) = \frac{2x^3-x^2-x}{2x^2-x-1}$$ so I tried to scompose the denominator and I get: $$f(x) = \frac{2x^3-x^2-x}{(...
1
vote
2answers
31 views

Elementary explanations for common terms?

I was exploring OEIS, and decided to make the following query: http://oeis.org/search?q=196680&sort=&language=english&go=Search The first 2 entries, which are sequences with generating ...
4
votes
0answers
32 views

Expansion of Elementary Symmetric Functions

Let $$e_k(X_1,X_2,\dots, X_n)=\sum_{1\le i_1<i_2<\dots<i_k\le n}X_{i_1}X_{i_2}\dots X_{i_k}$$ be the elementary symmetric function of degree $k$ and $$p_k(X_1,X_2,\dots, X_n)=\sum_{1\le i\le ...
13
votes
1answer
409 views

Finding a combinatorial formula for the following sequence of tables

While studying a subject in mathematical physics and topology (which is not necessarily relevant to this question anyway), I bumped into the following sequence of tables, let's call them $M_0, M_1, ...
2
votes
1answer
57 views

How to manipulate the given sum using Snake Oil method?

To solve : $$\frac{\binom{100}{1}}{100} + \frac{\binom{100}{2}}{99} + \frac{\binom{100}{3}}{98} +....+ \frac{\binom{100}{100}}{1} $$ I assumed the general form as $$\sum_{k=0}^\infty \frac{1}{n-...
5
votes
2answers
118 views

A tricky combinatorial sum

I'm looking for a clean expression of the following combinatorial sum : $$\sum\limits_{k=0}^{n}\frac{{n \choose k}^2}{{{2n} \choose {2k}}}$$ I recall being told it does have a neat expression. ...
1
vote
1answer
53 views

How to find the $n$- th term of the generating function $\frac{1}{(1-x-x^2)}^k$?

I know how to find the $n$ -th term for $k = 1$, of $\frac{1}{\left(1-x^2-x\right)^k}$ but I want to know if there's a general formula for $k > 1$.
0
votes
0answers
60 views

Need help finding a generating function

I need to find the generating function for $a_n$ where: $$a_{2k}=\dfrac{(-1)^k}{(2k)!}$$ $$a_{2k+1}=\dfrac{1}{(2k+1)}$$ $$k \geq 0$$ The solution is: $$f(x)=\cos(x)+\operatorname{atanh}(x)$$ So ...