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.

learn more… | top users | synonyms

1
vote
1answer
20 views

Understanding inclusion exclusion principle (with example question).

Hi here is a question that i solved with generating functions , and i try to solve the same question with the inclusion exclusion principle. Question: We have four type of balls - ...
0
votes
2answers
23 views

Why Can I divide generating function by $x$

In many books on generating functions author performs following operation to shift coefficients of $F(x) = \sum_i f_ix^i$ to the left $${F(x) - f_0} \over x$$ which in can be written as $$(F(x) - ...
1
vote
1answer
15 views

Generating Functions and Polynomial Expansions

Give a formula similar to: $\frac{1-x^{m+1}}{1-x} = 1 + x + x^2 + ... + x^m$ For the following (a) $1 + x^4 + x^8 + ... + x^{24}$ (b) $x^{20} + x^{40} + ... + x^{180}$ Workings a. $1 + x^4 + x^8 ...
2
votes
2answers
39 views

Generating function for Pell numbers

Problem: The Pell numbers $p_n$ are defined by the recurrence relation \begin{align*} p_{n+1} = 2p_n + p_{n-1} \end{align*} for $n \geq 1$. The initial conditions are $p_0 = 0$ and $p_1 = 1$. a) ...
1
vote
1answer
27 views

Generating function with a given weight function using 3 variables

So I'm given a set: [10] x [2] x $\mathbb N$ with a weight function: $w(a, b, c) = 4a + 2b + c$ And i'm asked to determine the generating series of this, but I'm confused due to the 3 variables.. I ...
0
votes
1answer
25 views

Generating Functions for Fruits

Find a generating function $(x_1, x_2, ..., x_m)$ whose coefficients of $x_1^{r_1} x_2^{r_2}\ldots x_m^{r_m}$ is the number of ways $n$ people can pick a total of $r_1$ fruits of type $1$, $r_2$ ...
0
votes
1answer
9 views

Problem with finding generating function for a sequence

Problem: Determine the generating function for the sequence $(a_k)$ given by $a_0 = 2$ and $a_k = 3a_{k-1} - 4$ for $k \geq 1$. Solution: We define $f(x) = \sum_{k=0}^{\infty} a_k x^k$ for the ...
0
votes
0answers
17 views

Explicit formula of f(n+1) = f(n) + k*(M - f(n))*(f(n) - m)

I have a lot of difficulty trying to translate the worked examples of generating functions I see online because they all use first order terms. That said, I would like to know how to approach ...
1
vote
1answer
26 views

Generating Functions for Multinomials

Find a generating function $(x_1, x_2, ... , x_m)$ whose coefficients of $x_1^{r_1}x_2^{r_2} ... x_m^{r_m}$ is the number of ways $n$ people can pick a total of $r_1$ candies of type $1$, $r_2$ ...
0
votes
1answer
11 views

Some first term of this sequence.

Let a generating function: $$(x^n A(x))' $$ How to determine some first term of this sequence. Thanks in advance.
-1
votes
1answer
24 views

Generating function. Inverse.

Let $D(x)= (x+1)(x^2 +1 ) (x^3 +1 ).... $ and let F(x) be inverse of $D(x)$ I know, that $ D$ is the number of ways to write n as a sum of positive integers without repeated summands. Sums only ...
0
votes
1answer
52 views

Generating function $D(x) = (1 + x)(1+x^2)(1+x^3)\cdots$ [on hold]

Let $$D(x) = (1 + x)(1+x^2)(1+x^3)\cdots $$ 1) What is the inverse function of $D(x)$? 2) What sequence is generated by $D(x) $ Please don't vote down, the subject is complicated for me. Sorry ...
1
vote
0answers
19 views

Probability question involving drawing balls from an urn

Suppose there's an urn containing $r$ red balls and $b$ blue balls. At each trial, I'm drawing a ball at random from the urn, without replacement. Let $R$ denote the event of drawing a red ball, and ...
0
votes
0answers
16 views

