login
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.
5
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
KEYWORD
nonn,nice
AUTHOR
Matthew Conroy, Dec 31 2010
STATUS
approved