《怎样解题:数学竞赛攻关宝典(第3版)》第 209 页:

题 6.4.9(普特南 1996)定义自私集为 它自己的基数(元素数)是该集合的一个元素的集合。 最小自私集是自私集,但它的任何真子集都不是自私集。 {1,2,...,n} 的所有子集中有多少个是最小自私集? 证明你的结论。


首先注意到,空集不是自私集,也不是最小自私集, 所以我们不必考虑子集为空集的情形。

这题的关键是:{1,2,...,n} 的非空子集 是最小自私集的充分必要条件 是其基数是该集合的最小元素。

因此,{1,2,...,n} 的基数为 i 的子集中有 个是最小自私集。

具体做法是, 选定最小元素 i,然后从 n-i 个大于 i 的数中选取其余 i-1 个元素。
(如果 n-i < i-1,相应的选取数量为零,表明 i 超出合理范围。)

因此,答案是:

易知 F(1) = F(2) = 1,所以 F(n) 就是斐波那契数 Fn

我们知道