A164988 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, 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, 85, 137, 37, 181, 248, 346, 893, 299, 106, 404, 1974, 993, 338, 669, 724, 853, 3335, 1068, 8757, 1371, 852, 2422, 9157, 7124, 17168, 2702, 11606, 6390, 10782, 17681, 68538
Offset: 1
Examples
a(9) = 3: subset selections are [{1},{3},{9}], [{1},{3},{2,7}], [{1},{3},{4,5}].
a(10) = 3: [{1},{2},{5},{10}], [{1},{2},{5},{3,7}], [{1},{2},{5},{4,6}].
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}].
a(12) = 2: [{1},{2},{3},{4},{6},{12}], [{1},{2},{3},{4},{6},{5,7}].
Links
- Alois P. Heinz, Table of n, a(n) for n = 1..155
Programs
-
Maple
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);
-
Mathematica
$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 *)
Formula
a(p) = A025147(p) for p prime. - Charlie Neder, Jan 15 2019