A178830 Number of distinct partitions of {1,...,n} into two nonempty sets P and S with the product of the elements of P equal to the sum of elements in S.

0, 0, 1, 0, 1, 1, 1, 1, 1, 3, 1, 2, 1, 3, 3, 3, 3, 1, 4, 4, 3, 2, 2, 4, 3, 5, 3, 2, 4, 5, 4, 5, 6, 1, 4, 2, 5, 4, 7, 4, 4, 3, 3, 6, 14, 3, 4, 10, 6, 3, 6, 4, 4, 4, 8, 7, 6, 8, 7, 10, 5, 11, 8, 5, 11, 4, 7, 7, 5, 8, 12, 5, 6, 9, 8, 11, 8, 5, 8, 9, 8, 10, 8, 12, 7, 11, 8, 7, 7, 8, 6, 7, 8, 11, 8, 16, 9, 12, 13, 8

Offset: 1

Author

Matthew Conroy, Dec 31 2010

Keywords

• nonn
• nice

Comments

That the terms are nonzero for n>4 is shown by the fact that for n odd, P={1,(n-1)/2,n-1} works, and for n even, P={1,(n-2)/2,n} works.

a(A207852(n)) = n and a(m) <> n for m < A207852(n). - Reinhard Zumkeller, Feb 21 2012

Examples

			{1,2,3} can be partitioned into P={3} and S={1,2} with 3=1+2.  This is the only such partition, so a(3)=1.
{1,2,3,4,5} can be partitioned into P={1,2,4} and S={3,5} with 1*2*4=3+5.  This is the only such partition, so a(5)=1.
{1,...,10} can be partitioned into subsets P={1,2,3,7} and S={4,5,6,8,9,10} since 1*2*3*7=4+5+6+8+9+10. P can also be taken as P={6,7} or P={1,4,10}, and so there are 3 distinct ways to partition {1,...,10}, and so a(10)=3.
		

References

• Problem 2826, Crux Mathematicorum, May 2004, 178-179

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..1800, (first 300 terms from Reinhard Zumkeller)

Programs

Haskell

a178830 1 = 0
a178830 n = z [1..n] (n * (n + 1) `div` 2) 1 where
   z []     s p             = fromEnum (s == p)
   z (x:xs) s p | s > p     = z xs (s - x) (p * x) + z xs s p
                | otherwise = fromEnum (s == p)
-- Reinhard Zumkeller, Feb 21 2012

Maple

b:= proc(n, s, p)
      `if`(s=p, 1, `if`(n<1, 0, b(n-1, s, p)+
      `if`(s-n `if`(n=1, 0, b(n, n*(n+1)/2, 1)):
seq(a(n), n=1..100);  # Alois P. Heinz, Jun 07 2012

Mathematica

b[, s, s_] = 1; b[n_ /; n < 1, , ] = 0; b[n_, s_, p_] := b[n, s, p] = b[n-1, s, p] + If[s-n < p*n, 0, b[n-1, s-n, p*n]]; a[1] = 0; a[n_] := a[n] = b[n, n*(n+1)/2, 1]; Table[Print[a[n]]; a[n], {n, 1, 100}] (* Jean-François Alcover, Aug 16 2013, after Alois P. Heinz *)

PARI

maxprodset(n)=ii=1;while(ii!+ii*(ii+1)/2