A104725 Number of complementing systems of subsets of {0, 1, ..., n-1}.

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

Offset: 0

Author

Augustine O. Munagi, Mar 20 2005; Dec 20 2006

Keywords

• nonn
• nice
• core

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.

Examples

			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.
		

Links

• N. J. A. Sloane, Table of n, a(n) for n = 0..10000
• C. T. Long, Addition Theorems for sets of Integers, Pacific J. Math. 23 (1967), 107-112.
• A. O. Munagi, Notes on A104725
• A. O. Munagi, k-Complementing Subsets of Nonnegative Integers, IJMMS 2005:2 (2005), 215-224.
• Index entries for "core" sequences

Crossrefs

Cf. A074206, A002033.

Programs

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 *)

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.

a(n)= A074206(n) if A001222(n)=1, 2.