重複組合、巴斯卡定理及Σk^n的公式(課堂筆記)

在教到重複組合的課程時，有一道題目：x₁＋x₂＋x₃＝n的非負整數解有幾組？解法類同n顆相同的球與2個＋號做排列的情況，即組。

若將題目改成：x₁＋x₂＋x₃≦n的非負整數解有幾組？可以用兩種想法來考慮，較直觀的方式，就是直接算x₁＋x₂＋x₃＝0、x₁＋x₂＋x₃＝1、x₁＋x₂＋x₃＝2、…、x₁＋x₂＋x₃＝n的非負整數解的組數和，即有組解，再利用巴斯卡定理，可得：

                                                             

                                                        

                                                        

                                                        

                                                        

                                                        

                                                        

這一題也可以直接這樣思考，令x₄＝n－(x₁＋x₂＋x₃)，則x₁＋x₂＋x₃≦n的非負整數解的組數，就與x₁＋x₂＋x₃＋x₄＝n的非負整數解的組數一樣多，故共有組，與上面的解法結果一致。

若我們直接考慮這個結論，把它寫成

故得

同理，若由，重寫後可得

利用同樣的方法，也可以得到其他Σkⁿ的公式。