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
57 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
19 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
40 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
8 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
39 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
58 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
26 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
25 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
28 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 ...
-2
votes
0answers
21 views

Acceptance-Rejection Method [closed]

Consider the PDF of a random variable $X$ defined as follows: $$ f(x) = \begin{cases} x(1-x/2) & \text{ if $0 \leq x<1$} \\ 0 & \text{ otherwise} \\ \end{cases} $$ Using ...
0
votes
0answers
11 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 ...
0
votes
0answers
12 views

Number of r-digit quaternary sequences (whose digits are 0,1,2,3) in which each of the digits 2 and 3 appears at least once

For each r $\in \mathbb N^*$, let $a_r$ denote the number of r-digit quaternary sequences (whose digits are 0,1,2,3) in which each of the digits 2 and 3 appears at least once. Find $a_r$. The ...
1
vote
2answers
59 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
41 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
34 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
142 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
42 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
41 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 ...
1
vote
1answer
43 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
21 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
31 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
33 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
46 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
60 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 + ...
0
votes
2answers
54 views

How to create a generating function that only includes multiples of 4?

I am going through generating functions to solve for the number of unordered selections or distributions. My text book asks the question: Give a formula similar to (1) for $1 + x^4 + x^8 + ... + ...
0
votes
0answers
23 views

Determine the generating function of $S_N:=\sum_{n=1}^{N}X_n$

Let $N,X,X_1,X_2,\ldots$ denote independent random variables with values in $\mathbb{N}_0$. Assume that $X,X_1,X_2,\ldots$ are identically distributed. Determine the generating function of ...
0
votes
4answers
88 views

Getting $(\frac{1-x^{6}}{1-x})^3$ from $(1 + x + x^2 + x^3+ x^4+ x^5)^3$ using generating functions

I came across when reading my solution that the expression $(1 + x + x^2 + x^3+ x^4+ x^5)^3$ simplifies to $(\frac{1-x^{6}}{1-x})^3$ using generating function. I'm not sure how they got this. I ...
2
votes
1answer
42 views

Exponential Generating Function for Permutation with no Fixed Points

While reviewing, I've come across a problem that seems to outline my lack of knowledge with regards to (specifically exponential) generating functions. For some reason, I understand "ordinary" ...
1
vote
1answer
27 views

Stirling numbers of the second kind — a series-expansion typo?

In H. S. Wilf's generatingfunctionology, (1.6.8) describes: $$ A_n(y) = \sum_k \begin{Bmatrix}n-1\\k-1\end{Bmatrix} y^k + \sum \begin{Bmatrix}n-1\\k\end{Bmatrix} y^k $$ $$ = yA_{n-1}(y) + \left( y ...
1
vote
0answers
33 views

Proving Identities using Partition and Generating Function

I have a problem with these two questions: Let $P_E(n)$ be the number of partitions of $n$ with an even number of parts, $P_O(n)$ the number of partitions of n with an odd number of parts, and ...
1
vote
1answer
68 views

Generating a rate equation from a paper

I'm going through equations in this paper Structure of Growing Networks with Preferential Linking, I was not able to understand how they derived equation $[3]$ by summing up equation $[2]$. eqn [2] ...
0
votes
2answers
30 views

Distributing 2 different kinds of identical objects into 4 distinct groups

The question is like this: In how many ways can 13 chocolate-chip cookies and 8 jelly donuts be distributed among four children that each child gets at least one cookies and one donuts? The ...
0
votes
0answers
20 views

Generating function for modified bessel functions of the second kind

There is a well known expression for a generating function of modified Bessel functions of the first kind: $$ \sum_{n=-\infty}^{+\infty} I_{n}(x)\, t^n = e^{\frac{x}{2}(t+\frac{1}{t})} $$ Does anyone ...
7
votes
0answers
157 views

Does $A193201$ count the partitions of $n$ of arbitrary dimension?

By my count, these sequences match for $n=0\ldots6$, where partitions that are the same after relabeling dimensions are considered equivalent (i.e., the dimensions are unordered). For example, for ...
0
votes
0answers
64 views

Summation of product of two binomial probabilities

