login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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
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.
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.
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
Sequence in context: A296118 A296121 A277120 * A289079 A249810 A257111
KEYWORD
nonn,nice,core
AUTHOR
Augustine O. Munagi, Mar 20 2005; Dec 20 2006
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 01:57 EDT 2024. Contains 370952 sequences. (Running on oeis4.)