A059443 -id:A059443 - cp's OEIS frontend

A059949 Number of 8-block bicoverings of an n-set.

0, 0, 0, 0, 0, 535, 51640, 2771685, 114713760, 4127125695, 136631722920, 4292250804985, 130278290187760, 3863262740532195, 112733098867629240, 3252644718804860925, 93093809127731630400, 2649006256251644780935

Offset: 1

Vladeta Jovovic, Feb 14 2001

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

Vincenzo Librandi, Table of n, a(n) for n = 1..100

Column k=8 of A059443.

Cf. A002718.

a(n) = (1/8!)*(28^n - 8*21^n - 28*16^n + 56*15^n + 168*11^n - 224*10^n + 210*8^n - 840*7^n + 700*6^n - 840*5^n + 1925*4^n + 1064*3^n - 5460*2^n + 4368).
E.g.f. for m-block bicoverings of an n-set is exp(-x-1/2*x^2*(exp(y)-1))*Sum_{i=0..inf} x^i/i!*exp(binomial(i, 2)*y).
G.f.: -5*x^6*(3390266880*x^8 -3368778336*x^7 +1334596314*x^6 -268312855*x^5 +27919999*x^4 -1171492*x^3 -29534*x^2 +4331*x -107) / ((x -1)*(2*x -1)*(3*x- 1)*(4*x -1)*(5*x -1)*(6*x -1)*(7*x -1)*(8*x -1)*(10*x -1)*(11*x -1)*(15*x -1)*(16*x -1)*(21*x -1)*(28*x -1)). - Colin Barker, Jul 08 2013

A059950 Number of 9-block bicoverings of an n-set.

Original entry on oeis.org

0, 0, 0, 0, 0, 15, 8456, 954213, 66253552, 3622342095, 172672602432, 7557346901841, 312733696544984, 12456923582109435, 483124650731622328, 18383758048494864909, 689931203330381971296, 25630900118611348761735, 945025181750878420241744, 34647077709586498046291817

Offset: 1

Vladeta Jovovic, Feb 14 2001

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

Vincenzo Librandi, Table of n, a(n) for n = 1..200

Column k=9 of A059443.

Cf. A002718.

a(n)=(1/9!)*(36^n -9*28^n -36*22^n +72*21^n +252*16^n -336*15^n +378*12^n -1512*11^n +1260*10^n -1890*8^n +5040*7^n -4536*6^n +7560*5^n -8820*4^n -11256*3^n +28728*2^n -19152).
E.g.f. for m-block bicoverings of an n-set is exp(-x-1/2*x^2*(exp(y)-1))*Sum_{i=0..inf} x^i/i!*exp(binomial(i, 2)*y).
G.f.: x^6*(69766476595200*x^11 -73112128911360*x^10 +31807557729984*x^9 -7437208397056*x^8 +993276127572*x^7 -70229555428*x^6 +1198328731*x^5 +199609307*x^4 -16366808*x^3 +505224*x^2 -5351*x -15) / ((x -1)*(2*x -1)*(3*x -1)*(4*x -1)*(5*x -1)*(6*x -1)*(7*x -1)*(8*x -1)*(10*x -1)*(11*x -1)*(12*x -1)*(15*x -1)*(16*x -1)*(21*x -1)*(22*x -1)*(28*x -1)*(36*x -1)). - Colin Barker, Jul 09 2013

A094573 Triangle T(n,k) giving number of (<=2)-covers of an n-set with k blocks.

Original entry on oeis.org

1, 1, 1, 3, 1, 1, 12, 20, 7, 1, 39, 169, 186, 59, 3, 1, 120, 1160, 2755, 2243, 661, 55, 1, 363, 7381, 33270, 52060, 33604, 9167, 910, 15, 1, 1092, 45500, 367087, 988750, 1126874, 601262, 151726, 16401, 525, 1, 3279, 276529, 3873786, 17005149

Offset: 0

Goran Kilibarda, Vladeta Jovovic, May 12 2004

Cover of a set is (<=2)-cover if every element of the set is covered with at most two blocks of the cover.

			Triangle T(n,k) begins:
  1;
  1;
  1,   3,    1;
  1,  12,   20,    7;
  1,  39,  169,  186,   59,   3;
  1, 120, 1160, 2755, 2243, 661, 55;
  ...

Row sums give A094574.

Cf. A059443, A060052.