How to find $a_n$ series from Dirichlet generating function

I am solving problems from Project Euler. Solutions for some of the problems is $n^{\rm th}$ term of a series. I know Dirichlet generating functions. How to find $n^{\rm th}$ term of a series from ...
0
votes
2answers
57 views

The number of nonnegative integer solutions of $x_1+\cdots+x_6=24$ with $x_1+x_2+x_3>x_4+x_5+x_6$

I try to find the number of nonnegative integer solutions of $\begin{align} & {{x}_{1}}+{{x}_{2}}+{{x}_{3}}+{{x}_{4}}+{{x}_{5}}+{{x}_{6}}=24 \\ & ...
2
votes
1answer
44 views

Counterexample for generating function?

This is Exercise 3.1.2 from Achim Klenke: »Probability Theory — A Comprehensive Course«. Exercise: Give an example for two different probability generating functions that coincide at countably ...
19
votes
1answer
3k views

Connection between the Laplace transform and generating functions

As I was sitting through a boring lecture rehashing basic techniques to solve ordinary differential equations, I began thinking about the Laplace transform and scribbled down a few ideas that I've ...
1
vote
1answer
46 views

every number $n\in \mathbb{Z} $ can be represented as sum of different power of $2$

Using generating function prove that every number $n\in \mathbb{Z} $ can be represented as sum of different power of $2$, I mean, that for every $n\in \mathbb{Z}$ $$n=2^{k_1} +2^{k_2} +2^{k_3} +... ...
1
vote
1answer
31 views

Solving recurrences using generating functions

I have the following solution for solving a recurrence using a generating function and I have a question on why it is multiplied by (1-z) and why this causes the second summand to disappear.
1
vote
0answers
37 views

Generating function from a set of binary strings

So this question is in my textbook and there's no solution, so I'm seeing if I can get a confirmation? Q: Let $S$ be the set of all binary strings of length 4, where for each string $a\in S$, the ...
1
vote
1answer
40 views

Generating Functions for Two Variables

Find the generating function for the number of words, from the standard 26-letter alphabet, that have $k$ letter with exactly 1 A and at least 2 Bs. ($k$ will vary) Workings: For the time being I'm ...
0
votes
1answer
78 views

Generating Functions of Partitions?

Show that $2(1-x)^{-3} [(1-x)^{-3} + (1+x)^{-3}]$ is the generating function for the number of ways to toss $r$ identical dice and obtain an even sum. Workings: I'm not too sure on this problem. ...
0
votes
0answers
11 views

Solution to Laguerre differential equation using generating function

This is an exercise in Modern Quantum Mechanics by Sakurai and Napolitano. Follow these steps to show that solutions to Kummer's equation (7.46) can be written in terms of Laguerre polynomials ...
2
votes
1answer
27 views

Why the generating function of $x^2(1-3x)^{-1}$ is $(0,0,1,3,3^2,3^3)$ instead of $(0,0,1,-3,3^2,-3^3)$?

I've made this exercise. First I expanded $(1-3x)^{-1}$ and obtained: $$1 - 3 x + 9 x^2 - 27 x^3 + 81 x^4 - 243 x^5 + 729 x^6$$ Then I took the sequence of $x^2$ which is $(0,0,1,0,0,\ldots)$ and ...
1
vote
1answer
36 views

Determining the coefficient of $x^n$ in $\prod_{i=1}^m\frac{1}{1-x^{\alpha_i}}$

I looking for an algorithm to efficiently find the value$\mod p$ of the coefficient of $x^n$ in a generating function of this form: $$\prod_{i=1}^m\frac{1}{1-x^{\alpha_i}}$$ where $p$ is some prime ...
2
votes
2answers
42 views

extracting the middle term of $ (z \cos \theta + w\sin \theta )^m(- z\sin \theta + w\cos \theta )^m $

