A262307 -id:A262307 - cp's OEIS frontend

A001047 a(n) = 3^n - 2^n.

0, 1, 5, 19, 65, 211, 665, 2059, 6305, 19171, 58025, 175099, 527345, 1586131, 4766585, 14316139, 42981185, 129009091, 387158345, 1161737179, 3485735825, 10458256051, 31376865305, 94134790219, 282412759265, 847255055011, 2541798719465, 7625463267259, 22876524019505

Offset: 0

N. J. A. Sloane, R. K. Guy

a(n+1) is the sum of the elements in the n-th row of triangle pertaining to A036561. - Amarnath Murthy, Jan 02 2002
Number of 2 X n binary arrays with a path of adjacent 1's and no path of adjacent 0's from top row to bottom row. - R. H. Hardin, Mar 21 2002
With offset 1, partial sums of A027649. - Paul Barry, Jun 24 2003
Number of distinct lines through the origin in the n-dimensional lattice of side length 2. A049691 has the values for the 2-dimensional lattice of side length n. - Joshua Zucker, Nov 19 2003
a(n+1)/(n+1)=(3*3^n-2*2^n)/(n+1) is the second binomial transform of the harmonic sequence 1/(n+1). - Paul Barry, Apr 19 2005
a(n+1) is the sum of n-th row of A036561. - Reinhard Zumkeller, May 14 2006
The sequence gives the sum of the lengths of the segments in Cantor's dust generating sequence up to the i-th step. Measurement unit = length of the segment of i-th step. - Giorgio Balzarotti, Nov 18 2006
Let T be a binary relation on the power set P(A) of a set A having n = |A| elements such that for every element x, y of P(A), xTy if x is a proper subset of y. Then a(n) = |T|. - Ross La Haye, Dec 22 2006
From Alexander Adamchuk, Jan 04 2007: (Start)
a(n) is prime for n in A057468.
p divides a(p) - 1 for prime p.
Quotients (3^p - 2^p - 1)/p, where p = prime(n), are listed in A127071.
Numbers k such that k divides 3^k - 2^k - 1 are listed in A127072.
Pseudoprimes in A127072(n) include all powers of primes {2,3,7} and some composite numbers that are listed in A127073, which includes all Carmichael numbers A002997.
Numbers n such that n^2 divides 3^n - 2^n - 1 are listed in A127074.
5 divides a(2n).
5^2 divides a(2*5n).
5^3 divides a(2*5^2n).
5^4 divides a(2*5^3n).
7^2 divides a(6*7n).
13 divides a(4n).
13^2 divides a(4*13n).
19 divides a(3n).
19^2 divides a(3*19n).
23^2 divides a(11n).
23^3 divides a(11*23n).
23^4 divides a(11*23^2n).
29 divides a(7n).
p divides a((p-1)n) for prime p>3.
p divides a((p-1)/2) for prime p in A097934. Also primes p such that 6 is a square mod p, except {2,3}, A038876(n).
p^(k+1) divides a(p^k*(p-1)/2*n) for prime p in A097934.
p^(k+1) divides a(p^k*(p-1)*n) for prime p>3.
Note the exception that for p = 23, p^(k+2) divides a(p^k*(p-1)/2*n).
There are no more such exceptions for primes p up to 600000. (End)
a(n) divides a(q*(n+1)-1), for all q integer. Leonardo Sarasua, Apr 15 2024
Final digits of terms follow sequence 1,5,9,5. - Enoch Haga, Nov 26 2007
This is also the second column sequence of the Sheffer triangle A143494 (2-restricted Stirling2 numbers). See the e.g.f. given below. - Wolfdieter Lang, Oct 08 2011
Partial sums give A000392. - Jon Perry, Apr 05 2014
For n >= 1, this is also row 2 of A281890: when consecutive positive integers are written as a product of primes in nondecreasing order, "3" occurs in n-th position a(n) times out of every 6^n. - Peter Munn, May 17 2017
a(n) is the number of ternary sequences of length n which include the digit 2. For example, a(2)=5 since the sequences are 02,20,12,21,22. - Enrique Navarrete, Apr 05 2021
a(n-1) is the number of ways we can form disjoint unions of two nonempty subsets of [n] such that the union contains n. For example, for n = 3, a(2) = 5 since the  disjoint unions are {1}U{3}, {1}U{2,3}, {2}U{3}, {2}U{1,3}, and {1,2}U{3}. Cf. A000392 if we drop the requirement that the union contains n. - Enrique Navarrete, Aug 24 2021
Configures as a composite Koch Snowflake Fractal (see illustration in links) based on the five-fold division of the Cantor Square/Cantor Dust Fractal of (9^n-4^n)/5 see my illustration in (A016153). - John Elias, Oct 13 2021
Number of pairs (A,B) where B is a subset of {1,2,...,n} and A is a proper subset of B. - Jianing Song, Jun 18 2022
From Manfred Boergens, Mar 29 2023: (Start)
With regard to the comments by Ross La Haye and Jianing Song: Omitting "proper" gives A000244.
Number of pairs (A,B) where B is a nonempty subset of {1,2,...,n} and A is a nonempty subset of B. For nonempty proper subsets see a(n+1) in A028243. (End)
a(n) is the number of n-digit numbers whose smallest decimal digit is 7. - Stefano Spezia, Nov 15 2023
a(n-1) is the number of all possible player-reduced binary games observed by each player in an nx2 game assuming the individual strategies of k < n - 1 players are fixed and the remaining n - k - 1 player will play as one, either maintaining their status quo strategies or jointly adopting an alternative strategy. - Ambrosio Valencia-Romero, Apr 11 2024

