Question

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

Answer 1

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

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

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