Sergey Kitaev - cp's OEIS frontend

A319492 Number of connected non-3-semi-transitively orientable graphs on n vertices.

0, 1, 25, 929, 54953, 4879508

Offset: 5

Sergey Kitaev, Sep 20 2018

A graph is k-semi-transitively orientable if it admits an acyclic orientation that avoids shortcuts of length k or less. The notion of a k-semi-transitive orientation refines that of a semi-transitive orientation, which is the case of k equal infinity. For n<9, the number of non-3-semi-transitively orientable graphs is precisely the number of non-semi-transitively orientable graphs, which in turn is the same as the number of non-word-representable graphs. For n=9, there are four 3-semi-transitively orientable graphs which are not semi-transitively orientable.

			The wheel graph W_5 is the only connected graph on 6 vertices that is non-3-semi-transitively orientable.

Ozgur Akgun, Ian P. Gent, Sergey Kitaev, Hans Zantema, Solving computational problems in the theory of word-representable graphs, arXiv:1808.01215 [math.CO], 2018.

The first four terms are the same as the terms 5 - 8 in A290814.

A319491 Number of minimal non-word-representable connected graphs on n vertices.

Original entry on oeis.org

0, 1, 10, 47, 179

Offset: 5

Sergey Kitaev, Sep 20 2018

A simple graph G=(V,E) is word-representable if there exists a word w over the alphabet V such that letters x and y alternate in w iff xy is an edge in E. Word-representable graphs generalize several important classes of graphs.

			The wheel graph W_5 is the only minimal connected graph on 6 vertices that is not word-representable.

Ozgur Akgun, Ian P. Gent, Sergey Kitaev, Hans Zantema, Solving computational problems in the theory of word-representable graphs, arXiv:1808.01215 [math.CO], 2018.
Sergey Kitaev, A comprehensive introduction to the theory of word-representable graphs, arXiv:1705.05924 [math.CO], 2017.

All non-word-representable connected graphs are in A290814.

A319490 Number of non-isomorphic connected graphs on n vertices with representation number 3.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 39, 1852, 88838

Offset: 1

Sergey Kitaev, Sep 20 2018

These are graphs that can be represented by words having three copies of each letter, but cannot be represented by words having two copies of each letter. In a word representing a graph G, letters x and y alternate if any only if there is an edge between x and y in G.

			The triangular prism is the only graph on 6 vertices that can be represented using three copies of each letter, but cannot be represented using 2 copies of each letter.

Ozgur Akgun, Ian P. Gent, Sergey Kitaev, Hans Zantema, Solving computational problems in the theory of word-representable graphs, arXiv:1808.01215 [math.CO], 2018.
Sergey Kitaev, A comprehensive introduction to the theory of word-representable graphs, arXiv:1705.05924 [math.CO], 2017.

Cf. A319489 (graphs with representation number 2).

A319489 Number of non-isomorphic connected graphs on n vertices with representation number 2.

Original entry on oeis.org

0, 0, 1, 5, 20, 109, 788, 8335, 117282, 2026330, 40302424, 892278075

Offset: 1

Sergey Kitaev, Sep 20 2018

These are graphs that can be represented by words having two copies of each letter, but cannot be represented by words having one copy of each letter. In a word representing a graph G, letters x and y alternate if and only if there is an edge between x and y in G. Such graphs, along with complete graphs, are precisely the class of circle graphs.

			For n=3 there is one connected graph with vertex set, say, {1,2}, which is represented by 1212.

Ozgur Akgun, Ian P. Gent, Sergey Kitaev, and Hans Zantema, Solving computational problems in the theory of word-representable graphs, arXiv:1808.01215 [math.CO], 2018.
Sergey Kitaev, A comprehensive introduction to the theory of word-representable graphs, arXiv:1705.05924 [math.CO], 2017.

Equals A156808 minus 1; graphs with representation number 3 are in A319490.

A099945 Number of 4 X n binary matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (00;1) and (11;0).

Original entry on oeis.org

188, 404, 836, 1700, 3428, 6884, 13796, 27620, 55268, 110564, 221156, 442340, 884708, 1769444, 3538916, 7077860, 14155748, 28311524, 56623076, 113246180, 226492388, 452984804, 905969636, 1811939300, 3623878628, 7247757284

Offset: 3

Sergey Kitaev, Nov 12 2004

nonn

An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i10 and n>2; for n=2 the number is (m+1)*2^m.

S. Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
Index entries for linear recurrences with constant coefficients, signature (3, -2).

Cf. A000105.

vector(50, n, i=n+2; 27*2^i-28) \\ Michel Marcus, Dec 01 2014

a(n) = 27*2^n-28.

A099944 Number of 3 X n binary matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (00;1) and (11;0).

Original entry on oeis.org

76, 164, 340, 692, 1396, 2804, 5620, 11252, 22516, 45044, 90100, 180212, 360436, 720884, 1441780, 2883572, 5767156, 11534324, 23068660, 46137332, 92274676, 184549364, 369098740, 738197492, 1476394996, 2952790004, 5905580020

