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
61 views

recursive generating functions

\begin{align} f(0) & = 1 \\ f(1) & = 1 \\ f(2) & = 2 \\ f(2n) & = f(n)+f(n+1), \;\;\;n\gt1 \\ f(2n+1) & = f(n-1)+f(n), \;\;\;n\ge1 \\ \end{align} I am trying to figure out ...
0
votes
1answer
34 views

Finding a generating function from an expression

Series representations: $$ \frac{1}{2(1-x)^3}+\frac{1}{4(1-x)^2}+\frac{1}{8(1-x)}+\frac{1}{8(1+x)}=\sum_{n=0}^\infty x^n\left(7+(-1)^n+8n+2n^2\right). $$ I'm trying to figure out to to turn this ...
3
votes
1answer
39 views

Find a generating function for $a_r=(r-1)^2$

Problem Find a generating function for $a_r=(r-1)^2$ My Solution $$g(x)=1+x+x^2+x^3+\cdots=\frac{1}{1-x}$$ $$g'(x)=1+2x+3x^2+4x^3+\cdots=\frac{1}{(1-x)^2}$$ $$x\times ...
1
vote
0answers
27 views

Find an ordinary generating function whose $a_r = 3r + 7$

Problem Find an ordinary generating function whose coefficient $a_r = 3r + 7$. My Solution $$g(x)=1+x+x^2+x^3+\cdots=\frac{1}{1-x}$$ $$7\times g(x)=7+7x+7x^2+7x^3=\frac{7}{1-x}$$ ...
0
votes
0answers
22 views

Explicit form of a generating function.

