用母函數(shù)求解排列問題

［摘 要］ 母函數(shù)是組合數(shù)學中的一個重要概念，用母函數(shù)來處理中學數(shù)學中的一些排列問題，其可操作性強，學生容易理解. 文章先介紹指數(shù)型母函數(shù)的相關(guān)內(nèi)容和定理，然后結(jié)合實例給出其應用.

［關(guān)鍵詞］ 排列問題；母函數(shù)；指數(shù)型母函數(shù)；理解；應用

計數(shù)問題在日常生活、生產(chǎn)中普遍存在. 計數(shù)問題屬于組合問題，而組合中有一個重要概念——母函數(shù)（也叫發(fā)生函數(shù)、生成函數(shù)）［1］. 指數(shù)型母函數(shù)（簡稱指母函數(shù)）正是將復雜的計數(shù)問題簡單化的一個工具，利用指母函數(shù)可以輕松求解排列問題.

預備知識

定義1 設(shè)a，a，…，a，…是一個給定的數(shù)列，我們稱形式冪級數(shù)

f（x）=xn=a+ax+x2+x3+…+xn+…①

為這個數(shù)列的指數(shù)型母函數(shù)，簡稱指母函數(shù)［2］.

例如，數(shù)列1，1，1，…，1，…的指母函數(shù)是f（x）=xn=1+x++…++…. 這個指母函數(shù)非常重要，我們專門用f（x）=ex來記它，即f（x）=ex=1+x++…++….

規(guī)定：在進行這些運算時，把形式冪級數(shù)看成冪級數(shù)，然后按照冪級數(shù)的運算法則去運算.

定義2 設(shè)f（x）=xn和g（x）=xn是兩個形式冪級數(shù)，則

f（x）±g（x）=xn，f（x）·g（x）=xn（其中c=Cakbn-k）.

定理1 ex·ey=ex+y.

在定理1中，取y=x，則（ex）2=e2x，即

=xn.

推論1 （ex）m=emx，即

=xn.

在定理1中，取y=-x，則ex·e-x=1，即=e-x. 由ex=1+DaiWAzYeH5rdxl986iFvKQ==x++…++…，e-x=1-x+-…+（-1）n+…，得到：

推論2 ex+e-x=2

1+++…++…

，ex-e-x=2

x+++…++…

.

注：對于指數(shù)冪ax（a>0，且a≠1），顯然ax·ay=ax+y. 從定理1可以看出，ex·ey=ex+y具有指數(shù)冪的運算性質(zhì). 這就是稱式①為指母函數(shù)的原因.

用指母函數(shù)求解排列問題

排列問題，困難在于對問題背景的理解，這是一個數(shù)學化過程，需要通過不同情境加強訓練、加深理解.我們先來看看下列三類排列問題.

問題1 （不許重復的排列）從n個不同的物體中，任意取出r個作排列，不許重復，問有多少種不同的排法？

問題2 （允許無限重復的排列）從n個不同的物體中，任意取出r個作排列，允許重復，問有多少種不同的排法？

問題3 （允許有限重復的排列）設(shè)n個物體中，有n個物體A，n個物體A，…，n個物體A，n+n+…+n=n，現(xiàn)從中任取r個作排列，問有多少種不同的排法？［3］

分析 問題1的解答很簡單，不同的排列的總數(shù)為A=n（n-1）…（n-r+1）. 特別地，當r=n時，不同的排列的總數(shù)為A=n（n-1）…3×2×1=n！. 這在中學課本上已經(jīng)很熟悉了.

問題2的解答也不困難.因為允許重復，所以每個排列的r個位置上都有可能放n個不同物體中的任何一個，即每個位置都有n種可能，因此不同的排列的總數(shù)為nr［4］.

解答困難的是問題3，因為每個物體重復的次數(shù)是有限的，這給問題帶來了復雜性.但如果考慮r=n的情形，問題還不算太難.

定理2 設(shè)n個物體中，有n個物體A，n個物體A，…，n個物體A，n+n+…+n=n，則這n個物體不同的排列的總數(shù)為.

證明 由于對每個排列來說，n個物體A，n個物體A，…，n個物體A都出現(xiàn)在排列中，因此n個物體排列的總數(shù)為n！，而在這n！個排列中有很多的排列是一樣的，例如n個物體A任意交換位置，若其他物體不動，這樣得到的排列全是一樣的，這種相同的排列有n！個. 同理，對物體A，A，…，A，也會有同類情況. 去掉這些相同的排列后，真正不同的排列的總數(shù)為.

注：這是問題3中當r=n時的解答.最困難的是r<n的情形，這沒有一般公式，而指母函數(shù)是解決這類問題的有力工具.

定理3 設(shè)n個物體中，有n個物體A，n個物體A，…，n個物體A，n+n+…+n=n，從這n個物體中任取r（r<n）個物體，不同的排列的總數(shù)記為a，則數(shù)列｛a｝的指母函數(shù)為f（x）=

1+x++…+

1+x++…+

…

1+x++…+

②.

證明 讓第i個括號代表第i個物體A（i=1，2，…，k）.從第一個括號中取出項，解釋為“取出3個物體A”；從第二個括號中取出項，解釋為“取出4個物體A”；其余類似.

