問題意識は UVa #11480 Jimmy’s Balls による。

つまり、自然数Nを3つの自然数 x, y, z に分割する時の分割数(組合せ数)。ただし、x < y < z。自然数とは1以上の整数のこと。

たとえば、N=10に対して、(x, y, z)は、(1,2,7), (1,3,6), (1,4,5), (2,3,5) の4通りしか選べないので、分割数は4になる。

p11480.png

割とよく遭遇しそうな問題だが、一般解は以下の数式で表される。

  分割数 f = 3p(p-1)+1  if m = 0

      = 3p(p-1)+mp  if m > 0

ただし、p=N/6 (6で割った時の商)、m=N%6(6で割った時の余り)。

いくつかの検証データ(N,f)を書いておく。

 (5,0) (6,1) (7,1) (8,2) (9,3) (10,4) (11,5) (12,7) (13,8) (14,10) (15,12) (100,784) (500,20584)

一般化して、Nをn個に分割する時の数式ってあるのだろうか。

Comments are closed.

Post Navigation