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
1answer
29 views

What happens from $\displaystyle (1+(x+x^2))^n$ to $\displaystyle \sum_k {n \choose k} (x+x^2)^n$?

I'm reading Harris/Hirst/Mossinghoff's: Combinatorics and Graph Theory. I don't understand what happens from $\displaystyle \bbox[1px,border:1px solid black]{(1+(x+x^2))^n} $ to $\displaystyle ...
0
votes
0answers
34 views

Truncation of partitions generating function question

$A (x)$ is the generating function for partitions. $B(x)=\sum_{n=0}^{\infty}b_nx^n $ $$b_n =\binom{\text{number of partitions of }n}{\text{into an even number of parts}}-\binom{\text{number of ...
1
vote
3answers
85 views

Series expansion of $\frac{1}{(1+x)(1−x)(1+x^2)(1−x^2)(1+x^3)(1−x^3)\cdots}$?

How would I find the series expansion $\displaystyle\frac{1}{(1+x)(1−x)(1+x^2)(1−x^2)(1+x^3)(1−x^3)\cdots}$ so that it will turn into an infinite power series again??
4
votes
1answer
83 views

How to write $1-x-x^3+x^4+x^5+x^6-x^7 \cdots$ as a power series representation

How can I write $1-x-x^3+x^4+x^5+x^6-x^7 ....$ as a power series representation (i.e., a neat fraction such as $\frac{1}{1-x}$. This stems from $\binom{\text{number of partitions of }n}{\text{into an ...
2
votes
3answers
63 views

Writing $1+3x^2+8x^4+21x^6+\cdots$ as a power series representation

How would I write the power series $$1+3x^2+8x^4+21x^6+\cdots$$ as a power series representation (something neat similar to $\frac{1}{1-x}$)? This reminds me of the power series ...
4
votes
4answers
220 views

Find the fraction where the decimal expansion is infinite?

Find the fraction with integers for the numerator and denominator, where the decimal expansion is $0.11235.....$ The numerator and denominator must be less than $100$. Find the fraction. I ...
5
votes
1answer
116 views

How to transform the product to sum?

I just wonder that how to prove that $$ \prod_{m=1}^{n}\Big(x-2\cos\frac{m\pi}{n+1}\Big)=\sum_{k=0}^{[n/2]}(-1)^{k}\binom{n-k}{k}x^{n-2k}. $$ Similarly, how to transform the product $$ ...
0
votes
2answers
25 views

Show that the number of subsets of $S_1 \cup \dots \cup S_t$ that contain at most one element from each $S_i$ is $(a_1 + 1)(a_2 + 1) \dots (a_t + 1)$.

I found this problems on Aigner's: A course in enumeration: 1.1 We are given $t$ disjoint sets $S_i$ with $|Si| = a_i$. Show that the number of subsets of $S_1 \cup \dots \cup S_t$ that contain ...
6
votes
4answers
122 views

How can I write this power series as a power series representation?

How can I write this power series ($1+x+2x^2+2x^3+3x^4+3x^5+4x^6+4x^7+5x^8....$) as a power series representation (like $\dfrac{1}{1-x}$ or something neat like that)?
1
vote
1answer
59 views

How to solve this kind of problem?

I've just found the following problem: $\quad\quad$ $\quad\quad$ $\quad\,$ And I believe that it could be done with something in combinatorics, my feeling is that generating functions would ...
0
votes
2answers
40 views

Determine generating function for given sequence.

Let $A(x) $ be generating function for sequence $a_n$ and let $s_n = \sum^{n}_{i=0} a_i $. Determine function generating sequence $a_n$ I am asking for an advice. The generating function makes me ...
1
vote
1answer
44 views

Partial Fraction Decomposition of Exponential Generating Functions

I want to see if it is possible to write $$ \left(\frac{x}{e^x-1}\right) \left(\frac{x^2/2! }{e^x-1-x}\right) \left(\frac{x^3/3!}{e^x-1-x-x^2/2}\right)$$ as a linear combination of the factors ...
1
vote
3answers
38 views

Generating Function. Sequence.

Prove, that generating function for $0,0,0,0,0,0,0,3,1,3,1,...$ is $$\frac{x^7}{1-x} + \frac{2x^7}{1-x^2}$$ I have a really problem with understanding generating function, so I don't show my attempt ...
4
votes
1answer
33 views

Generating function. Problem with understanding.

Let $F_0, F_1, F_2, ...$ be the Fibonacci numbers and let $f$ be the function defined $$f(x) = \frac{x}{1-x(1+x)}$$ Solution: The function $f$ is called the "generating function of the sequence ...
0
votes
1answer
35 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
25 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,j)=b(n,j)=\sum_{k=0}^j(-1)^k\binom{n}{k}S(n-k,j-k)$$ Where ...
0
votes
0answers
25 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
39 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
49 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
59 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
87 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
35 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
77 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
40 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
30 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
115 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
64 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
70 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 ...