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
Examples
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.
Crossrefs
Programs
-
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 *)
Extensions
a(26) from Alois P. Heinz, Oct 20 2014
Comments