|
|
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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,5
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
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}].
|
|
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 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
nice,nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|