二次项系数具有一定的对称性:
(
n
k
)
=
(
n
n
−
k
)
.
{\displaystyle {n \choose k}={n \choose n-k}.}
证明 :这个等式可以视为两个集合的元素个数。考虑以下n 个元素的集合:
S
=
{
a
1
,
a
2
,
⋯
,
a
n
}
{\displaystyle S=\{a_{1},a_{2},\cdots ,a_{n}\}}
,那么以下两个集合:
A
=
{
C
⊂
S
,
|
C
|
=
k
}
,
B
=
{
C
⊂
S
,
|
C
|
=
n
−
k
}
{\displaystyle A=\{C\subset S,\,|C|=k\},\qquad \,B=\{C\subset S,\,|C|=n-k\}}
集合A 的元素个数是
(
n
k
)
{\displaystyle {n \choose k}}
,集合B 的元素个数是
(
n
n
−
k
)
{\displaystyle {n \choose n-k}}
. 现在构造一个从集合A 到集合B 的映射:
f
:
A
→
B
C
↦
C
S
c
{\displaystyle {\begin{aligned}f&:\,\,A\rightarrow B\\&\,\,\,C\,\,\,\mapsto \,\,C_{S}^{c}\end{aligned}}}
对A 中的每个元素C(包含集合S中的
k
{\displaystyle k}
个元素),映射f 把C映射到它在S中的补集(有S中的
n
−
k
{\displaystyle n-k}
个元素),因此在集合B 中。可以验证,这个映射是双射。所以集合A 的元素个数等于B 的元素个数。也就是说
(
n
k
)
=
(
n
n
−
k
)
.
{\displaystyle {n \choose k}={n \choose n-k}.}
证明两种分解方法数相等
对一个大于2的自然数n,首先考虑将它写成若干个1和2的和,和项顺序不同认为是不同的写法,所有的方法数记作
a
n
{\displaystyle a_{n}}
,例如当n=4的时候,所有的写法是:
4
=
1
+
1
+
1
+
1
=
1
+
1
+
2
=
1
+
2
+
1
=
2
+
1
+
1
=
2
+
2.
{\displaystyle 4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2.}
所以
a
4
=
5
{\displaystyle a_{4}=5}
. 再考虑将它写成若干个大于等于2的自然数 的和,和项顺序不同认为是不同的写法,所有的方法数记作
b
n
{\displaystyle b_{n}}
。则有
a
n
=
b
n
+
2
.
{\displaystyle a_{n}=b_{n+2}.}
这个性质也可以用双射法证明:
证明 :考虑集合
A
n
=
{
(
x
1
,
x
2
,
⋯
,
x
m
)
,
m
⩾
1
,
∀
1
⩽
j
⩽
m
,
x
j
∈
{
1
,
2
}
,
x
1
+
x
2
+
⋯
+
x
m
=
n
}
{\displaystyle A_{n}=\{(x_{1},x_{2},\cdots ,x_{m}),\,\,\,m\geqslant 1,\,\,\forall 1\leqslant j\leqslant m,x_{j}\in \{1,2\},\,\,x_{1}+x_{2}+\cdots +x_{m}=n\}}
B
n
+
2
=
{
(
y
1
,
y
2
,
⋯
,
y
k
)
,
k
⩾
1
,
∀
1
⩽
j
⩽
k
,
y
j
⩾
2
,
y
1
+
y
2
+
⋯
+
y
k
=
n
+
2
}
.
{\displaystyle B_{n+2}=\{(y_{1},y_{2},\cdots ,y_{k}),\,\,\,k\geqslant 1,\,\,\forall 1\leqslant j\leqslant k,y_{j}\geqslant 2,\,\,y_{1}+y_{2}+\cdots +y_{k}=n+2\}.}
对集合
A
n
{\displaystyle A_{n}}
中的一个元素
(
x
1
,
x
2
,
⋯
,
x
m
)
{\displaystyle (x_{1},x_{2},\cdots ,x_{m})}
,假设其中有至少一个数为2,令
x
i
1
=
x
i
2
,
⋯
=
x
i
k
=
2
{\displaystyle x_{i_{1}}=x_{i_{2}},\cdots =x_{i_{k}}=2}
(其中的下标
1
⩽
i
1
<
i
2
<
⋯
<
i
k
⩽
m
{\displaystyle 1\leqslant i_{1}<i_{2}<\cdots <i_{k}\leqslant m}
),其余的等于1。如果
i
k
<
m
{\displaystyle i_{k}<m}
,那么下面设
k
+
1
{\displaystyle k+1}
个数:
y
1
=
x
1
+
⋯
+
x
i
1
,
y
2
=
x
i
1
+
1
+
⋯
+
x
i
2
,
⋮
⋮
y
k
=
x
i
k
−
1
+
1
+
⋯
+
x
i
k
,
y
k
+
1
=
x
i
k
+
1
+
⋯
+
x
m
+
2.
{\displaystyle {\begin{aligned}y_{1}&=x_{1}+\cdots +x_{i_{1}},\\y_{2}&=x_{i_{1}+1}+\cdots +x_{i_{2}},\\&\vdots \quad \quad \quad \vdots \\y_{k}&=x_{i_{k-1}+1}+\cdots +x_{i_{k}},\\y_{k+1}&=x_{i_{k}+1}+\cdots +x_{m}+2.\end{aligned}}}
如果
i
k
=
m
{\displaystyle i_{k}=m}
则
y
k
+
1
=
2
{\displaystyle y_{k+1}=2}
。如果
x
1
=
x
2
=
⋯
=
x
m
=
1
{\displaystyle x_{1}=x_{2}=\cdots =x_{m}=1}
,那么设
y
1
=
n
+
2
{\displaystyle y_{1}=n+2}
。
那么由于各个y元素的和必然是
n
+
2
{\displaystyle n+2}
,所以将
(
x
1
,
x
2
,
⋯
,
x
m
)
{\displaystyle (x_{1},x_{2},\cdots ,x_{m})}
映射到
(
y
1
,
y
2
,
⋯
,
y
k
+
1
)
{\displaystyle (y_{1},y_{2},\cdots ,y_{k+1})}
的映射f 是一个从
A
n
{\displaystyle A_{n}}
到
B
n
+
2
{\displaystyle B_{n+2}}
的映射。从构造方式可以看出,f 是一个单射。
对于
B
n
+
2
{\displaystyle B_{n+2}}
中每一个元素
(
y
1
,
y
2
,
⋯
,
y
k
)
{\displaystyle (y_{1},y_{2},\cdots ,y_{k})}
,将其中的每一个
y
j
{\displaystyle y_{j}}
换成
y
j
−
2
{\displaystyle y_{j}-2}
个1和一个2,然后删去最后一个2,就得到
A
n
{\displaystyle A_{n}}
中的一个元素,所以f 也是一个满射。
也就是说,f 是一个双射。这就证明了
a
n
=
b
n
+
2
.
{\displaystyle a_{n}=b_{n+2}.}