Re: [中學] 排列組合 (整數分拆 Partitions in rectangle)

看板Math作者 (真。盤古大洋)時間7年前 (2018/04/12 14:18), 7年前編輯推噓0(0推 0噓 13→)
留言13則, 4人參與, 7年前最新討論串1/1
※ 引述《freePrester (Prester)》之銘言： : ※ 引述《nrxadsl (異鄉人)》之銘言： : : 大家好： : : K島運氣很好的上了車 可是密碼卻是高二的數學題目 : : 小弟在國中二元二次就慘死了 : : 所以排列組合不會 : : 但是看到了這次的題目 又重新拾起對於數學的熱情 : : 可以請問數學版的各位前輩們可以幫忙解這個題目嗎? : : https://i.imgur.com/hhrBmyy.jpg
: : 感謝 : : 6. 我覺得不是最好的方法，還請高手補充 : ┌─┬─┬─┬─┌──→◇ : │ D │ │ │ : ├─┼─┼─┼─│─┼─┤ : │ C │ │ │ : ├─┼─┼─┌─┘─┼─┤ : │ B │ │ │ │ : ├─┌───┘─┼─┼─┤ : │A │ │ │ │ │ │ : ●─┘─┴─┴─┴─┴─┘ : 要平分兩邊，一邊就要有 12 個方格 : 得 0 ≦ A ≦ B ≦ C ≦ D ≦ 6 ，且 A + B + C + D = 12 : 列表： : <0,0,6,6> 、 <0,1,5,6> 、 <0,2,4,6> 、 <1,1,4,6> 、 <0,3,3,6> : <1,2,3,6> 、 <2,2,2,6> 、 <0,2,5,5> 、 <1,1,5,5> 、 <0,3,4,5> : <1,2,4,5> 、 <1,3,3,5> 、 <2,2,3,5> 、 <0,4,4,4> 、 <1,3,4,4> : <2,2,4,4> 、 <2,3,3,4> 、 <3,3,3,3> : 共 18 組 和原 Po 一樣，同時也很好奇有沒有更好的做法，剛好爬文時不經意看到了這篇： #1NlcJTn7 (Math) 作法是使用了 Gaussian binomial coefficient 作爲生成函數 ( https://en.wikipedia.org/wiki/Gaussian_binomial_coefficient ) ( 也就是原文提到的 q-analogue of the binomial coefficient ) Wikipedia 對這個問題 (Partitions in a rectangle) 的生成函數作法也有一些敘述， ( https://en.wikipedia.org/wiki/Partition_(number_theory) ) 所以這題可以用 C(10,4)_q 在 q^12 的係數求得。 C(10,4)_q = q^24 + q^23 + 2q^22 + 3q^21 + 5q^20 + 6q^19 + 9q^18 + 10q^17 + 13q^16 + 14q^15 + 16q^14 + 16q^13 + 18q^12 + 16q^11 + 16q^10 + 14q^9 + 13q^8 + 10q^7 + 9q^6 + 6q^5 + 5q^4 + 3q^3 + 2q^2 + q^1 + 1 (( 是不是好解法見仁見智，因為計算量實在太大了XD 但我好奇的是，生成函數的係數和 = C(10,4) ( q 代入 1 的結果 ) 就等於以下問題的答案： 0 <= A <= B <= C <= D <= 6, <A,B,C,D> 的可能數 想請問如何將 C 與這個問題，更直觀地連結在一起呢？ 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.4.192 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1523513922.A.3FC.html ※ 編輯: Panthalassa (140.112.25.100), 04/12/2018 15:06:52
→
04/12 16:22, 7年前 , 1F
要左右平分，路徑一定要經過中心點，然後前後兩段
04/12 16:22, 1F
→
04/12 16:22, 7年前 , 2F
對稱
04/12 16:22, 2F
→
04/12 16:23, 7年前 , 3F
所以只要算走到中心的方法就好
04/12 16:23, 3F
→
04/12 16:23, 7年前 , 4F
5!/(3!2!) = 10
04/12 16:23, 4F
和我一開始的想法一樣XD
→
04/12 16:24, 7年前 , 5F
q-Binomial就是按面積細分,q代1就是算總數
04/12 16:24, 5F
能理解 q 代 1 是算總數，而結果剛好是 C(m+n,n)， 因此在想能不能不從生成函數(q-Binomial)的方法， 直接從算總數的問題連結到 C(m+n,n)
→
04/12 16:24, 7年前 , 6F
...於是就錯了哈哈
04/12 16:24, 6F
※ 編輯: Panthalassa (223.140.43.193), 04/12/2018 16:35:24
→
04/12 19:12, 7年前 , 7F
你是要連結到 C(m+n,n) 還是 C_q(m+n,n) ?
04/12 19:12, 7F
→
04/12 20:31, 7年前 , 8F
如果可以的話都連結QQ
04/12 20:31, 8F
→
04/12 21:50, 7年前 , 9F
其實可以不用管生成函數，今天就是一個題目：
04/12 21:50, 9F
→
04/12 21:50, 7年前 , 10F
四顆相同的骰子，有幾種可能的結果 (ans: C(9,4)
04/12 21:50, 10F
→
04/12 22:27, 7年前 , 11F
那不就是走方格的方法數嗎@@
04/12 22:27, 11F
→
04/12 22:28, 7年前 , 12F
原題沒有 12 格的限制不就是國中(還是高中?)題?
04/12 22:28, 12F
→
04/12 22:30, 7年前 , 13F
噢是的 對不起，我丟臉了XD
04/12 22:30, 13F
‣ 更多 Panthalassa 的文章
文章代碼(AID): #1Qplf2Fy (Math)