Offset: 3

Sergey Kitaev, Nov 12 2004

An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i10 and n>2; for n=2 the number is (m+1)*2^m.

S. Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Cf. A000105.

LinearRecurrence[{3,-2},{76,164},30] (* Harvey P. Dale, Oct 22 2017 *)

vector(50, n, i=n+2; 11*2^i - 12) \\ Michel Marcus, Dec 01 2014

a(n) = 11*2^n - 12.
From Chai Wah Wu, Jun 06 2016: (Start)
a(n) = 3*a(n-1) - 2*a(n-2) for n > 4.
G.f.: 4*x^3*(19 - 16*x)/((1 - x)*(1 - 2*x)). (End)

A099003 Number of 4 X n 0-1 matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (00;1), (10;0) and (11;0).

Original entry on oeis.org

1, 16, 46, 106, 226, 466, 946, 1906, 3826, 7666, 15346, 30706, 61426, 122866, 245746, 491506, 983026, 1966066, 3932146, 7864306, 15728626, 31457266, 62914546, 125829106, 251658226, 503316466, 1006632946, 2013265906, 4026531826

Offset: 0

Sergey Kitaev, Nov 13 2004

An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1 < i2, j1 < j2 and these elements are in the same relative order as those in the triple (x,y,z). In general, the number of m X n 0-1 matrices in question is given by 2^(m+n) - 2^m - 2^n + 2.
Binomial transform of 1,15,15,... (15 infinitely repeated). - Gary W. Adamson, Apr 29 2008
The binomial transform of [1, c, c, c, ...] has the terms a(n) = 1 - c + c*2^(n-1) if the offset 1 is chosen. The o.g.f. of the a(n) is x*(1+(c-2)x)/((2x-1)*(x-1)). This applies to A139634 with c=10, to A139635 with c=11, to A139697 with c=12, to A139698 with c=25 and to A099003, A139700, A139701 accordingly. - R. J. Mathar, May 11 2008

S. Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Cf. A048489 (m=3).

LinearRecurrence[{3,-2},{1,16},40] (* Harvey P. Dale, May 20 2018 *)

a(n) = 15*2^n - 14.

O.g.f.: (1+13x)/((x-1)(2x-1)). - R. J. Mathar, May 06 2008

A100312 Number of 3 X n binary matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (10;0) and (01;1).

Original entry on oeis.org

1, 8, 32, 104, 304, 832, 2176, 5504, 13568, 32768, 77824, 182272, 421888, 966656, 2195456, 4947968, 11075584, 24641536, 54525952, 120061952, 263192576, 574619648, 1249902592, 2709520384, 5855248384, 12616466432, 27111981056, 58116276224, 124285616128

Offset: 0

Sergey Kitaev, Nov 13 2004

An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1 < i2, j1 < j2 and these elements are in the same relative order as those in the triple (x,y,z). In general, the number of m X n 0-1 matrices in question is given by the g.f. 2*x*y/(1-2*(x+y-x*y)).

G. C. Greubel, Table of n, a(n) for n = 0..1000
S. Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
Index entries for linear recurrences with constant coefficients, signature (6,-12,8).

Cf. A049611, this sequence (m=3), A100313 (m=4).

[2^(n-1)*(n^2+5*n+2): n in [0..50]]; // G. C. Greubel, Feb 01 2023

Table[2^(n-1)*(n^2+5*n+2), {n,0,50}] (* G. C. Greubel, Feb 01 2023 *)

vector(50, n, (n^2 + 5*n + 2) * 2^(n-1)) \\ Michel Marcus, Dec 01 2014

[2^(n-1)*(n^2+5*n+2) for n in range(51)] # G. C. Greubel, Feb 01 2023

G.f.: 1 + 8*x*(1-x)^2/(1-2*x)^3.
a(n) = 2^(n-1) * (n^2 + 5*n + 2).
a(n) = 8 * A049611(n) for n>0.
E.g.f.: (1 + 6*x + 2*x^2)*exp(2*x). - G. C. Greubel, Feb 01 2023

a(0)=1 prepended by Alois P. Heinz, Dec 21 2018

A100313 Number of 4 X n binary matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (10;0) and (01;1).

Original entry on oeis.org

1, 16, 96, 400, 1408, 4480, 13312, 37632, 102400, 270336, 696320, 1757184, 4358144, 10649600, 25690112, 61276160, 144703488, 338690048, 786432000, 1812987904, 4152360960, 9453961216, 21407727616, 48234496000, 108179488768, 241591910400, 537407782912

Offset: 0

Sergey Kitaev, Nov 13 2004

An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1 < i2, j1 < j2 and these elements are in the same relative order as those in the triple (x,y,z). In general, the number of m X n 0-1 matrices in question is given by the g.f. 2*x*y/(1-2*(x+y-x*y)).

