天天看點

計數原理

加法原理

完成一件事情有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個抽屜,那麼至少有一個抽屜是空的。

容斥原理

多個集合的并等于這些集合累加減去這些集合的多餘的交集。這個不好表述。。比如二維字首和就是個經典例子

先不考慮重疊的情況,把包含于某内容中的所有對象的數目先計算出來(容),然後再把計數時重複計算的數目排斥出去(斥),使得計算的結果既無遺漏又無重複。

遵循奇加偶減。

計數原理
計數原理

直接引用oiwiki。。

組合數學主要研究按一定規則安排一些物品,大概可分為以下四種問題

1.存在性問題

2.計數性問題

3.構造性問題

4.最優性問題 ​