[中學] 其中恰有一組a(i)>a(i+1)

[TOMOHISA (YAMASHITA)]

考慮(1,2,...,n)的所有重排(a(1),a(2),...,a(n))，
試問共有多少組重排，符合對所有的i=1,2,...,n-1，其中恰有一組a(i)>a(i+1)？

例如：
n=2時，(2,1)符合，但(1,2)不符合
n=3時，(1,3,2)符合，但(3,2,1)不符合


--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.164.227.215 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1617799563.A.13F.html
推 Vulpix      : 把 1~n 分成兩群，各自遞增排列。再扣掉不符的。
→ Vulpix      : 答案是 2^n -n -1 。
推 emptie      : 補充樓上說的，不符的就是最後兩群湊起來會等於(1
→ emptie      : ,2,3...,n) 的那些，共有n+1種
→ TOMOHISA    : 感謝樓上兩位大神解答
→ musicbox810 : 1~n遞增排列 不是就只1<2<3...<n一種嗎?還有其他種?
推 LPH66       : 注意是「分成兩群各自遞增排列」
→ LPH66       : 也就是題目要的是像 134682579 這種排列
→ musicbox810 : 123...n  每群各有n個數字 1~n任意塞 滿足只有一對
→ musicbox810 : a(i)>a(i+1) ?
→ musicbox810 : 我搞錯了XD
→ musicbox810 : 2^n -n -1不知道怎麼推出的
→ ejialan     : 2^n是每個數字有群1群2兩種選擇
→ ejialan     : 不符的就群1[] 群2[1-n]; 群1[1] 群2[2-n]...這種
→ ejialan     : 不符的n+1種
→ ejialan     : 上面群2應該用~ [1~n] [2~n]...[n] []
推 musicbox810 : 謝謝LP大和ej大 我想一下
推 doa2        : 104建中數資班入學考題
推 czk0622     : 101年建中教甄2招
→ musicbox810 : 還是想不出2^n是怎麼列出的
推 RicciCurvatu: 給出n 位元的01011001...
→ RicciCurvatu: 把標記0 的分進第一組 標記1的分進第二組 固有2^n
→ RicciCurvatu: 種可能
推 RicciCurvatu: 第一組降序排列放前面 第二組將續排列放後面 不難證
→ RicciCurvatu: 明我們已經考慮了充分情況 (對於所有滿足條件的排列
→ RicciCurvatu: 都在我們的考慮裡了) 再來刪去條件不符的 唯一的可
→ RicciCurvatu: 能要嘛你第一組一個數都沒有(11111....11) 要嘛第一
→ RicciCurvatu: 組的i個數都是最大的 I=1,2,...,n
→ musicbox810 : 這個重排數列不能有重複的數字  如果遞增數列跳到別
→ musicbox810 : 的數字 則跳過的數字還是要放進去,這種狀況怎麼考慮
→ musicbox810 : 假設5個數字，12345-12345，2^5是前面所選擇的遞增
→ musicbox810 : 數列，則後面數列也跟著被決定。
→ Ricestone   : 2^5就是已經考慮到你所想的那情況的數字了
→ Ricestone   : 換個角度來說，2^n就是C(n,0)+...+C(n,n)了
→ musicbox810 : 是的.但是不符的部分 應該是前面數列從1到i全滿的情
推 musicbox810 : 想通了，感謝2位R大