闲扯概率论中的计数问题

counting问题大概是古典概型里面最重要的一个内容。

面对不同的场景，result of counting the possible outcomes should be different.

我们不妨以从n个球抽取k个为例来看看如何计数。

1.考虑无放回：

​ 如果考虑顺序：n(n-1)(n-2)(n-k+1)

​ 如果不考虑顺序：c(n,k)

2.考虑有放回:

​ 如果考虑顺序:n^k

​ 如果不考虑顺序:这个情况比较复杂，但不妨先给出答案：c(n+k-1,k)

总结一下就是：

有放回，无顺序

如果有放回，且不考虑顺序，这就意味着先抽到A球，再抽到B球和先抽到B球，再抽到A球的情况是一模一样的，你拿到手的就是A，B。

不妨换一种思考方式，现在我们抛2枚硬币，可能会出现4种结果：{++,–,+-,-+}，这是因为这两枚硬币你知道哪一枚是哪一枚；但假设现在这两枚硬币完全一样，那么那么出现+-和-+其实是一回事（因为，第一枚出现+和第二枚出现+是一回事），也就是说，在这种情况下只有3种可能的结果。

现在，回到抽球问题，我们从最简单的情况看起。

假设n=1,k=3，那么有c(3，3)=1种情况，这很好理解，因为抽3次抽出来都是这个球；如果n=2，有k+1种情况（假设k=3，那么就有4种情况），直观理解，假设有A球和B球，如果不考虑顺序，这意味着我们只关心手里的球构成情况，而不关心哪个球先到手里，所以只可能有4种情况：{AAA,BBB,2个A1个B，2个B1个A}。

直接解决这类问题是很难的，但我们可以转化一下：

想象一下有n个球，每抽到一次该球就给该球记一个正号，那么，可以形象的表示为：

## 假设[]为球，o代表抽到的次数
## 设n=3,k=6,即一共3个球，抽6次
## 那么下面这种情况表示，第一个球被抽到3次，第二个球被抽到2次，第三个1次，
## 我们只关心结果，不关心球是第几个抽到的。
[ooo][oo][o]

上述问题稍微转化一下，问：现在有n个盒子，往里面扔k个球，能出现几种情况？

可以把上述图再转化一下，变成：

## k个球(o),n-1个|
ooo|oo|o

这是合理的，因此无论怎么填补，我们都是有n+k-1个位置。现在只需要把这k个球填到这n+k-1个位置里即可，所以有几种填法呢？c(n+k-1,k)种。

另一个相似的问题是：问x1+x2+…+xn=k有几种解；很显然，我们并不关心具体的是{x1=1,x2=2,x3}还是{x1=3,x2=2,x3=1}这种顺序问题，我们只关心最后的结果。

玻色－爱因斯坦凝聚物

实际上，上面这个问题在物理中是一个很经典的现象，即Bose-Einstein condensate ：

1924年，年轻的印度物理学家玻色寄给爱因斯坦一篇论文，提出 了一种新的统计理论，它与传统的统计理论仅在一条基本假定上不同。

传统统计理论假定一个体系中所有的原子（或分子）都是可以辨别的， 我们可以给一个原子取名张三，另一个取名李四……，并且不会将张 三认成李四，也不会将李四认成张三。

基于这一假定的传统理论圆满地解释了理想气体定律，可以说取得了非凡的成功。

然而玻色却挑战了上面的假定，认为在原子尺度上我们根本不可能区分两个同类原子 （如两个氧原子）有什么不同。

接着，玻色讨论了如下一个问题（这个问题所有高中生都做过）：

将N个相同的小球放进M个标号为1,2,…, M的箱子中，假定箱子的容积足够大，有多少种不同的放法？

在此问题的基础上，采用传统统计相似的作法，玻色便得到了一套新的统计理论。

玻色的论文引起了爱因斯坦的高度重视，迅速帮玻色译成德文发表。

随后将玻色的理论用于原子气体中，进而推测在足够低的温度下， 所有原子有可能处在相同的最低能态上，所有的原子的行为像一个粒子一样。

后来物理界将这种现象称为玻色－爱因斯坦凝聚。值得注意的是，这里的“凝聚”与日常生活中的凝聚不同，它表示原来不同状 态的原子突然“凝聚”到同一状态。

Chapter 1.4 How to count , Introduction to Probability, Joseph Blitzstein

百度百科：玻色-爱因斯坦冷凝物