组合数学-排列组合

组合数学的很多问题:关键是找到一一对应,把问题转化成容易理解和解决的。

可重排列

可重排列的两种理解方式:

  1. 先认为这N个东西都是不一样的,有N!排列方式。但实际上呢,这N1个a1是一样的,所以要把重复的给除掉,除以N1!;同样N2个a2我们原来也以为他们是不一样的,但实际上他们是一样的,所以同样还要除以N2!,其他的也一样要除掉,除完。
  2. 我一共就N个位置,要把这些所有东西放进去。我先从这N个里头挑出N1个位置出来,然后就把这N1个a1放进去,把这N个位置当中的N1个位置放完;我在从里头挑N2个位置出来,把那N2个a2放进去;再从剩下的N-N1-N2里挑N3个位置所a3放进去;到最后放ak的时候,就只剩下Nk个位置放Nk个东西了;然后再把所有的表达式代入化简,即得。

可重排列


可重排列


可重排列


可重组合

做组合有点像把那个小学奥数一样,他没有多少预备知识,他考的是你会不会换一个角度看这个问题。换一个角度看这个问题,就是你有没有好的方式把他对应到一个好算的东西上去。其关键还是一个找一一对应的问题。

可重组合的解决思路:

问题:现在问题是从N个不同的数里挑出r个数出来,允许重复挑,有多少种挑法。

  1. 方法一

    思路:我把它反过来看成是把r个相同的球放入N个不同的盒子,盒子编号从1到N,然后我就把这r个球往这些盒子里放。比如1号盒子放几个球就相当于我取了几个1,2号盒子放几个球就相当于我取了几个2,放完之后,哪个盒子里有几个球就相当于我从这个盒子里取了几个相同的数。所以1到N个数里取r个数做可重复的组合,与把r个相同的球往N个不同的盒子里放是一一对应的。 即问题转化成了:把r个相同的球放入N个不同的盒子有多少种放法。
    再作转换:N盒子我可把它看成是在一个大容器中有N-1块相同的隔板分隔出了N个不同的盒子,隔板是可以移动的。所以r个球往N个盒子里放,就相当于n-1个隔板与r个球的排列,即(N-1+r)!/(r!·(N-1)!) 种放法。两次找一一对应。 handwritting


  1. 方法二

    使用代数的方式,如下图演算。 可重组合


可重组合


可重组合


不相邻组合

不相邻组合


不相邻组合


不相邻组合


组合恒等式

组合恒等式


组合恒等式


组合恒等式


组合恒等式


组合恒等式


组合恒等式


组合恒等式


与路径有关的问题

与路径有关的问题


与路径有关的问题


与路径有关的问题


与路径有关的问题


与路径有关的问题


与路径有关的问题


与路径有关的问题


与路径有关的问题


与路径有关的问题


与路径有关的问题


与路径有关的问题


与路径有关的问题


与路径有关的问题


与路径有关的问题


Stirling近似公式

Stirling近似公式


Stirling近似公式


例子

例子


例子


版权所有,转载请注明出处 luowei.github.io.