基本的组合数学公式

加法法则和乘法法则

加法法则&＃xff1a;事件A与事件B的发生是和互不影响的&＃xff0c;则事件A或者B发生的次数为两者之和。

乘法法则&＃xff1a;事件A和事件B的发生是串行的&＃xff0c;则两者发生的次数为两者之积。

排列与组合

排列与组合问题包含四个子问题——集合的排列&＃xff0c;集合的组合&＃xff0c;多重集合的排列&＃xff0c;多重集合的组合。

定义&＃xff1a;设S为n元集。

①从S中有序的选取r个元素称为S的一个r排列。S的不同的r排列组合总数记为P&＃xff08;n,r&＃xff09;。r&＃61;n时的排列称作S的全排列。

②从S中无序的选取r个元素称作S的一个r组合.S的不同的r组合总数记为C&＃xff08;n,r&＃xff09;。

排列是有序的&＃xff0c;组合是无序的&＃xff0c;这是排列跟组合最大的区别&＃xff0c;由此也可以得出两者的推到公式。

显然对于排列数P&＃xff08;n,r&＃xff09;&＃61;n×&＃xff08;n-1&＃xff09;×&＃xff08;n-2&＃xff09;×…… x(n-r&＃43;1)&＃xff1b;

由于P&＃xff08;n,r&＃xff09;&＃61;C&＃xff08;n,r&＃xff09;×n&＃xff01;&＃xff0c;故C&＃xff08;n,r&＃xff09;&＃61;P&＃xff08;n,r&＃xff09;/n&＃xff01;;

多重集&＃xff1a;

组合数学中比较有趣的东西&＃xff1a;

证明&＃xff1a;

非降路径问题

栈操作中输出的组合数目