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

0
votes
0answers
22 views

Recursion. I don't understand proof.

Theorem Let $a_0$ and $a_1$ be given and let $a_2,a_3,...$ be defined by the recurrence relation $a_n=Aa_{n-1} + Ba_{n-2} (n>1)$ where $A$ and $B$ are constants. Then let $\alpha, \beta$ be the ...
0
votes
0answers
8 views

Transforming Exponential to Ordinary Generating Functions

I am looking for a particular ordinary generating function, if it exists for the Associated Stirling Numbers of the second kind $$b(1;n,k)=b(n,k)=\sum_{k=0}^j(-1)^k\binom{n}{k}S(n-k,j-k)$$ Where ...
0
votes
0answers
23 views

Express expected value with help generating function

I understand, how to express expected value with help generating function. For example, I have the following generating function: $D(z) = p K(z) + q M(z)$, where $p + q = 1$. How can I express ...
2
votes
1answer
38 views

Understanding Generating Function

I have been looking at This Problem and Answer about generating functions. The problem asked for the generating function of: $$a_n=4a_{n-1}-4a_{n-2}+{n\choose 2}2^n+1$$ I understand how Ron Gordon ...
0
votes
1answer
36 views

Solve the Recurrence

Solve the recurrence $a_k = 2a_{k-1} + 3a_{k-2}$, if $a_0 = 0$ and $a_1 = 8$. I understand how to get the generating function: $$G(x) = \sum_{k \geq0}a_kx^k = a_0 + a_1x + \sum_{k\geq 0}a_kx^k = 8x ...
1
vote
2answers
48 views

Solve the recurrence $a_{n+2}=5a_{n+1}-9a_n+3n$?

What is the simplest way to solve the recurrence $a_{n+2}=5a_{n+1}-9a_n+3n$, with the initial values $a_0=2,a_1=1$? Is it possible to do this with generating functions?
1
vote
1answer
26 views

Recurrence relation stuck on partial fraction decomposition

I am stuck in trying to solve the following recurrence relation: $$S_n = rS_{n-1} + nrB$$ where $r$ and $B$ are constants. To solve this I made the following generating function: $$f(x) = ...
0
votes
3answers
57 views

Find the n-th number from the generating function

Is there any way to find the n-th number in the series, by knowing it's genereting function. For example, I found that the closed form solution for a generating ...
4
votes
1answer
86 views

Proper Bernoulli Function Generating Function

Consider the function $$\frac{t}{e^t - 1} = \sum_{i=0}^{\infty}\frac{B_i}{i!}t^i$$ This has been one of the famous generating functions for the bernoulli numbers. What about the function associated ...
0
votes
2answers
24 views

Generating functions and central binomial coefficient

How would you prove that the generating function of $\binom{2n}{n}$ is $\frac{1}{\sqrt{1-4y}}$? More precisely, prove that( for $|x|<\frac{1}{4}$ ): ...
1
vote
2answers
32 views

generating function for harmonic sequence

How I can find the generating function for the sequence $$ \frac{ H_n } n $$ where $H_n$ -harmonic numbers. I know that $$ \sum\limits_{k=1}^{\infty}H_kz^k = -\frac{\ln(1 - z)}{1 - z} $$ So, what ...
1
vote
1answer
28 views

Generating function of the Laguerre Polynomials

The Laguerre Polynomials have the following integral representations $$L_{n}^{\alpha} (x) = x^{-\alpha} e^x \frac{1}{2\pi i } \oint_c \frac{e^{-z} z^{n+\alpha}}{(z-x)^{n+1}} dz$$ where $c$ is an ...
0
votes
2answers
21 views

Solving recurrence equations

Is there a method to determine the generating function for a mutually recursive recurrence equation? As an example, consider the following set if equations $$R_n = R_{n-1}+ 3P_{n-1}; R_0 = 3$$ ...
1
vote
1answer
48 views

