作者TOMOHISA (YAMASHITA)
看板Math
標題[中學] 其中恰有一組a(i)>a(i+1)
時間Wed Apr 7 20:46:01 2021
考慮(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://webptt.com/m.aspx?n=bbs/Math/M.1617799563.A.13F.html
1F：推 Vulpix : 把 1~n 分成兩群，各自遞增排列。再扣掉不符的。 04/07 22:05
2F：→ Vulpix : 答案是 2^n -n -1 。 04/07 22:05
3F：推 emptie : 補充樓上說的，不符的就是最後兩群湊起來會等於(1 04/07 22:21
4F：→ emptie : ,2,3...,n) 的那些，共有n+1種 04/07 22:21
5F：→ TOMOHISA : 感謝樓上兩位大神解答 04/07 23:32
6F：→ musicbox810 : 1~n遞增排列 不是就只1<2<3...<n一種嗎?還有其他種? 04/08 14:13
7F：推 LPH66 : 注意是「分成兩群各自遞增排列」 04/08 14:32
8F：→ LPH66 : 也就是題目要的是像 134682579 這種排列 04/08 14:33
9F：→ musicbox810 : 123...n 每群各有n個數字 1~n任意塞 滿足只有一對 04/08 14:39
10F：→ musicbox810 : a(i)>a(i+1) ? 04/08 14:39
11F：→ musicbox810 : 我搞錯了XD 04/08 14:40
12F：→ musicbox810 : 2^n -n -1不知道怎麼推出的 04/08 14:41
13F：→ ejialan : 2^n是每個數字有群1群2兩種選擇 04/08 14:44
14F：→ ejialan : 不符的就群1[] 群2[1-n]; 群1[1] 群2[2-n]...這種 04/08 14:45
15F：→ ejialan : 不符的n+1種 04/08 14:46
16F：→ ejialan : 上面群2應該用~ [1~n] [2~n]...[n] [] 04/08 14:49
17F：推 musicbox810 : 謝謝LP大和ej大 我想一下 04/08 14:54
18F：推 doa2 : 104建中數資班入學考題 04/09 04:48
19F：推 czk0622 : 101年建中教甄2招 04/09 11:25
20F：→ musicbox810 : 還是想不出2^n是怎麼列出的 04/09 11:30
21F：推 RicciCurvatu: 給出n 位元的01011001... 04/09 11:48
22F：→ RicciCurvatu: 把標記0 的分進第一組 標記1的分進第二組 固有2^n 04/09 11:48
23F：→ RicciCurvatu: 種可能 04/09 11:48
24F：推 RicciCurvatu: 第一組降序排列放前面 第二組將續排列放後面 不難證 04/09 12:02
25F：→ RicciCurvatu: 明我們已經考慮了充分情況 (對於所有滿足條件的排列 04/09 12:02
26F：→ RicciCurvatu: 都在我們的考慮裡了) 再來刪去條件不符的 唯一的可 04/09 12:02
27F：→ RicciCurvatu: 能要嘛你第一組一個數都沒有(11111....11) 要嘛第一 04/09 12:02
28F：→ RicciCurvatu: 組的i個數都是最大的 I=1,2,...,n 04/09 12:02
29F：→ musicbox810 : 這個重排數列不能有重複的數字 如果遞增數列跳到別 04/09 12:15
30F：→ musicbox810 : 的數字 則跳過的數字還是要放進去,這種狀況怎麼考慮 04/09 12:16
31F：→ musicbox810 : 假設5個數字，12345-12345，2^5是前面所選擇的遞增 04/09 12:17
32F：→ musicbox810 : 數列，則後面數列也跟著被決定。 04/09 12:18
33F：→ Ricestone : 2^5就是已經考慮到你所想的那情況的數字了 04/09 12:24
34F：→ Ricestone : 換個角度來說，2^n就是C(n,0)+...+C(n,n)了 04/09 12:27
35F：→ musicbox810 : 是的.但是不符的部分 應該是前面數列從1到i全滿的情 04/09 12:27
36F：推 musicbox810 : 想通了，感謝2位R大 04/09 12:31