作者Panthalassa (真。盤古大洋)
看板Math
標題Re: [中學] 排列組合 (整數分拆 Partitions in rectangle)
時間Thu Apr 12 14:18:39 2018
※ 引述《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
→ wohtp : 要左右平分，路徑一定要經過中心點，然後前後兩段04/12 16:22
→ wohtp : 對稱04/12 16:22
→ wohtp : 所以只要算走到中心的方法就好04/12 16:23
→ wohtp : 5!/(3!2!) = 1004/12 16:23
和我一開始的想法一樣XD
→ XII : q-Binomial就是按面積細分,q代1就是算總數04/12 16:24
能理解 q 代 1 是算總數，而結果剛好是 C(m+n,n)，
因此在想能不能不從生成函數(q-Binomial)的方法，
直接從算總數的問題連結到 C(m+n,n)
→ wohtp : ...於是就錯了哈哈04/12 16:24
※ 編輯: Panthalassa (223.140.43.193), 04/12/2018 16:35:24
→ arthurduh1 : 你是要連結到 C(m+n,n) 還是 C_q(m+n,n) ? 04/12 19:12
→ Panthalassa : 如果可以的話都連結QQ 04/12 20:31
→ Panthalassa : 其實可以不用管生成函數，今天就是一個題目： 04/12 21:50
→ Panthalassa : 四顆相同的骰子，有幾種可能的結果 (ans: C(9,4) 04/12 21:50
→ arthurduh1 : 那不就是走方格的方法數嗎@@ 04/12 22:27
→ arthurduh1 : 原題沒有 12 格的限制不就是國中(還是高中?)題? 04/12 22:28
→ Panthalassa : 噢是的 對不起，我丟臉了XD 04/12 22:30