Proof of De Moivre's theorem using generating functions

I've come across the following proof of De Moivre's theorem: $$ \cos(n\theta) + i\sin(n\theta) = ( \cos\theta + i \sin\theta )^n $$ The proof establishes that: $ \forall \ \ |s| <1 $, $$ ...
0
votes
1answer
73 views

How can I count the number of ways to connect a graph with $X$ vertices and $Y$ edges?

If I have a graph with $X$ vertices, and $Y$ edges, where $Y$ is between $X-1$ and $(X(X-1))/2$, how can I count the number of unique ways to connect the graph (strictly no more than two paths between ...
1
vote
0answers
38 views

How to solve this tough recurrence relation?

For solving a related probability problem, I'm required to solve the following recurrence relation:- $q(r,b,L)=\frac{b}{r+b}q(r,b-1,L)+\sum_{k=1}^{L}\frac{r}{r+b}\times\cdots \times ...
0
votes
2answers
36 views

Find the generating function for the finite sequence 0,0,0,1,2,3,4,5

I have the sequence $\{0,0,0,1,2,3,4,5\}$ and I need to find a generating function. I found the answer to be $\sum n x^{n+2}$. However to find the nth term, I would use $n-2$, correct? But then for ...
1
vote
1answer
29 views

Combinatorics: Using a Generating Function to Count the Number of Ways of Selecting a Hand From a Triple Deck

Use a generating function to determine the number of ways to select a hand of m cards from a triple deck, if there are n distinct cards in a single deck. Verify that your expression produces the ...
0
votes
0answers
15 views

Discrete time adaption rule

Is it possible to find an update rule for $d(k)$ that satisfy following equation $$\log\frac{d^2(k+1)+1}{d^2(k)+1}=-c\log\left(|f(d(k))|+10\right)$$ where $c>1$ . I appreciate the time you'll take ...
1
vote
1answer
40 views

how to generate rook polynomial

I've encountered rook polynomials. I just can't seem to understand how to generate them by hand for small examples such as 3x3 boards. Take for instance: $$\begin{matrix} 1 & 1 & 0 \\ 1 ...
1
vote
1answer
114 views

Finding recurrence relation for digits

codes have been generated odd number of odd digits. Let $ a_n $ be the number of valid n-digit activation codes. Find the recurrence relation. I can't figure out and understand the question. Can you ...
1
vote
1answer
25 views

How to determine if there exist at least one number that is generated by both of the given generating functions?

I'm just learning about Generating Functions so my question might not completely make sense (in that case, I apologize). I want to know whether there exist at least one number that is generated by ...
0
votes
2answers
23 views

Find the number of 17-digit binary sequences with more 0's than 1's.

Find the number of 17-digit binary sequences with more 0's than 1's. What I know: If there are more 0's than 1's, the cases I have to calculate for is 9 0's and 8 1's 10 0's and 7 1's 11 0's and ...
0
votes
1answer
19 views

Generating function for the sequence $(0,0,0,1,2,…,2^{r-3},…)$

Find the generating function for the sequence $(0,0,0,1,2,...,2^{r-3},...)$ I found this question in my notes. I know the generating function for the sequence $a_r$ is $\sum a_r x^r$ but I'm not sure ...
2
votes
1answer
25 views

How to use generating functions to partially sum multiple integer sequences?

Let's say I want to find the following double sum $$ \sum_{k=1}^mk\sum_{n=1}^kn={1\over24}m(1+m)(2+m)(1+3m) $$ but using a generating function for the involved sums. The polynomial generating function ...
1
vote
2answers
63 views

Trying to find the closed form for the nth term of $\frac{1}{1-x^4}$

I know that $\frac{1}{1-x^4}$ is the generating function for the sequence (1, 0, 0, 0, 1, 0, 0, 0, 1, ...) I don't know how to find the closed form for the nth term though. Itried messing around with ...
-1
votes
0answers
21 views

exponential generation functions for n choices of balls

This may be a simple question but can you help me with it? Using exponential generation functions how can we determine a_\n of ordered choices of n balls such that there are 2 or 4 red balls, an even ...
2
votes
1answer
56 views

Show that $\sum_{i=1}^{r} i^2 = \binom{r+1}{3} + \binom{r+2}{3}$ by finding generating function

Find the generating function for the sequence $c_r$ where $c_0 = 0$ and $ c_r = \sum_{i=1}^{r} i^2 $ for $r \in \mathbb N$. Hence show that $\sum_{i=1}^{r} i^2 = \binom{r+1}{3} + \binom{r+2}{3}$ ...
0
votes
0answers
12 views

ARIMA Estimating and Adjust the Effect

I am reading this paper, trying to understand how tsoutliers is implemented. Taken the outlier into consideration, the model is considered as: $$ Y_t^* = Y_t + \omega \frac{A(B)}{G(B)H(B)}I_t(t_1) ...
1
vote
2answers
43 views

Finding the generating function of a series with a binomial coefficient and a exponential coefficient

So I am given this series $$2^8, 2^7 \binom{8}{1}, 2^6 \binom{8}{2}, 2^5 \binom{8}{3}, 2^4 \binom{8}{4}, 2^3 \binom{8}{5}, 2^2 \binom{8}{6}, 2^1 \binom{8}{7}, \binom{8}{8}, 0, 0, 0, 0, ...$$ which I ...
0
votes
2answers
69 views

How to find the generating function and the closed form for the generating form

I'm trying to find the generating function and the closed form for the generating form for this sequence: $0,1,-2,4,-8,16,-32,64...$ I've tried the following: I think it's an index shift so that's ...
0
votes
2answers
50 views

Help to write the generating function

How do I write the generating function and the closed for form the generating function The sequence is 0 0 0 1 1 1 1 1 1 Is this correct? $$A(x) = 0+0x+0x^2+1x^3+1x^4+1x^5+1x^6+1x^7+1x^8$$ This is ...
2
votes
1answer
28 views

Generating function for number of ways n people can pick a total of r1 chairs of type 1, r2 chairs of type 2 etc

This is a homework question for my combinatorics class that I just need to be pointed in the right direction to start. Find a generating function $x_1, x_2, . . . , x_m$ whose coefficient of ...
1
vote
1answer
27 views

comparing sequences via generating functions

Suppose that we have two sequences of positive real numbers $\{ a_n \}$ and $\{ b_n \}$, and let $\displaystyle A(x) = \sum_{n=1}^\infty a_n x^n$ and $\displaystyle B(x) = \sum_{n=1}^\infty b_n x^n$ ...
2
votes
2answers
21 views

Analytic Combinatorics to asymptotically estimate the number of objects of size at most n?

I have read some bits of Flajolet's and Sedgewick's book on Analytic Combinatorics. I am quiet curious as how to asymptotically estimate the number of objects of size at most n. Suppose for example ...
0
votes
0answers
29 views

The coefficient of $t^n$ in $\left(\sum_{k=1}^{n-1} t^k\right)^r$

I'm trying to count the number of ways of writing a general natural number $n\geq 2$ as the sum of $r$ smaller numbers where each of these numbers is at least $2$ - that is, I want to count the number ...
0
votes
0answers
24 views

Queue-length and waiting time of M/D/1-queue

I studied the M/G/1 queue by myself. Now as an application, I considered the M/D/1- queue. I know that the results can be find in the internet, but I haven't seen any calculations. Let $Q$ be an ...
1
vote
2answers
65 views

Number of ways to distribute 100 identical chairs among 4 different rooms

In how many ways can 100 identical chairs be divided among 4 different rooms so that each room will have 10,20,30,40 or 50 chairs? I'm having problems coming up with the generating function for this ...
0
votes
1answer
25 views

struck on generating operating functions.

Find the ordinary generating function associated with t 1. he problem of finding the number of solutions in nonnegative integers of the equation? 2a + 3b + 2c + d = r. where (a) r=10 (b) r=15 any ...
2
votes
3answers
43 views

Reduce this series

Let $$f(x)= \sum_{n=2}^\infty nx^n4^n$$ How do we reduce this? I know that $$\sum_{n=0}^\infty nx^n = \frac{x}{(1-x)^2}$$ and $$\sum_{n=0}^\infty a^n x^n = \frac{1}{1-ax}$$ But how do I combine both? ...
1
vote
1answer
45 views

exponential generating function for bernoulli numbers [closed]

How I can find exponential generating function for this sequence $(2^n − 1) B_n,$ where $B_n$ is Bernoulli numbers
3
votes
2answers
146 views

Solving a 2 independent variables (2nd degree) recurrence relation

Changes to the recurrences and definition are changed! See here: $f(n, 1) = 2n^2 $ and $f (n, k) = 0$ for $k \geq 2n$ and for $k < 0$ and $f(n, 2n-1) = 1$ for all $n$. Question: Is it possible ...
0
votes
1answer
46 views

A Difficult Recursive Equation

I've got a recursive equation of the form $$ x_{n+1} - x_{n} = \frac{(-1)^n}{2 \cdot 4 \cdot 6 \cdot ... \cdot 2n}(x_0-x_1)$$ for $n \geq 2$. We can assume $x_0$ and $x_1$ are just real numbers/ I ...
2
votes
1answer
77 views

Show $e^x / (1 - x)^n$ is the exponential generating function for a specified sequence

Show that $e^x/(1-x)^n$ is the exponential generating function for the number of ways to choose some subset (possibly empty) of $r$ distinct objects and distribute them into $n$ different boxes ...
0
votes
1answer
45 views

How many 10-letter words are there in which each of the letters e,n,r,s occur at most once?

Solve with a generating function. My solution was $$g(x)=\left(\frac{x^0}{0!} + \frac{x^1}{1!}\right)^4 \left(\frac{x^0}{0!} + \frac{x^1}{1!} + \frac{x^2}{2!} + ... \right)^{26-4}$$ $$g(x) = (1 + ...
2
votes
1answer
25 views

Exponential generating function of product

It needs to find an exponential generating function for the next sequence: $(2^n-1)B_n$. Where $B_n$ is the n-th number of Bernoulli. I found that exponential generating function for sequence of $B_n$ ...
1
vote
1answer
35 views

Using exponential generating functions to solve recurrence equations

It needs to solve $a_{n+1}=3a_{n}+5$ by using an exponential generating function. I tried to solve it and finaly got next equation: $E'(t)=3E(t)+5e^t$. I do not know what to do next, may be I choose ...
4
votes
1answer
36 views

Evaluation of formal series

Is it possible to get a closed form for coefficients of $$\left(1+\frac{2t}{(1-t)^2}\right)^{-n}$$ there $n$ - positive integer? It's easy to obtain the formula for $m$-th coefficient as ...
2
votes
0answers
48 views

Correctness of counting with product of generating functions

In generating functions we can related the coefficients of the generating function with as sequence. $$f(x) = \sum^{\infty}_{n=0}f_nx^n$$ and the sequence that corresponds to it: $$( \ f_0 \ , \ ...
3
votes
1answer
63 views

Getting $(1-3x^6 + 3x^{12} - x^{18}) \sum_{i=0}^{\infty} \binom{i+2}{2} x^{i}$ from $(\frac{1-x^{6}}{1-x})^3$ using generating functions

I'm not sure how to get $(1-3x^6 + 3x^{12} - x^{18}) \sum_{i=0}^{\infty} \binom{i+2}{2} x^{i}$ from $(\frac{1-x^{6}}{1-x})^3$. I know the following series. $$\frac{1}{1-x}=(1+x+x^2 + x^3 + x^4 + ...