John H. Conway and Richard K. Guy, The Book of Numbers, New York: Springer-Verlag, 1996. See pp. 86-87.
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=0..200
A. Abdurrahman, CM Method and Expansion of Numbers, arXiv:1909.10889 [math.NT], 2019.
Nathan Bliss, Ben Fulan, Stephen Lovett and Jeff Sommars, Strong divisibility, cyclotomic polynomials and iterated polynomials, Am. Math. Monthly, Vol. 120, No. 6 (2013), pp. 519-536.
John Elias, Illustration: Sierpinski half-hexagons, Illustration: Nicomachus triangle 2^n & 3^n correlation, Koch Snowflake Fractal Configuration.
Joël Gay, Representation of Monoids and Lattice Structures in the Combinatorics of Weyl Groups, Doctoral Thesis, Discrete Mathematics [cs.DM], Université Paris-Saclay, 2018.
Samuele Giraudo, Combinatorial operads from monoids, Journal of Algebraic Combinatorics, Vol. 41, No. 2 (2015), pp. 493-538; arXiv preprint, arXiv preprint arXiv:1306.6938 [math.CO], 2013-2015.
Samuele Giraudo, Pluriassociative algebras I: The pluriassociative operad, Advances in Applied Mathematics, Vol. 77 (2016), pp. 1-42; arXiv preprint, arXiv:1603.01040 [math.CO], 2016.
Richard K. Guy, Letters to N. J. A. Sloane, June-August 1968
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 397.
B. D. Josephson and J. M. Boardman, Problems Drive 1961, Eureka, The Journal of the Archimedeans, Vol. 24 (1961), p. 20; entire volume.
Germain 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, Vol. 268 (1969), pp. A577-A579.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
Richard Miles, Synchronization points and associated dynamical invariants, Trans. Amer. Math. Soc., Vol. 365, No. 10 (2013), pp. 5503-5524.
Rajesh Kumar Mohapatra and Tzung-Pei Hong, On the Number of Finite Fuzzy Subsets with Analysis of Integer Sequences, Mathematics (2022) Vol. 10, No. 7, 1161.
Jon Perry, Relation to Collatz problem.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Kalika Prasad, Munesh Kumari, Rabiranjan Mohanta, and Hrishikesh Mahato, The sequence of higher order Mersenne numbers and associated binomial transforms, arXiv:2307.08073 [math.NT], 2023.
D. C. Santos, E. A. Costa, and P. M. M. C. Catarino, On Gersenne Sequence: A Study of One Family in the Horadam-Type Sequence, Axioms 14, 203, (2025). See p. 4.
Ambrosio Valencia-Romero and P. T. Grogan, The strategy dynamics of collective systems: Underlying hindrances beyond two-actor coordination, PLOS ONE 19(4): e0301394 (S1 Appendix).
Index entries for linear recurrences with constant coefficients, signature (5,-6).