現(xiàn)在研究式②的展開式中的系數(shù).

合并同類項前，式②的展開式中的是由各個括號中的項相乘而來的：··…·=，這里0≤m≤n，0≤m≤n，…，0≤m≤n，而且m+m+…+m=r. 故··…·=·. 由此可知，的系數(shù)是③，而且m+m+…+m=r.

根據(jù)定理2可知，式③恰好就是這r個物體不同的排列的總數(shù)：在這r個物體中有m個A，m個A，…，m個A，這說明乘積··…·就對應一種排列. 由于m（i=1，2，…，k）可以取遍0，1，2，…，n（i=1，2，…，k）中的所有整數(shù)，因此合并同類項后，的系數(shù)就表示從這n個物體中取出r個物體的不同的排列的總數(shù).這就證明了式②就是數(shù)列｛a｝的指母函數(shù).

在此我們可以把定理3推廣到更一般的情形：

定理4 設(shè)A=｛a，a，…，a｝，M，M，…，M均為非負整數(shù)集的子集，從A中可重復地選取r個元素作排列. 如果a可重復選取的全部次數(shù)為M（k=1，2，…，n），記所有可能的排列數(shù)為er，則數(shù)列｛er｝（r≥0）的指母函數(shù)為f（x）=

…

. 將指母函數(shù)解析式展開，的系數(shù)就是所求的排列數(shù)e.

證明留給讀者完成.

指母函數(shù)應用舉例

題1 將8個不同的球分發(fā)給4個不同的班級，要求每個班至少分得一個球，問有多少種不同的分法？

解析 將8個不同的球排成一列，4個班依次編號為1，2，3，4.對于一個滿足條件的分法，若把某個球分給編號為i的班，就在該球所排的位置上填上i，則得到｛1，2，3，4｝的一個“8可重”排列（即從集合｛1，2，3，4｝中可重復地選取8個元素作成排列）. 由于每個班至少分得一個球，所以每個數(shù)至少出現(xiàn)一次，即每個數(shù)出現(xiàn)的次數(shù)都屬于集合｛1，2，3，…｝. 將n個不同的球分給4個不同的班且每個班至少分得一個球的分法數(shù)記為a，由定理4可知數(shù)列｛a｝（n≥1）的指母函數(shù)為f（x）=

x+++…

=（ex-1）4=e4x-4e3x+6e2x-4ex+1=xn-4xn+6xn-4xn+1=（4n-4×3n+6×2n-4）+1. 由此可得，的系數(shù)a=48-4×38+6×28-4=40824. 所以，共有40824種不同的分法.

題2 用數(shù)字1，2，3，4作六位數(shù)，每個數(shù)字在六位數(shù)中出現(xiàn)的次數(shù)不得大于2，問可作出多少個不同的六位數(shù)？

解析 這是排列問題，每個數(shù)字出現(xiàn)的次數(shù)都屬于集合｛0，1，2｝. 設(shè)所求為N，由定理4可知，N是指母函數(shù)f（x）=

1+x+

的展開式中的系數(shù)，而

1+x+

=［x2+（2x+2）］4=［x8+4x6（2x+2）+6x4（2x+2）2+4x2（2x+2）3+（2x+2）4］，所以N=（4×2+6×22）=1440.

題3 把n（n≥1）個彼此不同的球放到4個不同的盒子A，A，A，A中，要求A有奇數(shù)個球，A有偶數(shù)個球，問不同的放球方法有多少種？

解析 設(shè)不同的放球方法有a種.因為要求A有奇數(shù)個球，A有偶數(shù)個球，A，A中球的個數(shù)沒有限制，所以A盒子出現(xiàn)的球的個數(shù)屬于集合｛1，3，5，…｝，A盒子出現(xiàn)的球的個數(shù)屬于集合｛0，2，4，…｝，A，A盒子出現(xiàn)的球的個數(shù)都屬于集合｛0，1，2，3，…｝.

由定理4可知，數(shù)列｛a｝的指母函數(shù)是f（x）=

x+++…

1+++…

1+x+++…

.

由推論1和推論2可得f（x）=··（ex）2=（e4x-1）=·=. 比較（n≥1）的系數(shù)，得a=4n-1.

結(jié)束語

母函數(shù)分為普通型母函數(shù)（簡稱普母函數(shù)）和指數(shù)型母函數(shù)（簡稱指母函數(shù)）.普母函數(shù)主要應用于求解組合問題，而指母函數(shù)則主要應用于求解排列問題.高中階段的排列問題，有些是難以處理的，這時可借助指母函數(shù)來求解. 利用指母函數(shù)求解排列問題，學生容易理解，而且可操作性強，是處理排列問題的好方法.

參考文獻：

［1］ 李鴻昌，徐章韜. 用母函數(shù)理解組合問題［J］. 數(shù)學通訊，2023（10）：59-61+66.

［2］ 曹汝成. 組合數(shù)學［M］. 廣州：華南理工大學出版社，2000.

［3］ 劉會科. 母函數(shù)在組合計數(shù)中的應用［J］. 數(shù)理化解題研究，2016（13）：16-17.

［4］ 高仕學. 用母函數(shù)法統(tǒng)一解決三類排列與組合問題［J］. 課程教育研究，2017（07）：161.