# 计数方法

## 计数方法 Counting Methods

### 乘法原理 Multiplication Rule

$${(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),\\ (2,1),(2,2),(2,3),(2,4),(2,5),(2,6),\\ (3,1),(3,2),(3,3),(3,4),(3,5),(3,6),\\ (4,1),(4,2),(4,3),(4,4),(4,5),(4,6),\\ (5,1),(5,2),(5,3),(5,4),(5,5),(5,6),\\ (6,1),(6,2),(6,3),(6,4),(6,5),(6,6)}$$

$${(HT),(HH),(TH),(TT)}$$

Definition: Multiplication Rule for Two-Part Experiments,
(i)The Experiments is performed two parts
(ii)The first part of the experiment has $m$ possible outcomes $x_1,x_2,\dots,x_m$ ,and regardless of which one of these outcomes $x_i$ occurs,the second part of the experiment has $n$ possible outcomes $y_1,y_2\dots,y_n$
the sample space $S$ contains excatly $mn$ outcomes

Definition:Multiplication Rule.Suppose that an experiment has k parts($k\geq2$),that the $i$th part of the experiment can have $n_i$ possible outcomes($i=1,\dots,k$),and that all of the outcomes in each part can occur regardless of which specific outcomes have occurred in the other parts.Then the sample space $S$ of the experiment will contain all vectors of the form $(u_1,\dots,u_k)$ where $u_i$ is one of the $n_i$ possible outcomes of part $i(i=1,\dots,k)$ .The total number of these vectors in $S$ will be equal to the product $n_1n_2\dots n_k$

### 排列 Permutations

1. 一个不透明的箱子，里面三个球，除了每个球颜色不同其他都相同（假设红R绿G蓝B三种颜色），也就是说如果靠触觉没办法区分，那么我们不看从箱子里拿球出来，每个球被拿出的可能性相同，并且，我们每次拿出球以后记录了颜色以后，再放回去，然后重复上述过程，这样我们重复三次，可能的结果：
$${ RRR,RRG,RRB,RGR,RGG,RGB,RBR,RBG,RBB,\\ GRR,GRG,GRB,GGR,GGG,GGB,GBR,GBG,GBB,\\ BRR,BRG,BRB,BGR,BGG,BGB,BBR,BBG,BBB }$$
根据实验的各步骤之间互不影响，所以乘法原理成立，结果有27种($3\times3\times3$) 这个重复的过程有个关键的步骤就是，每次取出球记录颜色后再放回去，这一步很重要。

2. 如果我们取出球以后不放回去呢？那么我们可能得到的结果就是：
$${ RGB,RBG,GRB,GBR,BRG,BGR }$$
解释下，第一步我们有三种可能的结果，同时第一个球不会放回，第二步受到第一步的影响，只可能有两种结果，同时第二个球不会被放回，那么第三步只有最后一个球，没有选择，只能是他，那么，这个不放回的过程，共有$3\times2\times1$ 种结果，比上面的模型1，要少很多种情况，

3. 我们简化上面2中步骤，把三步减到两步，那么根据2，我们共有$3\times2$种，虽然结果都是6，但是，效果是不同的，例如如果我们有四个球，不放回的取两个 $4\times3$ 共12种情况，如果是全取出 $4\times3\times2\times1$ 种情况。

Definition: Permutations. Suppose that a set has $n$ elements.Suppose that an experiment consisits of selecting $k$ of the elements one at a time without replacement.Let each outcome consist of the $k$ elements in the order selected.Each such outcome is called a permutation of n elements taken $k$ at a time.We denote the number of distinct such permutations by the symbol $P_{n,k}$

Theorem Number of Permutations. The number of permutations of $n$ elements taken $k$ at a time is $P_{n,k}=n(n-1)\dots(n-k+1)$

Theorem Permutations:The number of distinct orderings of $k$ items selected without replacement from a collectioin of $n$ different items $(0\leq k\leq n)$ is:
$$P_{n,k}=\frac{n!}{(n-k)!}$$

### 生日问题 Birthday Problem

$$Pr(A)=1-Pr(A^c)=1-\frac{P_{365,k}}{365^k}=1-\frac{365!}{(365-k)!365^k}$$

$k$ $Pr(A)$ $k$ $Pr(A)$
5 0.027 25 0.569
10 0.117 30 0.706
15 0.253 40 0.891
20 0.411 50 0.970
22 0.476 60 0.994
23 0.507

### 斯特林公式 Stirling’s Formula

Stirling’s Formula,斯特林公式，主要为了解决的问题是，在$P_{n,k}=\frac{n!}{(n-k)!}$ 的计算过程中，当n比较大的而k不太大的时候，这个计算变得很麻烦，因为数字太大了！什么？没有概念？那我下面写几个不太大的数字直观的给你看下：
$$P_{10,2}=\frac{10!}{(10-2)!}=10\times9=90\\ P_{100,2}=\frac{10!}{(10-2)!}=10\times9=9,900\\ P_{1000,2}=\frac{10!}{(10-2)!}=10\times9=999,000\\ P_{10000,2}=\frac{10!}{(10-2)!}=10\times9=99,990,000$$

$$\frac{n!}{a_n}=e^{ln(n!)-ln(a_n)}$$

Theorem Stirling’s Formula .Let:
$$set:\;s_n=\frac{1}{2}ln(2\pi)+(n+\frac{1}{2})ln(n)-n\\ then:\;lim_{n\to \infty}|s_n-ln(n!)|=0\\ or:\;lim_{n\to \infty}\frac{(2\pi)^{1/2}n^{n+1/2}e^{-n}}{n!}=1$$

$e^{ln(n!)}\sim e^{\frac{1}{2}ln(2\pi)+(n+\frac{1}{2})ln(n)-n}$ 也就是证明$n!\sim (2\pi)^{1/2}n^{n+\frac{1}{2}}e^{-n}$ 成立：

Share

Subscribe