組合數學/計數

看起來很奇怪，但有時計數是數學中最困難的事情之一。事實上，將組合數學稱為排列物件的藝術並計數它們並不為過。在組合數學中，當透過列舉所有可能性來計數物件時，蠻力技術通常註定會失敗，我們被迫依賴各種技術和數學思想。有時，即使這些想法也無法幫助我們，我們也必須滿足於建立給定估計或要計數物件的界限。

雙重計數

在組合數學中，雙重計數，也稱為雙向計數，是一種證明技術，它涉及以兩種方式計算集合的大小，以證明集合大小的兩個結果表示式是相等的。我們從兩個角度描述一個有限集合 X，從而得到兩個不同的表示式。透過這兩個角度，我們證明了每一個都等於 |X|。

讓我們看兩個例子。第一個被稱為握手引理，可以簡潔地表述為

在一次大會上，握手次數為奇數的代表人數是偶數。

為了看到這一點，讓 $D_{1},\cdots D_{n}$ 是代表。讓 $x_{i}\,$ 是 $D_{i}\,$ 握手次數，$y\,$ 是發生的握手總數。很明顯，手的伸出次數總共是

$\sum _{i=1}^{n}x_{i}$.

但從另一個角度計數，它僅僅是 $2y\,$ - 每次握手 $y\,$ 伸出的兩隻手。所以，

$\sum _{i=1}^{n}x_{i}=2y$.

現在總共有多少奇數 $x_{i}\,$ 可以出現在總和中。如果奇數 $x_{i}\,$ 的數量是奇數，那麼它們的總和也一定是奇數（例如 2a+1）。當它加到偶數 $x_{i}\,$ 的總和（例如 2b）時，會得到一個奇數（2a+2b+1）。但我們剛剛看到 $\sum _{i=1}^{n}x_{i}$ 是偶數。因此，奇數 $x_{i}\,$ 的數量是偶數。但這僅僅是另一種說法，即握手次數為奇數的代表人數是偶數。

讓我們看另一個例子。我們想要推匯出前 n 個自然數之和的公式。假設我們有一個 (n + 1)×(n + 1) 的點陣。對角線上點的數量正好是 n + 1，並且顯然嚴格位於對角線上的點的數量 S 等於嚴格位於對角線下的點的數量，因此方陣中點的總數是 n + 1 + 2S。另一方面，方陣中點的總數是 (n + 1)²，所以

$(n+1)^{2}=n+1+2S\,$,

因此

$n(n+1)=2S\,$,

所以

$S=\sum _{k=1}^{n}{k}={\frac {n(n+1)}{2}}.$