A196534 Number of different ways to select disjoint nonempty subsets from {1..n} with equal element sum.

1, 3, 8, 18, 39, 83, 179, 388, 857, 1914, 4494, 10844, 26923, 70645, 192297, 538646, 1579602, 4793718, 15010425, 48941642, 164010913, 566065123, 2025354291, 7450901462, 27986863322, 107940691328

Offset

1,2

Comments

A000225(n) <= a(n) <= A058692(n+1).

Links

Table of n, a(n) for n=1..26.

Example

a(3) = 8: {{1}}, {{2}}, {{3}}, {{1,2}}, {{1,3}}, {{2,3}}, {{1,2,3}}, {{1,2},{3}}. Element sums are 1, 2, 3, 3, 4, 5, 6, and 3, respectively.

Maple

b:= proc(l, n, k) option remember; local i, j; `if`(l=[0$k], 1, `if`(add(j, j=l)>n*(n-1)/2, 0, b(l, n-1, k))+ add(`if`(l[j]-n<0, 0, b(sort([seq(l[i] -`if`(i=j, n, 0), i=1..k)]), n-1, k)), j=1..k)) end: a:= n-> add(add(b([t$k], n, k), t=2*k-1..floor(n*(n+1)/(2*k)))/k!, k=1..n): seq(a(n), n=1..15);

Mathematica

b[l_, n_, k_] := b[l, n, k] = If[l == Array[0&, k], 1, If[Total[l] > n*(n-1)/2, 0, b[l, n-1, k]] + Sum[If[l[[j]]-n < 0, 0, b[Sort[Table[ l[[i]] - If[i == j, n, 0], {i, 1, k}]], n-1, k]], {j, 1, k}]];
a[n_] := Sum[Sum[b[Array[t&, k], n, k], {t, 2*k-1, Floor[n*(n+1)/(2*k)]} ]/k!, {k, 1, Ceiling[n/2]}];
Table[Print[n, " ", a[n]]; a[n], {n, 1, 25}] (* Jean-François Alcover, Jun 01 2022, after Alois P. Heinz *)

Crossrefs

Row sums of A196231. Cf. A000225, A161943, A164934, A164949, A196232, A196233, A196234, A196235, A196236, A196237, A058692.

Sequence in context: A178420 A011377 A036385 * A317188 A360784 A335464

Adjacent sequences: A196531 A196532 A196533 * A196535 A196536 A196537

Keyword

nonn,more

Author

Alois P. Heinz, Oct 03 2011

Extensions

a(26) from Alois P. Heinz, Oct 20 2014

Status

approved