Re: [理工] [離散]-台大105-資工

[outofyou ()]

※ 引述《JKLee (J.K.Lee)》之銘言：
: 標題: Re: [理工] [離散]-台大105-資工
: 時間: Tue Sep  5 21:36:49 2017
:
: 複述題目：
: 1 <= x_1 < x_2 < ... < x_n <= r
: 求 x_1 + x_2 + ... + x_n = r 之整數解的數量。
:
: 翻譯題目為
: 將正整數r，整數分割為n個相異正整數的方法數。
:
: 假設所求為p(n,r)。
:
: 我目前只算出
: p(n,r) = 1, if n=1;
: p(n,r) = floor[(r-1)/2], if n=2;
: p(n,r) = 0, if n>1 and r < n*(n+1)/2;
: p(n,r) = 1, if r = n*(n+1)/2;
:
: 嘗試用生成函數
: (1+yx^1)(1+yx^2)...(1+yx^r)
: 所求為y^n x^r 之係數
:
: 然後就卡住了
:
: --
: ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.137.89.238
: ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1504618611.A.5A3.html
: 推 FRAXIS: 可以搜尋 distinct partition number                      09/06 09:53
: → JKLee: 看似沒有close form                                       09/07 20:58
: → JKLee:      ^d                                                  09/07 20:59
沒有close form的話可以這樣寫嗎？


解相當於數列<x_n> = a_1+b_1 , a_2+b_2 , ... , a_n+b_n ，
        其中<a_n> = 1,2,...,n
            <b_n> = b_1, b_2, ... , b_n
                           且 0 <= b_1 <= b_2 <= ... <= b_n <= r - n*(1+n)/2

                  n
解數量相當於符合Σb_i = r - n*(1+n)/2的<b_n>的數量
                 i=1


        r - n*(1+n)/2
相當於求 Σ F( r - n*(1+n)/2 , i , n)
         i=0


其中 F(N,h,w) = 1 , when N=h=0

                0 , when N<h or N>h*w

                 h
                Σ F(N-h,i,w-1) , when else
                i=0


F(N,h,w)代表符合 N = 序列加總, h = 序列最後一個數字的大小, w=序列長度
的序列數量。

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 219.85.131.170
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1504860548.A.012.html
推 JKLee: i=0~N是否要改成1~h
→ outofyou: 不可，在r-n*(1+n)/2 = 0的情況, F(0,0,n)=1 是必須的。
→ outofyou: 但r-n*(1+n)2不為0時，因F(r - n*(1+n)2,0,n)=0，可不加
→ outofyou: 因為F(N,0,n)=0 by N>h*w，每個input多一次+0的計算還好
→ outofyou: 遞迴式裡=0也要保留，例如F(5,5,3)=F(0,0,2)=1
※ 編輯: outofyou (219.85.181.154), 09/13/2017 14:32:48
遞迴式中i=0~N修正為i=0~h
※ 編輯: outofyou (219.85.181.154), 09/13/2017 14:34:05

如果不想經過r-n*(1+n)/2的處理，也可以

    r
求  Σ F( r , i , n)
   i=0


其中 F(r,h,n) = 0 , when r<h
                      or (r>h and n=0)
                      or (r=h=0 and n!=0)
                      or (r=h>=1 and n=0)
                      or (r>h and n=1)
                      or (h<=1 and n>1)

              = 1 , when r=h=n=0
                      or r=h=n=1

                h-1
              =  Σ F(r-h, i , n-1) , when else
                i=1

邊界條件好複雜
※ 編輯: outofyou (219.85.181.154), 09/13/2017 15:53:43