17391：0以上の整数x,y,z, x+y+z<=9を満たす相異なるx,y,zの組みはいくつ？...

問題17391・・・http://task.naganoblog.jp/c73677_3.html より引用 Orz～

解答

・わたしの...

(1)

3H9=11C2=55

(2)

x+y+z+w=9

4H9=12C2=66

(3)

x<y<z<w

x<x+1<x+2<x+3

x+y+z+w=3

so...

4H3=6C3=20

でいいですよね？

↑

間違ってます ^^; Orz...

↓

・鍵コメT様からのもの Orz～

(2) 4H9=12C3=220です．
(3) やっていることがわかりませんが，
・(2)の結論が違うので，修正が必要です．
・wは，zより大きいとは限りません．
特に工夫せず，{x,y,z}の組合せを列挙して，3!を掛ける方法でも
それほど大変ではありません．
例えば，最小数が0である場合，残る2数は
1+[2～8],2+[3～7],3+[4～6],4+5の16通りです．

*再考してみまっす ^^;v

・再考...

f(0)={(0,0,0)}=1
f(1)=f(0)=1
f(2)={(0,0,2),(0,1,1)}=2
f(3)={(1,1,1),(0,0,3),(0,1,2)}=3
f(4)={(1,1,2),(0,0,4),(0,1,3),(0,2,2)}=4
f(5)={(1,1,3),(1,2,2),(0,0,5),(0,1,4),(0,2,3)}=5
f(6)={(1,1,4),(1,2,3),(0,0,6),(0,1,5),(0,2,4),(0,3,3),(2,2,2)}=7
so...23*3!=138

漸化式みたいにできるのかしらん...?

・鍵コメT様からのもの Orz～

f(n)は，x+y+z=nかつ0≦x≦y≦zである整数の組x,y,zの個数ですね．
すると，f(6)=7です．・・・赤字で訂正 Orz～

1+1+2+3+4+5+7=23なので，最終結果は正しいです．

なお本問は，素朴に数えたり，(2)から不適なものを除いたりすることでも，
さほど大変ではなく答えを出すことができます．
(一度アップして削除したのはこの方法です．)

(解1)
最小数が0である場合の残る2数が1+[2～8],2+[3～7],3+[4～6],4+5の16通り，
最小数が1である場合の残る2数が2+[3～6],3+[4～5]で合計6通り，
最小数が2である場合の残る2数が3+4の1通りとなるから，
求める数は，(16+6+1)*3!=138(通り)．

(解2)
(2)のうち，条件を満たさないものを数える．
x=y=0が，z=0,1,2,…,9の10通り．
x=y=1が，z=0,1,2,…,7の8通り．
x=y=2が，z=0,1,2,…,5の6通り．
x=y=3が，z=0,1,2,3の4通り．
x=y=4が，z=0,1の2通り
で，x=yのものが合計30通り．
y=zやz=xのものも同数だけある．
ただし，x=y=z=0,1,2,3である4通りは，3回ずつ数えているから，
条件を満たさないのは，実際は，30*3-(4*3-4)=82(通り)．
したがって，求める数は，220-82=138(通り)．

ついでに，スモークマンさんの提示されたfについても考察してみました．

[1] このfは次の漸化式を満たします．
f(n)=[n/2]-[(n-1)/3]+f(n-1).
(理由: f(n)組のうち，y≠zであるものは，
x+y+(z-1)=n-1かつ0≦x≦y≦z-1である組x,y,zに対応して，f(n-1)通り．
y=zであるものは，
yをn/3≦y≦n/2の範囲の整数にすることで得られ，[n/2]-[(n-1)/3]通り．)

また，f(n)=f(n-3)+[n/2]+1も成り立ちます．
(理由: f(n)組のうち，x≠0であるものは，(x-1)+(y-1)+(z-1)=n-3かつ
0≦x-1≦y-1≦z-1である組x,y,zに対応して，f(n-3)通り．
x=0であるものは，yとして0～[n/2]が可能であり，[n/2]+1通り．)

[2] y-x=Y,z-y=Zとおくことで，f(n)は，
「x+(x+Y)+(x+Y+Z)=nかつ0≦x≦x+Y≦x+Y+Zである整数の組x,Y,Zの個数」，
つまり「3x+2Y+Z=nかつx≧0,Y≧0,Z≧0である整数の組x,Y,Zの個数」
と言い換えられ，xを0,1,…,[n/3]のいずれかに固定することで，
Y=0,1,…[(n-3x)/2]のように，Yが[(n-3x)/2]+1通りとれて，
それに応じてZが定まるので，
f(n)は，
「[(n-3x)/2]+1を，n-3x≧0であるようなすべてのxに対して足したもの」
として計算することもできます．
すると，
f(0)=[0/2]+1=1
f(1)=[1/2]+1=1
f(2)=[2/2]+1=2
f(3)=([3/2]+1)+([0/2]+1)=3
f(4)=([4/2]+1)+([1/2]+1)=4
f(5)=([5/2]+1)+([2/2]+1)=5
f(6)=([6/2]+1)+([3/2]+1)+([0/2]+1)=7
のようになります．

小さいnに対してなら，この方法で，手軽にf(n)が計算できますし，
本問ではf(0)～f(6)の和がほしいので，
[6/2]+1,[5/2]+1,[4/2]+1は1つずつ，[3/2]+1.[2/2]+1,[1/2]+1は2つずつ，
[0/2]+1は3つ足すことで和を求めることも可能です．

[3] [1]で得た「f(n)=f(n-3)+[n/2]+1」を用いると，
f(n+3)=f(n)+[(n+3)/2]+1,f(n+6)=f(n+3)+[(n+6)/2]+1であり，
f(n+6)=f(n)+[(n+3)/2]+[(n+6)/2]+2となり，
n+3,n+6はその一方だけが奇数だから，(n+3)/2,(n+6)/2の小数部分は合計1/2．
よって，f(n+6)=f(n)+(n+3)/2+(n+6)/2-1/2+2=f(n)+n+6となります．
これとf(0)～f(5)の値より，f(n)は，「nからはじめて，正である限り6ずつ
減らして合計し，nが6の倍数のときだけ1を足したもの」です．
(例)f(25)=25+19+13+7+1，f(30)=30+24+18+12+6+1，
f(6k+4)=(6k+4)+(6k-2)+…+4=6(k+(k-1)+(k-2)+…+1+0)+4(k+1)=(k+1)(3k+4)
このように，n÷6の余りで分類して，f(n)の一般項を求めることもできます．

*漸化式の方も考えてくださりグラッチェでっす～m(_ _)m～v

but..[1]はそこはかとなく、.[2],[3]はなんとなく理解できましたぁ...^^;v