Research Space for Linear Algebra & Discrete Mathematics
0~19個數 其中偶數的有10個
不好意思你可以解釋的詳細一點嗎因為這個整數分割的問題我不是很清楚麻煩了 謝謝
老師上課的時候是給一個式子2^19=(19,0)+.....+(19,19)但我不是很了解這個事子的意思
1. 一個正整數 n 的 composition 的個數為 2^(n-1), 我自己是用遞迴解的, 利用類似書上習題5-56的想法可寫出遞迴式 a_n = 2*a_(n-1), a_1 = 1 不過看你給的式子, 我想老師上課時用來說明的方法應該是類似這樣子: 假設現在有 20 個 1, 其間的 19 個位置上皆可放置一個中斷點, 且每一種放置中斷點的方法皆對應到一組composition, 例如:1111,11111,111,1111,1,111所對應到的就是4+5+3+4+1+3因為放置中斷點的個數介於 0 到 19 之間, 且欲放置 i 個中斷點會有 c(19,i) 種方法, 所以總數就是 c(19,0)+...+c(19,19) = 2^192. 因為每一個 20 的 composition 中所有 summand 皆為 even 的結果皆會對應到一個 10 的 composition例如: 20 = 2+4+12+2 = 2(1+2+6+1) = 2*10所以算這種分割法的個數就相當於是算 10 的 composition 的個數, 那答案就是 2^(10-1) = 2^9
那我想問一下那假設取一個中斷點的話111111111111111,11111=5+1511111,111111111111111=15+5這樣的話是不是會有重覆算到呢??
沒有重覆算的問題, 根據composition的定義, 5+15和15+5是不一樣的, 我們之前在chap 4有學過的那個整數分割的問題才是不看順序的, 且那一種分割法沒有公式解
歐歐懂了謝謝!
張貼留言
7 則留言:
0~19個數 其中偶數的有10個
不好意思你可以解釋的詳細一點嗎
因為這個整數分割的問題我不是很清楚
麻煩了 謝謝
老師上課的時候是給一個式子
2^19=(19,0)+.....+(19,19)
但我不是很了解這個事子的意思
1. 一個正整數 n 的 composition 的個數為 2^(n-1), 我自己是用遞迴解的, 利用類似書上習題5-56的想法可寫出遞迴式 a_n = 2*a_(n-1), a_1 = 1
不過看你給的式子, 我想老師上課時用來說明的方法應該是類似這樣子: 假設現在有 20 個 1, 其間的 19 個位置上皆可放置一個中斷點, 且每一種放置中斷點的方法皆對應到一組composition, 例如:
1111,11111,111,1111,1,111
所對應到的就是
4+5+3+4+1+3
因為放置中斷點的個數介於 0 到 19 之間, 且欲放置 i 個中斷點會有 c(19,i) 種方法, 所以總數就是
c(19,0)+...+c(19,19) = 2^19
2. 因為每一個 20 的 composition 中所有 summand 皆為 even 的結果皆會對應到一個 10 的 composition
例如:
20 = 2+4+12+2 = 2(1+2+6+1) = 2*10
所以算這種分割法的個數就相當於是算 10 的 composition 的個數, 那答案就是 2^(10-1) = 2^9
那我想問一下那假設取一個中斷點的話
111111111111111,11111=5+15
11111,111111111111111=15+5
這樣的話是不是會有重覆算到呢??
沒有重覆算的問題, 根據composition的定義, 5+15和15+5是不一樣的, 我們之前在chap 4有學過的那個整數分割的問題才是不看順序的, 且那一種分割法沒有公式解
歐歐懂了謝謝!
張貼留言