+----------------------------------------------------+ | | | t(n,k) = 1 + Sum(t(i,j): i>j>k & i+j=n), 0<=k<=n | | | +----------------------------------------------------+ +----+ k = 0 | n | / 1 +----+ / 2 | 0 | . . . . . . . . . . . . . 1 / 3 | 1 | . . . . . . . . . . . . 1 1 / 4 | 2 | . . . . . . . . . . . 1 1 1 / 5 | 3 | . . . . . . . . . . 2 1 1 1 / 6 | 4 | . . . . . . . . . 2 1 1 1 1 / 7 | 5 | . . . . . . . . 3 2 1 1 1 1 / 8 | 6 | . . . . . . . 4 2 1 1 1 1 1 / 9 | 7 | . . . . . . 5 3 2 1 1 1 1 1 / 10 | 8 | . . . . . 6 3 2 1 1 1 1 1 1 / 11 | 9 | . . . . 8 5 3 2 1 1 1 1 1 1 / 12 | 10 | . . . 10 5 3 2 1 1 1 1 1 1 1 / 13 | 11 | . . 12 7 4 3 2 1 1 1 1 1 1 1 / 14 | 12 | . 15 8 4 3 2 1 1 1 1 1 1 1 1 / 15 | 13 | 18 10 6 4 3 2 1 1 1 1 1 1 1 1 / | 14 | 22 12 7 4 3 2 1 1 1 1 1 1 1 1 1 | 15 | 27 15 9 6 4 3 2 1 1 1 1 1 1 1 1 1 Properties: [1] t(n,k) > 1 iff 0 <= 2*k+1 < n [2] t(n,k) <= t(n+1,k) [3] t(n,k+1) <= t(n,k) Proposition: t(n,k) = 1 + Sum(t(i,j): i>j>k & i+j=n), 0<=k<=n, is the number of all partitions of n into distinct numbers notless k. Proof outline: The "1" counts {n}, the trivial unique partition, whereas the "Sum" counts recursevly the proper partitions, having more than one member (see example for illustration). Corollary: t(n,0) is the number of all partitions of n into distinct positive integers; A000009(n) = t(n,0). E x a m p l e: n = 13 t(13,0) = 1 + t(12,1) + t(11,2) + t(10,3) + t(9,4) + t(8,5) + t(7,6); t(12,1) = 1 + t(10,2) + t(9,3) + t(8,4) + t(7,5); t(10,2) = 1 + t(7,3) + t(6,4); t(7,3) = 1; t(6,4) = 1; t(9,3) = 1 + t(5,4); t(5,4) = 1; t(8,4) = 1; t(7,5) = 1 t(11,2) = 1 + t(8,3) + t(7,4) + t(6,5); t(8,3) = 1; t(7,4) = 1; t(6,5) = 1 t(10,3) = 1 + t(6,4) t(6,4) = 1 t(9,4) = 1; t(8,5) = 1; t(7,6) = 1 t(13,0) = 1 + ((1 + ((1+1+1)+(1+1)+1+1)) + (1+1+1+1) + (1+1) + 1 + 1 + 1) = 1 + 8 + 4 + 2 + 1 + 1 + 1 = 18 +----+ k = 0 | n | / 1 +----+ / 2 | 0 | . . . . . . . . . . . . . _ / 3 | 1 | . . . . . . . . . . . . _ _ / 4 | 2 | . . . . . . . . . . . _ _ _ / 5 | 3 | . . . . . . . . . . _ _ _ _ / 6 | 4 | . . . . . . . . . _ _ _ _ _ / 7 | 5 | . . . . . . . . _ _ _ _ 1 _ / 8 | 6 | . . . . . . . _ _ _ _ 1 1 _ / 9 | 7 | . . . . . . _ _ _ 1 1 1 1 _ / 10 | 8 | . . . . . _ _ _ 1 1 1 _ _ _ / 11 | 9 | . . . . _ _ _ 2 1 _ _ _ _ _ / 12 | 10 | . . . _ _ 3 2 _ _ _ _ _ _ _ / 13 | 11 | . . _ _ 4 _ _ _ _ _ _ _ _ _ / 14 | 12 | . _ 8 _ _ _ _ _ _ _ _ _ _ _ / 15 | 13 | 18 _ _ _ _ _ _ _ _ _ _ _ _ _ / | 14 | _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 1) 13 : [x x x x x x x x x x x x x] 2) 12+1: [x x x x x x x x x x x x] [x] 3) 10+2+1: [x x x x x x x x x x] [x x] [x] 4) 7+3+2+1: [x x x x x x x] [x x x] [x x] [x] 5) 6+4+2+1: [x x x x x x] [x x x x] [x x] [x] 6) 9+3+1: [x x x x x x x x x] [x x x] [x] 7) 5+4+3+1: [x x x x x] [x x x x] [x x x] [x] 8) 8+4+1: [x x x x x x x x] [x x x x] [x] 9) 7+5+1: [x x x x x x x] [x x x x x] [x] 10) 11+2: [x x x x x x x x x x x] [x x] 11) 8+3+2: [x x x x x x x x] [x x x] [x x] 12) 7+4+2: [x x x x x x x] [x x x x] [x x] 13) 6+5+2: [x x x x x x] [x x x x x] [x x] 14) 10+3: [x x x x x x x x x x] [x x x] 15) 6+4+3: [x x x x x x] [x x x x] [x x x] 16) 9+4: [x x x x x x x x x] [x x x x] 17) 8+5: [x x x x x x x x] [x x x x x] 18) 7+6: [x x x x x x x] [x x x x x x]