Cf. A000225, A016189, A036561, A097934, A038876, A127071, A127072, A127073, A127074, A002997, A057468, A109235, A281890, A329064, A350771.
a(n) = row sums of A091913, row 2 of A047969, column 1 of A090888 and column 1 of A038719.
Cf. A000392, A240400, A000244, A028243.
Cf. partitions: A241766, A241759.
A diagonal of A262307.

a001047 n = a001047_list !! n
a001047_list = map fst $ iterate (\(u, v) -> (3 * u + v, 2 * v)) (0, 1)
-- Reinhard Zumkeller, Jun 09 2013

[3^n - 2^n: n in [0..30]]; // Vincenzo Librandi, Jul 17 2011

seq(3^n - 2^n, n=0..40); # Giorgio Balzarotti, Nov 18 2006
A001047:=1/(3*z-1)/(2*z-1); # Simon Plouffe in his 1992 dissertation, dropping the initial zero

Table[ 3^n - 2^n, {n, 0, 25} ]
LinearRecurrence[{5, -6}, {0, 1}, 25] (* Harvey P. Dale, Aug 18 2011 *)
Numerator@NestList[(3#+1)/2&,1/2,100] (* Zak Seidov, Oct 03 2011 *)

PARI
```
{a(n) = 3^n - 2^n};
```

[3**n - 2**n for n in range(25)] # Ross La Haye, Aug 19 2005; corrected by David Radcliffe, Jun 26 2016

[lucas_number1(n, 5, 6) for n in range(26)]  # Zerinvary Lajos, Apr 22 2009

G.f.: x/((1-2*x)*(1-3*x)).
a(n) = 5*a(n-1) - 6*a(n-2).
a(n) = 3*a(n-1) + 2^(n-1). - Jon Perry, Aug 23 2002
Starting 0, 0, 1, 5, 19, ... this is 3^n/3 - 2^n/2 + 0^n/6, the binomial transform of A086218. - Paul Barry, Aug 18 2003
a(n) = A083323(n)-1 = A056182(n)/2 = (A002783(n)-1)/2 = (A003063(n+2)-A003063(n+1))/2. - Ralf Stephan, Jan 12 2004
Binomial transform of A000225. - Ross La Haye, Feb 07 2005
a(n) = Sum_{k=0..n-1} binomial(n, k)*2^k. - Ross La Haye, Aug 20 2005
a(n) = 2^(2n) - A083324(n). - Ross La Haye, Sep 10 2005
a(n) = A112626(n, 1). - Ross La Haye, Jan 11 2006
E.g.f.: exp(3*x) - exp(2*x). - Mohammad K. Azarian, Jan 14 2009
a(n) = A217764(n,1). - Ross La Haye, Mar 27 2013
a(n) = 2*a(n-1) + 3^(n-1). - Toby Gottfried, Mar 28 2013
a(n) = A000244(n) - A000079(n). - Omar E. Pol, Mar 28 2013
a(n) = Sum_{k=0..2} Stirling1(2,k)*(k+1)^n = c_2^{(-n)}, poly-Cauchy numbers. - Takao Komatsu, Mar 28 2013
a(n) = A227048(n,A098294(n)). - Reinhard Zumkeller, Jun 30 2013
a(n+1) = Sum_{k=0..n} 2^k*3^(n-k). - J. M. Bergot, Mar 27 2018
Sum_{n>=1} 1/a(n) = A329064. - Amiram Eldar, Nov 20 2020
a(n) = (1/2)*Sum_{k=0..n} binomial(n, k)*(2^(n-k) + 2^k - 2).
a(n) = A001117(n) + 2*A000918(n) + 1. - Ambrosio Valencia-Romero, Mar 08 2022
a(n) = A000225(n) + A028243(n+1). - Ambrosio Valencia-Romero, Mar 09 2022
From Peter Bala, Jun 27 2025: (Start)
exp(Sum_{n >=1} a(2*n)/a(n)*x^n/n) = Sum_{n >= 0} a(n+1)*x^n.
exp(Sum_{n >=1} a(3*n)/a(n)*x^n/n) = 1 + 19*x + 247*x^2 + ... is the g.f. of A019443.
exp(Sum_{n >=1} a(4*n)/a(n)*x^n/n) = 1 + 65*x + 2743*x^2 + ... is the g.f. of A383754.
The following are all examples of telescoping series:
Sum_{n >= 1} 6^n/(a(n)*a(n+1)) = 2, since 6^n/(a(n)*a(n+1)) = b(n) - b(n+1), where b(n) = 2^n/a(n);
Sum_{n >= 1} 18^n/(a(n)*a(n+1)*a(n+2)) = 22/75, since 18^n/(a(n)*a(n+1)*a(n+2)) = c(n) - c(n+1), where c(n) = (5*6^n - 2*4^n)/(15*a(n)*a(n+1));
Sum_{n >= 1} 54^n/(a(n)*a(n+1)*a(n+2)*a(n+3)) = 634/48735 since 54^n/(a(n)*a(n+1)*a(n+2)*a(n+3)) = d(n) - d(n+1), where d(n) = (57*18^n - 38*12^n + 8*8^n)/(513*a(n)*a(n+1)*a(n+2)).
Sum_{n >= 1} 6^n/(a(n)*a(n+2)) = 14/25; Sum_{n >= 1} (-6)^n/(a(n)*a(n+2)) = -6/25.
Sum_{n >= 1} 6^n/(a(n)*a(n+3)) = 306/1805.
Sum_{n >= 1} 6^n/(a(n)*a(n+4)) = 4282/80275; Sum_{n >= 1} (-6)^n/(a(n)*a(n+4)) = -1698/80275. (End)

Edited by Charles R Greathouse IV, Mar 24 2010

A286189 Number of connected induced (non-null) subgraphs of the n X n rook graph.

Original entry on oeis.org

1, 13, 397, 55933, 31450861, 67253507293, 559182556492477, 18408476382988290493, 2416307646576708948065581, 1267404418454077249779938768413, 2658301080374793666228695738368407037, 22300360304310794054520197736231374212892413

Offset: 1

Giovanni Resta, May 04 2017

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Rook Graph
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph

Main diagonal of A360873.
Cf. A262307, A183109.
Cf. A020873 (wheel), A059020 (ladder), A059525 (grid), A286139 (king), A286182 (prism), A286183 (antiprism), A286184 (helm), A286185 (Möbius ladder), A286186 (friendship), A286187 (web), A286188 (gear), A285765 (queen).

{1} ~ Join ~ Table[g = GraphData[{"Rook", {n,n}}]; -1 + ParallelSum[ Boole@ ConnectedGraphQ@ Subgraph[g, s], {s, Subsets@ Range[n^2]}], {n, 2, 4}]
(* Second program: *)
(* b = A183109, T = A262307 *)
b[n_, m_] := Sum[(-1)^j*Binomial[m, j]*(2^(m - j) - 1)^n, {j, 0, m}];
T[m_, n_] := T[m, n] = b[m, n] - Sum[T[i, j]*b[m - i, n - j] Binomial[m - 1, i - 1]*Binomial[n, j], {i, 1, m - 1}, {j, 1, n - 1}];
a[n_] := Sum[Binomial[n, i]*Binomial[n, j]*T[i, j], {i, 1, n}, {j, 1, n}];
Array[a, 12] (* Jean-François Alcover, Oct 11 2017, after Andrew Howroyd *)

G(N)={my(S=matrix(N,N), T=matrix(N,N), U=matrix(N,N));
\\ S is A183109, T is A262307, U is mxn variant of this sequence.
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)));
U[m,n]=sum(i=1,m,sum(j=1,n,binomial(m,i)*binomial(n,j)*T[i,j])) ));U}
a(n)=G(n)[n,n]; \\ Andrew Howroyd, May 22 2017

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

