A005333 -id:A005333 - cp's OEIS frontend

A002501 a(n) = 7^n - 34^n + 23^n.

1, 19, 205, 1795, 14221, 106819, 778765, 5581315, 39606541, 279447619, 1965098125, 13792018435, 96690872461, 677427332419, 4744368982285, 33220131761155, 232579232659981, 1628208214321219, 11398072876175245, 79788974736297475, 558532690864457101

Offset: 1

N. J. A. Sloane

Counts connected relations. On page 578 Kreweras (1969) says: "Le théorème s'applique notamment au dénombrement des relations binaires externes qui possèdent la propriété de connexité; cela revient à calculer le nombre a(m,n) de manières de remplir un tableau de m lignes et n colonnes avec des 0 et des 1, en respectant les deux conditions suivantes: (1): aucune rangée (ligne ni colonne) ne doit être tout entière remplie de zéros; (2): deux cases quelconques marquées 1 peuvent être jointes par une chaîne de cases marquées 1 telle que deux cases consécutives de la chaîne appartiennent à une même rangée."

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..200
G. Kreweras, Inversion des polynomes de Bell bidimensionnels et application au dénombrement des relations binaires connexes, C. R. Acad. Sci. Paris Ser. A-B 268 1969 A577-A579.
Index entries for linear recurrences with constant coefficients, signature (14,-61,84)

Cf. A005333, A001047, A002502, A093732, A093733.

A diagonal of A262307.

Table[7^n - 3*4^n + 2*3^n, {n, 20}] (* T. D. Noe, May 29 2012 *)

a(n)=7^n-3*4^n+2*3^n \\ Charles R Greathouse IV, Sep 24 2015

G.f.: -x*(1+5*x) / ( (3*x-1)*(7*x-1)*(4*x-1) ). - R. J. Mathar, Jun 09 2013

a(n) = 14*a(n-1) - 61*a(n-2) + 84*a(n-3). - Wesley Ivan Hurt, Apr 11 2022

Better definition and more terms from Goran Kilibarda, Vladeta Jovovic, Apr 14 2004

A002502 Number of connected relations.

Original entry on oeis.org

1, 65, 1795, 36317, 636331, 10365005, 162470155, 2495037197, 37898120011, 572284920845, 8614868501515, 129467758660877, 1943971108806091, 29175170378428685, 437752102106036875, 6567275797761209357

Offset: 1

N. J. A. Sloane

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=1..100
G. Kreweras, Inversion des polynômes de Bell bidimensionnels et application au dénombrement des relations binaires connexes. C. R. Acad. Sci. Paris Ser. A-B 268 1969 A577-A579.
Index entries for linear recurrences with constant coefficients, signature (38,-539,3622,-11640,14400).

Cf. A005333, A001047, A002501, A093732, A093733.

A diagonal of A262307.

LinearRecurrence[{38,-539,3622,-11640,14400},{1,65,1795,36317,636331},20] (* Harvey P. Dale, Mar 24 2017 *)

15^n-4*8^n-3*6^n+12*5^n-6*4^n. - Goran Kilibarda, Vladeta Jovovic, Apr 14 2004
G.f. x*( -1-27*x+136*x^2+480*x^3 ) / ( (6*x-1)*(5*x-1)*(15*x-1)*(4*x-1)*(8*x-1) ).
- R. J. Mathar, Jun 09 2013

More terms from Goran Kilibarda, Vladeta Jovovic, Apr 14 2004

A093732 Number of connected relations.

Original entry on oeis.org

1, 211, 14221, 636331, 23679901, 805351531, 26175881341, 831358677451, 26094426008221, 814105545191851, 25320182311228861, 786251347986776971, 24394981288950302941, 756583120577782494571, 23459491617092461686781, 727330825918603925122891

Offset: 1

Goran Kilibarda, Vladeta Jovovic, Apr 14 2004

