組合問題

[stuCKSH 12]

Q: 3個非負整數和為9的組合?

目前只想到窮舉

0 0 9

0 1 8

0 2 7

0 3 6

0 4 5

1 1 7

1 2 6

1 3 5

1 4 4

2 2 5

2 3 4

3 3 3

[＊～☆小黑 10]

H3取9?

[howt 10]

Q: 3個非負整數和為9的組合?

目前只想到窮舉

0 0 9

0 1 8

0 2 7

0 3 6

0 4 5

1 1 7

1 2 6

1 3 5

1 4 4

2 2 5

2 3 4

3 3 3

[(9+3)^2]/12

若是和為n，則答案為與 [(n+3)^2]/12 最接近的整數

[乂月之雪乂囧 10]

大大的解法沒看過= =

我只會用H來解~

[乂月之雪乂囧 10]

[(9+3)^2]/12

若是和為n，則答案為與 [(n+3)^2]/12 最接近的整數

大大的解法沒看過= =

我只會用H來解~

[stuCKSH 12]

題目若為x+y+z=n(x,y,z為非負整數)的排列

可以用重複組合解

但是組合就不能用H來解

不知道學長 [(n+3)^2]/12的公式 是如何推出來的???

[howt 10]

題目若為x+y+z=n(x,y,z為非負整數)的排列

可以用重複組合解

但是組合就不能用H來解

不知道學長 [(n+3)^2]/12的公式 是如何推出來的???

可用遞迴或硬幹法

遞迴法：假設a1+a2..+am = n ，且a1≥a2≥....≥am 的正整數解方法數為F(m,n)

易證F(m,n) = F(m,n-m)+F(m-1,n-1) (對am≥2或=1作討論)

原題為m=3，意即F(3,n) = F(3,n-3)+F(2,n-1)，而F(2,n)很簡單

於是簡單分類一下，就得到一個包含多項式的遞迴，

再代入n=1、2...5、6的初始值化簡分類之後可以得到最接近(n^2)/12的整數。

(這裡才是最麻煩的地方)

你的題目則是取上面答案裡的n=n+3即可。

之前無聊還算了m=4的情況，令{a}表示最接近a的整數

那麼當n是偶數，答案為{(n^3+3n^2)/144}；當n是奇數，答案為{(n^3+3n^2-9n)/144}。

至於硬幹法就不贅述了..