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

How do generating function created from solution of system of polynomials

What are the examples of generating function derived from solution of system of polynomials? how to count the number of points in varieties which are solution of system of polynomials? From Wiki, ...
1
vote
2answers
112 views

Binomial theorem / Generating function

I had trouble figuring out if the following equality holds by applying the binomial theorem and using generating functions. Could anyone please shed some light? Any help is greatly appreciated. $${n ...
1
vote
2answers
32 views

Solving (for asymptotics) of certain recurrence equations.

I am thinking of examples of the kind where the function occurs multiple times on the R.H.S with different arguments. This is the case where most techniques I know don't seem to work. For example ...
1
vote
2answers
48 views

Generating function for number of integer solutions, no computer

How do you solve a Generating function for the number of integer solutions with no computer? Use a generating function to solve the number of integer solutions for $$x_1+x_2+x_3=17$$ Where ...
0
votes
1answer
51 views

Generating function to calculate number of ways of distributing $10$ or less items to $3$ people.

There is a container of 10 identical chocolate frogs and three students, Adam, Bob, and Charles, are to be given some of these chocolate frogs, but not necessarily all of the chocolate frogs. ...
4
votes
2answers
76 views

Geometric Generating Functions

Let $p(t) = t^3 + Ft^2 + Et + V$, where $F,E,V$ are the number of faces, edges, and vertices of a cube, respectively. Factor $p(t)$ and explain your results in terms of generating functions. A hint ...
2
votes
1answer
62 views

More Generating Functions problems

(a) For this problem, define a nonstandard die as a 6-sided die that is equally likely to come up on each side, but has a different set of numbers than the usual 1,2,3,4,5,6 on its sides. A standard ...
1
vote
2answers
60 views

Stuck on Generating Functions

1) Determine how many ways Brian, Katie, and Charlie can split a 50 dollar dinner bill such that Brian and Katie each pay an odd number of dollars and Charlie pays at least 5 dollars . 2) Determine ...
2
votes
2answers
46 views

Number of partitions of number n and number 3n

On some exam i had task "Show that number of partitions of $n$ on four parts is equal to number of partitions of number 3n on four parts, but each part not greater than $n-1$" So first is $$n = a + ...
2
votes
1answer
79 views

What's the shape of this “addsTo” function …?

Note that in this combinatronics question, How many lists of 100 numbers (1 to 10 only) add to 700? I was asking: For an array of 100 numbers, each 1 to 10 inclusive, and the total is T - how many ...
0
votes
2answers
49 views

Showing that a generating function is equivalent to some fraction

I am working with generating functions and am required to prove that the generating function for the sequence $\{a_k\}$ where $a_k = (-8)^k$ for all integers $k\geq0$ is $\cfrac{1}{1+8x}$ and I have ...
0
votes
1answer
42 views

Finding number of ways of distributing toys without generating function

Suppose I want to distribute $30$ toys in $30$ boxes. Any number of toys (from the given toys) can be kept in any box. In how many ways can this be done? I know how to solve this problem using ...
3
votes
2answers
76 views

Find the generating function of the sequence $a_n = \sum\limits_{k=0}^n k(k-1)$

Find the generating function of the sequence $ a_n =\sum\limits_{k=0}^n k(k-1)$ My try: Let's assume $k(k-1)$ is genereated by $F(x)$ then $a_n$ is generated by $\frac{F(x)}{1-x}$ (that's a ...
1
vote
1answer
67 views

Prime number generation - speed comparison

"Efficient prime number generating" leads to some algorithms being displayed as "fast". Up to PG7.8 which does takes 65786 seconds to generate the prime numbers > ...
0
votes
1answer
40 views

How many sequences are there (Using generating functions)

How many sequences are there, with the length of $n$ above $\left\{0,1,2,3,4\right\}$ such that the digits sum is $9$. The solution offers the following generating function for the problem: $$ ...
1
vote
1answer
50 views

Learning about generating functions and sequences.

I've been reading through other questions on this site and external resources for a few hours now but seem to be having a mental block, probably through some elementary misunderstanding of my course ...
0
votes
1answer
21 views

Generating function question, seemingly lacking information

I have to prove that a generating function for the sequence $\{a_k\}$ where $a_k = (-8)^k$ for all integers $k\geq 0$ is $\cfrac{1}{1+8x}$. But I don't have any information on what $x$ is. Nor is ...
2
votes
0answers
95 views

Stirling numbers and Power Group Enumeration

The following question is a reference request concerning a derivation of the EGF for the Stirling numbers of the second kind by Power Group Enumeration / Burnside's Lemma, which is $$\sum_{n\ge 0} ...
2
votes
0answers
68 views

Partitions of 200 into at most 6 parts.

I'm working on a partition problem, and I got an answer that is simply staggering, and I was hoping for someone to verify whether my answer is correct. The question was simply to determine the number ...
2
votes
1answer
64 views

