OFFSET
1,10
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.
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)
EXAMPLE
{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.
MAPLE
b:= proc(n, s, p)
`if`(s=p, 1, `if`(n<1, 0, b(n-1, s, p)+
`if`(s-n<p*n, 0, b(n-1, s-n, p*n))))
end:
a:= 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 *)
PROG
(PARI) maxprodset(n)=ii=1; while(ii!+ii*(ii+1)/2<n*(n+1)/2, ii=ii+1); return(ii-1);
{for(jj=2, 100,
countK=0;
S=vector(jj, ii, ii);
for(subsize=1, maxprodset(jj),
forvec(v=vector(subsize, k, [1, #S]),
vs=vecextract(S, v);
summ=jj*(jj+1)/2-sum(jk=1, #vs, vs[jk]);
prodd=prod(jk=1, #vs, vs[jk]);
if(summ==prodd, countK=countK+1),
2));
print1(countK, ", ");
)
}
(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
CROSSREFS
KEYWORD
nonn,nice
AUTHOR
Matthew Conroy, Dec 31 2010
STATUS
approved