Let $q \geq p$ be natural numbers both larger than or equal to two. Let $u(z):=z^p+z^{p+1}+...+z^q$ and $p(z)=\frac{z u'(z)}{1-u(z)}$. Since $p(z)$ is rational, one can write (by the theory of ...
-1
votes
0answers
30 views

Problems deriving probability generating function for the negative binomial distribution [on hold]

My problem is the following: Part A.a I can't get the moment generating function to be what it states in the exercise. And I found other people asking the same question but they get a different ...
1
vote
0answers
31 views

Vandermonde-type convolution with geometric term

Is there a closed-form solution to the following sum? \begin{align*} f(r, s, n) = \sum_{k=0}^{n}c^k\binom{r}{k}\binom{s}{n-k} \end{align*} I know this corresponds to find the coefficient of $x^n$ of ...
2
votes
0answers
102 views
+50

Inequality with analytic functions on the unit ball

Let $g(z) = \sum_{n\geqslant 0} a_nz^n$ be an analytic function where $a_n$ only take values in $\{0,1\}$ (not sure if it is a necessary condition, it is just the case I'm considering). Let ...
3
votes
1answer
174 views

Conditional probability generating function - Binomial

I'm working on the following problem: Y = $X{_1}+X{_2}+X{_3}+...+X{_N}$ $N\overset{d}{\sim}Bi(n,p) $ and $X_i\overset{d}{\sim}Bi(m,q)$ $N, X_1, X_2 $ are independent $a)$ Find ...
1
vote
0answers
19 views

Determining the E.G.F from an Umbral Type Recurrence Formula

Suppose I have the recurrence formula $$\left(A+\frac{2}{3}\right)^n+w_3^2\left(A+\frac{1+w_3}{3}\right)^n+w_3\left(A+\frac{1+w_3^2}{3}\right)^n=0; A_0=1, A_1=-\frac{1}{3}$$ where ...
0
votes
1answer
25 views

Generating Normals with specific means and variances

Suppose I wish to generate normals $X, Y, Z$ with the correlation matrix R but with means $0, 1, 2$, and variances $4, 16, 25$, respectively. How would you do this? The only way I know of doing ...
1
vote
3answers
26 views

Complicated partial fraction expansion

I'm reading the book generatingfunctionology by Herbert Wilf and I came across a partial fraction expansion on page 20 that I cannot understand. The derivation is as follows: $$ ...
0
votes
2answers
33 views

A function that satisfies the $n$-th derivative where $x=0$ is $\frac{1}{n}$ [closed]

Is there a function that satisfies $f^{(n)}(0)=\frac{1}{n}$ for every positive integer $n$?
2
votes
3answers
82 views

Inclusion–Exclusion Identical Computers Problem

Find the number of ways to distribute 19 identical computers to four schools, if School A must get at least three, School B must get at least two and at most five, School C get at most four, and ...
0
votes
1answer
30 views

Coefficient of $x^n$ in binomial expansion

I want to find the coefficient of $x^n$ in $G(x)$ where $ G(x) = \frac{1}{1-x^{a_1}}\times\frac{1}{1-x^{a_2}}\times\dots\times\frac{1}{1-x^{a_k}}$ how do I approach this? It would be helpful if it ...
3
votes
2answers
57 views

Multiplying A Coefficient by an Indexed Multiplier using Generating Functions

If I have a particular exponential generating function, $$G(x)=\sum_{n=0}^\infty a_n\frac{x^n}{n!}$$ then what would be the generating function for $$H(x)=\sum_{n=0}^\infty ...
4
votes
4answers
128 views

Find a generating function for the number of strings

The string $AAABBAAABB$ is a string of ten letters, each of which is $A$ or $B$, that does include the consecutive letters $ABBA$. Determine, with justification, the total number of strings of ten ...
1
vote
0answers
15 views

How would you write the OGF for the sequence {hk}

Write the ordinary gen. function for the sequence. So trying to work this out. I ended up with (1+x)^7. But I am not sure if this is correct. Thanks for any help.
4
votes
2answers
55 views

Counting numbers of fruit baskets

Suppose you have $10$ apples, $12$ bananas, and $8$ peaches, and you want to divide them into $3$ baskets containing $10$ fruit each. In how many ways can you do this, if the fruit of each type is ...
2
votes
3answers
141 views

A combinatorial task I just can't solve

Suppose you have $7$ apples, $3$ banana, $5$ lemons. How many options to form $3$ equal in size baskets ($5$ fruits in each) are exist? At first I wrote: $\displaystyle \frac{15!}{7!3!5!} $ But its ...
0
votes
0answers
78 views

Coefficients of powers of the generating function of the Fibonnaci numbers

How to find the coefficent of $x^M$ in $$( x + x^2 + x^3 + x^5 + x^8 + x^{13} + x^{21} + \ldots )^n$$ where $n$ is a positive integer and the exponents are the Fibonacci numbers?
1
vote
1answer
38 views

Finding a generating function for $\{(n+2)C_{n+1}\}^\infty_{n=0}$

I'm trying to come up with a generating function for $\{(n+2)C_{n+1}\}^\infty_{n=0}$ where $C_n$ is the $n$th Catalan number. I know we can write $(n+2)C_{n+1} = 2(2n+1)C_n$. I also tried to follow ...
0
votes
0answers
56 views

Coefficient of generating function in two variables

I have a generating function $$\sum_{m,n} P(m,n)y^{m}x^{n} = \prod(1-yx^t)^{-1}$$ where $t \in \{1,2,3,5,8,...\}$ i.e. Fibonacci set with single 1. For now, I have a naive script to calculate ...
1
vote
1answer
68 views

Luis Suarez goalscoring record.

Problem: The $2013-14$ season was a short-lived ray of hope in an otherwise long dark night for the world’s greatest football team. The team played $38$ league games and the main contributing ...
1
vote
3answers
33 views

Use generating functions to determine the number of ways

Use generating functions to determine the number of different ways $12$ identical action figures can be given to $5$ children so that each child receives at most $3$ action figures So far I have come ...
0
votes
1answer
18 views

How to develop a formula for a function?

What are the general tips and techniques to define an explicit formula for a function when the mapping of that function is known. Say f: N to Z (N is natural numbers and Z is integers). In this ...
1
vote
2answers
43 views

Find the generating function for the recurrence $a_n=a_{n-1}-a_{n-2}$, with $a_0=0$ and $a_1=1.$

This was a test question and I felt confident about it but all he put on it was no and circled a problem and left it at that. My solution up until I messed up which was early was $G_a(x) = ...
-2
votes
0answers
18 views

Principle of Inclusion/Exclusion (PIE) Homework Help [duplicate]

Prompt Suppose Sue is a Mail Carrier who is crazy. He likes to ensure that none of the n houses on his delivery route get the mail they are supposed to. Your goal, should you choose to accept it, for ...
1
vote
0answers
37 views

Reference for Coefficient Extraction of Multiple Sum

In a post here, the final answer is obtained by coefficent extraction of the quadruple sum. ...
1
vote
1answer
22 views

Exponential generating function and fibonnaci

$F_n$ is the $n$th Fibonnaci number. $$g(x) = \sum^\infty_{n=0}F_n \frac{x^n}{n!}$$ Prove that $$g''(x)=g'(x)+g(x)$$ I've never dealt with derivatives in the above form so I am not exactly sure ...
1
vote
1answer
67 views

A sum of Stirling numbers of the second kind

Find a formula (either exact or asymptotic in $N$) for $S(N)$, where \begin{equation} S(N) = \sum_{n=N}^\infty \sum_{k=N}^n \sum_{j=0}^k \binom{k}{j} (-1)^{k-j} (1+j)^n \frac{t^n}{n!}. \end{equation} ...
2
votes
2answers
42 views

Counting the number of ways (variants)

I'm learning about combinatorics and wanted to see if I understand when to apply what methods when it comes to counting the number of ways to distribute x items. There are a lot of concepts I've ...
0
votes
1answer
102 views

Proving the closed form of a generating function of the sum of n lucas numbers is equal to the n+2th lucas number

1760887     I've been working on this homework problem for a while now and can't seem to solve it. Let $L_n = L_{n-1} + L_{n-2}$ for $n\ge 2$ where $L_0 = 2$ and $L_1 = 1$ $M_n = 1 + ...
0
votes
1answer
37 views

Recurrence Relation With Non-constant Coefficient

I have a question that involves finding the closed form of the generating function for this sequence $$na_n = 3a_{n-1} -4a_{n-2}+ \frac{8.3^{n-2}}{(n-2)!}$$ with $$a_0=2, a_1=6$$ My lecturer told me ...
0
votes
2answers
27 views

Understanding the equality $x^k(1-x)^{-k} = \sum_{n = k}^{\infty}{{n-1}\choose{k-1}}x^n$

Can anyone explain me why this equality is true? $x^k(1-x)^{-k} = \sum_{n = k}^{\infty}{{n-1}\choose{k-1}}x^n$ I really don't see how any manipulation could give me this result. Thanks!
0
votes
1answer
27 views

Literature on generating functions for networks

Are you aware of any material the presents all (or most, or many) the properties and applications of generating functions in the context of graphs? For example I am aware of 'Generating ...
1
vote
0answers
26 views

Generating functions, Schur's identity

Let $S=\{n\in \mathbb{Z}_+ \mid n \equiv 1, 5 \,\,(\text{mod 6})\}.$ Let $a(n)$ be the number of partitions of $n$ into parts belonging to $S,$ and $b(n)$ be the number of partitions of $n$ into ...
1
vote
2answers
30 views

Help resolving particular solution to recurrence relation?

$a_n=5a_{n-1} - 6_{n-2} + 4^n + 2n + 3$ for $n>=2$ , $a0 = 5, a1 = 19.$ I get the general solution $ c_n = C_12^n+C_23^n.$ For a particular solution in the form $pn = An + B + C4^n$; we have ...
1
vote
1answer
30 views

Prove using generating functions the equality of amount of solutions for provided equation with two given groups of limitations

At first, I hope the title for the post is fine, because I wasn't able to sum up the question to a better title. Anyways, this is the problem: I've got to prove that $a_n=b_n$ for every $n$ while: ...
2
votes
2answers
49 views

Restrictions for rule of general sequence: $T_{n+2}=T_{n} + T_{n+1}$

This is a rule which gives a sequence where $11$ times the seventh term ($11 t_7$) is equal to the sum of the first $10$ terms ($s_{10}$), where the first two starting numbers can be chosen. Do any ...
0
votes
1answer
42 views

Help with generating functions

I've got two questions. I'm trying to extract the "coefficients" of a power series. I think my terminology is incorrect here but here is what I mean. Here are some examples A(Z) = 1/(1-Z) ...
1
vote
1answer
37 views

Solving a third-order homogeneous recurrence relation with variable coefficients

I'm working on a problem that I've managed to reduce to a third-order homogeneous recurrence relation given by the following expression: $$(n + 3) f_{n + 3} - 2(n + 2) f_{n + 2} + (n - 1) f_{n + 1} + ...
1
vote
1answer
33 views

Non-homogeneous Recurrence Relation with Fibonacci Sequence

I have this question in my assignment, I'm just not sure how to handle finding the closed form fully. I have most of it. Here's the question for context. Recall that the Fibonacci sequence is defined ...
0
votes
0answers
73 views

Partitions into non-negative powers of $2$

Let $c(n)$ denote the number of partitions of $n$ into non-negative powers of $2.$ (Thus $c(5)=4$ since $5=4+1=2+2+1=2+1+1+1=1+1+1+1+1).$ (a). Prove that $1+\sum\limits_{n=1}^{\infty} c(n) ...
1
vote
2answers
50 views

Find and solve simultaneous recurrence relations for determining n-digit ternary sequences whose sum of digits is a multiple of 3

I'm studying recurrence relations, and I ran into the following problem: Find and solve simultaneous recurrence relations for determining $n$-digit ternary sequences whose sum of digits is a multiple ...
2
votes
0answers
29 views

Generating function for the Josephus Problem?

According to the Wikpedia article on the Josephus problem, the general solution is by dynamic programming. However, since there seems to be an explicit recurrence rule for the problem, should there ...
3
votes
2answers
50 views

Extract coefficients for a formal power series using Lagrange Inversion Formula

Given $f(x)$ is a formal power series that satisfies $f(0) = 0$ $(f(x))^{3} + 2(f(x))^{2} + f(x) - x = 0$ I know that the Lagrange inversion formula states given f(u) & $\varphi(u)$ are formal ...
0
votes
1answer
22 views

Generating function for multiset formula

It's said that the generating function for $g(x) = \sum_{d=0}^\infty {d+m-1 \choose m-1} x^d$ is equal to $\frac{1}{(1-x)^m}$. In the proof that I have seen it states that: By the geometric series, ...
0
votes
1answer
35 views

Find a recurrence relation and associated generating function for the number of different binary trees with n leaves

Find a recurrence relation and associated generating function for the number of different binary trees with n leaves. I'm learning about recurrence relations, and I'm struggling more with defining my ...
0
votes
0answers
39 views

Probability of finding $n$ individuals in the logistic model

A population has a birth rate proportional to both the actual population, and its difference with a certain saturation population $\sigma$. The equation for the probability of finding $n$ individuals ...