Question

對(duì)正整數(shù)n≥1的一個(gè)劃分π，是指將n分成一個(gè)或若干個(gè)正整數(shù)之和，且按非減順序排列(如n＝4，劃分π有1＋1＋1＋1，1＋1＋2，1＋3，2＋2及4共5種)．對(duì)任一劃分π，定義A(π)為劃分π中數(shù)1出現(xiàn)的個(gè)數(shù)；B(π)為π中出現(xiàn)不同的數(shù)的個(gè)數(shù)(如對(duì)n＝13的一個(gè)劃分π：1＋1＋2＋2＋2＋5而言，A(π)＝2，B(π)＝3)．求證：對(duì)任意正整數(shù)n，其所有劃分π的A(π)之和等于B(π)之和．

Answer 1

證明：設(shè)p(n)表示n劃分的個(gè)數(shù)．那么第一個(gè)位置是1的劃分有p(n－1)個(gè)，第二個(gè)位置上是1的(當(dāng)然它第一個(gè)位置上也是1)的劃分有p(n－2)個(gè)．等等．第n－1個(gè)位置上是1的劃分有P(1)＝1個(gè)，第n個(gè)位置上是1的只有1種．若令P(0)＝1．則所有劃分中含1的數(shù)A(π)之和等于P(n－1)＋P(n－2)＋…＋P(1)＋P(0)．

另一方面，從含有1的每個(gè)劃分中拿去一個(gè)1，都成為一個(gè)(n－1)的劃分，共拿去P(n－1)個(gè)1．再?gòu)暮��?的每個(gè)劃分中拿去一個(gè)2，都成為n－2的劃分，共拿去P(n－2)個(gè)2．…從含有(n－1)的劃分(只有一個(gè)：1＋(n－1)，拿去(n－1)，即拿去了P(1)＝1個(gè)1．再加上含有n的一個(gè)劃分，n為P(0)＝1個(gè)，故B(π)總和也等于P(n－1)＋P(n－2)＋…＋P(1)＋P(0)．

因此，A(π)＝B(π)．