Number of integral soultions to linear equations without unit coefficients

To determine the number of integral solutions for the linear equation $$ x_1+x_2+x_3+\cdots+x_k = N$$ we have an expression $$ ^{N+k-1}C_{k-1}$$ But I want to know if the coefficients of ...
3
votes
0answers
99 views

Generating functions to solve number of integer solution problem

If I have $x_1 + x_2 + x_3 =10$ with $1\leq x_1 \leq 5, \; 2 \leq x_2 \leq 6, \;3 \leq x_3 \leq 9$ I know that I compute $(t^1+\dots + t^5)(t^2 +\dots + t^6)(t^3+\dots +t^9)$ and look at the ...
4
votes
2answers
72 views

How many numbers are less than million such that their digits sum is $\le 19$?

How many numbers are less than million such that their digits sum is $\le 19$? This question is a Generating-Functions exercise. The solution claims the answer is the coefficient of $x^{19}$ ...
2
votes
1answer
35 views

Why is this function generate $a_n = 2^n(n+1)$?

Let $G(x) = \frac{1}{(1-x)^2}$ which generates the sequence $a_n = n+1$ How can one infer that $G(2x) = \frac{1}{(1-2x)^2}$ generates $a_n = 2^n(n+1)$? Thanks.
3
votes
3answers
126 views

Evaluate the sum

I need to evaluate the following sum, which depends on $n \in \mathbb N$ (call it $S(n)$ if you will) $$ \sum_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)$$ where $f$ defined over $\mathbb N$ is ...
0
votes
0answers
52 views

proof of equation - generating function, stirling number

Look at following equation: $$\frac{x^n}{(1-x)(1-2x)...(1-nx)} = \sum_{k} {k\brace n}x^k $$ I see that it is product of generating function: $$x^n \cdot \frac{1}{1-x}\cdot \frac{1}{1-2x} ...
5
votes
3answers
320 views

Generating Functions and Linear Diophantine Inequalities

The following exercise is from Analytic Combinatorics by Philippe Flajolet and Robert Sedgewick, page 46. A $k$-composition of $n$ is an ordered $k$-tuple of non-negative integers whose sum is $n$. ...
0
votes
0answers
32 views

Iterated integrals of Legendre polynomials

Let $P_n$ denote the $n$th order Legendre polynomial. It is known that for $n\not= 0$ we have $\int P_n(x)\, \mathrm{d}x = \frac{1}{1+2n} (P_{n+1}(x) - P_{n-1}(x))+ C $. Setting all integration ...
3
votes
0answers
45 views

Generating series - Finite groups of order $n$

I am wondering if something of interest can be said about one of the two series $$G_1(x)=\sum_{n=1}^{+\infty}{\mathcal{G}(n)z^n}$$ $$G_2(s)=\sum_{n=1}^{+\infty}{\frac{\mathcal{G}(n)}{n^s}}$$ where ...
5
votes
3answers
115 views

Make $n$ cents with $1$-cent, $2$-cent, and $3$-cent coins

I encountered the following problem in Herber Wilf's book Generatingfunctionology: Prove that, in country that has $1$-cent, $2$-cent, and $3$-cent coins only, the number of ways of changing ...
1
vote
1answer
67 views

How can I distribute 15 pennies (1 cent) and 17 nickels (5 cents)?

How can I distribute 15 pennies (1 cent) and 17 nickels (5 cents), between four children, with the following restriction: A child receives at leat 1 penny and 3 nickels The children 2,3 and 4, ...
1
vote
2answers
104 views

How to obtain probability distribution from the generating function $G(s) = e^{a(s-1)^2}$?

I was trying to get the probability distribution $p(n)$ from a generating function $G(s)$ like this: $G(s) = e^{a(s-1)^2}=\sum s^np(n)$ I need first to do Maclaurin expansion of the exponential and ...
2
votes
1answer
64 views

Explain this generating function

I have a task: Explain equation: $$\prod_{n=1}^{\infty}(1+x^nz) = 1 + \sum_{n=m=1}^{\infty}\lambda(n,m)x^nz^m $$ $\lambda(n,m)$ - is number of breakdown $n$ to $m$ different numbers (>0) It's ...
0
votes
1answer
22 views

Find the probability generating function of a GW process

Consider a Galton-Watson process with offspring distribution $\mathrm{Poisson}(1)$. That is, $\textbf{p}(k) = \frac{e^{-1}}{k!}$. Given this information, and that $P(z) = ...
0
votes
0answers
34 views

Need help with understanding a generating function

An exercise asks me to construct a generating function for the number of sequences starting with a subsequence of letters (30 characters in my language) and ending with a subsequence of digits. The ...
2
votes
2answers
118 views

Finding the number of solutions to $x+2y+4z=400$

