1993 Putnam A3

Let ${\cal P}_n$ be the set of subsets of $\{1, 2, \dots,

n\}$. Let$c(n, m)$be the number of functions$f: {\cal P}_n \to \{1, 2,

\dots, m\}$such that$f(A \cap B) = \min\{f(A), f(B)\}$. Prove that

$$

c(n, m) = \sum_{j=1}^m j^n.

$$

令 ${\cal P}_n$ 为 $\{1, 2, \dots,

n\}$。设$c(n, m)$为函数$f 的数量： {\cal P}_n \to \{1, 2,

\dots, m\}$使得$f(A \cap B) = \min\{f(A), f(B)\}$。证明

$$

c(n, m) = \sum_{j=1}^m j^n。

$$