A060070 -id:A060070 - cp's OEIS frontend

A331039 Array read by antidiagonals: A(n,k) is the number of T_0 n-regular set-systems on a k-set.

1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 5, 0, 0, 1, 0, 1, 43, 5, 0, 0, 1, 0, 1, 518, 175, 1, 0, 0, 1, 0, 1, 8186, 9426, 272, 0, 0, 0, 1, 0, 1, 163356, 751365, 64453, 205, 0, 0, 0, 1, 0, 1, 3988342, 84012191, 23553340, 248685, 80, 0, 0, 0, 1

Offset: 0

Andrew Howroyd, Jan 08 2020

An n-regular set-system is a finite set of nonempty sets in which each element appears in n blocks.
A set-system is T_0 if for every two distinct elements there exists a block containing one but not the other element.
A(n,k) is the number of binary matrices with k distinct columns and any number of distinct nonzero rows with n ones in every column and rows in decreasing lexicographic order.

			Array begins:
==========================================================
n\k | 0 1 2 3   4       5           6                7
----+-----------------------------------------------------
  0 | 1 1 0 0   0       0           0                0 ...
  1 | 1 1 1 1   1       1           1                1 ...
  2 | 1 0 1 5  43     518        8186           163356 ...
  3 | 1 0 0 5 175    9426      751365         84012191 ...
  4 | 1 0 0 1 272   64453    23553340      13241130441 ...
  5 | 1 0 0 0 205  248685   421934358    1176014951129 ...
  6 | 1 0 0 0  80  620548  5055634889   69754280936418 ...
  7 | 1 0 0 0  15 1057989 43402628681 2972156676325398 ...
  ...
The A(2,3) = 5 matrices are:
  [1 1 1]    [1 1 0]    [1 1 0]    [1 0 1]    [1 1 0]
  [1 0 0]    [1 0 1]    [1 0 0]    [1 0 0]    [1 0 1]
  [0 1 0]    [0 1 0]    [0 1 1]    [0 1 1]    [0 1 1]
  [0 0 1]    [0 0 1]    [0 0 1]    [0 1 0]
The corresponding set-systems are:
  {{1,2,3}, {1}, {2}, {3}},
  {{1,2}, {1,3}, {2,3}},
  {{1,2}, {1,3}, {2}, {3}},
  {{1,2}, {1}, {2,3}, {3}},
  {{1,3}, {1}, {2,3}, {2}}.

Andrew Howroyd, Table of n, a(n) for n = 0..209

Rows n=1..4 are A000012, A060053, A060070, A331655.

