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
2answers
48 views

Help proving a recursive formula involving planes and lines

Suppose that $n$ lines are drawn on a plane in such a way that no lines are parallel and no three of them intersect at a point. Let $r_n$ be the number of regions in the plane is divided into after ...
0
votes
1answer
28 views

Generating functions in simplified form

If you have the generating function: $$(1+x+x^2+\dotso)$$ is the same as $$\frac{1}{(1-x)}$$ If you have the generating function (evens): $$(1+x^2+x^4+x^6+\dotso)$$ is the same as ...
0
votes
1answer
19 views

Generating Function Coefficient with Multiples

I need the number of solutions to the problem $100 = 10x_1 +8x_2 + 5x_3 + 7x_4 + 11x_5$ with the constraints that $x_1$ is even, $x_2$ is greater than or equal to 2, $x_3$ is 0 or 4, $x_4$ is less ...
0
votes
1answer
18 views

How do you find the generating function for the number of integer solutions of this equation?

I am halfway stuck on this problem, can someone explain to me how to continue from where I am stuck? Question:3a + 5b +7c = n, where a,b,c >= 0. So I first turned it into this $$( 1 + x^3 + ...
0
votes
1answer
37 views

Discrete maths. Finding generating sequence for function.

I have a problem with generating sequences. I do not understand them at all. The task I have is: Find generating sequence for f(x)=ln(1-x). So, to my understanding, D(f)=(-infinity;0] Edit: my ...
1
vote
0answers
18 views

Deriving binomial distribution from a recurrence.

Let $X_n, n\geqslant1$ be iid random variables with distribution $\mathbb P(X_1=1)=p = 1 - \mathbb P(X_1=0)$. Let $S_0=0$ and $S_n=\sum_{i=1}^n X_i$, $n\geqslant1$. Let $q_{n,k}=\mathbb P(S_n=k)$, for ...
2
votes
2answers
37 views

Why to ignore the factorials as part of the coefficients in the exponential generating function?

I just perceived that, for the ordinary generating function $e^x$, it's coefficients are: $$\left(1,1,\frac{1}{2!},\frac{1}{3!},\frac{1}{4!},\dots \right)$$ But for the exponential generating ...
3
votes
2answers
50 views

Finding number of integer solutions using Generating Functions

This is a problem for a practice test my professor gave me. $$\text{How many integer solutions are there to } x_1+x_2+x_3+x_4 \leq 50 \\ \text{with } x_i \geq 2 \text{ for all } i = 1,2,3,4 \text{ ...
1
vote
0answers
27 views

Sequence from generating function.

Consider the recurrence $$\mu_1=1, \mu_2=2, \mu_3=4, \mu_4=8, \mu_5=16, \mu_6=32 $$ and $$\mu_{n+6} = \mu_n + \mu_{n+1} + \mu_{n+2} + \mu_{n+3} + \mu_{n+4} + \mu_{n+5}, n\geqslant 1. $$ The generating ...
0
votes
0answers
15 views

How to steepen logarithmic function without reducing constant of deceleration

As you can see I have plotted my points in Geogebra and compared them to the function $ y=log_{10}x $ They clearly don't coincide, how would I go about adjusting the function in order to find the ...
0
votes
0answers
28 views

Second order Fibonacci numbers

Let's consider a recurrence: $A_{0}=0$, $A_{1}=1$, $ A_{n}=A_{n-1}+A_{n-2}+F_{n}$, where $F_{n}$ is the $n$th Fibonacci number. How to express $A_{n}$ in a closed form? Despite the fact that it ...
1
vote
1answer
43 views

How many solutions for the equation $x_1 + x_2 + x_3 = n $ for positive integers when…

Hey I'm preparing for finals and I'm a little lost, I need your help to find the right direction... The question is how many solutions are there for the equation $x_1 + x_2 + x_3 = n $ for positive ...
11
votes
1answer
368 views

Challenging identity regarding Bell polynomials

Note: [2015-03-08] A proof of the identity below was aimed to close the gap of a rather extensive elaboration of this answer of mine. The identity (1) below is part of a more complex one, which is ...
0
votes
2answers
60 views

Find the number of ways to obtain a total of $15$ points by throwing $4$ different dice?

I've been assigned this problem: Find the number of ways to obtain a total of $15$ points by throwing $4$ different dice? The problem can be stated as: $$x_1+x_2+x_3+x_4=15\text{ with } 1\leq ...
1
vote
0answers
26 views

Why do I need the subtraction for this generating function?

I'm reading George E. Martin's: The art of enumerative combinatorics. In here: I don't understand why the need of the subtraction here. Could you expand a little more?
1
vote
1answer
40 views

Getting the proof of the generating function formula for Stirling numbers by 'staring' at the expression using combinatorial classes.

In his lectures on enumerative combinatorics, Prof. Federico Ardila gives a homework. For a fixed natural $k$, he asks us to prove the identity: $$\sum_{n \geq 0} S(n,k) z^n = ...
0
votes
1answer
38 views

What is the need of exponential generating functions on combinatorial problems?

I've been introduced in my last lectures. And for the following problem: Having 3 different types of books $a,b,c$ in how many ways can we take four different books putting them in a shelf such ...
1
vote
1answer
45 views

What to do after finding products for coefficients in generating functions?

The problem is as follows: $\text{Determine the coef. of } x^{10} \text{ in } (x^3 + x^5 + x^6)(x^4 + x^5 + x^7)(1+x^5+x^{10}+x^{15}+...)$ With this, there are three ways to get $x^{10}$. 1) ...
1
vote
3answers
46 views

Find coefficient of x in a generating function

The problem is as follows: $\text{Determine the coef. of } x^{10} \text{ in } (x^3 + x^5 + x^6)(x^4 + x^5 + x^7)(1+x^5+x^{10}+x^{15}+...)$ I factored out some $x$'s, to get ...
6
votes
7answers
369 views

EGF of rooted minimal directed acylic graph

I am trying to find the exponential generating function of directed minimal acyclic graphs (which I now call dag), where every non-leaf node has two outgoing edges. Context: A simple tree ...
1
vote
1answer
55 views

Find the coefficient of $x^{15}$ [closed]

How do you find the coefficient of $x^{15}$ from $x^{3}$$(1-2x)^{10}$? Thank you.
0
votes
0answers
28 views

Question about multiplying summations with another summation inside

I have the following: $$ y = \sum_{n=0}^\infty [x^n \sum_{k=0}^\infty (k+1)a_{k+1} P_{n-k}] \sum_{n=0}^\infty x^n[s_n - \sum_{k=0}^n a_{k+1}(k+1)R_{n-k}] $$ I can easily multiply $$ ...
3
votes
1answer
166 views

Hard binomial sum [closed]

How to prove this relation? $$\sum_{i=0}^{n}\frac{2^{-2i}\binom{2i}{i}}{n+i+2}=\frac{2^{4n+2}-\binom{2n+1}{n}^2}{(2n+3)2^{2n+1}\binom{2n+1}{n}}$$ That seems difficult!
1
vote
0answers
26 views

Determine a generating function and name the coefficient you would need to count the solutions to distribution question

The Full Question Find the generating function and name the coefficient which would give us the solution to this problem: count all integer solutions to $x_1 + x_2 + x_3+x_4+x_5 = 30$ where $x_i ...
1
vote
1answer
33 views

In how many ways can we distribute 24 bullets among four burglars?

When distributing these bullets, each burglar must at least have three bullets, but no more than eight. I have tried solving this with generating functions, but I am stuck at this part where I am not ...
1
vote
1answer
65 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 - ...
1
vote
2answers
44 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
25 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
49 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
31 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
28 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
10 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
21 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
34 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
25 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 ...
1
vote
0answers
36 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
24 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
62 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
51 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 ...
20
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
62 views

every number $n\in \mathbb{Z} $ can be represented as sum of different powers 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
49 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
48 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
41 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
87 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. ...
3
votes
1answer
95 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
37 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
46 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 ...