a(n) ~ 2^(n^2). - Vaclav Kotesovec, Oct 12 2017

Terms a(7) and beyond from Andrew Howroyd, May 22 2017

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

Original entry on oeis.org

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

A005333 Number of 2-colored connected labeled graphs with n vertices of the first color and n vertices of the second color.

Original entry on oeis.org

1, 5, 205, 36317, 23679901, 56294206205, 502757743028605, 17309316971673776957, 2333508400614646874734621, 1243000239291173897659593056765, 2629967962392578020413552363565293565, 22170252073745058975210005804934596601690557

Offset: 1

N. J. A. Sloane

nonn

Conjecture: if n > 1, then a(n) is the number of labeled digraphs D (allowing self-loops) with n vertices such that D|D' and D'|D are (strongly) connected (see preliminaries of Broere et al.). - Lorenzo Sauras Altuzarra, Sep 17 2022

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
I. Broere, W. Imrich, R. Kalinowski, and M. Pilsniak, Asymmetric colorings of products of graphs and digraphs, Discrete Applied Mathematics 266 (p. 56-64), 2019.
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 A262307 and A227322.

c[0, 1] = c[1, 0] = 1; c[0, ] = c[, 0] = 0; c[n_, m_] := c[n, m] = 2^(n*m) - Sum[If[k < n || j < m, Binomial[n - 1, k - 1]*Binomial[m, j]* 2^((n - k)*(m - j))*c[k, j], 0], {k, 1, n}, {j, 0, m}];
a[n_] := c[n, n];
Array[a, 12] (* Jean-François Alcover, Sep 03 2019 *)