T. D. Noe, Table of n, a(n) for n = 1..200
G. Kilibarda and V. Jovovic, Enumeration of some classes of T_0-hypergraphs, arXiv:1411.4187 [math.CO], 2014.
G. Kreweras, Inversion des polynômes de Bell bidimensionnels et application au dénombrement des relations binaires connexes, C. R. Acad. Sci. Paris Ser. A-B 268 1969 A577-A579.
Index entries for linear recurrences with constant coefficients, signature (84,-2774,47548,-462525,2575088,-7643820,9374400).

Cf. A005333, A001047, A002501, A002502, A093733.

Table[31^n - 5*16^n - 10*10^n + 20*9^n + 30*7^n - 60*6^n + 24*5^n, {n, 25}] (* T. D. Noe, May 29 2012 *)

a(n)=31^n-5*16^n-10*10^n+20*9^n+30*7^n-60*6^n+24*5^n \\ Charles R Greathouse IV, Jun 16 2015

a(n) = 31^n - 5*16^n - 10*10^n + 20*9^n + 30*7^n - 60*6^n + 24*5^n.

G.f.: -x*(1+127*x-729*x^2-20467*x^3+107048*x^4+259620*x^5) / ( (9*x-1)*(6*x-1)*(7*x-1)*(5*x-1)*(31*x-1)*(10*x-1)*(16*x-1) ). - R. J. Mathar, Jun 09 2013

A093733 Number of connected relations.

Original entry on oeis.org

1, 665, 106819, 10365005, 805351531, 56294206205, 3735873535339, 241600284318365, 15423235216318411, 978180744322139645, 61834480769377286059, 3902270609960140639325, 246057483524862034206091, 15508484277325946034039485, 977254123876968508188975979

Offset: 1

Goran Kilibarda and Vladeta Jovovic, Apr 14 2004

T. D. Noe, Table of n, a(n) for n = 1..100
Goran Kilibarda and Vladeta Jovovic, Enumeration of some classes of T_0-hypergraphs, arXiv:1411.4187 [math.CO], 2014.
G. Kreweras, Inversion des polynômes de Bell bidimensionnels et application au dénombrement des relations binaires connexes, C. R. Acad. Sci. Paris Ser. A-B 268 1969 A577-A579.
Index entries for linear recurrences with constant coefficients, signature (-195, 15886, -726290, 20952193, -403792115, 5336718048, -48588590600, 299693200656, -1195947048240, 2785165036416, -2872859996160).

Cf. A001047, A002501, A002502, A005333, A093732.

Table[63^n-6*32^n-15*18^n+30*17^n-10*14^n+120*11^n-120*10^n+30*9^n-270*8^n+360*7^n-120*6^n, {n,1,25}] (* G. C. Greubel, Oct 06 2017 *)
CoefficientList[Series[x (96368590080x^9+27682953984x^8-13185435000x^7+774468980x^6+ 143028190x^5-19071533x^4+626800x^3+6970x^2-470x-1)/((6x-1)(7x-1)(8x-1)(9x-1)(10x-1)(11x-1)(14x-1)(17x-1)(18x-1)(32x-1)(63x-1)),{x,0,20}],x] (* or *) LinearRecurrence[{195,-15886,726290,-20952193,403792115,-5336718048,48588590600,-299693200656,1195947048240,-2785165036416,2872859996160},{0,1,665,106819,10365005,805351531,56294206205,3735873535339,241600284318365,15423235216318411,978180744322139645},20] (* Harvey P. Dale, Sep 23 2023 *)

for(n=1,25, print1(63^n-6*32^n-15*18^n+30*17^n-10*14^n+120*11^n-120*10^n+30*9^n-270*8^n+360*7^n-120*6^n, ", ")) \\ G. C. Greubel, Oct 06 2017

a(n) = 63^n - 6*32^n - 15*18^n + 30*17^n - 10*14^n + 120*11^n - 120*10^n + 30*9^n - 270*8^n + 360*7^n - 120*6^n.

