|
| |
|
|
A104725
|
|
Number of complementing systems of subsets of {0, 1, ..., n-1}.
|
|
6
|
|
|
|
0, 1, 1, 1, 2, 1, 3, 1, 5, 2, 3, 1, 11, 1, 3, 3, 15, 1, 11, 1, 11, 3, 3, 1, 45, 2, 3, 5, 11, 1, 19, 1, 52, 3, 3, 3, 62, 1, 3, 3, 45, 1, 19, 1, 11, 11, 3, 1, 200, 2, 11, 3, 11, 1, 45, 3, 45, 3, 3, 1, 113, 1, 3, 11, 203, 3, 19, 1, 11, 3, 19, 1, 355, 1, 3, 11, 11, 3, 19, 1, 200, 15, 3, 1, 113, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,5
|
|
|
COMMENTS
|
Number of collections {S_1, S_2, ..., S_k} of subsets of {0, 1, ..., n-1}, each subset containing 0, such that every element x of {0,1, ..., n-1} can be uniquely expressed as x=x_1+x_2+ ...+ x_k with x_i in S_i for all i=1..k.
|
|
|
LINKS
|
|
|
|
FORMULA
|
a(0)=0, a(1)=1, a(n)=Sum(ordfac(n,k)*Bell(k-1),k=1..Omega(n)), n>1, where ordfac(n,k)=number of ordered factorizations of n into k factors.
|
|
|
EXAMPLE
|
a(6) = 3: {{0,1,2,3,4,5}}, {{0,1,2},{0,3}} and {{0,1},{0,2,4}}.
Thus since {{0,1,2},{0,3}} is a complementing system of subsets of {0,1,2,3,4,5} we have 0=0+0, 1=1+0, 2=2+0, 3=0+3, 4=1+3, 5=2+3.
|
|
|
MAPLE
|
with(combinat): a:=proc(n::integer) local u, r, i, j, k; if n<1 then return 0; elif n=1 then return 1; end if; u:=map(x->x[2], ifactors(n)[2]); r:=add(u[i], i=1..nops(u)); add(add((-1)^i*binomial(k, i)*product(binomial(u[j]+k-i-1, u[j]), j=1..nops(u)), i=0..k-1)*bell(k-1), k=1..r); end proc: seq(a(n), n=0..90);
|
|
|
MATHEMATICA
|
nmax=85; a[n_] := (u = FactorInteger[n][[All, 2]]; r = Total[u]; Sum[ Sum[(-1)^i*Binomial[k, i]* Product[ Binomial[ u[[j]]+k-i-1, u[[j]] ], {j, 1, Length[u]}], {i, 0, k-1}]*BellB[k-1], {k, 1, r}]); a[0] = 0; a[1] = 1; Table[a[n], {n, 0, nmax}](* Jean-François Alcover, Nov 18 2011, after Maple *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice,core
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
