1. 基本計數(shù)原理
設(shè)集合S的 一個劃分 即為S的子集的集合贰健，使得S的每一個元素恰好是這些子集之一的元素：
子集稱為該劃分的部分苏研。
集合S的元素個數(shù)表示為, 又稱之為S的大小等浊。
加法原理
設(shè)集合S劃分為部分 。則S的元素個數(shù)可以通過找出它的每一個劃分的個數(shù)來確定，我們把這些數(shù)相加撒踪，得到：
如果集合可以重疊掸绞，那么要使用一個更深刻的原理（容斥原理）來計數(shù)S中的元素個數(shù)。
用選擇的術(shù)語敘述加法原理的形式為 ：如果有p種方法能夠從一堆中選擇一個物體耕捞，而有q種方法能從另一堆中選擇一個物體衔掸，那么從這兩堆中選擇一個物體的方法共有p+q種。這種形式的加法原理可以很容易推廣到多堆俺抽。
乘法原理
令S是元素的有序?qū)?a, b)的集合具篇，其中一個元素a來自大小為p的一個集合，而對a的每個選擇凌埂，元素b存在著q種選擇驱显。于是，S的大小為p × q :
乘法原理的第二種形式： 如果一項任務(wù)有p項結(jié)果瞳抓，而不論第一項任務(wù)的結(jié)果如何埃疫，第二項任務(wù)都有q個結(jié)果，那么孩哑，這兩個任務(wù)連續(xù)執(zhí)行就有p×q個結(jié)果栓霜。
注意這里兩項任務(wù)的關(guān)系不能存在依賴的情況，如果出現(xiàn)横蜒，需要交換次序胳蛮，優(yōu)先選擇約束性最強的選擇。
減法原理
令A(yù)是一個集合丛晌，而U是包含A的更大的集合仅炊。設(shè)
是A在U中的補。那么A中的元素個數(shù)|A|由下列法則給出：
在應(yīng)用減法原理中澎蛛，集合U通常是包括討論中所有元素的某個自然的集合（即所謂的泛集）抚垄。使用減法原理只有當(dāng)對U中的元素計數(shù)和對中元素計數(shù)比對A中元素計數(shù)容易時才有意義。
除法原理
令S是一個有限集谋逻，它以下述方式被劃分成k部分呆馁，每一部分包含相同數(shù)目的元素。此時毁兆，劃分中的部分的數(shù)目由下述公式給出：
(在一個部分中的元素個數(shù))
于是浙滤，如果我們知道S中元素個數(shù)以及各部分所含元素的相同的個數(shù)，則可以確定部分的數(shù)目气堕。
計數(shù)問題的分類
多重集：集合有一條重要原則纺腊，即集合中的元素都是不可重復(fù)的畔咧，而多重集則沒有這一限制
多數(shù)計數(shù)問題都可以分類為一下形式：
- 計數(shù)對象的有序排列的個數(shù)或者是有序選擇的個數(shù)
- 任何對象都不重復(fù)（這里重復(fù)是指排列過后不能再次排列或者拿過的東西不能再拿一遍）
- 允許對象重復(fù)（可以再次排列或拿取，但可能有限制）
- 計數(shù)對象的無序組合的個數(shù)或者是無序選擇的個數(shù)
- 任何對象都不重復(fù)（同上）
- 允許對象重復(fù)（同上）
如果我們允許對象重復(fù)摹菠，可以變換一種思維方式盒卸，將集合擴展為可重集骗爆，這樣從可重集中選擇對象次氨，選擇出來的結(jié)果正好對應(yīng)于集合中對象允許重復(fù)的排列組合。
2.排列與組合
集合的排列
令是正整數(shù)摘投。 我們把
個元素的集合
的一個
排列理解為：在n個元素中的取出r個元素的有序擺放的數(shù)目煮寡。
我們用 表示n個元素集合的r排列的數(shù)目。如果
犀呼。顯然幸撕，對每一個正整數(shù)
外臂。n元素集合S的一個n排列被更簡單地稱為S的一個排列或n個元素的一個排列坐儿。于是，集合S的一個排列就是以某種順序列出S的所有元素宋光。
定理1 ： 對于正整數(shù)
定義n!（讀作n的階乘）為 罪佳。并約定
逛漫。于是我們可以寫成：
對于赘艳，正好與r = 0時的公式一致酌毡。n個元素的排列數(shù)為
在上面的排列中我們是把對象排成一條線的，稱之為線性排列蕾管，或線排列枷踏。如果我們更看重對象之間的相對位置而不是絕對位置時，就有了圓排列掰曾，或循環(huán)排列的概念呕寝。在兩個圓排列中，通過旋轉(zhuǎn)能夠重合的婴梧，我們認為這是同一個排列贮预。下面給出正式定義：
從集合個不同元素中包归，取出r個元素按照某種次序（如逆時針）排成一個圓圈，稱這樣的排列為圓排列，或循環(huán)排列轨功。
定理2 : n個元素的集合的循環(huán)r排列的個數(shù)由給出。特別的乍恐，n個元素的循環(huán)排列的個數(shù)是
默蚌。
在圓排列中辆琅，還有一種項鏈排列，在圓排列中这刷，經(jīng)翻轉(zhuǎn)能與原來重合的排列視為同一排列婉烟。項鏈排列在圓排列的基礎(chǔ)上計算，為圓排列的一半暇屋。
例子 用20個不同顏色的念珠串成一條項鏈似袁，能夠做成多少不同的項鏈？
20個念珠共有20咐刨！種不同的排列昙衅。由于每條項鏈都可以旋轉(zhuǎn)而不必改變念珠的排列，項鏈的數(shù)目最多為20定鸟！/20=19而涉！。又由于項鏈不可以翻轉(zhuǎn)過來而念珠的排放未改動联予，因此項鏈的總數(shù)是19啼县！/2。
下面介紹幾個排列中常用的恒等式：