Cf. A188445, A330942, A330964, A331126, A331160, A331161, A331569, A331654.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
D(p, n, k)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); binomial(WeighT(v)[n], k)*k!/prod(i=1, #v, i^v[i]*v[i]!)}
T(n, k)={my(m=n*k+1, q=Vec(exp(intformal(O(x^m) - x^n/(1-x)))/(1+x))); if(n==0, k<=1, (-1)^m*sum(j=0, m, my(s=0); forpart(p=j, s+=(-1)^#p*D(p, n, k), [1, n]); s*q[#q-j])/2)}

A(n, k) = Sum_{j=1..k} Stirling1(k, j)*A188445(n, j) for n, k >= 1.
A(n, k) = 0 for k >= 1, n > 2^(k-1).
A331654(n) = Sum_{d|n} A(n/d, d).

A060090 Number of ordered bicoverings of an unlabeled n-set.

Original entry on oeis.org

1, 0, 3, 23, 290, 4298, 79143, 1702923, 42299820, 1188147639, 37276597020, 1291633545897, 48995506718702, 2019395409175529, 89864601931874318, 4294295828157319651, 219321170795303112118, 11922219151375200468886

Offset: 0

Vladeta Jovovic, Feb 25 2001

nonn

			There are 23 ordered bicoverings of an unlabeled 3-set, 7 3-block bicoverings:
1 ( { 3 }, { 1, 2 }, { 1, 2, 3 } )
2 ( { 3 }, { 1, 2, 3 }, { 1, 2 } )
3 ( { 2, 3 }, { 1 }, { 1, 2, 3 } )
4 ( { 2, 3 }, { 1, 3 }, { 1, 2 } )
5 ( { 2, 3 }, { 1, 2, 3 }, { 1 } )
6 ( { 1, 2, 3 }, { 3 }, { 1, 2 } )
7 ( { 1, 2, 3 }, { 2, 3 }, { 1 } )
and 16 4-block bicoverings:
1 ( { 3 }, { 2 }, { 1 }, { 1, 2, 3 } )
2 ( { 3 }, { 2 }, { 1, 3 }, { 1, 2 } )
3 ( { 3 }, { 2 }, { 1, 2 }, { 1, 3 } )
4 ( { 3 }, { 2 }, { 1, 2, 3 }, { 1 } )
5 ( { 3 }, { 2, 3 }, { 1 }, { 1, 2 } )
6 ( { 3 }, { 2, 3 }, { 1, 2 }, { 1 } )
7 ( { 3 }, { 1, 2 }, { 2 }, { 1, 3 } )
8 ( { 3 }, { 1, 2 }, { 2, 3 }, { 1 } )
9 ( { 3 }, { 1, 2, 3 }, { 2 }, { 1 } )
10 ( { 2, 3 }, { 3 }, { 1 }, { 1, 2 } )
11 ( { 2, 3 }, { 3 }, { 1, 2 }, { 1 } )
12 ( { 2, 3 }, { 1 }, { 3 }, { 1, 2 } )
13 ( { 2, 3 }, { 1 }, { 1, 3 }, { 2 } )
14 ( { 2, 3 }, { 1, 3 }, { 2 }, { 1 } )
15 ( { 2, 3 }, { 1, 3 }, { 1 }, { 2 } )
16 ( { 1, 2, 3 }, { 3 }, { 2 }, { 1 } )

Andrew Howroyd, Table of n, a(n) for n = 0..200

Row n=2 of A331571.
Row sums of A060092.
Cf. A060069, A060070, A060051, A060052, A060053, A002718, A059443.

seq(n)={my(m=3*n\2, y='y + O('y^(n+1))); Vec(subst(Pol(serlaplace(exp(-x - x^2*y/(2*(1-y)) + O(x*x^m))*sum(k=0, m, 1/(1-y)^binomial(k, 2)*x^k/k!))), x, 1))} \\ Andrew Howroyd, Jan 30 2020

E.g.f. for ordered k-block bicoverings of an unlabeled n-set is exp(-x-x^2/2*y/(1-y)) * Sum_{k>=0} 1/(1-y)^binomial(k,2)*x^k/k!.

A060051 Number of n-block r-bicoverings.

Original entry on oeis.org

1, 0, 0, 2, 79, 82117, 4936900199, 27555467226181396, 20554872166566046969648895, 2786548447182420815380482508924733911, 89607283195144164483079065133414172790220498449945, 864608448649084311874549352448884076627916391005243593208944730790

Offset: 0

Vladeta Jovovic, Feb 15 2001

A bicovering is an r-bicovering if the intersection of every two blocks contains at most one element.

			There are 2 3-block r-bicoverings: {{1},{2},{1,2}} and {{1,2},{1,3},{2,3}}.

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.

Andrew Howroyd, Table of n, a(n) for n = 0..30

Column sums of A060052.

Cf. A002718, A060053, A060069, A060070.

E.g.f. for number of n-block r-bicoverings of a k-set is exp(-x-1/2*x^2*y)*Sum_{i=0..inf} (1+y)^binomial(i, 2)*x^i/i!.

Terms a(11) and beyond from Andrew Howroyd, Jan 30 2020

A060069 Number of n-block T_0-tricoverings.

Original entry on oeis.org

1, 0, 0, 0, 2, 82194, 9185157387760082, 5573096894405951375691132323893805593, 47933892393105239218152796441416602126447041437452022947424986090407628

Offset: 0

Vladeta Jovovic, Feb 19 2001

nonn

A covering of a set is a tricovering if every element of the set is covered by exactly three blocks of the covering; A covering of a set is a T_0-covering if for every two distinct elements of the set there exists a block of the covering containing one but not the other element.

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.

Andrew Howroyd, Table of n, a(n) for n = 0..15

Column sums of A059530.

Cf. A060051, A060053, A060070, A060486.

E.g.f. for n-block T_0-tricoverings of a k-set is exp(-x+1/2*x^2+1/3*x^3*y)*Sum_{i=0..inf} (1+y)^binomial(i, 3)*exp(-1/2*x^2*(1+y)^i)*x^i/i!.

A060487 Triangle T(n,k) of k-block tricoverings of an n-set (n >= 3, k >= 4).

Original entry on oeis.org

1, 3, 1, 7, 57, 95, 43, 3, 35, 717, 3107, 4520, 2465, 445, 12, 155, 7845, 75835, 244035, 325890, 195215, 50825, 4710, 70, 651, 81333, 1653771, 10418070, 27074575, 33453959, 20891962, 6580070, 965965, 52430, 465

Offset: 3

Vladeta Jovovic, Mar 20 2001

A covering of a set is a tricovering if every element of the set is covered by exactly three blocks of the covering.

			Triangle begins:
  [1, 3, 1];
  [7, 57, 95, 43, 3];
  [35, 717, 3107, 4520, 2465, 445, 12];
  [155, 7845, 75835, 244035, 325890, 195215, 50825, 4710, 70];
  [651, 81333, 1653771, 10418070, 27074575, 33453959, 20891962, 6580070, 965965, 52430, 465];
   ...
There are 205 tricoverings of a 4-set(cf. A060486): 7 4-block, 57 5-block, 95 6-block, 43 7-block and 3 8-block tricoverings.

Andrew Howroyd, Table of n, a(n) for n = 3..1157

Columns include A060483, A060484, A060485.
Row sums are A060486.
Cf. A006095, A060090-A060095, A060069, A060070, A060051-A060053, A002718, A059443, A003462, A059945-A059951.

WeighT(v)={Vec(exp(x*Ser(dirmul(v, vector(#v, n, (-1)^(n-1)/n))))-1, -#v)}
D(p, n, k)={my(v=vector(n)); for(i=1, #p, v[p[i]]++); WeighT(v)[n]^k/prod(i=1, #v, i^v[i]*v[i]!)}
row(n, k)={my(m=n*k+1, q=Vec(exp(intformal(O(x^m) - x^n/(1-x)))/(y+x))); if(n==0, 1, (-1)^m*sum(j=0, m, my(s=0); forpart(p=j, s+=(-1)^#p*D(p, n, k), [1, n]); s*q[#q-j])*y^(m-n)/(1+y))}
for(n=3, 8, print(Vecrev(row(3,n)))); \\ Andrew Howroyd, Dec 23 2018

E.g.f. for k-block tricoverings of an n-set is exp(-x+x^2/2+(exp(y)-1)*x^3/3)*Sum_{k=0..inf}x^k/k!*exp(-1/2*x^2*exp(k*y))*exp(binomial(k, 3)*y).

A060486 Tricoverings of an n-set.

Original entry on oeis.org

1, 0, 0, 5, 205, 11301, 904580, 101173251, 15207243828, 2975725761202, 738628553556470, 227636079973503479, 85554823285296622543, 38621481302086460057613, 20669385794052533823555309, 12966707189875262685801947906, 9441485712482676603570079314728

Offset: 0

Vladeta Jovovic, Mar 20 2001

nonn

A covering of a set is a tricovering if every element of the set is covered by exactly three blocks of the covering.

			There are 1 4-block tricovering, 3 5-block tricoverings and 1 6-block tricovering of a 3-set (cf. A060487), so a(3)=5.

Andrew Howroyd, Table of n, a(n) for n = 0..100

Row 3 of A188445.

Cf. A006095, A060483-A060485, (row sums of) A060487, A060090-A060095, A060069, A060070, A060051-A060053, A002718, A059443, A003462, A059945-A059951.

E.g.f. for k-block tricoverings of an n-set is exp(-x+x^2/2+(exp(y)-1)*x^3/3)*Sum_{k=0..inf}x^k/k!*exp(-1/2*x^2*exp(k*y))*exp(binomial(k, 3)*y).

Terms a(11) and beyond from Andrew Howroyd, Dec 15 2018

A059530 Triangle T(n,k) of k-block T_0-tricoverings of an n-set, n >= 3, k = 0..2*n.

Original entry on oeis.org

0, 0, 0, 0, 1, 3, 1, 0, 0, 0, 0, 1, 39, 89, 43, 3, 0, 0, 0, 0, 0, 252, 2192, 4090, 2435, 445, 12, 0, 0, 0, 0, 0, 1260, 37080, 179890, 289170, 188540, 50645, 4710, 70, 0, 0, 0, 0, 0, 5040, 536760, 6052730, 20660055, 29432319, 19826737, 6481160, 964495, 52430

Offset: 3

Vladeta Jovovic, Feb 22 2001

A covering of a set is a tricovering if every element of the set is covered by exactly three blocks of the covering. A covering of a set is a T_0-covering if for every two distinct elements of the set there exists a block of the covering containing one but not the other element.

			Triangle begins:
  [0, 0, 0, 0, 1, 3, 1],
  [0, 0, 0, 0, 1, 39, 89, 43, 3],
  [0, 0, 0, 0, 0, 252, 2192, 4090, 2435, 445, 12],
  [0, 0, 0, 0, 0, 1260, 37080, 179890, 289170, 188540, 50645, 4710, 70],
   ...
There are 5 = 1 + 3 + 1 T_0-tricoverings of a 3-set and 175 = 1 + 39 + 89 + 43 + 3 T_0-tricoverings of a 4-set, cf. A060070.

I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983.

Andrew Howroyd, Table of n, a(n) for n = 3..1674
Vladeta Jovovic, T_0-tricoverings of a 4-set

Column sums are A060069.
Row sums are A060070.
Cf. A059443, A060052, A060092, A060487, A060492, A331039.

\\ gets k-th column as vector
C(k)=if(k<4, [], Vecrev(serlaplace(polcoef(exp(-x + x^2/2 + x^3*y/3 + O(x*x^k))*sum(i=0, 2*k, (1+y)^binomial(i, 3)*exp(-x^2*(1+y)^i/2 + O(x*x^k))*x^i/i!), k))/y)) \\ Andrew Howroyd, Jan 30 2020

T(n)={my(m=2*n, y='y + O('y^(n+1))); my(g=exp(-x + x^2/2 + x^3*y/3 + O(x*x^m))*sum(k=0, m, (1+y)^binomial(k, 3)*exp(-x^2*(1+y)^k/2 + O(x*x^m))*x^k/k!)); Mat([Col(serlaplace(p), -n) | p<-Vec(g)[2..m+1]]);}
{ my(A=T(8)); for(n=3, matsize(A)[1], print(concat([0], A[n, 1..2*n]))) } \\ Andrew Howroyd, Jan 30 2020

E.g.f. for k-block T_0-tricoverings of an n-set is exp(-x+1/2*x^2+1/3*x^3*y)*Sum_{i=0..inf}(1+y)^binomial(i, 3)*exp(-1/2*x^2*(1+y)^i)*x^i/i!.

T(n,k) = 0 for n > binomial(k, 3). - Andrew Howroyd, Jan 30 2020

A060483 Number of 5-block tricoverings of an n-set.

Original entry on oeis.org

3, 57, 717, 7845, 81333, 825237, 8300757, 83202645, 832809813, 8331237717, 83324947797, 833299785045, 8333199127893, 83332796486997, 833331185898837, 8333324743497045, 83333298973791573, 833333195894773077, 8333332783578305877, 83333331134311650645

Offset: 3

Vladeta Jovovic, Mar 20 2001

A covering of a set is a tricovering if every element of the set is covered by exactly three blocks of the covering.

Andrew Howroyd, Table of n, a(n) for n = 3..500
Index entries for linear recurrences with constant coefficients, signature (17,-84,148,-80).

Column k=5 of A060487.

Cf. A006095, A060484, A060485, A060486, A060090-A060095, A060069, A060070, A060051-A060053, A002718, A059443, A003462, A059945-A059951.

Vec(3*(1+2*x)/(x-1)/(2*x-1)/(4*x-1)/(10*x-1)+O(x^99)) \\ Charles R Greathouse IV, Jan 11 2013

a(n) = (1/5!)*(10^n - 15*4^n + 45*2^n - 40).
Generally, e.g.f. for k-block tricoverings of an n-set is exp(-x+x^2/2+(exp(y)-1)*x^3/3)*Sum_{k=0..inf}x^k/k!*exp(-1/2*x^2*exp(k*y))*exp(binomial(k, 3)*y).
G.f.: 3*x^3*(2*x+1) / ((x-1)*(2*x-1)*(4*x-1)*(10*x-1)). - Colin Barker, Jan 11 2013

More terms from Colin Barker, Jan 11 2013

A060491 Number of ordered tricoverings of an unlabeled n-set.

Original entry on oeis.org

1, 0, 0, 184, 17488, 2780752, 689187720, 236477490418, 107317805999204, 62318195302890305, 45081693413563797127, 39762626850034005271588, 42009504510315968282400843, 52381340312720286113688037624, 76118747309505733406576769607755

Offset: 0

Vladeta Jovovic, Mar 20 2001

nonn

A covering of a set is a tricovering if every element of the set is covered by exactly three blocks of the covering.

			There are 184 ordered tricoverings of an unlabeled 3-set: 4 4-block, 60 5-block and 120 6-block tricoverings (cf. A060492).

Andrew Howroyd, Table of n, a(n) for n = 0..100

Row n=3 of A331571.
Row sums of A060492.
Cf. A060486, A060487, A060090, A060092, A060069, A060070, A060051, A060052, A060053, A002718, A059443.

seq(n)={my(m=2*n\2, y='y + O('y^(n+1))); Vec(subst(Pol(serlaplace(exp(-x + x^2/2 + x^3*y/(3*(1-y)) + O(x*x^m))*sum(k=0, m, 1/(1-y)^binomial(k, 3)*exp((-x^2/2)/(1-y)^k + O(x*x^m))*x^k/k!))), x, 1))} \\ Andrew Howroyd, Jan 30 2020

E.g.f. for ordered k-block tricoverings of an unlabeled n-set is exp(-x+x^2/2+x^3/3*y/(1-y))*Sum_{k=0..inf}1/(1-y)^binomial(k, 3)*exp(-x^2/2*1/(1-y)^n)*x^k/k!.

Terms a(11) and beyond from Andrew Howroyd, Jan 30 2020

A060484 Number of 6-block tricoverings of an n-set.

Original entry on oeis.org

1, 95, 3107, 75835, 1653771, 34384875, 700030507, 14116715435, 283432939691, 5679127043755, 113683003777707, 2274630646577835, 45502044971338411, 910133025632152235, 18203564201836161707, 364080180268471397035

Offset: 3

Vladeta Jovovic, Mar 20 2001

A covering of a set is a tricovering if every element of the set is covered by exactly three blocks of the covering.

Andrew Howroyd, Table of n, a(n) for n = 3..200
Index entries for linear recurrences with constant coefficients, signature (45,-720,5220,-17664,25920,-12800).

Column k=6 of A060487.

Cf. A006095, A060483, A060485, A060486, A060090-A060095, A060069, A060070, A060051-A060053, A002718, A059443, A003462, A059945-A059951.

With[{c=1/6!},Table[c(20^n-6*10^n-15*8^n+135*4^n-310*2^n+240),{n,3,20}]] (* or *) LinearRecurrence[{45,-720,5220,-17664,25920,-12800},{1,95,3107,75835,1653771,34384875},20] (* Harvey P. Dale, Jan 05 2017 *)

a(n) = (1/6!)*(20^n - 6*10^n - 15*8^n + 135*4^n - 310*2^n + 240) \\ Andrew Howroyd, Dec 15 2018

a(n) = (1/6!)*(20^n - 6*10^n - 15*8^n + 135*4^n - 310*2^n + 240).
E.g.f. for k-block tricoverings of an n-set is exp(-x+x^2/2+(exp(y)-1)*x^3/3)*Sum_{k=0..inf}x^k/k!*exp(-1/2*x^2*exp(k*y))*exp(binomial(k, 3)*y).
G.f.: -x^3*(800*x^3+448*x^2-50*x-1) / ((x-1)*(2*x-1)*(4*x-1)*(8*x-1)*(10*x-1)*(20*x-1)). - Colin Barker, Jan 12 2013
a(n) = 45*a(n-1)-720*a(n-2)+5220*a(n-3)-17664*a(n-4)+25920*a(n-5)-12800*a(n-6). - Wesley Ivan Hurt, Oct 18 2021

cp's OEIS Frontend

A331039 Array read by antidiagonals: A(n,k) is the number of T_0 n-regular set-systems on a k-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A060090 Number of ordered bicoverings of an unlabeled n-set.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A060051 Number of n-block r-bicoverings.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

Extensions

A060069 Number of n-block T_0-tricoverings.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

A060487 Triangle T(n,k) of k-block tricoverings of an n-set (n >= 3, k >= 4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A060486 Tricoverings of an n-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A059530 Triangle T(n,k) of k-block T_0-tricoverings of an n-set, n >= 3, k = 0..2*n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

PARI

Formula

A060483 Number of 5-block tricoverings of an n-set.

Views

Author

Keywords