A140517 -id:A140517 - cp's OEIS frontend

A231829 Square array read by antidiagonals: T(m,n) = number of ways of creating a closed, simple loop on an m X n rectangular lattice.

1, 3, 3, 6, 13, 6, 10, 40, 40, 10, 15, 108, 213, 108, 15, 21, 275, 1049, 1049, 275, 21, 28, 681, 5034, 9349, 5034, 681, 28, 36, 1664, 23984, 80626, 80626, 23984, 1664, 36, 45, 4040, 114069, 692194, 1222363, 692194, 114069, 4040, 45

Offset: 1

Douglas Boffey, Nov 14 2013

This sequence is read in a table, thus:
    m ->
    1,  3,  6, 10, …
n   3, 13, 40, …
|   6, 40, …
v  10, …
    …
This sequence gives the number of closed, simple loops on a rectangular lattice of dots, where the edges of the loop can be horizontal or vertical.
This is also the number of solutions to an unclued slitherlink puzzle.
Main diagonal is A140517. - Joerg Arndt, Sep 01 2014
Equivalently, the number of cycles in the grid graph P_{m+1} X P_{n+1}. - Andrew Howroyd, Jun 12 2017

			Table starts:
=================================================================
m\n|  1    2      3       4         5           6            7
---|-------------------------------------------------------------
1  |  1    3      6      10        15          21           28...
2  |  3   13     40     108       275         681         1664...
3  |  6   40    213    1049      5034       23984       114069...
4  | 10  108   1049    9349     80626      692194      5948291...
5  | 15  275   5034   80626   1222363    18438929    279285399...
6  | 21  681  23984  692194  18438929   487150371  12947640143...
7  | 28 1664 114069 5948291 279285399 12947640143 603841648931...
... - _Andrew Howroyd_, Jun 12 2017
a(2,2) = 13, thus:
1)        2)        3)        4)        5)
+-+ +     + +-+     + + +     + + +     +-+ +
| |         | |                         | |
+-+ +     + +-+     +-+ +     + +-+     + + +
                    | |         | |     | |
+ + +     + + +     +-+ +     + +-+     +-+ +
6)        7)        8)        9)        10)
+ +-+     +-+-+     + + +     +-+ +     + +-+
  | |     |   |               | |         | |
+ + +     +-+-+     +-+-+     + +-+     +-+ +
  | |               |   |     |   |     |   |
+ +-+     + + +     +-+-+     +-+-+     +-+-+
11)       12)       13)
+-+-+     +-+-+     +-+-+
|   |     |   |     |   |
+-+ +     + +-+     + + +
  | |     | |       |   |
+ +-+     +-+ +     +-+-+

Douglas Boffey and Andrew Howroyd, Table of n, a(n) for n = 1..325 (terms 1..70 from Douglas Boffey)
Wikipedia, Slitherlink

