容斥原理與不定方程

摘 要： 要求一個不定方程的全部的解相當困難。利用容斥原理和排列組合的有關知識可求得一類不定方程的正整數解的組數，本文例舉了一些解該類型題的常用的技巧與方法。

關鍵詞： 不定方程 隔板法 容斥原理

一

不定方程，是指未知數的個數多于獨立方程的個數的方程或方程組。一般不定方程存在無窮多組解。求不定方程的正整數解的問題，屬于數學中的一個古老而重要的分支——數論的內容。而數論的初級階段所涉及的一些數學方面的知識，看起來似乎很簡單，任何人都能了解，但在解題中合理、靈活地應用，卻是多數人辦不到的。一般來說，求解不定方程的整數解這一類型的題目，有時并不需要很多的基礎知識，但卻必須具有較強的邏輯思維和邏輯推理能力。

例1：求方程x+x+x+x=18的正整數解的組數。

解析：求方程x+x+x+x=18的正整數解的組數，可以處理成以下這種模型：把18個小球一字排開，中間有17個空位，若從中任取3個空位插上隔板，則可把這18個小球分成4份，每份至少1個小球，如果x，x，x，x分別對應取其中一份，隔板放法的種數恰好就是方程x+x+x+x=18的正整數解的組數，即有C=680個正整數解。（這種解決問題的方法叫做隔板法）

由這個例子我們可以得到一個定理。定理：方程x+x+x+…+x=n（m≤n，m，n∈N）的正整數解的組數為C。

證明：由題意，方程的正整數解的組數等于把n個元素分成m組，每組至少一個共有的分法數。

n個元素中間有（n-1）個空，在其中選取（m-1）個放入隔板即可，共有C種做法，即方程解的組數共有C。

注意：定理對x（i=1，2，…，m）的基本要求為x≥1，x∈N（i=1，2，…，m）。

二

對于不滿足定理條件的不定方程，有的可以通過轉化，然后用定理來解決。

例2：求不定方程x+x+x+x=18的非負整數解的組數。

解析：求不定方程x+x+x+x=18的非負整數解的組數，即對x（i=1，2…4）的要求為x≥0，x∈N（i=1，2，…，4），它不滿足定理的要求，不能直接用定理來解決，但是x+x+x+x=18（x≥0，x∈N，i=1，2，…，4）等價于（x+1）+（x+1）+（x+1）+（x+1）=22（x≥0，x∈N，i=1，2，…，4），令x+1=x′，則原不定方程等價于x′+x′+x′+x′=22（x′≥1，x∈N，i=1，2，…，4），此時不定方程滿足定理的要求，而以上三個不定方程解的組數是相同的。所以原不定方程的解的組數C=1330。

三

以上類型的轉化，就是通過變量代換，把不滿足定理條件的不定方程，轉換為滿足定理條件的不定方程。應用容斥原理和定理還能夠解決另一類型的不定方程的解的組數問題。在這里先介紹一下容斥原理。

如上圖所示，集合A∪B的元素個數|A∪B|=|A|+|B|-|A∩B|，

對于三個集合A，B，C的情況，我們有|A∪B∪C|=|A|+|B|+|C|-（|A∩B|+|B∩C|+|C∩A|）+|A∩B∩C|。

將上述公式推廣到有限集合的情形，得到下面的容斥原理一：

|A∪A∪…∪A|=|A|-|A∩A|+|A∩A∩A|-…+（-1）|A∩A…∩A|。

證明：n=2時，有|A∪A|=|A|+|A|-|A∩A|。

假設n-1時有|A∪A∪…∪A|=|A|-|A∩A|+|A∩A∩A|-…+（-1）|A∩A…∩A||A∪A∪…∪A|=|（A∪A∪…∪A）∪A|=|A∪A∪…∪A|+|A|-|（A∪A∪…∪A）∩A|。

而（A∪A∪…∪A）∩A=（A∩A）∪（A∩A）∪…∪（A∩A），

∴|（A∪A∪…∪A）∩A|=（A∩A）∪（A∩A）∪…∪（A∩A）=|A∩A|+|A∩A|+…+|A∩A|-|A∩A∩A|-|A∩A∩A|-…-|A∩A∩A|+…+（-1）|A∩A∩…A|= |A|-|A∩A|+|A∩A∩A|-…+（-1）|A∩A…∩A|，

定理得證。

另外我們容易證明若A，A，…，A是集合I的子集，CA表示A在I中的補集，則有：

C（A∪A∪…∪A）=CA∩CA∩…∩CA，

C（A∩A∩…∩A）=CA∪CA∪…∪CA。

由以上兩式我們得到容斥原理二：

|CA∩CA∩…∩CA|=|I|-|A∪A∪…∪A|=|I|-|A|+|A∩A|-|A∩A∩A|+…+（-1）|A∩A…∩A|。

例3：求不定方程x+x+x+x=18（x≤5，x≤4，x≤3，x≤6，x∈N，i=1，2，…，4）的解的組數。

分析：記x+x+x+x=18（x∈N，i=1，2，…，4）的解的集合為I，則|I|=C=680。記x+x+x+x=18（x＞5，x∈N，i=1，2，…，4）的解的集合為A，則|A|=C=220。記x+x+x+x=18（x＞4，x∈N，i=1，2，…，4）的解的集合為A，則|A|=C=286。記x+x+x+x=18（x＞3，x∈N，i=1，2，…，4）的解的集合為A，則|A|=C=364。記x+x+x+x=18（x＞6，x∈N，i=1，2，…，4）的解的集合為A，則|A|=C=165。

|A∩A|為x+x+x+x=18（x＞5，x＞4，x∈N，i=1，2，…，4）的解的個數，|A∩A|=C=56，同理|A∩A|=C=84，|A∩A|=C=20，|A∩A|=C=120，|A∩A|=C=35，|A∩A|=C=56，|A∩A∩A|=C=10，|A∩A∩A|=0，|A∩A∩A|=C=1，|A∩A∩A|=C=4，|A∩A∩A∩A|=0。

所求的x+x+x+x=18（x≤5，x≤4，x≤3，x≤6，x∈N，i=1，2，…，4）的解的組數即為|CA∩CA∩CA∩CA|=|I|-|A|- |A|-|A|-|A|+|A∩A|+|A∩A|+|A∩A|+|A∩A|+|A∩A|+|A∩A|-|A∩A∩A|-|A∩A∩A|-|A∩A∩A|-|A∩A∩A|+ |A∩A∩A∩A|=C-C-C-C-C+C+C+C+C+C+C-C-0-C-C+0=1。

參考文獻：

［1］單慶權.利用不定方程巧解一類題［J］.數理化解題研究，2007，（05）.

［2］蔣彩榮.利用不定方程解一類排列組合問題［J］.數學通報，2004，（08）.

［3］劉慶生.求不定方程的整數解［J］.內蒙古教育學院學報，1994，（09）.

［4］唐續俞.容斥原理及一般公式［J］.廣州航海高等專科學校學報，1995，（12）.