fundamentals\Counting

fundamental of counting

Enumeration, or counting, may strike one(第一擊) as an obvious process that a student learns when first studying arithmetic.

The Rule of Sum: If a first task can be performed in m ways, while a second task can be performed in n ways, and the two tasks cannot be performed simultaneously, then performing either task can be accomplished in any one of

 ways.

The Rule of Product: If a procedure can be broken down into first and second stages, and if there are m possible outcomes for the first stage and if, for each of these outcomes, there are n possible outcomes for the second stage, then the total procedure can be carried out, in the designated order, in

 ways. 

舉個栗子：

從52張牌種抽 1 張 “王”，有多少種抽法？

答：1種，啊 2 種！

從52張牌中抽 1 張 "花臉"，有多少種抽法？

答：1，2，3，4，5，6，7，.... , 12 種！

卧槽，你能 3 * 4 麼？

J、Q、K 每個 4 種花色 

3 * 4 = 12 種

舉個栗子：A 鎮去 C 鎮 有多少種走法？

A,B,C表示小鎮,而R1~R9表示小鎮之間的路

路的數量	A	B	C
A	-	4	2
B	4	-	3
C	2	3	-

想要從A鎮到C鎮，可以先走R1，R2, R3, R4, R5, R9，額，匡瓢了，偷看答案中....

A->C	2
A->B->C	4	3

答案為：2 + (4 * 3) = 14 種走法

舉個栗子：由 3 位偶數和 3 個字母，可以組成多少個證書編号：

舉個栗子：8 個女的 5 個男的，選舉。選一個 總統和一個女副總統，有多少種選法：

舉個簡單的栗子：

// 求 counter 的值 = 11 * (5 + 7)
// 這讓我想起了，有次hr就給我做了這個題 ━┳━　━┳━
counter := 0
for i := 1 to 12 do
    for j:= 5 to 10 do
        counter := counter + 1
    for k := 15 downto 8 do
        counter := counter + 3
           

Factorials: If 

 then "n factorial" is  denoted 

舉個栗子：7 個數字（1，2，3，4，5，6，7）組成一列，不能有重複的數字？

如果前三個數字必須是偶數呢？

The number of permutations of length k from a list of n elements without repetition is  

舉個栗子：單詞 “BASKET” 的 6 個字母有多少種排法：

單詞 “ERR” 呢：

Permutations:If there are n distinct objects and r is an integer, with 

, then by the rule of product, the number of permutations of size r for the n objects is

Permutations with Repetition: If there are n objects with n1 indistinguishable objects of a first type, n2 indistinguishable objects of a second type,…,and nr indistinguishable objects of an rth type, where

,then there are 

(linear) arrangements of the given n objects.

舉個栗子：

舉個栗子：6 個男的和 4 個女的站成一排，要求女的不能相鄰，有多少種站法？

舉個栗子：5 個 0 和 14 個 1 ，每個 0 後面必須跟兩個 1 ，一共有多少種排法？

Permutations in circular: Consequently, there are

Arrangements of n objects around the circular.

舉個栗子：16 個人座兩張圓桌，一張桌子能座 10 個人，另一張能座 6 個人，問一共有多少種座法：

Combinations The Binomial Theorem: If we start with n distinct objects, each selection, or combination, of r of these objects, with no reference to order, corresponds to r! permutations of size r from the n objects. Thus the number of combinations of size r from a collection of size n is 

Binomial Theorem. If x and y are variables and n is a positive integer.  

通俗的講，這等價于 一個白球 和 一個黑球 從中取 3 次 有多少種取法？ 

圖：二項式展開的通俗了解

Combinations with Repetition: When we wish to select, with repetition, r of n distinct objects, we find that we can considering all arrangements of r x’s and n-1 |’s and that their number is

. Consequently, the number of combinations of n objects taken r at a time, with repetition, is

有放回的組合，相當于可以重複選擇。

Equivalence:

1. The number of Integer solutions of the equation 

   

2. The number of selection, with repletion, of size r from a collection of size n.
3. The number of ways r identical objects can be distributed among n distinct containers.

 從 3 個容器中選 7 個用 

 從 7 個物體的 9 個（7 個物體，2個分割）中選 2 個的排列

