Generating Function

发表于   |   分类于   |  

A generating function describes an infinite sequence of numbers (An) by treating them as the coefficients of a series expansion.For example, the generating function of sequence {0，1，2，3，4，5…n} is g(x)=0+x+2x^2+3x^3+4x^4+…+nx^n.

Applications

Condition：There are four weights weigh 1g， 2g， 3g， 4g.
Question：How many weight can you weigh？How many methods to combine each weight？

We use 1+x represents one 1g weights.The same applies to 2g， 3g， 4g weights.And we use

(1+x)(1+x^2)(1+x^3)(1+x^4)
to express all conditions.

Expanding the formula, we can get a polynomial：

1+x+x^2+2x^3+2x^4+2x^5+2x^6+2x^7+x^8+x^9+x^10

The power of each monomial represents the weight we can weigh and the coefficient represents the number of methods to each weight.In this case, we can weigh from 0g to 10g, as the power range from 0 to 10, and there are 2 methods to weigh 5g, as the coefficient of x^5 is 2.

Implements

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//Core Code
menset(c1, 0, sizeof(c1));
menset(c2, 0, sizeof(c2));
for (i = 0;i <= weight[0]*num[0] && i <= n;i+=weight[0])
	c1[i] = 1;
// n monomials multiplication
for (i = 1;i < LenofSeq;i++) {
	// coefficients of polynomial
	for (j = 0;j <= POWER;j++)
		// and coefficient of current monomial
		for (k = 0;k <= weight[i]*num[i] && k+j <= POWER;k+=weight[i])
			c2[k+j] += c1[j];
	for (j = 0;j <= POWER;j++) {
		c1[j] = c2[j];
		c2[j] = 0;
	}
}

Properties

Assume two sequences {Ak}, {Bk}, the corresponding generating function are A(x), B(x)

Property One：
A(x)=B(x) if and only if Ai=Bi， i=0，1，2，…
Note A(x)=ΣAix^i as sequence {Ak}’s generating function
Note B(x)=ΣBix^i as sequence {Bk}’s generating function

Property Two：
if A(x)+B(x) = C(X)
then Ci=Ai+Bi， i=0，1，2，…

Property Three：
if Bk=0 when k=l
then B(x) = x^lA(X)

Property Four：
if Bk = Ak+1
then B(x)=[A(x)-ΣAkX^k]/x^l， Σ：k=0~l-1

Property Five：
if Bk=ΣAi， Σ：i=0~k
then B(x)=A(x)/(1-x)

Property Six：
if ΣAk is convergent，Σ：k=0~∞
then B(x)=(A(1)-xA(x))/(1-x)

Property Seven：
if Bk=kAk
then B(x)=xA(x)

Property Eight：
if Bk=Ak/(1+k)
then B(x)=1/x (∫A(x）dx)， ∫：0~x

Property Nine：
if Ck=ΣAiB(k-i)， Σ：i=0~k
then C(x)=A(x)B(x)

Reference

https://en.wikipedia.org/wiki/Generating_function