Is there a systematic way to extract the middle term of the following expression? $$ (z \cos \theta + w\sin \theta )^m(- z\sin \theta + w\cos \theta )^m $$ This is homogeneous polynomial of degree ...
1
vote
1answer
33 views

Formal power series manipulations and a closed formula for $\sum_{n\geq 0}{\frac{n^2+4n+5}{n!}}$

I'm reading a book on generating functions, and in their formal power series section they define: If $f \overset{ops}{\leftrightarrow} \left \{ a_n \right \}_{0}^{\infty}$, and $P$ is a polynomial, ...
1
vote
1answer
39 views

How to identify which terms are infinite sequences?

I've made this question some time ago. I thought that the term $x$ in $x+e^x$ would be a sequence $a_x=x=\{0,1,2,3,\ldots\}$ and it turns out that it is the sequence $\{0,1,0,0,\ldots\}$. Whenever I ...
1
vote
1answer
27 views

Exponential GF application [closed]

I have $15$ different books I have $5$ child. I want to give it all to all my child where every my child get at least $1$ book How many way I can distribute it????
1
vote
1answer
34 views

Rewrite formula using exponential generating functions

In the equation below I want to extract $b_k$. $$\frac{a_n}{n!} = \sum_{k=0}^{n}\frac{b_k}{k!(n-k)!}$$ For all other exercises in the book I had to use $e^x = \sum_{n=0}^{\infty}\frac{x^n}{n!}$ or ...
1
vote
1answer
50 views

How to write $\frac{27-17x}{2x^2-x+1}$ as a series to solve this recurrence relations problem?

The relation is: $$a_n=a_{n-1}-2a_{n-2}+4^{n-2}$$ $$a_0=2, a_1=1$$ I managed to reduce the problem to the generating function: $$A(x)=\frac{2-9x+5x^2}{(1-4x)(1-x+2x^2)}$$ and then I got this: ...
1
vote
1answer
35 views

Number of spanning trees in a wheel graph without an external edge.

How many different spanning tree contains n-element graph shown above? Determine the generating function for considered sequence. I am asking for advice.
1
vote
1answer
24 views

Why the generating function of $a_r=r$ is $xf'(x)$ instead of $f'(x)$?

I've seen the following definition: Theorem 5.1 $f(x),g(x)$ are the generating functions of the sequence $(a_r),(b_r)$. $[...]$ $(iv)$ The generating function to $(ra_r)$ is ...
0
votes
0answers
13 views

When generating function solution is valid analytical solution

When can I assume that closed form acquired by methods used for generating functions is valid also for analytical power series. In other words if there is closed form for convergent power series will ...
0
votes
2answers
52 views

Why the sequence generated by $x+e^x$ is $(1,x,\frac{x^2}{2!},\frac{x^3}{3!},\frac{x^4}{4!}\ldots)$?

I am trying to find the sequence generated by $x+e^x$. I have the sequence generated by the function $e^x$ which is $\displaystyle (1,x,\frac{x^2}{2!},\frac{x^3}{3!},\frac{x^4}{4!},\ldots)$, as for ...
0
votes
0answers
16 views

What is distinguishble and indistinguishble in generating functions?

Having a box with $2$ yellow balls, $1$ white ball and $1$ grey ball and enlisting all the possibilities of taking one or more balls, we have: $$(1+yx+y^2x^2)(1+wx)(1+gx)\tag{1}$$ But if we're not ...
12
votes
1answer
425 views

Why is it important to have the closed form of a generating function?

I am having introductory lectures on combinatorial analysis, I've been presented to the concept of generating functions and it's applications to solving combinatorial problems. The generating function ...
0
votes
0answers
43 views

How to find bivariate generating function

I have bivariate function $N(a,b)=2^{ab}$. I need to find generating function for it. My try: $$\sum_{n=0}^\infty\sum_{k=0}^\infty2^{kn}x^ny^k=$$ $$=\sum_{n=0}^\infty x^n\sum_{k=0}^\infty2^{kn}y^k=$$ ...
0
votes
1answer
62 views