I am trying to find the closed form solution for this formula but got stuck: $\displaystyle\sum_{k=m}^{\infty}{\binom{k}{m}\cdot2^{-k}}$ Actually I try to compute the values of summation of product ...
0
votes
1answer
32 views

Use a trig substitution (Half-Angle) in $a_n=2^\frac{n+1}{2}\sqrt{2^n-\sqrt{4^n-a_{n-1}^2}} \ \ \ \forall n\gt1$

I'm given $$a_1=2\sqrt{2}$$$$a_n=2^\frac{n+1}{2}\sqrt{2^n-\sqrt{4^n-a_{n-1}^2}} \ \ \ \forall n\gt1$$ I've tried finding $a_1,a_2,a_3,....$ to try and find a pattern, but it gives no simple pattern ...
1
vote
1answer
32 views

Probability Generating Functions- Dependent Poisson Distributions

I was wondering if anyone could give me a tip on how to proceed with the following question? Suppose X~Poisson(N), where N~Poisson($\lambda$). What is the PGF of X + N? (Where $\lambda$ is a number) ...
0
votes
2answers
95 views

Find the coefficient of $x^{24}$ in $(1 + x + x^2 + x^3 + x^4 + x^5)^8$

I'm not sure how to go about doing this. Do I find the ways to add up to 24 using the exponents with repetition? Is the multinomial theorem useful here? I also have a feeling that generating functions ...
4
votes
2answers
47 views

Extending generating function into series.

There is a reccurent equation: $a_{n+2}-2\cos(\phi)a_{n+1}+a_n=0$ and I must to solve it. I found generating function: $$A(t) = \dfrac{1 - t\cos(\phi)}{1 - 2t\cos(\phi) + t^2},$$ but I can not extend ...
2
votes
0answers
35 views

Generating Function for 2-Associated Stirling Numbers of the Second Kind

I am looking for a paper which explicitly defines a power series for 2-associated Stirling Numbers of the Second Kind. The paper defines the generating function as follows: Let $S_2(n,k)=b(n,k)$ be ...
0
votes
1answer
38 views

Expressing one generating function like combination of another generating functions.

Let A (t), B (t) and C (t) - generating functions for sequences $a_0, a_1, a_2,\dots; b_0, b_1, b_2,\dots and\ c_0, c_1, c_2,\dots$ Express C (t) through A (t) and B (t), if ...
1
vote
1answer
50 views

Showing the equality of two rook polynomials.

I'm reading Barbeau's Polynomials. I've done the following: Taking an arbitrary chessboard $C$ with some of the squares forbidden (with $n$ being the number of squares and $F$ the number of ...
1
vote
1answer
27 views

Generating-function problem

$A(t),B(t) $ and $ C(t)$ are generating functions for sequences $a_0,a_1,a_2,...;b_0,b_1,b_2,...;c_0,c_1,c_2,\dots$ I do not know how to express C(t) through A(t) and B(t), if $c(n)=\sum_{k = 0}^{[n ...
1
vote
1answer
29 views

Generating functions, sequences with unlimited history of recursion

There is sequence $a_n = a_{n - 1} + 2 a_{n - 2} + \dots + n a_0$, and $a_0 = 1$. I found the generating function for this sequence: $(3t^2-3t+1)/(1-2t)^2$ but I do not know what to do next. How can I ...
2
votes
1answer
42 views

How to find $\sum_{n = 0}^{ \infty} \frac{F_n}{3^n}$

How can I find $$\sum_{n = 0}^{ \infty} \frac{F_n}{3^n}$$ If I know that the generating function for the Fibonacci sequence is $G(t) = \frac{t}{1 - t - t^2}$?
2
votes
1answer
31 views

Generation function for recurrence

Could you tell me how I can find the generation function for recurrence $\sum_{n = 0}^{ \infty} n a_n t^n$ if I know $A(t)$ - generation function for $a_0, a_1, a_2 \dots$ . Thanks
0
votes
1answer
10 views

Uncertain Step in Proving an Identity from Generating Functions

From a lecture: It is required to prove that $ \sum_{i=1}^{n} i = \frac{n(n+1)}{2} $ using generating functions. It goes as follows: The generating function $ g(x) = 1+2x+3x^2+4x^3...= ...