G. C. Greubel, Table of n, a(n) for n = 0..1000
S. Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
Index entries for linear recurrences with constant coefficients, signature (8,-24,32,-16).

Cf. A055585, A100312 (m=3), this sequence (m=4).

[2^n*n*(n^2+9*n+14)/3 +0^n: n in [0..40]]; // G. C. Greubel, Feb 01 2023

Table[If[n==0, 1, 2^n*n*(n^2+9*n+14)/3], {n,0,40}] (* G. C. Greubel, Feb 01 2023 *)

vector(50, n, n*(n^2+9*n+14) * 2^n / 3) \\ Michel Marcus, Dec 01 2014

[2^n*n*(n^2+9*n+14)/3 +0^n for n in range(41)] # G. C. Greubel, Feb 01 2023

G.f.: 1 + 16*x*(1-x)^2/(1-2*x)^4.
a(n) = (1/3) n*(n^2 + 9*n + 14) * 2^n for n>0, with a(0) = 1.
a(n) = 16 * A055585(n-1) for n>0.
E.g.f.: (1/3)*(3 + 8*x*(6 + 6*x + x^2)*exp(2*x)). - G. C. Greubel, Feb 01 2023

a(0)=1 prepended by Alois P. Heinz, Dec 21 2018

A100314 Number of 2 X n 0-1 matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (00;1), (01;0), (10;0) and (01;1).

Original entry on oeis.org

1, 4, 8, 14, 24, 42, 76, 142, 272, 530, 1044, 2070, 4120, 8218, 16412, 32798, 65568, 131106, 262180, 524326, 1048616, 2097194, 4194348, 8388654, 16777264, 33554482, 67108916, 134217782, 268435512, 536870970, 1073741884, 2147483710, 4294967360, 8589934658

Offset: 0

Sergey Kitaev, Nov 13 2004

An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1 < i2, j1 < j2 and these elements are in the same relative order as those in the triple (x,y,z). In general, the number of m X n 0-1 matrices in question is given by 2^m + 2^n + 2*(n*m-n-m).

Arthur H. Stroud, Approximate calculation of multiple integrals, Prentice-Hall, 1971.

Vincenzo Librandi, Table of n, a(n) for n = 0..2000
Ronald Cools, Encyclopaedia of Cubature Formulas
S. Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Cf. this sequence (m=2), A100315 (m=3), A100316 (m=4).
Cf. A000051, A000079, A001787, A002064, A005126, A005843.
Cf. A052548, A058331, A099003, A132750, A176691.
Row sums of A131830.

List([0..40],n->2^n+2*n); # Muniru A Asiru, Dec 21 2018

[2^n+2*n: n in [1..40]]; // Vincenzo Librandi, Oct 22 2011

a:= proc(n) 2^n + 2*n: end: seq(a(n),n=0..50); # Gary W. Adamson, Jul 20 2007

LinearRecurrence[{4,-5,2}, {1,4,8}, 34] (* Jean-François Alcover, Mar 19 2020 *)

makelist(2^n + 2*n, n, 0, 50); /* Franck Maminirina Ramaharo, Dec 19 2018 */

[2^n +2*n for n in range(41)] # G. C. Greubel, Feb 01 2023

a(n) = 2^n + 2*n.
From Gary W. Adamson, Jul 20 2007: (Start)
Binomial transform of (1, 3, 1, 1, 1, ...).
For n > 0, a(n) = 2*A005126(n-1). (End)
From R. J. Mathar, Jun 13 2008: (Start)
G.f.: 1 + 2*x*(2 -4*x +x^2)/((1-x)^2*(1-2*x)).
a(n+1)-a(n) = A052548(n). (End)
From Colin Barker, Oct 16 2013: (Start)
a(n) = 4*a(n-1) - 5*a(n-2) + 2*a(n-3).
G.f.: (1 - 3*x^2)/((1-x)^2*(1-2*x)). (End)
E.g.f.: exp(2*x) + 2*x*exp(x). - Franck Maminirina Ramaharo, Dec 19 2018
a(n) = A000079(n) + A005843(n). - Muniru A Asiru, Dec 21 2018

a(0)=1 prepended by Alois P. Heinz, Dec 21 2018

cp's OEIS Frontend

User: Sergey Kitaev

A319492 Number of connected non-3-semi-transitively orientable graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A319491 Number of minimal non-word-representable connected graphs on n vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A319490 Number of non-isomorphic connected graphs on n vertices with representation number 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A319489 Number of non-isomorphic connected graphs on n vertices with representation number 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A099945 Number of 4 X n binary matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (00;1) and (11;0).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A099944 Number of 3 X n binary matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (00;1) and (11;0).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A099003 Number of 4 X n 0-1 matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (00;1), (10;0) and (11;0).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A100312 Number of 3 X n binary matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (10;0) and (01;1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

SageMath

Formula

Extensions

A100313 Number of 4 X n binary matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (10;0) and (01;1).