My question is how to find the easiest way to find the number of non-negative integer solutions to $$x+2y+4z=400$$ I know that I can use generating functions, and think of it as partitioning $400$ ...
0
votes
1answer
105 views

Use generating functions to prove Pascal’s identity

How do I prove Pascal's identity using generating functions? $C(n,r) = C(n−1,r) + C(n−1,r−1)$ when $n$ and $r$ are positive integers with $r < n$. I am given the hint to use the identity ...
0
votes
1answer
30 views

For each integer $s$, how many N-tuples with possible elements $\{0, 1, -1\}$ satisfy the condition that the sum of its elements is $s$?

So, we can find the answer using the generating function: $$f(x)=(1+x+x^{-1})^N=x^{-N}\sum_{k=0}^{N}\sum_{m=0}^{k}{N \choose k}{k \choose m}x^kx^m$$ and the number of N-tuples for each integer $s$ is ...
2
votes
3answers
114 views

Finding the general term for the sequence $a_n = \frac{3}{4}a_{n-1} +4e$

How do I find the general term for the sequence $$a_n = \frac{3}{4}a_{n-1} +4e$$ using a generating function? If there is an easier way to do it without using a generating function, please tell me. ...
0
votes
0answers
76 views

Relationship between $\sum\limits_{n=0}^\infty \frac{a_n x^n}{n!}$ and $\sum\limits_{n=0}^\infty \frac{a_n^2 x^n}{n!}$

For an analytic function with the property $f^{(n)}(0)=a_n$, we have $f(x)=\sum\limits_{n=0}^\infty \frac{a_n x^n}{n!}$. This can be extended to $f^{(n)}(x)=\sum\limits_{n=0}^\infty \frac{a_{n+1} ...
0
votes
1answer
36 views

Initial values appear from nothing

This answer says that any casual sequence of the kind $y_n = y_{n-1} + y_{n-2} + y_{n-3} + \ldots $ will stay constant-0 because $y_0$ is a sum of zeroes, so is $y_1$ and the rest of the sequence. I ...
2
votes
0answers
50 views

Do asymptotically equivalent coefficients survive convolution at least in Θ?

This is a follow-up question to this one where I asked if asymptotic equivalence of coefficients carried over after convolution, resp. why this was not the case. Answerer Daniel Fischer proposed that ...
0
votes
0answers
27 views

Lower bound for a relative of the central binomial coeff

The central binomial coefficients $\binom{2m}{m}$ have g.f. $\frac{1}{\sqrt{1-4z}}$ and lower bound $\frac{4^m}{\sqrt{4m}} \le \binom{2m}{m}$. I'm interested in a related integer series $$T(2m, m) = ...
1
vote
1answer
113 views

Count the number of ways n different-sided dice can add up to a given number

I am trying to find a way to count the number of ways n different-sided dice can add up to a given number. For example, 2 dice, 4- and 6-sided, can add up to 8 in 3 different ways: ...
2
votes
1answer
62 views

Simplifying a generating function in two variables with two binomial coefficients

I'm trying to to make the below expression simpler, and it would be great if it could be expressed as something like $(x+y)^k$. $$ \sum_{i=0}^k\binom{n+1}i\binom{m+1}{k-i}x^iy^{k-i} $$ The number ...
3
votes
1answer
118 views

Why does convolution not maintain asymptotic equality of coefficients?

Assume I have four (generating) functions $f$, $f'$, $g$ and $g'$. If that is interesting, we can assume that they all share the same radius of convergence $\rho > 0$. In addition, we know that ...
4
votes
2answers
116 views

Difficult generating function

Define a beautiful number to be an integer of the form $a^n$, where $a\in\{3,4,5,6\}$ and $n$ is a positive integer. Prove that each integer greater than $2$ can be expressed as the sum of pairwise ...
4
votes
1answer
116 views

Generating functions and closed form solution for fibonacci sequence

Doing some extra practice problems and am having a hard time with this concept. Thanks!
3
votes
1answer
59 views

Solving a recurrence (with the form of a convolution) involving binomial coefficients

While dealing with a problem related to intersection of hyperplanes I have come across the following recurrence to obtain the values of $K_{j}$ \begin{array}{cccccccccc} 1 & = & ...
1
vote
2answers
78 views

Find a closed form for the generating function for this sequence

The sequence: $0, 0, 0, 1, 1, 1, 1, 1, 1, \ldots$ The book gives the answer of $\frac{x^3}{1-x}$ but I'm not sure how to get this answer. I understand the generating function of this sequence will be ...
4
votes
2answers
105 views

Is there a nice function representation of $\sum_{n=1}^\infty \zeta(2n+1)x^{2n+1}$

$$\sum_{n=1}^\infty \zeta(2n)x^{2n} = -\frac{\pi x}{2}\cot(\pi x) $$ Does $$\sum_{n=1}^\infty \zeta(2n+1)x^{2n+1}$$ have a nice function representation as well? From its graph, it looks like a ...