G.f.: x*(96368590080*x^9 + 27682953984*x^8 - 13185435000*x^7 + 774468980*x^6 + 143028190*x^5 - 19071533*x^4 + 626800*x^3 + 6970*x^2 - 470*x - 1) / ((6*x -1)*(7*x -1)*(8*x -1)*(9*x -1)*(10*x -1)*(11*x -1)*(14*x -1)*(17*x -1)*(18*x -1)*(32*x -1)*(63*x -1)). - Colin Barker, Jul 07 2013

A262307 Array read by antidiagonals: T(m,n) = number of m X n binary matrices with all 1's connected and no zero rows or columns.

Original entry on oeis.org

1, 1, 1, 1, 5, 1, 1, 19, 19, 1, 1, 65, 205, 65, 1, 1, 211, 1795, 1795, 211, 1, 1, 665, 14221, 36317, 14221, 665, 1, 1, 2059, 106819, 636331, 636331, 106819, 2059, 1, 1, 6305, 778765, 10365005, 23679901, 10365005, 778765, 6305, 1

Offset: 1

N. J. A. Sloane, Oct 04 2015

Two 1's are connected if they are in the same row or column. The requirement is for them to form a single connected set.
The number of m X n binary matrices with no zero rows or columns is given by A183109(m, n). If there are multiple components (not connected) then they cannot share either rows or columns. For i < n and j < m there are T(i,j) ways of creating an i X j component that occupies the first row. Its remaining i-1 rows may be on any of the remaining m-1 rows with its j columns on any of the n columns. The m-i rows and n-j columns not used by this component can be any matrix with no zero rows or columns.
T(m,n) is also the number of bipartite connected labeled graphs with parts of size m and n. (See A005333, A227322.)
This is the array a(m,n) in Kreweras (1969). Kreweras describes this as a symmetric triangle read by rows, giving numbers of connected relations.
The companion array b(m,n) (and the first few of its diagonals) in Kreweras (1969) should also be added to the OEIS if they are not already present.

			Table starts:
==========================================================================
m\n| 1    2      3         4           5             6               7
---|----------------------------------------------------------------------
1  | 1    1      1         1           1             1               1 ...
2  | 1    5     19        65         211           665            2059 ...
3  | 1   19    205      1795       14221        106819          778765 ...
4  | 1   65   1795     36317      636331      10365005       162470155 ...
5  | 1  211  14221    636331    23679901     805351531     26175881341 ...
6  | 1  665 106819  10365005   805351531   56294206205   3735873535339 ...
7  | 1 2059 778765 162470155 26175881341 3735873535339 502757743028605 ...
...
As a triangle, this begins:
  1;
  1,    1;
  1,    5,      1;
  1,   19,     19,      1;
  1,   65,    205,     65,      1;
  1,  211,   1795,   1795,    211,      1;
  1,  665,  14221,  36317,  14221,    665,    1;
  1, 2059, 106819, 636331, 636331, 106819, 2059, 1;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..780
G. Kreweras, Inversion des polynômes de Bell bidimensionnels et application au dénombrement des relations binaires connexes, C. R. Acad. Sci. Paris Ser. A-B 268 1969 A577-A579.

Essentially same table as triangle A227322 (where the antidiagonals only go halfway).
Main diagonal is A005333.
Initial diagonals give A001047, A002501, A002502.
Cf. A226658, A123260, A286189, A183109, A048291, A287274.

A183109[n_, m_] := Sum[(-1)^j*Binomial[m, j]*(2^(m-j) - 1)^n, {j, 0, m}];
T[m_, n_] := A183109[m, n] - Sum[T[i, j]*A183109[m - i, n - j] Binomial[m - 1, i - 1]*Binomial[n, j], {i, 1, m - 1}, {j, 1, n - 1}];
Table[T[m - n + 1, n], {m, 1, 9}, {n, 1, m}] // Flatten (* Jean-François Alcover, Oct 08 2017, after Andrew Howroyd *)

G(N)={my(S=matrix(N,N), T=matrix(N,N));
for(m=1,N,for(n=1,N,
S[m,n]=sum(j=0, m, (-1)^j*binomial(m, j)*(2^(m - j) - 1)^n);
T[m,n]=S[m,n]-sum(i=1, m-1, sum(j=1, n-1, T[i,j]*S[m-i,n-j]*binomial(m-1,i-1)*binomial(n,j)));
));T}
G(7) \\ Andrew Howroyd, May 22 2017

