一次方程式非負整數解與排列組合

如果有3個學生要競逐爭取4個獎牌,可能有人沒得到任何獎牌,則他們各自獲得的獎牌數有幾種可能結果?

假設3個學生得到獎牌數分別是x1、x2、x3,依題意可列出方程式x1+x2+x3=4此方程式有幾組非負整數解即所求

可將4視為4個 ☆,即☆☆☆☆,將他們和2個加號 ++作排列,其排列數即為所求。

排列次別 圖示解
1

++☆☆☆☆

0+0+4
2 +☆+☆☆☆ 0+1+3
3 +☆☆+☆☆ 0+2+2
4 +☆☆☆+☆ 0+3+1
5 +☆☆☆☆+ 0+4+0
6 ☆++☆☆☆ 1+0+3
7 ☆+☆+☆☆ 1+1+2
8 ☆+☆☆+☆ 1+2+1
9 ☆+☆☆☆+ 1+3+0
10 ☆☆++☆☆ 2+0+2
11 ☆☆+☆+☆ 2+1+1
12 ☆☆+☆☆+ 2+2+0
13 ☆☆☆++☆ 3+0+1
14 ☆☆☆+☆+ 3+1+0
15 ☆☆☆☆++ 4+0+0

此方程式有幾組非負整數解相當於求++☆☆☆☆的排列數=$\large\frac{6!}{2!4!}$=15,相當於組合數$\small\left( \begin{array}{} 6 \\ 4 \end{array} \right) $。

推廣至x1+x2+x3+......+xn=m,m是自然數,此方程式的非負整數解有$\large\frac{(m+n-1)!}{(n-1)!m!}$,即$\small\left( \begin{array}{} m+n-1 \\   m\end{array} \right) $組。

 

n=       m=


        

的非負整數解有

 


Copyright ©昌爸工作坊 all rights reserved.