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,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.

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

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

Sequence in context: A338804 A090270 A326441 * A029329 A287872 A191863

Adjacent sequences: A178827 A178828 A178829 * A178831 A178832 A178833

Keyword

nonn,nice

Author

Matthew Conroy, Dec 31 2010

Status

approved