加法原理
完成一件事情有n種辦法,每種辦法有\(a_i\)個,那麼一共有\(\sum_{}^{}a_i\)個方法。或者可以了解為有n個事件,每個事件有\(a_i\)種産生方式,那麼事件1或事件2或事件...事件n的産生方式就是上式。要使用加法原理,那麼這些事件必須兩兩不重疊,即一種方式隻能完成一個事件。
乘法原理
完成一件事情有n個步驟,每個步驟有\(a_i\)個方法,那麼一共有$\prod a_i \(個方法。或者可以了解為有n個事件,每個事件有\)a_i$種産生方式,那麼事件1與事件2與事件...事件n的産生方式就是上式。。要使用乘法原理,那麼這些事件必須兩兩不重疊,即一種方式隻能完成一個事件。
抽屜原理(鴿巢原理)
把n+1件物品放入n個抽屜,那麼至少有一個抽屜放了兩件及以上的物品。把n-1件物品放入n個抽屜,那麼至少有一個抽屜是空的。
容斥原理
多個集合的并等于這些集合累加減去這些集合的多餘的交集。這個不好表述。。比如二維字首和就是個經典例子
先不考慮重疊的情況,把包含于某内容中的所有對象的數目先計算出來(容),然後再把計數時重複計算的數目排斥出去(斥),使得計算的結果既無遺漏又無重複。
遵循奇加偶減。
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5yNyMjN2AjMzkzNzkjM1MDMlJTYhBzMmhTNzIGO1MTOh9CXwEzLchDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjL3M3Lc9CX6MHc0RHaiojIsJye.png)
直接引用oiwiki。。
組合數學主要研究按一定規則安排一些物品,大概可分為以下四種問題
1.存在性問題
2.計數性問題
3.構造性問題
4.最優性問題