名古屋大学 情報学研究科 数理情報学専攻 2017年8月実施 問題3 離散数学

标签：

• Nagoya-University
• Binomial-Inversion
• Mobius-Inversion

Author

祭音Myyura

Description

以下の各問に答えよ。

(1)

$f$ を非負の整数で定義される関数とする。非負の整数 $n$ に対して関数 $g$ を

$$g(n) = \sum_{k=0}^n \binom{n}{k} f(k)$$

と定める、このとき,

$$f(n) = \sum_{k=0}^n \binom{n}{k} (-1)^{n-k} g(k)$$

が成立することを示せ。

(2)

$\mu$ を Mobius 関数とする。すなわち、正の整数に対して

$$\mu(n) = \begin{cases} 1 &(n=1) \\ (-1)^k &(n \text{ is a product of } k \text{ distinct prime numbers}) \\ 0 &(\text{otherwise}) \end{cases}$$

とする。

(i)

正の整数 $n$ に対して、

$$\sum_{d \mid n} \mu(d) = \begin{cases} 1 &(n = 1) \\ 0 &(n \geq 2) \end{cases}$$

が成立することを示せ。ただし、$d$ は $n$ のすべての正の約数を動くものとする。

(ii)

$f$ を正の整数で定義される関数とする。正の整数 $n$ に対して関数 $g$ を

$$g(n) = \sum_{d \mid n} f(d)$$

と定める。 このとき、

$$f(n) = \sum_{d \mid n} \mu(\frac{n}{d})g(d)$$

が成立することを示せ。

题目描述

回答下列离散数学问题。

1. 设 $f$ 是定义在非负整数上的函数，并对非负整数 $n$ 定义 $g(n)=\sum_{k=0}^{n}\binom{n}{k}f(k).$ 证明二项反演公式 $f(n)=\sum_{k=0}^{n}\binom{n}{k}(-1)^{n-k}g(k).$
2. 设 $\mu$ 为 Möbius 函数：
   \begin{cases} 1,&n=1,\\ (-1)^k,&n\text{ 是 }k\text{ 个互异素数之积},\\ 0,&\text{其他情况}. \end{cases}$$ 1. 对任意正整数 $n$，证明 $$\sum_{d\mid n}\mu(d)= \begin{cases} 1,&n=1,\\ 0,&n\ge2; \end{cases}$$ 其中 $d$ 遍历 $n$ 的全部正因数。 2. 设 $f$ 定义在正整数上，并令 $$g(n)=\sum_{d\mid n}f(d).$$ 证明 Möbius 反演公式 $$f(n)=\sum_{d\mid n}\mu\!\left(\frac nd\right)g(d).$$

考点

• 二项反演：交换有限求和顺序，并使用交错二项式和消去非目标项。
• Möbius 函数：根据整数的互异素因子分解理解函数取值。
• 因数格上的求和：利用 $\sum_{d\mid n}\mu(d)$ 的消去性质。
• Möbius 反演：从因数和关系恢复原算术函数。

Kai

(1)

$$\begin{aligned} \sum_{k=0}^n(-1)^{n-k}\binom{n}{k}g(k)&=\sum_{k=0}^n(-1)^{n-k}\binom{n}k\sum_{j=0}^k\binom{k}{j} f(j)\\ &=\sum_{j=0}^n\sum_{k=j}^n(-1)^{n-k}\binom{n}k\binom{k}{j} f(j)\\ &=\sum_{j=0}^n\sum_{k=j}^n(-1)^{n-k}\binom{n}{j}\binom{n-j}{n-k} f(j)\\ &=\sum_{j=0}^n\binom{n}{j} f(j)\sum_{k=0}^{n-j}(-1)^k\binom{n-j}{k}\,. \end{aligned}$$

By the binomial theorem

$$\sum_{k=0}^{n-j}(-1)^k\binom{n-j}{k}=\begin{cases} 1,&\text{if }n=j\\ 0,&\text{otherwise,} \end{cases}$$

hence

$$\sum_{k=0}^n (-1)^{n-k}\binom{n}{k}g(k)=\binom{n}{n}f(n)=f(n)\,,$$

(2)

(i)

The statement clearly holds if $n=1$.

Assume that $n > 1$ and by the fundamental theorem of arithmetic we write

$$n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$$

In the sum $\sum_{d \mid n} \mu(d)$ the only non-zero terms come from $d = 1$ and the divisors of $n$ which are products of distinct primes.

From the definition of Binomial coefficient, there are $\binom{k}{m}$ ways to choose $m$ primes from $p_1,p_2,\ldots,p_k$ to multiply together.

Thus:

$$\begin{aligned} \sum_{d \mid n} \mu(d) &= \mu(1) + \mu(p_1) + \cdots + \mu(p_k) + \mu(p_1p_2) + \cdots + \mu(p_{k-1}p_{k}) + \cdots + \mu(p_1p_2\cdots p_k) \\ &= \binom{k}{0} + \binom{k}{1}(-1) + \binom{k}{2}(-1)^2 + \cdots + \binom{k}{k}(-1)^k \\ &= 0 \end{aligned}$$

(ii)

(This is the so-called Mobius inversion formula)

$$\sum_{d \mid n} \mu(\frac{n}{d})g(d) = \sum_{d \mid n} \mu(d) g(\frac{n}{d}) = \sum_{d \mid n} \mu(d) \sum_{c \mid \frac{n}{d}} f(c) = \sum_{c \mid n} f(c) \sum_{d \mid \frac{n}{c}} \mu(d)$$

By using the result of Question (2)-(i), i.e.,

$$\sum_{d \mid n} \mu(d) = 1 \text{ for } n=1, \sum_{d \mid n} \mu(d) = 0 \text{ for } n > 1$$

If we have $\frac{n}{c} = 1$, i.e., $n=c$ then we have

$$\sum_{d \mid \frac{n}{c}} \mu(d) = \sum_{d \mid 1} \mu(d) = 1$$

and that $\sum_{d \mid \frac{n}{c}} \mu(d) = 0$ if otherwise. Hence by considering $n=c$ we get

$$\sum_{c|n}f(c)\sum_{d|\frac{n}{c}}\mu(d)=\sum_{c|n}f(c)=f(n).$$