T(m,n) = A183109(m,n) - Sum_{i=1..m-1} Sum_{j=1..n-1} T(i,j)*A183109(m-i, n-j)*binomial(m-1,i-1)*binomial(n,j). - Andrew Howroyd, May 22 2017

Revised by N. J. A. Sloane, May 26 2017, to incorporate material from Andrew Howroyd's May 22 2017 submission (formerly A287297), which was essentially identical to this, although giving an alternative description and more information.

A005334 Number of labeled nonseparable (or 2-connected) bicolored graphs with n nodes of the first color and n nodes of the second color.

Original entry on oeis.org

1, 1, 34, 7037, 6317926, 21073662977, 251973418941994, 10878710974408306717, 1727230695707098000548430, 1028983422758641650604161840065, 2342608062302306704492272616530549874, 20683716767972841770515007707311751484424893

Offset: 1

N. J. A. Sloane

nonn

The two color classes are not interchangeable and have separate labels. Nonseparable graphs are also called blocks.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 1..50
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68. (Annotated scanned copy)

Main diagonal of A123301 as an array.

Cf. A005333, A005335, A005336.

Name clarified and more terms added by Andrew Howroyd, Jan 03 2021

A226658 T(n,k)=Number of nXk 0..4 arrays of sums of 2X2 subblocks of some (n+1)X(k+1) binary array.

Original entry on oeis.org

5, 19, 19, 65, 205, 65, 211, 1795, 1795, 211, 665, 14221, 36317, 14221, 665, 2059, 106819, 636331, 636331, 106819, 2059, 6305, 778765, 10365005, 23679901, 10365005, 778765, 6305, 19171, 5581315, 162470155, 805351531, 805351531, 162470155

Offset: 1

R. H. Hardin Jun 14 2013

Table starts
......5.........19...........65............211.............665............2059
.....19........205.........1795..........14221..........106819..........778765
.....65.......1795........36317.........636331........10365005.......162470155
....211......14221.......636331.......23679901.......805351531.....26175881341
....665.....106819.....10365005......805351531.....56294206205...3735873535339
...2059.....778765....162470155....26175881341...3735873535339.502757743028605
...6305....5581315...2495037197...831358677451.241600284318365
..19171...39606541..37898120011.26094426008221
..58025..279447619.572284920845
.175099.1965098125
.527345

			Some solutions for n=3 k=4
..1..1..1..0....0..1..1..1....0..1..1..0....1..0..1..1....1..0..2..3
..3..1..1..2....1..1..2..1....1..2..2..2....1..2..3..2....1..2..2..1
..3..2..2..3....3..1..2..3....2..1..2..3....2..3..2..1....3..3..1..0

R. H. Hardin, Table of n, a(n) for n = 1..71

Diagonal is A005333(n+1)
Staircase diagonal is A123281(n-3)
Column 1 is A001047(n+1)
Column 2 is A002501(n+1)
Column 3 is A002502(n+1)
Column 4 is A093732(n+1)
Column 5 is A093733(n+1)

A377649 Number of edge cuts in the complete bipartite graph K_n,n.

Original entry on oeis.org

1, 11, 307, 29219, 9874531, 12425270531, 60192210392707, 1137427102035774659, 84343238614611474677731, 24650360937055503837110148611, 28488029177253725394061756995395587, 130493124785564166325712467713764904289859, 2373201513573386990964332212910033418138729872611

Offset: 1

Eric W. Weisstein, Nov 03 2024

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Complete Bipartite Graph.
Eric Weisstein's World of Mathematics, Edge Cut.

Cf. A005333, A048291 (edge covers), A379215.

a(n) = 2^(n^2) - A005333(n). - Andrew Howroyd, Dec 18 2024

a(6) onwards from Andrew Howroyd, Dec 18 2024

A227322 Triangle read by rows: T(n, m) for 0 <= m <= n is the number of bipartite connected labeled graphs with parts of size n and m.

