login
Number of ways to select disjoint subsets out of {1..n} such that their (sorted) element sums give the list of divisors of n.
1

%I #17 Jan 18 2019 09:58:49

%S 1,1,1,1,2,1,3,2,3,3,7,2,10,9,7,9,21,8,29,12,31,67,56,11,79,167,105,

%T 85,137,37,181,248,346,893,299,106,404,1974,993,338,669,724,853,3335,

%U 1068,8757,1371,852,2422,9157,7124,17168,2702,11606,6390,10782,17681,68538

%N Number of ways to select disjoint subsets out of {1..n} such that their (sorted) element sums give the list of divisors of n.

%H Alois P. Heinz, <a href="/A164988/b164988.txt">Table of n, a(n) for n = 1..155</a>

%F a(p) = A025147(p) for p prime. - _Charlie Neder_, Jan 15 2019

%e a(9) = 3: subset selections are [{1},{3},{9}], [{1},{3},{2,7}], [{1},{3},{4,5}].

%e a(10) = 3: [{1},{2},{5},{10}], [{1},{2},{5},{3,7}], [{1},{2},{5},{4,6}].

%e a(11) = 7: [{1},{11}], [{1},{2,9}], [{1},{3,8}], [{1},{4,7}], [{1},{5,6}], [{1},{2,3,6}], [{1},{2,4,5}].

%e a(12) = 2: [{1},{2},{3},{4},{6},{12}], [{1},{2},{3},{4},{6},{5,7}].

%p with(numtheory): b:= proc() option remember; local i, j, t, m; m:= args[nargs]; if nargs=1 then 1 elif args[1]=0 then b(args[t] $t=2..nargs) elif m=0 or add(args[i], i=1..nargs-1)> m*(m+1)/2 then 0 else b(args[t] $t=1..nargs-1, m-1) +add(`if`(args[j]-m<0, 0, b(sort([seq(args[i] -`if`(i=j, m, 0), i=1..nargs-1)])[], m-1)), j=1..nargs-1) fi end: a:= n-> b(divisors(n)[], n): seq(a(n), n=1..40);

%t $RecursionLimit = 1000; b[args__] := b[args] = Module[{i, j, t, m, nargs}, nargs = Length[{args}]; m = Last[{args}]; Which [nargs == 1, 1, {args}[[1]] == 0, b @@ Rest[{args}], m == 0 || Total[Most[{args}]] > m*(m+1)/2, 0, True, b[Sequence @@ Most[{args}], m-1] + Sum [If[{args}[[j]] - m < 0, 0, b[Sequence @@ Sort[Table[{args}[[i]] - If [i == j, m, 0], {i, 1, nargs-1}]], m-1]], {j, 1, nargs-1}]] ]; a[n_] := b[Sequence @@ Divisors[n], n]; Table[Print["a(", n, ") = ", an = a[n]]; an, {n, 1, 95}] (* _Jean-François Alcover_, Dec 13 2013, translated from Maple *)

%Y Cf. A065205, A035470.

%K nice,nonn

%O 1,5

%A _Alois P. Heinz_, Sep 03 2009