a(n) = c(n,n) where c(0,1) = 1, c(0,m) = 0, c(n,m) = 2^(n*m) - Sum_{1 <= k <= n, 0 <= j <= m, k < n or j < m} C(n-1, k-1) * C(m, j) * 2^((n-k)*(m-j)) * c(k, j). - Sean A. Irvine, May 11 2016

More precise definition by Pavel Irzhavski, Jul 09 2013

More terms from Sean A. Irvine, May 11 2016

A360873 Array read by antidiagonals: T(m,n) is the number of (non-null) connected induced subgraphs in the rook graph K_m X K_n.

Original entry on oeis.org

1, 3, 3, 7, 13, 7, 15, 51, 51, 15, 31, 205, 397, 205, 31, 63, 843, 3303, 3303, 843, 63, 127, 3493, 27877, 55933, 27877, 3493, 127, 255, 14451, 233751, 943095, 943095, 233751, 14451, 255, 511, 59485, 1938517, 15678925, 31450861, 15678925, 1938517, 59485, 511

Offset: 1

Andrew Howroyd, Feb 24 2023

			Array begins:
=======================================================
m\n|  1    2      3        4          5           6 ...
---+---------------------------------------------------
1  |  1    3      7       15         31          63 ...
2  |  3   13     51      205        843        3493 ...
3  |  7   51    397     3303      27877      233751 ...
4  | 15  205   3303    55933     943095    15678925 ...
5  | 31  843  27877   943095   31450861  1033355223 ...
6  | 63 3493 233751 15678925 1033355223 67253507293 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals).
Eric Weisstein's World of Mathematics, Rook Graph.
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph.

Main diagonal is A286189.
Rows 1..2 are A000225, A360874.
Cf. A360850, A360851, A360853, A360875.