// 求 n 的值
n = 0;
for (i = 1; i <= 20; i++)
    for (j = 1; j <= i; j++)
        for (k = 1; k <= j; k++)
            for (m = 1; m <= k; m++)
                print ( ++n );
           

即為 

從中選 4 個可重複數字的組合 {1,3,3,20}

設 

 從中選擇 3 個元素

1. 沒有重複的有序序列數 

   

2. 可重複的有序序列數 

   

3. 沒有重複的沒有順序的組合數 

   

   1. 升序序列數 

      

   2. 降序序列數 

      

4. 可重複的沒有順序的組合數 

   

   1. 可重複的升序序列數 

      

考慮單詞 “aeemrry”

1. 有多少個排列 

   

2. 有多少個包含 “eye” 的排列 

   

   

3. 有多少個包含 “ram” 和 “eye” 的排列 

   

   

然後，我們使用 

 來求解一道國小數學題吧！

15+1=15移動一根火柴使等式成立

1. 我們将問題轉化為 

   

   ，其中 

   

    = 構成等号左邊 15 的 1 的上半截 ，

   

    = 下半截，包括等号和等式右邊的結果，一共 20 根火柴。
2. 我們發現問題很複雜，我們無法在短時間内依靠人力 “看” 出來。
3. 我們将 20 堆火柴切分成數字和符号一共 7 堆： 

   

    (1, 5, + , 1, = , 1, 5)
4. 我們從 7 個 “和式” 中任取 2 個（可重複），并嘗試求解。
5. 如果不能求解，則嘗試将某個可拆分的 “和式” 拆分，栗如 将 7 拆分為兩堆 - 号 和 數字 1，重複第 4 步
6. 無解（你丫逗我，當我三歲小孩呢？）

好的，我們舉個栗子：

昨兒個玩打架遊戲，頭都被錘飛了。

這是自然語言，我們能不能模組化成數學語言？ 用Counting數數這句話裡的可計數地方。

誰玩遊戲？我。玩什麼遊戲？打架遊戲。誰打誰？他打我，我也打他。他是誰？其他人。打赢了麼？頭都被錘飛了。一直都輸？赢了3把輸了10把。

Sum原則：○我和其他人玩打架遊戲 + 打架結果輸了 = 昨兒個；○赢了3把 + 輸了12把 = 打了15把；

Product原則：○我1和 {其他人2，其他人3，其他人4} 打架 有1 × 3 種打法；○{其他人2，其他人3，其他人4}和 我1 打架有 3 × 1 種打法；

Permutations原則：○{我1，其他人2，其他人3，其他人4} 取兩個人出來打架，并區分我打你和你打我，有4！/(4-2)! = 12種打法；

比如登記系統，因為區分客戶找業務員，與業務員找客戶兩種不同的客戶來源，是以我們有單獨的登記表，然後流程表引用登記表，流程不關心客戶找業務員還是業務員找客戶。簡而言之，登記業務中{客戶，業務員}是排列算法，流程業務中{客戶，業務員}是組合算法。

Permutations with Repetition原則：○{我1，其他人2，其他人3，其他人4}排隊，有4！/3！= 4 種排列；

Permutations in circular原則：○{我1，其他人2，其他人3，其他人4}排成一圈，有4！/4 = 6 種排法；

Combinations原則：○{我1，其他人2，其他人3，其他人4} 取兩個人出來打架，有 4!/ 2! (4-2)! = 6 種方法；

Combinations with Repetition原則：○{我，其他人} 從中取出兩個人 ，有C(2 + 2 – 1, 2) = 3!/2!=3 種方法；減去其中 {我1，我1}的不合理組合 = 3 - 1 = 2 種打法，分别為：{我，其他人}打架、 {其他人， 其他人}打架；

複雜點的：一共打了10場，分别是和張三打了兩回共6次，和李四打了兩回共3次，有多少種打法；x1+x2=6(x1,x2>0)<=>x1+x2=4(x1,x2>=0)為C(2+4-1，4)=5種。y1+y2=3(y1,y2>0)<=>y1+y2=1(y1,y2>=0)=C(2+1-1,1)=2種，一共有5+2=7種打法；

Favior combination over Inherited