存在性問題與計數問題是組合數學的兩個主要內容.由於組合計數的內容豐富，方法靈活，因而成為競賽數學的重要內容之一.在解答組合計數問題時，除應掌握一些基本的計數原理之外，還應掌握一些常用的分析問題的手段與方法.
下面對組合計數的基本原理與方法作一介紹.
1. 基本原理
定理1 設是有限集，是乙個對映.
（1） 若為單射，則；
（2） 若為滿射，則；
（3） 若為雙射，則；
（4） 是乙個正整數，若，都恰有個原象，則.
定理2 不定方程
1）的非負整數解的個數為.
證對於方程（1）的乙個非負整數解，作0—1序列
2）序列（2）中恰有個，個，將與0—1序列（2）相對應.反之，任給乙個恰有個，個的0—1序列，將第1個前面零的個數記為，第1個與第個1之間零的個數記為，…，將第個後面零的個數記為，則有
，從而知是（1）的乙個非負整數解.這樣，我們在方程（1）的非負整數解構成的集合與恰有個，個的0—1序列構成的集合之間建立了雙射.由於恰有個，個的0—1序列可按如下方式給定：
先在個位置上選個位置安排，再在其餘位置上安排，所以，這樣的0—1序列共有個，從而知不定方程（1）的非負整數解共有個.
定理2是乙個重要的計數模型，許多計數問題可化歸成形如方程（1）的非負整數解的個數問題.例如，人們把從元集中可重複選取的個元素稱為的可重組合.關於元集的可重組合的個數，我們有如下結論.
定理3元集的可重組合的個數為.
證設元集，是的可重組合.對於，設中恰有個，則，為整數，且
1）因此是不定方程（1）的非負整數解.
反之，對於不定方程（1）的乙個非負整數解，在中取個，取個，…，取個，則這個元素構成了的可重組合.因此，集合的可重組合與不定方程（1）的非負整數解之間建立了一一對應關係.由定理2知，不定方程（1）的非負整數解的個數為，從而知集合的可重組合的個數為.
在元集合中可重複地選取個元素，並把這個元素排成一行，我們把這樣的排列稱為的可重排列.關於元集的可重排列，我們有如下結論：
定理4元集的可重排列的個數為.
證元集的可重排列可分如下步完成：第一步確定第乙個位置上的元素，第2步確定第2個位置上的元素，…，第步確定第個位置上的元素.由於每個位置上的元素有種安排方式，由乘法原理知共有種安排方式，所以元集的可重排列的個數為.
定理5 設為元集，為正整數，.
，則在的可重排列中，恰出現次，恰出現次，…，恰出現次的可重排列的個數為
.證滿足定理條件的可重排列可分為如下步完成：第一步在個位置中選取個位置安排個，共有種方法；第2步在剩下的個位置中選取個位置安排個，共有種方法，…，第步在個位置中選取個位置安排個，有種方法，第步在個位置安排個，只有1種方法，由乘法原理知，共有的安排方式為
.中學教材中討論的排列通常稱為線排列.我們把從元集中選取個不同的元素排在乙個圓周上的排列稱為元集的圓排列.
根據這個定義可知，將乙個元集的圓排列旋轉後得到的排列仍是原排列.對於圓排列，我們有如下結論.
定理6元集的圓排列的個數為
.證對於元集的乙個圓排列，在任意兩個元素之間剪開，拉直後得到乙個線排列，這樣，乙個圓排列可展成個線排列.又易知，元集的任乙個元的線排列將首尾連起來就成為這個元集的乙個圓排列，從而知元集的元線排列的個數是該集合圓排列的個數的倍，而元集的元線排列的個數為，從而知結論成立.
推論1個不同元素排成乙個圓的排列方法有種.
推論2 用粒不同的珠子串成一根項鍊的方法有種.
推論1與推論2留給讀者證明.
2. 方法解讀
對於組合計數問題，除直接用計數的基本原理與公式之外，常用的方法還有列舉法、
對應法和遞推方法.列舉法是根據計數問題的特點將計數物件或方法進行分類或分步，計算出各類物件的數目，然後用加法原理或乘法原理進行計數.對應法是通過一一對映，將不熟悉的計數問題轉化成我們熟悉的計數問題.
遞推方法是建立實際問題所對應的數列的乙個遞推關係，然後用遞推關係的解法進行求解.下面我們用例項對這幾種方法作一說明.
例1 用紅旗面，黃旗面，藍旗面排成一列組成一種訊號，共可排出多少種不同的訊號.
分析每種訊號是種不同顏色旗幟的乙個可重複排列，且每種顏色旗幟重複的次數是確定的，故可用定理5.
解由定理5知，可排出的訊號的種數為
.例2 （2023年全國高中聯賽試題）設三位數，若以為三條邊的長可以構成乙個等腰三角形（含等邊三角形），則這樣的三位數有多少個.
分析將等腰三角形分為如下三類：①等邊三角形；②腰大於底的等腰三角形；③腰小於底的等腰三角形，易對每一類分別計數.
解 （1）當時，由於，從而知等邊三角形有個；
（2） 當時，此時三角形由數對所唯一確定，是的乙個組合，故共有種.
（3） 當時，要成為乙個三角形的邊，還應有.從取出滿足條件的數對有種，其中使的有如下表中的種：
故此時能構成的等腰三角形有種.
由加法原理知，滿足題設的三位數共有
.例3 設是正整數，若且的最大公約數是，則稱有序陣列為素勾股陣列.已知是恰有個素因子的奇數，求素勾股陣列的個數.
解設，其中是互不相同的奇素數，是正整數.，1）
對於，若存在，使得且，則，因為為奇素數，所以，從而，這與的最大公約數為相矛盾，所以恰整除與中的乙個.由（1）知，只能是與之一的因子，從而的取值有種（組成時，每個的選取有取與不取兩種方式）.注意到
，故的上述取值只有一半合乎要求，即滿足（1）的有種.
又若，，與互素，則令，
從而有，，.
綜上知，滿足題設的素勾股陣列有個.
例4個女孩和個男孩排成一圈，任何兩個女孩之間至少有個男孩，問共有多少種排列方法？
分析圓排問題通常化為線排問題.先取定乙個女孩a排在圓上作為「標識」，再按順時針方向從與a相鄰的位置開始依次將個位置標號為，則其餘個女孩與個男孩是這32個位置上的線排列，要求號位排男孩，且任何兩個女孩之間至少有兩個男孩.故問題化歸成如下計數問題：
個女孩和個男孩排成一排，每個女孩左右兩邊均至少有個男孩，有多少種排法.下面對這一計數問題作解答.
解對於上述線排列，可分兩步完成：第一步確定男女的站位方式；第二步確定男孩與女孩在每一種站位方式上的排法.
為了確定男女的站位方式，我們用表示第1個女孩前面的男孩數，對於，用表示第個女孩與第個女孩之間的男孩數，用表示第7個女孩後面的男孩數，則，從而每一種站位方式唯一對應不定方程
1）的乙個整數解.
令，，則有
2）而不定方程（2）的非負整數解的乙個數為
，從而知男女的站位方式有種.又當男孩與女孩的位置確定之後，個女孩在個位置上的排法有種，個男孩在個位置上的排法有種.由乘法原理知，滿足條件的排法種數為：.
例5 設正邊形內接於圓，該圓的圓心為，考慮所有以這邊形的頂點為頂點的三角形，其中有多少個三角形內部含該圓的圓心？
分析是三角形外接圓的圓心.易知三角形的外心在三角形內部的充要條件是這個三角形為銳角三角形.因此，問題歸結為求以正邊形的頂點為頂點的銳角三角形的個數.
又對正邊形的兩個頂點，連並延長交⊙於，連並延長交⊙於,如圖1，則對於正邊形的另一點，△為銳角三角形的充要條件是點在弧上.
圖1圖2
解如圖2，先取定乙個頂點,將其餘個頂點依次標號為.對於，設的延長線交⊙於，的延長線交⊙於，則弧上有正邊形的個頂點，而△為銳角三角形的充要條件是頂點在弧上，於是以為頂點的銳角三角形有個.從而知以為頂點的銳角三角形的個數為
.因為點有種取法，且在積中，每個銳角三角形均被計算了三次，所以滿足題設條件的三角形個數為
.例6 乙個盒子被鎖上了若干把鎖，不同的鎖鑰匙不同.盒子上的所有鎖被開啟後盒子才能開啟.
現有個人，每個人都有其中某些鎖的鑰匙.已知他們中的任何個人均不能開啟盒子，而任何個人均能開啟盒子，試問這個盒子上最少要鎖上多少把鎖，並求此時每把鎖要配多少把鑰匙.
分析因為任何人組都至少有一把鎖不能開啟，任何人組都能開啟所有的鎖.因此可考慮建立人組與鎖之間的對應關係.
解令為這個人構成的集合，是盒子上所有鎖構成的集合，.我們規定到的對映如下：，設中的個人不能開啟鎖，則令（當中的個人不能開啟的鎖有多把時，任取一把鎖即可），下證是到的單射.
事實上，若有，使得
，則中的人均不能開啟鎖，又，這與題設矛盾.
因為是到的單射，所以.又當盒子上的鎖為把時，是到的雙射，此時對於每一把鎖，必有唯一的，使得中的個人均不能開啟鎖；又因為任意個人均能開啟鎖，從而知剩下的個人均能開啟鎖，所以鎖應配把鑰匙.
綜上可知，盒子上至少應鎖上把鎖，每把鎖應配把鑰匙.
例7 定義：稱子集是好的，如果它有下列性質：
1 若，則且；
2 若，則.
空集和都是好的.
稱子集是好的，如果它有下列性質：
若，則且.
空集和都是好的.
記，求的好子集的個數.
分析與相關，且不易直接計算，因此可考慮建立所滿足的乙個遞推關係.
解易知.當時，若，則的好子集分為兩類：第一類是不含的好子集，依題意知這樣的好子集也不含，因此，這樣的好子集有個，即個.
第二類是含的好子集，依題意知這樣的好子集可含，也可不含，共有個，即有個，從而有
1）同理可證，當時，也有（1）成立.
解遞推關係（1）可得
.例8 求位十進位制正整數**現偶數個的數的個數.
分析所求結論與相關，而又不易直接計數，因此希望通過用遞推關係求解.在建立遞推關係時，需要用到位十進位制數中恰有奇數個的數的個數，所以應建立所求數列所滿足的遞推關係組.
解用表示位十進位制正整數**現偶數個的數的個數，表示位十進位制正整數**現奇數個的數的個數.則有.當時，我們將所有含偶數個的位十進位制正整數構成的集合記為，含且的個位不為，且的個位為，則.
，，即1）
分類計數原理和分步計數原理教案
10.1分類計數原理和分步計數原理 松四中趙芹 教學目標 1.了解學習本章的意義，激發學生的興趣 2.理解分類計數原理和分步計數原理，培養學生歸納概括的能力 3.會利用兩個原理分析和解決一些簡單的應用問題 教學重點 理解分類計數原理和分步計數原理，培養學生歸納概括的能力 教學難點 會利用兩個原理分析...
計數原理總結
計數原理練習卷 1 排列數與組合數計算 1.若 n n且 n 20，則 27 n 28 n 34 n 等於 a b c d 2.已知，則 3.化簡 2 站隊相鄰與不相鄰問題 4.記者要為5名志願者和他們幫助的2位老人拍照，要求排成一排，2位老人相鄰但不排在兩端，不同的排法共有 1440種960種 7...
分類計數原理
北京四中 撰稿 萬元春編審 趙菁責編 辛文公升 分類計數原理 分步計數原理 授課重點 分類計數原理，分步計數原理的不同以及它們的應用。授課難點 1 解決學生思考過程中對加法，分步計數原理理解產生的誤區。2 幫助學生找到 重 漏 產生的原因。一 概念與規律 1 分類計數原理 做一件事，完成它可以有n類...