\\ S is A183109, T is A262307, U is this sequence.
G(M,N=M)={ my(S=matrix(M, N), T=matrix(M, N), U=matrix(M, N));
for(m=1, M, 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)));
  U[m, n]=sum(i=1, m, sum(j=1, n, binomial(m, i)*binomial(n, j)*T[i, j])) )); U
}
{ my(A=G(7)); for(n=1, #A~, print(A[n,])) }

T(m,n) = Sum_{i=1..m} Sum_{j=1..n} binomial(m, i) * binomial(n, j) * A262307(i, j).

T(m,n) = T(n,m).

A123260 Triangle read by rows: T(n,k) = number of specially labeled bicolored connected graphs with k points in one color class and n-k points in the other class . "Special" means there are separate labels 1,2, ...,k and 1,2, ...,n-k for the two color classes (n >= 1, k = floor((n+1)/2), ..., n).

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Nov 12 2006

			The first few entries are:
T( 1, 0) = 1
T( 1, 1) = 1
T( 2, 0) = 0
T( 2, 1) = 1
T( 3, 0) = 0
T( 2, 2) = 5
T( 3, 1) = 1
T( 4, 0) = 0
T( 3, 2) = 19
T( 4, 1) = 1
T( 5, 0) = 0
T( 3, 3) = 205
T( 4, 2) = 65
T( 5, 1) = 1
T( 6, 0) = 0
1, 1;
0, 1, 5 ;
0, 1, 19, 205;
0, 1, 65, 1795, 36317;
0, 1, 211, 14221, ,...
0, 1, ....
0,

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.

R. W. Robinson, Rows 1 through 30, flattened

Leading diagonal gives A123281. Cf. A262307.

A360875 Array read by antidiagonals: T(m,n) is the number of connected dominating sets in the rook graph K_m X K_n.

Original entry on oeis.org

1, 3, 3, 7, 9, 7, 15, 39, 39, 15, 31, 177, 325, 177, 31, 63, 783, 2931, 2931, 783, 63, 127, 3369, 26077, 51465, 26077, 3369, 127, 255, 14199, 225459, 894675, 894675, 225459, 14199, 255, 511, 58977, 1901725, 15195897, 30331861, 15195897, 1901725, 58977, 511

Offset: 1

Andrew Howroyd, Feb 24 2023

			Array begins:
=======================================================
m\n|  1    2      3        4          5           6 ...
---+---------------------------------------------------
1  |  1    3      7       15         31          63 ...
2  |  3    9     39      177        783        3369 ...
3  |  7   39    325     2931      26077      225459 ...
4  | 15  177   2931    51465     894675    15195897 ...
5  | 31  783  26077   894675   30331861  1010163363 ...
6  | 63 3369 225459 15195897 1010163363 66273667449 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals).
Eric Weisstein's World of Mathematics, Connected Dominating Set
Eric Weisstein's World of Mathematics, Rook Graph

Main diagonal is A289196.
Rows 1..2 are A000225, A360876.
Cf. A287274, A360873.

\\ S is A183109, T is A262307, U is this sequence.
G(M,N=M)={S=matrix(M, N); T=matrix(M, N); U=matrix(M, N);
for(m=1, M, 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)));
  U[m, n]=sum(i=1, m, binomial(m, i)*T[i, n])+sum(j=1, n, binomial(n, j)*T[m, j])-T[m, n] )); U
}
{ my(A=G(7)); for(n=1, #A~, print(A[n,])) }

T(m,n) = (Sum_{i=1..m} binomial(m,i) * A262307(n,i)) + (Sum_{j=1..n} binomial(n,j) * A262307(m,j)) - A262307(m,n).

T(m,n) = T(n,m).

A123301 Triangle read by rows: T(n,k) is the number of specially labeled bicolored nonseparable graphs with k points in one color class and n-k points in the other class. "Special" means there are separate labels 1,2,...,k and 1,2,...,n-k for the two color classes (n >= 2, k = 1,...,n-1).

Original entry on oeis.org

1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 34, 1, 0, 0, 1, 199, 199, 1, 0, 0, 1, 916, 7037, 916, 1, 0, 0, 1, 3889, 117071, 117071, 3889, 1, 0, 0, 1, 15982, 1535601, 6317926, 1535601, 15982, 1, 0, 0, 1, 64747, 18271947, 228842801, 228842801, 18271947

Offset: 2

N. J. A. Sloane, Nov 12 2006

			Triangle begins:
  1;
  0, 0;
  0, 1,    0;
  0, 1,    1,      0;
  0, 1,   34,      1,      0;
  0, 1,  199,    199,      1,    0;
  0, 1,  916,   7037,    916,    1, 0;
  0, 1, 3889, 117071, 117071, 3889, 1, 0;
  ...
Formatted as an array:
=================================================
k/j | 1 2    3       4         5           6
--- +-------------------------------------------
  1 | 1 0    0       0         0           0 ...
  2 | 0 1    1       1         1           1 ...
  3 | 0 1   34     199       916        3889 ...
  4 | 0 1  199    7037    117071     1535601 ...
  5 | 0 1  916  117071   6317926   228842801 ...
  6 | 0 1 3889 1535601 228842801 21073662977 ...
  ...

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.

Andrew Howroyd, Table of n, a(n) for n = 2..1276 (first 50 rows; first 24 rows from R. W. Robinson)
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.

Central coefficients are A005334.

Cf. A004100, A123474, A262307.

G(n)={sum(i=0, n, x^i*(sum(j=0, n, y^j*2^(i*j)/(i!*j!)) + O(y*y^n))) + O(x*x^n)}
\\ this switches x/y halfway through because PARI only does serreverse in x.
B(n)={my(p=log(G(n))); p=subst(deriv(p,y), x, serreverse(x*deriv(p,x))); p=substvec(p, [x,y], [y,x]); intformal(log(x/serreverse(x*p)))}
M(n)={my(p=B(n)); matrix(n,n,i,j,polcoef(polcoef(p,j),i)*i!*j!)}
{ my(A=M(6)); for(n=1, #A~, print(A[n,])) } \\ Andrew Howroyd, Jan 04 2021

A004100(n) = (1/2) * Sum_{k=1..n-1} binomial(n,k)*T(n,k). - Andrew Howroyd, Jan 03 2021

Offset corrected by Andrew Howroyd, Jan 04 2021

A123474 Triangle read by rows: T(n,k) = number of labeled bicolored nonseparable graphs with k points in one color class and n-k points in the other class. The classes are interchangeable if k = n-k. Here n >= 2, k=1..n-1.

Original entry on oeis.org

1, 0, 0, 0, 3, 0, 0, 10, 10, 0, 0, 15, 340, 15, 0, 0, 21, 6965, 6965, 21, 0, 0, 28, 51296, 246295, 51296, 28, 0, 0, 36, 326676, 14750946, 14750946, 326676, 36, 0, 0, 45, 1917840, 322476210, 796058676, 322476210, 1917840, 45, 0, 0, 55, 10683255

Offset: 2

N. J. A. Sloane, Nov 12 2006

			Triangle begins:
  1;
  0,  0;
  0,  3,     0;
  0, 10,    10,      0;
  0, 15,   340,     15,     0;
  0, 21,  6965,   6965,    21,  0;
  0, 28, 51296, 246295, 51296, 28, 0;
  ...
Formatted as an array:
==========================================================
m/n | 1  2       3        4            5             6
----+-----------------------------------------------------
  1 | 1  0      0         0            0             0 ...
  2 | 0  3     10        15           21            28 ...
  3 | 0 10    340      6965        51296        326676 ...
  4 | 0 15   6965    246295     14750946     322476210 ...
  5 | 0 21  51296  14750946    796058676  105725374062 ...
  6 | 0 28 326676 322476210 105725374062 9736032295374 ...
  ...

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1977.

Andrew Howroyd, Table of n, a(n) for n = 2..1276 (first 50 rows; first 24 rows from R. W. Robinson)
F. Harary and R. W. Robinson, Labeled bipartite blocks, Canad. J. Math., 31 (1979), 60-68.

Central coefficients are A005335.

Cf. A004100, A123301, A262307.

From Andrew Howroyd, Jan 03 2021: (Start)
T(n,k) = f(n-2*k) * binomial(n,k) * A123301(n, k) where f(0) = 1/2 and 1 otherwise.
A004100(n) = Sum_{k=0..floor(n/2)} T(n,k). (End)

cp's OEIS Frontend

A001047 a(n) = 3^n - 2^n.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

Extensions

A286189 Number of connected induced (non-null) subgraphs of the n X n rook graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

A005333 Number of 2-colored connected labeled graphs with n vertices of the first color and n vertices of the second color.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A360873 Array read by antidiagonals: T(m,n) is the number of (non-null) connected induced subgraphs in the rook graph K_m X K_n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A123260 Triangle read by rows: T(n,k) = number of specially labeled bicolored connected graphs with k points in one color class and n-k points in the other class . "Special" means there are separate labels 1,2, ...,k and 1,2, ...,n-k for the two color classes (n >= 1, k = floor((n+1)/2), ..., n).

Views

Author

Keywords

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