Rows 2..10 are A059020, A288637, A339117, A339118, A339119, A339120, A339121, A358707, A358785.
Main diagonal is A140517.
Cf. A288518, A003763, A222202.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A231829(n, k):
    universe = tl.grid(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
print([A231829(j + 1, i - j + 1) for i in range(9) for j in range(i + 1)])  # Seiichi Manyama, Nov 24 2020

A333466 Number of self-avoiding closed paths on an n X n grid which pass through four corners ((0,0), (0,n-1), (n-1,n-1), (n-1,0)).

Original entry on oeis.org

1, 1, 11, 373, 44930, 17720400, 22013629316, 84579095455492

Offset: 2

Seiichi Manyama, Mar 22 2020

a(11) = 36061721109572407840288. - Seiichi Manyama, Apr 07 2020

			a(2) = 1;
   +--+
   |  |
   +--+
a(3) = 1;
   +--*--+
   |     |
   *     *
   |     |
   +--*--+
a(4) = 11;
   +--*--*--+   +--*--*--+   +--*--*--+
   |        |   |        |   |        |
   *--*--*  *   *--*  *--*   *--*     *
         |  |      |  |         |     |
   *--*--*  *   *--*  *--*   *--*     *
   |        |   |        |   |        |
   +--*--*--+   +--*--*--+   +--*--*--+
   +--*--*--+   +--*--*--+   +--*--*--+
   |        |   |        |   |        |
   *  *--*--*   *  *--*  *   *     *--*
   |  |         |  |  |  |   |     |
   *  *--*--*   *  *  *  *   *     *--*
   |        |   |  |  |  |   |        |
   +--*--*--+   +--*  *--+   +--*--*--+
   +--*--*--+   +--*--*--+   +--*  *--+
   |        |   |        |   |  |  |  |
   *        *   *        *   *  *--*  *
   |        |   |        |   |        |
   *  *--*  *   *        *   *  *--*  *
   |  |  |  |   |        |   |  |  |  |
   +--*  *--+   +--*--*--+   +--*  *--+
   +--*  *--+   +--*  *--+
   |  |  |  |   |  |  |  |
   *  *--*  *   *  *  *  *
   |        |   |  |  |  |
   *        *   *  *--*  *
   |        |   |        |
   +--*--*--+   +--*--*--+

Main diagonal of A333513.

Cf. A003763, A140517, A333246, A333247, A333323.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333466(n):
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    for i in [1, n, n * (n - 1) + 1, n * n]:
        cycles = cycles.including(i)
    return cycles.len()
print([A333466(n) for n in range(2, 10)])

def search(x, y, n, used)
  return 0 if x < 0 || n <= x || y < 0 || n <= y || used[x + y * n]
  return 1 if x == 0 && y == 1 && [n - 1, n * (n - 1), n * n - 1].all?{|i| used[i] == true}
  cnt = 0
  used[x + y * n] = true
  @move.each{|mo|
    cnt += search(x + mo[0], y + mo[1], n, used)
  }
  used[x + y * n] = false
  cnt
end
def A(n)
  return 1 if n < 3
  @move = [[1, 0], [-1, 0], [0, 1], [0, -1]]
  used = Array.new(n * n, false)
  search(0, 0, n, used)
end
def A333466(n)
  (2..n).map{|i| A(i)}
end
p A333466(6)

A297664 Number of chordless cycles in the n X n grid graph.

Original entry on oeis.org

0, 1, 5, 24, 229, 3436, 65772, 1743247, 78586742, 7234839185, 1330059590925, 421587920205546, 212201572752086670, 170288846375423693683, 227570453486998336648738, 527014715702923506908210573, 2140337449056844246626590305042, 15055309813180236733267168372538873

Offset: 1

Eric W. Weisstein, Jan 02 2018

nonn

Eric Weisstein's World of Mathematics, Chordless Cycle
Eric Weisstein's World of Mathematics, Grid Graph

Main diagonal of A360196.

Cf. A003763, A140517, A360200, A360914.

a(7)-a(18) from Andrew Howroyd, Jan 08 2018

A302337 Triangle read by rows: T(n,k) is the number of 2k-cycles in the n X n grid graph (2 <= k <= floor(n^2/2), n >= 2).

Original entry on oeis.org

1, 4, 4, 5, 9, 12, 26, 52, 76, 32, 6, 16, 24, 61, 164, 446, 1100, 2102, 2436, 1874, 900, 226, 25, 40, 110, 332, 1070, 3504, 11144, 32172, 77874, 146680, 217470, 255156, 233786, 158652, 69544, 13732, 1072, 36, 60, 173, 556, 1942, 7092, 26424, 97624, 346428, 1136164, 3313812, 8342388, 18064642, 33777148, 54661008, 76165128, 89790912, 86547168, 64626638, 34785284, 12527632, 2677024, 255088

Offset: 2

Eric W. Weisstein, Apr 05 2018

			Triangle begins:
   1;
   4,  4,  5;
   9, 12, 26,  52,  76,   32,    6;
  16, 24, 61, 164, 446, 1100, 2102, 2436, 1874, 900, 226;
  ...
So for example, the 3 X 3 grid graph has 4 4-cycles, 4 6-cycles, and 5 8-cycles.

Seiichi Manyama, Rows n = 2..9, flattened
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Grid Graph

Cf. A003763 (number of Hamiltonian cycles in 2n X 2n grid graph).
Cf. A140517 (number of cycles).
Cf. A301648 (number of longest cycles).

Flatten[Table[Tally[Length /@ FindCycle[GridGraph[{n, n}], Infinity, All]][[All, 2]], {n, 6}]] (* Eric W. Weisstein, Mar 26 2021 *)

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A302337(n):
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return [cycles.len(2 * k).len() for k in range(2, n * n // 2 + 1)]
print([i for n in range(2, 8) for i in A302337(n)])  # Seiichi Manyama, Mar 29 2020

Row sums equal A140517(n).
Length of row n equals A047838(n) = floor(n^2/2) - 1.
T(n,2) =    1 -   2*n +     n^2 = (n-1)^2.
T(n,3) =    4 -   6*n +   2*n^2 = A046092(n-2).
T(n,4) =   26 -  28*n +   7*n^2 for n > 2.
T(n,5) =  164 - 140*n +  28*n^2 for n > 3.
T(n,6) = 1046 - 740*n + 124*n^2 for n > 4.
T(n,k) = A302335(k) - A302336(k)*n + A002931(k)*n^2 for n > k-2.
T(n,floor(n^2/2)) = A301648(n).
T(n,n^2/2) = A003763(n) for n even.

A266513 Number of undirected cycles in a triangular grid graph, n vertices on each side.

Original entry on oeis.org

0, 1, 11, 110, 2402, 128967, 16767653, 5436906668, 4406952731948, 8819634719356421, 43329348004927734247, 522235268182347360718818, 15436131339319739257518081878, 1117847654274955574635482276231683, 198163274851163063009517020867737770265

Offset: 1

Andrew Howroyd, Apr 06 2016

nonn

			Of the 11 cycles in the triangular grid with 3 vertices per side, 4 have length 3, 3 have length 4, 3 have length 5 and 1 has length 6.
4 basic cycle shapes on a(3):
                                      o
                                     / \
        o       o---o    o---o      o   o
       / \     /   /    /     \    /     \
      o---o   o---o    o---o---o  o---o---o

Ed Wynn, Table of n, a(n) for n = 1..17
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Triangular Grid Graph

Cf. A112676, A112675, A140517, A269869.

# Using graphillion
from graphillion import GraphSet
def make_n_triangular_grid_graph(n):
    s = 1
    grids = []
    for i in range(n + 1, 1, -1):
        for j in range(i - 1):
            a, b, c = s + j, s + j + 1, s + i + j
            grids.extend([(a, b), (a, c), (b, c)])
        s += i
    return grids
def A266513(n):
    if n == 1: return 0
    universe = make_n_triangular_grid_graph(n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
print([A266513(n) for n in range(1, 12)])  # Seiichi Manyama, Nov 30 2020

A333246 Number of self-avoiding closed paths on an n X n grid which pass through NW corner.

Original entry on oeis.org

1, 7, 97, 4111, 532269, 212372937, 263708907211, 1013068026356375, 11955420069208095719, 432101605951906251627393, 47778407166747833830058004149, 16149888968763663448192636077980753, 16675786862526496319891707194153887550751, 52568166380872328447478940416604864445574575709

Offset: 2

Seiichi Manyama, Mar 23 2020

nonn

			a(2) = 1;
   +--*
   |  |
   *--*
a(3) = 7;
   +--*      +--*--*   +--*--*   +--*
   |  |      |     |   |     |   |  |
   *--*      *--*--*   *     *   *  *
                       |     |   |  |
                       *--*--*   *--*
   +--*--*   +--*--*   +--*
   |     |   |     |   |  |
   *  *--*   *--*  *   *  *--*
   |  |         |  |   |     |
   *--*         *--*   *--*--*

Cf. A140517, A333247, A333323, A333438, A333439, A333466.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A333246(n):
    universe = tl.grid(n - 1, n - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles().including(1)
    return cycles.len()
print([A333246(n) for n in range(2, 10)])

a(n) = A333439(n) - 1 for n > 1.

a(11), a(13) from Seiichi Manyama, Apr 07 2020

a(10), a(12), a(14)-a(15) from Andrew Howroyd, Jan 30 2022

A068416 Number of partitionings of n X n checkerboard into two edgewise-connected sets.

Original entry on oeis.org

0, 6, 53, 627, 16213, 1123743, 221984391, 127561384993, 215767063451331, 1082828220389781579, 16209089366362071416785, 726438398002211876667379681, 97741115155002465272674416929195, 39565596445488219947994403962984729307

Offset: 1

R. H. Hardin, Mar 02 2002

nonn

One of the partitions may completely surround the other. (Cf. A271802) - Andrew Howroyd, Apr 14 2016

Number of minimal edge cuts in the n X n grid graph. - Andrew Howroyd, Dec 11 2024

			Illustration of a(2)=6:
   11   12   12   12   11   11
   22   12   22   11   12   21
Illustration of a few solutions of a(3):
   111   112   122   111   111
   121   111   112   212   111
   111   111   222   222   222

Anthony J. Guttmann and Iwan Jensen, Table of n, a(n) for n = 1..26
Benjamin Fifield, Kosuke Imai, Jun Kawahara, and Christopher T. Kenny, The Essential Role of Empirical Validation in Legislative Redistricting Simulation, Tech. rep., Department of Government and Department of Statistics, Harvard University (2019).
Anthony J. Guttmann and Iwan Jensen, The gerrymander sequence, or A348456, arXiv:2211.14482 [math.CO], 2022.
Eric Weisstein's World of Mathematics, Grid Graph.
Eric Weisstein's World of Mathematics, Minimal Edge Cut.

Cf. A068392, A166755, A271802, A068381, A068417, A113900, A348456, A358289.

a(n) = A271802(n) + A140517(n-2). - Andrew Howroyd, Apr 14 2016

a(n) = A166755(n)/2. - Andrew Howroyd, Dec 11 2024

a(7)-a(14) from Andrew Howroyd, Apr 14 2016

A234622 Numbers of undirected cycles in the n X n king graph.

Original entry on oeis.org

7, 348, 136597, 545217435, 21964731190911, 9389890985897322572, 41930442683035614068268389, 1912714607714074785106312737308553, 888957501697133413663023517792044869026260, 4209348789084188565760570660849691414465827388642586

Offset: 2

Eric W. Weisstein, Dec 28 2013

nonn

Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, King Graph

Cf. A140519, A158651, A234623, A140517.

a(7)-a(11) from Andrew Howroyd, Apr 06 2016

A339140 Number of (undirected) cycles in the graph C_n X P_n.

Original entry on oeis.org

6, 63, 1540, 119235, 29059380, 21898886793, 50826232189144, 361947451544923557, 7884768474166076906420, 524518303312357729182869149, 106448798893410608983300257207398, 65866487708413725073741586390176988083, 124207126413825808953168887580780401519104028

Offset: 2

Seiichi Manyama, Nov 25 2020

nonn

			If we represent each vertex with o, used edges with lines and unused edges with dots, and repeat the wraparound edges on left and right, the a(2) = 6 solutions for n = 2 are:
    .o-o.   -o.o-   .o-o.   -o.o-   -o-o-   .o.o.
     | |     | |     | |     | |     . .     . .
    .o-o.   .o-o.   -o.o-   -o.o-   .o.o.   -o-o-

Ed Wynn, Table of n, a(n) for n = 2..18
Eric Weisstein's World of Mathematics, Graph Cycle

Cf. A140517, A222197, A296527, A339136, A339137, A339142, A339143.

# Using graphillion
from graphillion import GraphSet
def make_CnXPk(n, k):
    grids = []
    for i in range(1, k + 1):
        for j in range(1, n):
            grids.append((i + (j - 1) * k, i + j * k))
        grids.append((i + (n - 1) * k, i))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A339140(n):
    universe = make_CnXPk(n, n)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
print([A339140(n) for n in range(3, 7)])

a(10) and a(12) from Seiichi Manyama, Nov 25 2020

a(2), a(9), a(11) and a(13)-a(18) from Ed Wynn, Jun 25 2023

A339117 Number of cycles in the grid graph P_5 X P_n.

Original entry on oeis.org

10, 108, 1049, 9349, 80626, 692194, 5948291, 51139577, 439673502, 3779989098, 32497334055, 279386435639, 2401945965628, 20650054358200, 177533025653767, 1526290165248783, 13121849649571820, 112811405309454694, 969864273118112913, 8338134834111643373, 71684765011673779732

Offset: 2

Seiichi Manyama, Nov 24 2020

nonn

a(n+1) / a(n) tends to 8.597218255461742020947886618374491114891840151635008721734194641555448999... - Vaclav Kotesovec, Nov 24 2020

Seiichi Manyama, Table of n, a(n) for n = 2..500
Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, Grid Graph

Cf. A140517, A231829.

# Using graphillion
from graphillion import GraphSet
import graphillion.tutorial as tl
def A(n, k):
    universe = tl.grid(n - 1, k - 1)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
def A339117(n):
    return A(n, 5)
print([A339117(n) for n in range(2, 15)])

Empirical g.f.: -x^2*(10 - 42*x + 149*x^2 - 300*x^3 - 393*x^4 + 693*x^5 + 230*x^6 - 473*x^7 - 72*x^8 + 202*x^9 + 84*x^10) / ((1 - x)^2 * (-1 + 13*x - 45*x^2 + 66*x^3 - 17*x^4 - 209*x^5 + 151*x^6 + 140*x^7 - 112*x^8 - 48*x^9 + 50*x^10 + 28*x^11)). - Vaclav Kotesovec, Nov 24 2020

cp's OEIS Frontend

A231829 Square array read by antidiagonals: T(m,n) = number of ways of creating a closed, simple loop on an m X n rectangular lattice.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A333466 Number of self-avoiding closed paths on an n X n grid which pass through four corners ((0,0), (0,n-1), (n-1,n-1), (n-1,0)).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Python

Ruby

A297664 Number of chordless cycles in the n X n grid graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A302337 Triangle read by rows: T(n,k) is the number of 2k-cycles in the n X n grid graph (2 <= k <= floor(n^2/2), n >= 2).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A266513 Number of undirected cycles in a triangular grid graph, n vertices on each side.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

A333246 Number of self-avoiding closed paths on an n X n grid which pass through NW corner.

Views

Author

Keywords

Examples

Crossrefs

Programs

Python

Formula

Extensions

A068416 Number of partitionings of n X n checkerboard into two edgewise-connected sets.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A234622 Numbers of undirected cycles in the n X n king graph.

Views

Author

Keywords

Links

Crossrefs

Extensions

A339140 Number of (undirected) cycles in the graph C_n X P_n.

Views

Author

Keywords

Examples