Извините, этот техт доступен только в “中文” и “Американский Английский”. For the sake of viewer convenience, the content is shown below in this site default language. You may click one of the links to switch the site language to another available language.

今天我们讨论生成函数

Problem 1: Give a finite set of positive integers T. Let \mathfrak{T}_n be the collection of sequences (t_1,t_2,...,t_m), such that \sum_{i=1}^m t_m=n, and each t_i\in T. Let a_n=|\mathfrak{T}_n| for n\ge1 and a_0=1, and f(x)=\sum_{n=0}^{\infty}a_n x^n. Find out what is f(x) explicitly.

Solution: It is not hard to note the recursive relation a_n=\sum_{t\in T} a_{n-t} for n\ge1, if we set a_i=0 for negative i. So that f(x)=1+\sum_{t\in T} x^t f(x) and f(x)=1/(1-\sum_{t\in T} x^t), which is a rational function.

Variantion 1: If T is infinite, what would happen? Would f(x) still be rational?

We first analyze simple cases. If T=\mathbb{N}^+, it is expected that f(x)=1+\sum_{t=1}^{\infty} x^t f(x)=1+f(x) x/(1-x), so that f(x)=(1-x)/(1-2x)=1+\sum_{n=1}^{\infty} 2^{n-1} x^n. Indeed, in this case, counting the sequences amounts to divide a sequence of n objects arbitrarily. You can choose to divide between the ith and i+1th for 1\ge i\ge n-1, so in all 2^{n-1} choices, justifying the expansion.

I think it is equivalent to f being rational.

Theorem: \mathbb{Q}_p(t)\cap\mathbb{Q}[[t]]=\mathbb{Q}(t)

It is very interesting that this theorem is used for the rationality of \zeta-functions for algebraic varieties, which is part of the Weil conjectures.

2013 年 7 月 10 日