Why the generating function of $\frac{2^K}{k!}$ is $e^{2x}$ instead of $e^{2^{x}}$?

I'm trying to find the generating function of $\frac{2^k}{k!}$, as there is a $k!$ in the denominator, it must be related to $e^x$, then perhaps, just a simple substitution is needed. The sequence ...
0
votes
0answers
35 views

Is there any closed form for the following series?

I am looking for any closed form expression for the series given below: $$ \sum_{m \ge 1} \frac{(xy)^m}{m(1-y^m)}. $$
1
vote
1answer
40 views

Num. of ways of stacking shelves using generating functions

We have $n$ books that need to be put on $k$ shelves so that each shelf contains at least $w$ books. Now, I know how to do it using stars and bars, but how to do it using exponential generating ...
0
votes
0answers
14 views

Nonstandard exponential generating functions

Exponential generating functions have an $n!$ in the denominator. Does anyone have references to generating functions with an $n^n$ in the denominator?
3
votes
1answer
24 views

Using generating function determine $u_n$

Using generating function determine $u_n$ $$u_{n+2}+8u_{n+1}-9u_n=8 \cdot 3 \cdot 3^n$$ $$u_0 =2 $$ $$u_1 = -6$$ And my attempt: $$u(x) = \sum^\infty_{n=0} u_nx^n$$ $$u_{n+2}+8u_{n+1}-9u_n=8 \cdot 3 ...
2
votes
0answers
33 views

Don't understand why this generating function needs to be taken to the power $-1$

I'm given the following recursive formula for a sequence: $u_{n+1}=u_n+\sum_{k=1}^{n-1}u_ku_{n-k}\ (n\ge1),\ u_0=0,\ u_1=1$ Since $u_0=0$ we can rewrite: $u_{n+1}=u_n+\sum_{k=0}^{n}u_ku_{n-k},\ ...
2
votes
1answer
37 views

Find the first coefficients of the inverse series of $x+x^2\sqrt{1+x}$

This is exercise 2c from chapter 2 of Wilf's generatingfunctionology. The problem is to find the inverse series $g(x)$ of the series of $f(x)=x+x^2\sqrt{1+x}$ (i.e. $f(g(x))=g(f(x))=x$). I get nowhere ...
1
vote
2answers
78 views

Recursion with generating function.

Using generating function determine $u_n$ $$u_{n+2} -6u_{n+1} + 9u_n = 2^n + n $$ I am asking for you to give me some advices. Thanks in advance.
-1
votes
2answers
53 views

Determine sequence using generating function.

Using generating function determine sequence $u_n$: $$u_0 = 1, \ u_1 = 0, u_{n+2} - 4u_{n+1} + 4u_n =0 $$ I am asking for advices. Thanks in advance.
2
votes
0answers
44 views

Is there a systematic relation between the generating functions for the rows vs that for columns of infinite sized Carleman-matrices?

(Roughly related, but generalizing, of this earlier question) Background: The first part of the following(the column-wise-focus) is also described in Eri Jabotinski's 1953-treatize Representation of ...
0
votes
3answers
34 views

If $X \sim Bin(n,p)$, using $E(X(X-1)) = g''(1) = n(n-1)p^2$ show that Var$(X) = npg$.

If $X \sim Bin(n,p)$ using $E(X(X-1)) = g''(1) = n(n-1)p^2$ show that Var$(X) = npg$. I understand that g is the generating function $g_{x}(t) = \sum_{k=0}^{\infty} p_{k}t^{k}$, and I know that the ...
1
vote
0answers
52 views

Closed form for generating function of Riemann Xi function

What is the closed form for $$f(x)=\ \sum_{k=1}^\infty \frac{\xi(k)x^k}{k!}$$ or $$g(x)=\frac12 \sum_{k=1}^\infty \frac{\xi(k+1/2)x^k}{k!}$$ or $$w(x)=\frac12 \sum_{k=1}^\infty ...