rows = 9; m = rows + 2;
egf = Exp[-x - (x^2/2)*(Exp[y]-1)]*Sum[Exp[y*Binomial[n+1, 2]]*(x^n/n!), {n, 0, m}];
cc = CoefficientList[# + O[x]^m, x]& /@ CoefficientList[egf + O[y]^m, y];
(Range[0, Length[cc]-1]! * cc)[[1 ;; rows]] /. {0, a__} :> {a} // Flatten (* Jean-François Alcover, May 13 2019 *)

E.g.f.: exp(-x-x^2/2*(exp(y)-1))*(Sum_{n>=0} exp(y*binomial(n+1, 2))*x^n/n!).

A275517 Number of n-block bicoverings of an n-set.

Original entry on oeis.org

1, 0, 0, 4, 39, 472, 7255, 131876, 2771685, 66253552, 1775801814, 52761229240, 1721387545471, 61187851111432, 2353835271333611, 97437447411025008, 4318780849687684325, 204079128112017902848, 10241833975586335217950, 544031400274026445420368

Offset: 0

Alois P. Heinz, Jul 31 2016

nonn

			a(3) = 4: 1|123|23, 12|13|23, 12|123|3, 123|13|2.

Alois P. Heinz, Table of n, a(n) for n = 0..150

Main diagonal of A059443.

a(n) = n! * [(x*y)^n] 1/exp(x+x^2/2*(exp(y)-1)) * Sum_{j>=0} x^j/j! * exp(C(j,2)*y).
a(n) = A059443(n,n).
a(n)/n! ~ c * d^n / n, where d = 2.942382880944169398..., c = 0.1111860502273875... . - Vaclav Kotesovec, Aug 02 2016

A275521 Number of (n+floor(n/2))-block bicoverings of an n-set.

Original entry on oeis.org

1, 0, 1, 4, 3, 40, 15, 420, 105, 5040, 945, 69300, 10395, 1081080, 135135, 18918900, 2027025, 367567200, 34459425, 7856748900, 654729075, 183324141000, 13749310575, 4638100767300, 316234143225, 126493657290000, 7905853580625, 3699939475732500, 213458046676875

Offset: 0

Alois P. Heinz, Jul 31 2016

nonn

There are no bicoverings of an n-set with more than n+floor(n/2) blocks.

			a(2) = 1: 1|12|2.
a(3) = 4: 1|12|23|3, 1|13|2|23, 1|123|2|3, 12|13|2|3.
a(4) = 3: 1|12|2|3|34|4, 1|13|2|24|3|4, 1|14|2|23|3|4.

Alois P. Heinz, Table of n, a(n) for n = 0..808

Right border of triangle A059443.

Bisections give: A001147, 4*A000457(n-1) (for n>0).

a:= proc(n) option remember; `if`(n<5, [1, 0, 1, 4, 3]
       [n+1], ((8*n-41)*a(n-1) +(6*n^2-12*n-12)*a(n-2)
       -(n-2)*(8*n-17)*a(n-3)) / (6*n-24))
    end:
seq(a(n), n=0..30);

a(n) = A059443(n,n+floor(n/2)).

A276640 Triangle T(n, k) = the number of point-labeled graphs with n points and k edges, no points isolated, no edges isolated. By rows, 0 <= n, ceiling(2*n/3) <= k <= binomial(n, 2).

Original entry on oeis.org

1, 3, 1, 16, 15, 6, 1, 125, 222, 205, 120, 45, 10, 1, 90, 1356, 3670, 5700, 6165, 4945, 2997, 1365, 455, 105, 15, 1, 1680, 18942, 69450, 156870, 258160, 331506, 343140, 290745, 202755, 116175, 54257, 20349, 5985, 1330, 210, 21, 1

Offset: 1

David Pasino, Sep 08 2016

In an incidence matrix for a graph of this kind, with n columns and k rows, each row has 2 ones (since it is a graph), the rows are distinct (since it is not a multigraph), no column is all zeros (since there are no isolated points), and the columns are distinct (since there are no isolated edges). The transpose of such a matrix, and only such, is an incidence matrix of a covering of a set of k elements (called points) by n distinct nonempty subsets (called blocks) such that every point belongs to exactly 2 blocks, and every 2 blocks have at most 1 point of intersection (for if 2 points each belong to both of 2 blocks, then those 2 blocks are all the blocks that either of those 2 points belong to, so the columns for those 2 points in the matrix are equal). Referring all these matrices to canonical ordered sets of n and k points, the number of matrices for each covering by blocks of these kinds is the factorial of the number of blocks. (Since the rows are distinct, every permutation of the blocks as row indices gives a different matrix.) Hence the number of these graphs, with k blocks on n points, T(n, k), is related to the number of those covers, A060052, by T(n, k) * k! = A060052(k, n) * n!.

			The triangle T(n, k) begins:
n\k 0 1 2 3  4   5    6    7    8    9   10   11   12  13  14
0   1 0 0 0  0   0    0    0    0    0    0    0    0   0   0
1   0 0 0 0  0   0    0    0    0    0    0    0    0   0   0
2   0 0 0 0  0   0    0    0    0    0    0    0    0   0   0
3   0 0 3 1  0   0    0    0    0    0    0    0    0   0   0
4   0 0 0 16 15  6    1    0    0    0    0    0    0   0   0
5   0 0 0 0  125 222  205  120  45   10   1    0    0   0   0
6   0 0 0 0  90  1356 3670 5700 6165 4945 2997 1365 455 105 15

David Pasino, Table of n, a(n) for n = 1..491

Cf. A059443, A060052.

T(n, k) = Sum{s=0..min(floor(n/2), k)} binomial(n, 2*s) * ((2*s)! / (2^s * s!)) * (-1)^s * A276639(n - 2*s, k - s). (This is the inverse relationship of A276639 in terms of T. A276639(n, k) counts graphs with no isolated points, n points, k edges. The summation range of s, the role of s in the arguments (n - 2s, k - s) of the T or A function being summed, and the coefficient function of s, are the same in the relationship going either way, except that the factor (-1)^s is absent when the function being summed is this T. The coefficient, without the -1, is the number of ways to choose 2s points among the n and group them into s pairs to be s isolated edges. A graph with no isolated points is a graph with some number s of isolated edges and a graph on the complement of the union of those with no isolated edges and no isolated points. That the inverse relationship is almost the same was found empirically for small values of n (leaving k as k), and once found, was readily proved.)

cp's OEIS Frontend

A059949 Number of 8-block bicoverings of an n-set.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A059950 Number of 9-block bicoverings of an n-set.

Views

Author

Keywords

References

Links

Crossrefs

Formula

A094573 Triangle T(n,k) giving number of (<=2)-covers of an n-set with k blocks.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A275517 Number of n-block bicoverings of an n-set.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A275521 Number of (n+floor(n/2))-block bicoverings of an n-set.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

A276640 Triangle T(n, k) = the number of point-labeled graphs with n points and k edges, no points isolated, no edges isolated. By rows, 0 <= n, ceiling(2*n/3) <= k <= binomial(n, 2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula