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.
8
votes
6answers
3k views
Making Change for a Dollar (and other number partitioning problems)
I was trying to solve a problem similar to the "how many ways are there to make change for a dollar" problem. I ran across a site that said I could use a generating function similar to the one quoted ...
7
votes
2answers
362 views
Lines in the plane and recurrence relation
I am trying to solve the following problem from Cohen's Basic Techniques of Combinatorial Theory:
A collection of $n$ lines in the plane are are said to be in general position if no two are ...
6
votes
4answers
906 views
Formal power series coefficient multiplication
Given that I have two formal power series:
$$ A(x) = \sum_{k \ge 0} a_k x^k $$
$$ B(x) = \sum_{k \ge 0} b_k x^k $$
The Cauchy Product gives a series
$$ C(x) = \sum_{k \ge 0} c_k x^k $$
$$ c_k = ...
5
votes
3answers
478 views
Combinatorial proof for two identities
Does exist a combinatorial proof for the following two identities ?
$\sum_{k = 0}^{n} \binom{x+k}{k} = \binom{x+n+1}{n}$
$\sum_{k = 0}^{n} k\binom{n}{k} = n2^{n-1}$
I know how to derive the ...
6
votes
3answers
357 views
Given an exponential generating function, is it possible to isolate only the even terms?
Suppose you have an exponential generating function
$$
F(x)=F_0+F_1x+F_2\frac{x^2}{2!}+\cdots+F_n\frac{x^n}{n!}+\cdots
$$
and you want to get only the even terms
$$
...
32
votes
3answers
1k views
Factorial and exponential dual identities
There are two identities that have a seemingly dual correspondence:
$$e^x = \sum_{n\ge0} {x^n\over n!}$$
and
$$n! = \int_0^{\infty} {x^n\over e^x}\ dx.$$
Is there anything to this comparison? (I ...
7
votes
1answer
822 views
Integral Representation of Infinite series
Let's take a look at the following integrals :
1) $\displaystyle \int\limits_{0}^{1} \frac{\log{x}}{1+x} \ dx = -\frac{\pi^{2}}{12} = -\frac 1 2 \sum\limits_{n=1}^{\infty} \frac{1}{n^2}= -\frac 1 2 ...
10
votes
4answers
2k views
Generating functions for combinatorics
I have no formal education in generating functions, but, based on another question, I have seen that they can be powerful for combinatorics.
Are there a few general principles for using generating ...
4
votes
2answers
121 views
Generating functions and the Riemann Zeta Function
The generating function for the terms of the harmonic series:
$\frac{1}{n}$
is $-\ln(1 - x)$.
Does an ordinary generating function exist for the terms of the zeta function $\zeta(s) = ...
1
vote
2answers
286 views
Proof that $(1-x)^n\cdot \left ( \frac{1}{1-x} \right )^n=1$
As part of a proof that $$(1-x)^n\cdot \left ( \frac{1}{1-x} \right )^n=1$$ in the context of generating functions it states that $$\sum_{i=0}^k(-1)^i\binom{n}{i}D(n,k-i))=0$$ where $D(n,k)$ is ...
7
votes
2answers
560 views
Squared binomial coefficient
I've got the following finite sum:
$s_{n}=\sum\limits_{k=0}^{n}\binom{n}{k}^2p^k$ (esp. if $p$ is a function of $n$, like $p=\frac1{n}$), which can be rewritten as ...
4
votes
3answers
704 views
Exponential Generating Functions For Derangements
I have been introduced to the concept of exponential generating functions a few days ago. However, my understanding of them are still quite limited, and I would like to see some examples. Earlier this ...
2
votes
1answer
87 views
Construct a generating function for the components of a sum
Let $j \in Z_+$. Set
$$
a_j^{(1)}=a_j:=\sum_{i=0}^j\frac{(-1)^{j-i}}{i!6^i(2(j-i)+1)!}
$$
and $a_j^{(l+1)}=\sum_{i=0}^ja_ia_{j-i}^{(l)}$.
Find generating function $\sum_{j}a_jx^j$ so that allows to ...
5
votes
1answer
207 views
Recurrence for perfect matchings revisited.
I like to study combinatorics a bit as a hobby, and recently a question I found interesting was posed asking to derive a recurrence for the generating function $G_n(x)$, the ordinary generating ...
3
votes
0answers
93 views
How many different ways to combine $2? [duplicate]
Suppose there are these coins: 1c, 5c, 10c, 25c, \$1 (100c) and \$2 (200c). How many different ways can \$2 be made using any number of coins?
I figure we need to use generating functions, so let ...
