双射的品味：什么叫自然的组合证明

luyuanhong

双射的品味：什么叫自然的组合证明

原创  MoMo 酱的 PA  数学猫 MoMo 酱  2026 年 5 月 17 日 09:31  上海



本文基于 Martin Aigner , A Course in Enumeration , Chapter 1 , Sections 1.1--1.2 ，主要讨论 Exercises 1.8 与 1.15 。

这一篇想讨论的不是 Fibonacci 数列本身，而是一个更基本的问题：为什么有些组合证明让人觉得“答案本来就该这样”？这种感觉背后，通常是一条自然的 bijection 。

1. 原题



2. 这个题为什么值得认真读



3. 主问题：不相邻的 k 元子集



4. 为什么这个 bijection 自然



5. Fibonacci number 为什么出现



6. Exercise 1.15：Pascal matrix 斜对角线中的同一个结构



7. 直接用 Pascal recurrence 证明斜对角线公式



8. 什么叫一个“有品味”的组合证明



9. 低效视角与高效视角



10. 这一题通向哪里



11. 小结



12. 给读者的两个追问



数学猫 MoMo 酱