Original entry on oeis.org

1, 1, 1, 0, 1, 5, 0, 1, 19, 205, 0, 1, 65, 1795, 36317, 0, 1, 211, 14221, 636331, 23679901, 0, 1, 665, 106819, 10365005, 805351531, 56294206205, 0, 1, 2059, 778765, 162470155, 26175881341, 3735873535339, 502757743028605

Offset: 0

Pavel Irzhavski, Jul 06 2013

			Triangle T(n, m) begins:
n\m 0 1    2      3         4           5             6               7
0   1
1   1 1
2   0 1    5
3   0 1   19    205
4   0 1   65   1795     36317
5   0 1  211  14221    636331    23679901
6   0 1  665 106819  10365005   805351531   56294206205
7   0 1 2059 778765 162470155 26175881341 3735873535339 502757743028605
...
Consider labeled bipartite graph with parts of size 2 and 2. To make graph connected it is possible to use all four possible edges or omit any one of them. Thus T(2, 2) = 5.

F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.

Cf. A226658, A123260.
Main diagonal gives: A005333.
Columns m=2, 3, 4 give: A001047, A002501, A002502.

T(n, m) = 2^(n*m) - sum for all (i, j) in ({1, 2, ..., n} X {1, 2, ..., m} UNION (1, 0)) \ (n, m) \ (1 - n, 0) of T(i, j)*C(n - 1, i - 1)*C(m, j)*2^((n - i)*(m - j)), where C(n, m) is the binomial coefficient (A007318). This relation can be obtained considering connected component which contains the first vertex of the largest part. (If the largest part has zero size we get T(0, 0) = 2^0 - 0 = 1 which is true.)

A092794 Number of connected relations.

Original entry on oeis.org

1, 21, 265, 2733, 25441, 223461, 1895545, 15736413, 128882641, 1046542101, 8451838825, 68020609293, 546227922241, 4380272835141, 35094966838105, 281025802973373, 2249545355064241, 18003091856638581, 144058517372685385, 1152637601335180653

Offset: 1

Goran Kilibarda, Vladeta Jovovic, Apr 15 2004

G. C. Greubel, Table of n, a(n) for n = 1..1000
G. Kilibarda and V. Jovovic, Enumeration of some classes of T_0-hypergraphs, arXiv:1411.4187 [math.CO], 2014.
Index entries for linear recurrences with constant coefficients, signature (17,-92,160).

Cf. A005333, A001047, A002501, A002502, A093732, A093733.

CoefficientList[Series[-x*(4*x + 1)/((4*x - 1)*(5*x - 1)*(8*x - 1)), {x, 0, 50}], x] (* G. C. Greubel, Oct 05 2017 *)

x='x+O('x^50); Vec(x*(4*x+1)/((1-4*x)*(1-5*x)*(1-8*x))) \\ G. C. Greubel, Oct 05 2017

a(n) = 8^n - 3*5^n + 2*4^n.
From Colin Barker, Jul 13 2013: (Start)
a(n) = 17*a(n-1) - 92*a(n-2) + 160*a(n-3).
G.f.: x*(4*x+1) / ((1-4*x)*(1-5*x)*(1-8*x)). (End)

Additional term from Colin Barker, Jul 13 2013

cp's OEIS Frontend

A002501 a(n) = 7^n - 3*4^n + 2*3^n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A002502 Number of connected relations.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A093732 Number of connected relations.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A093733 Number of connected relations.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A262307 Array read by antidiagonals: T(m,n) = number of m X n binary matrices with all 1's connected and no zero rows or columns.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A005334 Number of labeled nonseparable (or 2-connected) bicolored graphs with n nodes of the first color and n nodes of the second color.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A226658 T(n,k)=Number of nXk 0..4 arrays of sums of 2X2 subblocks of some (n+1)X(k+1) binary array.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A377649 Number of edge cuts in the complete bipartite graph K_n,n.

Views

Author

Keywords

Links

A002501 a(n) = 7^n - 34^n + 23^n.