<jupyter_start><jupyter_text>排列組合與離散機率（Combinatorics and Discrete Probability） ![Creative Commons License](https://i.creativecommons.org/l/by/4.0/88x31.png)This work by <NAME> is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/). _Tested on SageMath version 8.7_  排列組合  排列從 $n$ 個東西中拿出 $k$ 個出來**排列**時要計較順序  可以用 `Permutations` 來找出所有排列  （注意最後有個 `s`）<jupyter_code>elements = [1,2,3,4,5]
for per in Permutations(elements,2):
    print(per)<jupyter_output>[1, 2]
[1, 3]
[1, 4]
[1, 5]
[2, 1]
[2, 3]
[2, 4]
[2, 5]
[3, 1]
[3, 2]
[3, 4]
[3, 5]
[4, 1]
[4, 2]
[4, 3]
[4, 5]
[5, 1]
[5, 2]
[5, 3]
[5, 4]<jupyter_text>從 $n$ 個東西中拿出 $k$ 個出來排列的  方法數有 $P^n_k=\frac{n!}{(n-k)!}$ 種也有人把 $P^n_k$ 記作 $[n]_k$<jupyter_code>factorial(5)/factorial(5-2)<jupyter_output><empty_output><jupyter_text>組合從 $n$ 個東西中拿出 $k$ 個出來**組合**時要**不計較**順序  可以用 `Combinations` 來找出所有組合  （注意最後一樣有個 `s`）<jupyter_code>elements = [1,2,3,4,5]
for com in Combinations(elements,2):
    print(com)<jupyter_output>[1, 2]
[1, 3]
[1, 4]
[1, 5]
[2, 3]
[2, 4]
[2, 5]
[3, 4]
[3, 5]
[4, 5]<jupyter_text>從 $n$ 個東西中拿出 $k$ 個出來組合的  方法數有 $C^n_k=\frac{n!}{k!(n-k)!}$ 種也有人把 $C^n_k$ 記作 $\binom{n}{k}$<jupyter_code>factorial(5)/factorial(5-2)/factorial(2)<jupyter_output><empty_output><jupyter_text>計數組合學（Enumerative Combinatorics）到底有幾個？何不全部列出來試試看？ 自己設定一個參數（比如說 `counter`）來計算次數 在 1 到 100 中  除以 13 餘 1  或是  除以 17 餘 1  的數字有幾個<jupyter_code>counter = 0

for i in range(1,101):
    if i%13 == 1 or i%17 == 1:
        counter = counter + 1
        print(i)

counter<jupyter_output>1
14
18
27
35
40
52
53
66
69
79
86
92<jupyter_text>數字 1,2,3,4,5 排成一排  1 在開頭  而且  5 不在結尾  的排列有幾種<jupyter_code>elements = [1,2,3,4,5]

counter = 0
for per in Permutations(elements,5):
    if per[0] == 1 and per[4] != 5:
        counter = counter + 1

counter<jupyter_output><empty_output><jupyter_text>數字 1,1,2,2,3 排成一排  的排列有幾種<jupyter_code>elements = [1,1,2,2,3]

counter = 0
for per in Permutations(elements,5):
    counter = counter + 1

counter<jupyter_output><empty_output><jupyter_text>從數字 1,2,3,4,5 中選出三個  選到 1  而且  沒選到 5  的組合有幾種<jupyter_code>elements = [1,2,3,4,5]

counter = 0
for com in Combinations(elements,3):
    if 1 in com and 5 not in com:
        counter = counter + 1

counter<jupyter_output><empty_output><jupyter_text>從數字 1,1,2,2,3 中選出三個  的組合有幾種<jupyter_code>elements = [1,1,2,2,3]

counter = 0
for com in Combinations(elements,3):
    counter = counter + 1

counter<jupyter_output><empty_output><jupyter_text>$x+y+z = 5$  的非負整數解有幾組<jupyter_code>counter = 0

for x in range(6):
    for y in range(6):
        for z in range(6):
            if x + y + z == 5:
                counter = counter + 1
                
counter<jupyter_output><empty_output><jupyter_text>$x+y+z=5$  的正整數解有幾組<jupyter_code>counter = 0

for x in range(1,6):
    for y in range(1,6):
        for z in range(1,6):
            if x + y + z == 5:
                counter = counter + 1
                
counter<jupyter_output><empty_output><jupyter_text>100 的因數有幾個<jupyter_code>n = 100

counter = 0

for p in range(1,101):
    if n % p == 0:
        counter = counter + 1
        
counter<jupyter_output><empty_output><jupyter_text>100 的因數總和是多少<jupyter_code>n = 100

total = 0

for p in range(1,101):
    if n % p == 0:
        total = total + p
        
total<jupyter_output><empty_output><jupyter_text>二項式定理將 $(1+x)^n$ 展開後  其 $x^k$ 的係數為 $C^n_k$  所以 $C^n_k$ 又稱為**二項式係數**（binomial coefficient）<jupyter_code>x = var('x')
n = 10
k = 4

p = expand((1+x)^n)

print(p)
print(p.coefficient(x^k))<jupyter_output>x^10 + 10*x^9 + 45*x^8 + 120*x^7 + 210*x^6 + 252*x^5 + 210*x^4 + 120*x^3 + 45*x^2 + 10*x + 1
210<jupyter_text>驗證一下對不對<jupyter_code>n = 10
k = 4

factorial(n)/factorial(n-k)/factorial(k)<jupyter_output><empty_output><jupyter_text>也可以用 `binomial(n,k)` 來計算<jupyter_code>n = 10
k = 4

binomial(n,k)<jupyter_output><empty_output><jupyter_text>離散機率機率就存在我們生活之中  用 `random` 套件來模擬看看吧！ 後面的程式很多都要用到 `random` 套件  記得要執行下面這行以後才能用<jupyter_code>import random<jupyter_output><empty_output><jupyter_text>`random.choice` 會從輸入的列表中  隨機挑出一個元素  多執行幾次試試看<jupyter_code>numbers = [1,2,3,4,5,6]
random.choice(numbers)<jupyter_output><empty_output><jupyter_text>把它包成一個函數就可以  做出一個虛擬的骰子了<jupyter_code>def roll_a_dice():
    return random.choice([1,2,3,4,5,6])
roll_a_dice()<jupyter_output><empty_output><jupyter_text>骰子公不公正？  要試試看才知道<jupyter_code>counter = [0,0,0,0,0,0]
n = 10000

for i in range(n):
    k = roll_a_dice()
    counter[k-1] = counter[k-1] + 1
    # 骰子的數字是 1,2,3,4,5,6
    # counter 的編號是 0,1,2,3,4,5
    
print('出現次數 %s'%counter)
print('機率 %s'%[N(count/n, digits=4) for count in counter])<jupyter_output>出現次數 [1678, 1618, 1662, 1665, 1656, 1721]
機率 [0.1678, 0.1618, 0.1662, 0.1665, 0.1656, 0.1721]<jupyter_text>也可以用 `random.randint(a,b)`  隨機從 `a` 到 `b` 之間取出一個數  （注意 `a` 和 `b` 都有可能取到，這和 `range(a,b)` 不一樣）<jupyter_code>random.randint(1,6)<jupyter_output><empty_output><jupyter_text>撲克牌裡有 52 張牌  連抽五張  抽到鐵支（4+1）的機率是多少？<jupyter_code>def pick_one(l):
    card = random.choice(l)
    l.remove(card)
    return card
suits = ['spade', 'heart', 'diamond', 'club']
ranks = [1,2,3,4,5,6,7,8,9,10,11,12,13]
cards = [(suit,rank) for suit in suits for rank in ranks]

hand = []
for _ in range(5):
    hand.append(pick_one(cards))
    
hand
K = 100000
counter = 0

for _ in range(K):
    suits = ['spade', 'heart', 'diamond', 'club']
    ranks = [1,2,3,4,5,6,7,8,9,10,11,12,13]
    cards = [(suit,rank) for suit in suits for rank in ranks]

    hand = []
    for _ in range(5):
        hand.append(pick_one(cards))

    for i in range(1,14):
        occur = [card for card in hand if card[1] == i]
        if len(occur) == 4:
            counter += 1
            break;
    
print(N(counter / K))<jupyter_output>0.000300000000000000<jupyter_text>從 1 到 100 中  有幾個質數？  選到一個質數的機率是多少？<jupyter_code>counter = 0

for i in range(1,101):
    if is_prime(i):
        counter = counter + 1
        
print(counter)
print(N(counter/100))<jupyter_output>25
0.250000000000000<jupyter_text>包成一個函數從 1 到 `K` 中  選出一個數字  回傳這數字是不是質數<jupyter_code>def prime_in_K(K=100):
    p = random.randint(1,K)
    return is_prime(p)<jupyter_output><empty_output><jupyter_text>真的來測測看機率  換言之，這就是 1 到 `K` 中  質數出現的比例  換成不同的 `K` 試試看<jupyter_code>K = 100
n = 10000

counter = 0

for i in range(n):
    if prime_in_K():
        counter = counter + 1
        
N(counter / n)<jupyter_output><empty_output><jupyter_text>Monty Hall 問題美國有一個電視節目叫 Let's Make a Deal  （Monty Hall 是主持人）  節目中有三扇門  其中一扇後面是車子  另外兩扇後面是山羊  如果玩家選中車子的門  就可以帶走車子 但是當玩家選好一扇門以後  主持人就會到後面看一看  打開一扇沒被選到的門  告訴玩家這扇門後面並不是車子  問你要不要換  如果你是玩家  你會換嗎？ 我們來**模擬一場遊戲**：三扇門  隨機選一扇放車子  玩家隨機選一個門   現在沒被選到又不是車子的門  可能有一扇（你沒選到車子）  也有可能是兩扇（你選到車子了！）  主持人打開其中一扇 你決定換到最後那扇  沒選到 也不是主持人打開的  那扇門  然後開獎！  選中是 `True`  沒選中是 `False`<jupyter_code>doors = [1,2,3]
car = random.choice(doors)
player_choose = random.choice(doors)

no_car_no_choose = [door for door in doors if door != car and door != player_choose]
host_open = random.choice(no_car_no_choose)

no_choose_no_open = [door for door in doors if door != player_choose and door != host_open]
player_change = no_choose_no_open[0]

player_change == car<jupyter_output><empty_output><jupyter_text>把整場遊戲包成一個函數  這樣我們才能一次又一次的模擬  並計算成功的機率<jupyter_code>def Monty_Hall_game():
    doors = [1,2,3]
    car = random.choice(doors)
    player_choose = random.choice(doors)

    no_car_no_choose = [door for door in doors if door != car and door != player_choose]
    host_open = random.choice(no_car_no_choose)

    no_choose_no_open = [door for door in doors if door != player_choose and door != host_open]
    player_change = no_choose_no_open[0]

    return player_change == car<jupyter_output><empty_output><jupyter_text>玩很多場試試看  究竟決定換一扇門  選到車子的機率是多少<jupyter_code>n = 10000

counter = 0
for i in range(n):
    if Monty_Hall_game():
        counter = counter + 1

N(counter / n)<jupyter_output><empty_output><jupyter_text>動手試試看  練習用 1,2,3,4,5 排成一排，  其中 1 不在第一位、  2 不在第二位、  3 不在第三位、  4 不在第四位、而且  5 不在第五位  的排法有幾種。<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>練習 1袋中有三顆紅球、兩顆白球，  用 `'r'` 代表紅球，  用 `'w'` 代表白球。  列出所有  從袋中取出三顆球的組合方法。<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>練習 2求整數解的個數：  $x+y+z=10$  $0\leq x\leq 4$,  $1\leq y\leq 5$,  $2\leq z\leq 6$。<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>練習 3求偶數解的個數：  $x+y+z=10$  $0\leq x\leq 4$,  $1\leq y\leq 5$,  $2\leq z\leq 6$。<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>練習 4從 5 個 1 和 5 個 0  中拿出 5 個數字排列。  恰好使用奇數個 1 的排列方法有幾種。<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>_做以下練習前記得先_ `import random`<jupyter_code>import random<jupyter_output><empty_output><jupyter_text>練習 5下面定義一顆虛擬的硬幣（1 是正面、0 是反面）。  試著丟這顆硬幣許多次來猜測  丟到正面的機率是多少。<jupyter_code>def unknown_dice():
    a = list(bin(1365))[2:]
    return int(random.choice(a))
### your answer here<jupyter_output><empty_output><jupyter_text>練習 6定義一個函數 `six_get_three` 其功能為：  不輸入任何參數，  隨機產生一個長度是六的列表 `a`，  每個個元素為 1 或 0 的機率各為 0.5， 若 `a` 剛好有 3 個 1，  則回傳 `True`，否則回傳 `False`。回傳 `True` 的機率是多少？<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>練習 7撲克牌裡有 52 張牌  連抽五張  抽到葫蘆（3+2）的機率是多少？<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>練習 8除了 `for` 迴圈以外，  還有 `while` 迴圈：  ```Python while condition:    do something```當條件 `condition` 成立時  程式會不斷重覆執行 `do something`。  猜看看這個函數的功能是什麼？（輸入的 `a` 和 `b` 必須是正整數。）```Pythondef  the_number(a,b):    k = 1    again = True    while again:        if k % a == 0 and k % b == 0:            again = False            return k        else:            k = k + 1```<jupyter_code>### your answer here<jupyter_output><empty_output><jupyter_text>練習 9（Monty Fall 問題）同樣在 Let's Make a Deal 的節目上，  玩家選了一扇門，  主持人在走向門的時候滑到了並不小心打開一扇門  （這時候主持人不知道哪扇門後面有車子），  好險主持人不小心打開的剛好不是車子。  主持人問玩家要不要換一扇門。如果你是玩家，你要換嗎？寫一個函數 `Monty_Fall_game` 來模擬這個問題：  這函數不輸入參數，  每次執行時做以下的事情  1. 建立三扇門2. 隨機選一扇放車子3. 玩家隨機選一扇門4. 主持人從玩家沒選到的兩扇門中隨機開啟一扇5. 如果主持人開到車子的門，則這局不算並從步驟 1 重新開始6. 如果主持人沒開到車子的門，則繼續步驟 77. 玩家換一扇門（一開始沒選到、也不是主持人打開的那扇）8. 如果玩家選到車子，回傳 `True`，否則回傳 `False`若須要可以參考下方提示以及數學解釋<jupyter_code>### your answer here<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14523716189729519, 'fraction_numerical': 0.05791846334770678, 'mean_word_length': 4.644358407079646, 'pattern_counts': {'":': 0, '<': 151, '<?xml version=': 0, '>': 151, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '39', 'dir': 'jupyter-structured-clean-dedup', 'id': '500790', 'license': 'CC-BY-4.0', 'n_tokens_mistral': 6021, 'n_tokens_neox': 5964, 'n_words': 924, 'path': 'Sage4HS/03-Combinatorics-and-Discrete-Probability.ipynb', 'repo_name': 'jephianlin/outreach', 'size': '10209'}