Размер видео: 1280 X 720853 X 480640 X 360
Показать панель управления
Автовоспроизведение
Автоповтор
感謝老師特別為我的留言拍了一部影片。這是我在高中某次考試的時候發現的方法，巧妙的是可以化成等比級數的公式，所以特別有印象。
Here's the man! 謝謝你的分享. 那個等比級數看上去真是爽快啊. 現在我一直在想如果有4個一樣的箱子, 或是更多箱子的時候可以怎麼做.
天哪，好強！怎麼想到的？
太棒了吧，居然能發現這麼好玩的算法
請教4個箱子如何做？6顆球
感覺方法不是很通用，假如有1000顆不同的球，放到150個相同的箱子裡邊，有更通用的方法嗎？😂
這題的公式解是 S(n, k) + S(n, k-1) + ... + S(n, 1)。(加到0項也可以，因為S(n, 0)=0)。n是球數、k是箱子數、S是第二類斯特林數。論時間複雜度的話，據我所知，直接計算S(n, k)大概要算k次的"某數的n次方"加上算一次k的階乘，這兩個運算可能分別需要 log(n)和k次的乘法運算，這樣解這題的時間複雜度可能落在 O(k^2(logn+k))。若用建表的方式去解，可以O(n^2)，用python的話五行內寫得出來(只用list、range、sum)。
用 the same 會有問題，容易讓人誤會這些箱子其實是同一個(數學常用的手法：稱兩個同類物件為 x, y，然後推論出其實是同一個)而用 identical、indistinguishable 就恰當得多
我看只有你會誤會啊
這方法厲害在基本上不會漏掉任何一個方法，然後最後相加用等比級數更漂亮
6個球隨便丟= 3^6， 三個箱子一樣要除掉重複的3!=6，但其中6個同箱子只重複3次要另外算，答案=(3^6-3)/6 + (3/3)=122
要將6顆不同的球放進3個相同的箱子，可以使用斯特林數（Stirling numbers of the second kind）來計算。斯特林數 𝑆(𝑛,𝑘) 表示將 𝑛 顆不同的球分成 𝑘 個非空的相同的箱子的方法數。對於本題，我們需要計算 𝑆(6,1)、𝑆(6,2) 和 𝑆(6,3) 的總和。𝑆(6,1)+𝑆(6,2)+𝑆(6,3)=1+31+90=122所以，將6顆不同的球放進3個相同的箱子，一共有 122 種放法。
斯特林數:docs.google.com/spreadsheets/d/1ZAIoJcbfT6Jq9LR_-z7ydxIvXSlUBTHP/edit?usp=sharing&ouid=105734715278473767662&rtpof=true&sd=true
是不是chatgpt
@@sincho48763 是
@@sincho48763 absolutely, yes
還沒看老師的算法我想到的做法：首先，把1號球丟進去，有1號球的箱子就是A箱2號球可以進A箱，也可以進其他箱如果2號球進了其他箱，那有2號的就是B箱，則三個箱子已經不同，剩下4顆球有3^4種放法如果2號球進了A箱，則輪到3號球確定是否進A箱，如果不進A箱，那放了3號球的就是B箱，則剩下3顆球有3^3種放法以此類推，可以得到有產生「B箱」時的方法數是3^4 + 3^3 + ... + 3 + 1而沒有產生「B箱」表示全部都在A箱，一種方法所以總和是1 + (1 + 3 + 3^2 + ... + 3^4) = 1 + (3^5-1)/(3-1) = 122種要嘗試看看如何擴展到任意數量個箱子
看完影片，竟然跟我是一樣的做法XDD
高手在民間👏
自己製造不同的箱子好頂
我的天，居然拍了兩次！
重複組合很舒服~~
其實可以有個快速暴力想法：你的箱子因為是identical，所以把球決定好之後，去排列箱子，可是因為是identical，所以C(3,2)的排法的結果其實是identical所以就變成 3⁶ / C(3,2) = 3⁵
這個是32年前我們學排列組合的時候，老師講過的暴力解
@@sanyuanChen 3^5=243，可是答案是122😅
@@ken90007 oh........多了最後一個1.......我想想
@@sanyuanChen 這個方法的問題在於，認定每種排法都一定有 C(3, 2) = 3 種重複，然而我們可以輕鬆舉出反例：[ 1 2 3 ] [ 4 5 6 ] [][ 1 2 3 ] [] [ 4 5 6 ][] [ 1 2 3 ] [ 4 5 6 ][ 4 5 6 ] [ 1 2 3 ] [][ 4 5 6 ] [] [ 1 2 3 ][] [ 4 5 6 ] [ 1 2 3 ]簡單思考一下就知道，當「有兩個或三個箱子有球時，被重複算到的次數是 6 而不是 3（你錯誤的第一點在於這不是組合而是排列，不該是 C(3, 2) = 3 種重複而是 3! = 6 種重複）」，而「只有一個箱子有球時，被重複算到的次數是 3（你錯誤的第二點，沒有注意到並非所有排法的重複次數都一樣）」所以如果要照這個思路，正確的作法如下：1. 總共 729 種不考慮箱子相同的排列方式2. 先排除掉僅有 3 種的單箱子有六顆球的排法3. 剩下的都是重複次數為 3! = 6 的狀況4. 最後再加回 1 種被我們排除掉的六球一箱狀況得到 (729 - 3) / 3! + 1 = 122 正解
@@sanyuanChen 如果三個箱子內容物各不相同（有至少兩個不是空的）那麼排列數是3!，而不是C3取2。如果6顆球都在同一個箱子，那麼排列數才是C3取2，所以算式應該是(3^6 - 3) / 3! + 3/3=122前面那一項是「三個箱子內容物各不相同的排列數」除以3!，後面則是「球都在同一個箱子裡的排列數」除以3編輯：剛去看了李翰老師的影片，發現這就是他的算法
好酷喔！！！
這方法漂亮，想問問老師2024AMC8的第25題是不是也可以用類似的標記方法呢？（這題也是排列組合 再算機率）
那如果我們有6個不同的球跟10個相同的箱子怎麼算?
這種箱子跟球的問題在組合學叫做 Twelvefold way 直接查表就可以了😀
我上次有跟其他人討論推導出一個可以適用不同數量的球跟箱子的公式，雖然有點小複雜當有m個不同球跟n個相同箱子的方法數:令Ak=[k^m-P(k,k-1)*A(k-1)-P(k,k-2)*A(k-2)-......-P(k,1)*A1]/k!，然後把A1加到An基本的邏輯是，Ak代表球放到恰好k個箱子的方法數，並且先把箱子當成不同的，之後再除k!
@@DoongXiouHua哦在這邊看到你了。基本上就是可以寫成遞迴形式，針對不同的球跟箱子數量會跟比較少的球或比較少的箱子的情況有關，這樣化簡到最後就能全部變成最基本的情況來算。
@@bprptw 多出來的箱子用不到阿XD
該觀眾也姓張嗎，好像失焦了@@
n個異物分成m堆，共有幾種分法，可用遞迴求得一公式
這種題目有沒有辦法轉成公式化？畢竟映射在生活中 同樣箱子不好去思考(可能用分堆?)像是同樣的球分到不同箱子 可以映射成x+y+…=k 的非負整數解
重複組合？
這題在離散數學屬於基本題 這類型稱為 m 相異物放入 n 相同箱 *且允許空箱* 的方法數而公式解即：S(m, 1) + S(m, 2) +...+ S(m, n) 其中 S(m, n) 為 Stirling numbers of the second kind (這東西有兩類 我們這邊談的是第二類)其他留言也有提到這個公式解 以下簡稱 Stirling numbers這個 Stirling numbers 有個很深刻的看法即「將含有 m 個元素的集合分割成 n 個非空集合的方法數」回到公式解本身 為什麼長這樣呢？考慮 m 相異物放入 n 相同箱 恰有 k 個不可空 則我們知道方法數為 S(m, k), 1
為什麼有些影片在英文頻道有做但沒做在英文頻道
感謝老師特別為我的留言拍了一部影片。這是我在高中某次考試的時候發現的方法，巧妙的是可以化成等比級數的公式，所以特別有印象。
Here's the man! 謝謝你的分享. 那個等比級數看上去真是爽快啊. 現在我一直在想如果有4個一樣的箱子, 或是更多箱子的時候可以怎麼做.
天哪，好強！怎麼想到的？
太棒了吧，居然能發現這麼好玩的算法
請教4個箱子如何做？6顆球
感覺方法不是很通用，假如有1000顆不同的球，放到150個相同的箱子裡邊，有更通用的方法嗎？😂
這題的公式解是 S(n, k) + S(n, k-1) + ... + S(n, 1)。(加到0項也可以，因為S(n, 0)=0)。n是球數、k是箱子數、S是第二類斯特林數。
論時間複雜度的話，據我所知，直接計算S(n, k)大概要算k次的"某數的n次方"加上算一次k的階乘，這兩個運算可能分別需要 log(n)和k次的乘法運算，這樣解這題的時間複雜度可能落在 O(k^2(logn+k))。若用建表的方式去解，可以O(n^2)，用python的話五行內寫得出來(只用list、range、sum)。
用 the same 會有問題，容易讓人誤會這些箱子其實是同一個
(數學常用的手法：稱兩個同類物件為 x, y，然後推論出其實是同一個)
而用 identical、indistinguishable 就恰當得多
我看只有你會誤會啊
這方法厲害在基本上不會漏掉任何一個方法，然後最後相加用等比級數更漂亮
6個球隨便丟= 3^6， 三個箱子一樣要除掉重複的3!=6，但其中6個同箱子只重複3次要另外算，答案=(3^6-3)/6 + (3/3)=122
要將6顆不同的球放進3個相同的箱子，可以使用斯特林數（Stirling numbers of the second kind）來計算。
斯特林數 𝑆(𝑛,𝑘) 表示將 𝑛 顆不同的球分成 𝑘 個非空的相同的箱子的方法數。
對於本題，我們需要計算 𝑆(6,1)、𝑆(6,2) 和 𝑆(6,3) 的總和。
𝑆(6,1)+𝑆(6,2)+𝑆(6,3)=1+31+90=122
所以，將6顆不同的球放進3個相同的箱子，一共有 122 種放法。
斯特林數:
docs.google.com/spreadsheets/d/1ZAIoJcbfT6Jq9LR_-z7ydxIvXSlUBTHP/edit?usp=sharing&ouid=105734715278473767662&rtpof=true&sd=true
是不是chatgpt
@@sincho48763 是
@@sincho48763 absolutely, yes
還沒看老師的算法
我想到的做法：
首先，把1號球丟進去，有1號球的箱子就是A箱
2號球可以進A箱，也可以進其他箱
如果2號球進了其他箱，那有2號的就是B箱，則三個箱子已經不同，剩下4顆球有3^4種放法
如果2號球進了A箱，則輪到3號球確定是否進A箱，如果不進A箱，那放了3號球的就是B箱，則剩下3顆球有3^3種放法
以此類推，可以得到有產生「B箱」時的方法數是3^4 + 3^3 + ... + 3 + 1
而沒有產生「B箱」表示全部都在A箱，一種方法
所以總和是1 + (1 + 3 + 3^2 + ... + 3^4) = 1 + (3^5-1)/(3-1) = 122種
要嘗試看看如何擴展到任意數量個箱子
看完影片，竟然跟我是一樣的做法XDD
高手在民間👏
自己製造不同的箱子好頂
我的天，居然拍了兩次！
重複組合很舒服~~
其實可以有個快速暴力想法：
你的箱子因為是identical，所以把球決定好之後，去排列箱子，可是因為是identical，所以C(3,2)的排法的結果其實是identical
所以就變成 3⁶ / C(3,2) = 3⁵
這個是32年前我們學排列組合的時候，老師講過的暴力解
@@sanyuanChen 3^5=243，可是答案是122😅
@@ken90007 oh........多了最後一個1.......我想想
@@sanyuanChen 這個方法的問題在於，認定每種排法都一定有 C(3, 2) = 3 種重複，然而我們可以輕鬆舉出反例：
[ 1 2 3 ] [ 4 5 6 ] []
[ 1 2 3 ] [] [ 4 5 6 ]
[] [ 1 2 3 ] [ 4 5 6 ]
[ 4 5 6 ] [ 1 2 3 ] []
[ 4 5 6 ] [] [ 1 2 3 ]
[] [ 4 5 6 ] [ 1 2 3 ]
簡單思考一下就知道，當「有兩個或三個箱子有球時，被重複算到的次數是 6 而不是 3（你錯誤的第一點在於這不是組合而是排列，不該是 C(3, 2) = 3 種重複而是 3! = 6 種重複）」，而「只有一個箱子有球時，被重複算到的次數是 3（你錯誤的第二點，沒有注意到並非所有排法的重複次數都一樣）」
所以如果要照這個思路，正確的作法如下：
1. 總共 729 種不考慮箱子相同的排列方式
2. 先排除掉僅有 3 種的單箱子有六顆球的排法
3. 剩下的都是重複次數為 3! = 6 的狀況
4. 最後再加回 1 種被我們排除掉的六球一箱狀況
得到 (729 - 3) / 3! + 1 = 122 正解
@@sanyuanChen 如果三個箱子內容物各不相同（有至少兩個不是空的）那麼排列數是3!，而不是C3取2。
如果6顆球都在同一個箱子，那麼排列數才是C3取2，所以算式應該是
(3^6 - 3) / 3! + 3/3=122
前面那一項是「三個箱子內容物各不相同的排列數」除以3!，後面則是「球都在同一個箱子裡的排列數」除以3
編輯：剛去看了李翰老師的影片，發現這就是他的算法
好酷喔！！！
這方法漂亮，想問問老師2024AMC8的第25題是不是也可以用類似的標記方法呢？（這題也是排列組合 再算機率）
那如果我們有6個不同的球跟10個相同的箱子怎麼算?
這種箱子跟球的問題在組合學叫做 Twelvefold way 直接查表就可以了😀
我上次有跟其他人討論推導出一個可以適用不同數量的球跟箱子的公式，雖然有點小複雜
當有m個不同球跟n個相同箱子的方法數:
令Ak=[k^m-P(k,k-1)*A(k-1)-P(k,k-2)*A(k-2)-......-P(k,1)*A1]/k!，然後把A1加到An
基本的邏輯是，Ak代表球放到恰好k個箱子的方法數，並且先把箱子當成不同的，之後再除k!
@@DoongXiouHua哦在這邊看到你了。
基本上就是可以寫成遞迴形式，針對不同的球跟箱子數量會跟比較少的球或比較少的箱子的情況有關，這樣化簡到最後就能全部變成最基本的情況來算。
@@bprptw 多出來的箱子用不到阿XD
該觀眾也姓張嗎，好像失焦了@@
n個異物分成m堆，共有幾種分法，可用遞迴求得一公式
這種題目有沒有辦法轉成公式化？畢竟映射在生活中 同樣箱子不好去思考(可能用分堆?)
像是同樣的球分到不同箱子 可以映射成
x+y+…=k 的非負整數解
重複組合？
這題在離散數學屬於基本題 這類型稱為 m 相異物放入 n 相同箱 *且允許空箱* 的方法數
而公式解即：S(m, 1) + S(m, 2) +...+ S(m, n) 其中 S(m, n) 為 Stirling numbers of the second kind (這東西有兩類 我們這邊談的是第二類)
其他留言也有提到這個公式解 以下簡稱 Stirling numbers
這個 Stirling numbers 有個很深刻的看法即「將含有 m 個元素的集合分割成 n 個非空集合的方法數」
回到公式解本身 為什麼長這樣呢？
考慮 m 相異物放入 n 相同箱 恰有 k 個不可空 則我們知道方法數為 S(m, k), 1
為什麼有些影片在英文頻道有做但沒做在英文頻道