回復 3# omfun 的帖子
4.
設有n個正立方體，邊長分別為1,2,\ldots,n公分，現在將他們由下而上堆疊起來，可隨機以任意大小順序堆疊，但是若連續堆疊兩個立方體，在上面的立方體邊長超過位在下面立方體邊長2公分，則此堆疊方式將會傾倒(例如：若由下而上是②①③④則可安全堆疊，但①④②③則否)，問能安全堆疊的機率為何？
感謝 Pacers31 指正，下面是錯的...不小心誤會題意了，請往下找解答
解1：
若安全，1 的上方必為 2 或沒有。如果 2 在 1 上一層，那麼必是 3 在 2 上，或沒有東西在 2 上。
因此可類推至由上至下到 1 出現，必為連續正整數的型： k_{1},k_1-1,k_1-2,\ldots 1；
接著不看這 k_1 個，我們又會有相同之結論，即 1 的下方將是連續正整數 k_{1}+k_{2},k_{1}+k_{2}-1,\ldots,k_{1}+1 ；
重覆推論得第一個大層 k_{1} 個最小連續整，第一個大層 k_{2} 個剩於的最小連續整數…
第 j 層 k_{j} 個剩於最小的連續整數。其中 k_{1}+k_{2}+\ldots+k_{j}=n , k_{j} 為正整數。(總共分 j 大層)
所以共有 \sum_{j=1}^{n}H_{n-j}^{j}=\sum_{j=1}^{n}C_{n-j}^{n-1}=2^{n-1} 種不會傾倒的情形。
所求機率為 \frac{2^{n-1}}{n!} .
解2：
考慮以逐次插入的方式，依小到大的方式插入。
第一步，放一個 1。
第二步， 2 可選擇在 1 的上方或下方。
第三步，3 可放在 2 上方的位置，或最下。
而不能放在 1 上方的位置，因為往後愈來愈大，不可能在 3 和 1 中間放入可安全疊起的的方式。
第四步，同上， 4 僅能放在 3 上方的位置，或最下。
...
得安全的放法僅有 2^{n-1}
因此所求機率為 \frac{2^{n-1}}{n!} .
[ 本帖最後由 tsusy 於 2013-7-25 05:06 PM 編輯 ]
