A077054 -id:A077054 - cp's OEIS frontend

A005316 Meandric numbers: number of ways a river can cross a road n times.

1, 1, 1, 2, 3, 8, 14, 42, 81, 262, 538, 1828, 3926, 13820, 30694, 110954, 252939, 933458, 2172830, 8152860, 19304190, 73424650, 176343390, 678390116, 1649008456, 6405031050, 15730575554, 61606881612, 152663683494, 602188541928, 1503962954930, 5969806669034, 15012865733351, 59923200729046, 151622652413194, 608188709574124, 1547365078534578, 6234277838531806, 15939972379349178, 64477712119584604, 165597452660771610, 672265814872772972, 1733609081727968492, 7060941974458061392

Offset: 0

N. J. A. Sloane, Stéphane Legendre

Number of ways that a river (or directed line) that starts in the southwest and flows east can cross an east-west road n times (see the illustration).

Or, number of ways that an undirected line can cross a road with at least one end below the road.

Alon, Noga and Maass, Wolfgang, Meanders and their applications in lower bounds arguments. Twenty-Seventh Annual IEEE Symposium on the Foundations of Computer Science (Toronto, ON, 1986). J. Comput. System Sci. 37 (1988), no. 2, 118-129.
V. I. Arnol'd, A branched covering of CP^2->S^4, hyperbolicity and projective topology [ Russian ], Sibir. Mat. Zhurn., 29 (No. 2, 1988), 36-47 = Siberian Math. J., 29 (1988), 717-725.
V. I. Arnol'd, ed., Arnold's Problems, Springer, 2005; Problem 1989-18.
B. Bobier and J. Sawada, A fast algorithm to generate open meandric systems and meanders, ACM Transactions on Algorithms, Vol. 6, No. 2, 2010, article #42.
Di Francesco, P. The meander determinant and its generalizations. Calogero-Moser-Sutherland models (Montreal, QC, 1997), 127-144, CRM Ser. Math. Phys., Springer, New York, 2000.
Di Francesco, P., SU(N) meander determinants. J. Math. Phys. 38 (1997), no. 11, 5905-5943.
Di Francesco, P. Truncated meanders. Recent developments in quantum affine algebras and related topics (Raleigh, NC, 1998), 135-162, Contemp. Math., 248, Amer. Math. Soc., Providence, RI, 1999.
Di Francesco, P. Meander determinants. Comm. Math. Phys. 191 (1998), no. 3, 543-583.
Di Francesco, P. Exact asymptotics of meander numbers. Formal power series and algebraic combinatorics (Moscow, 2000), 3-14, Springer, Berlin, 2000.
Di Francesco, P., Golinelli, O. and Guitter, E., Meanders. In The Mathematical Beauty of Physics (Saclay, 1996), pp. 12-50, Adv. Ser. Math. Phys., 24, World Sci. Publishing, River Edge, NJ, 1997.
Di Francesco, P., Golinelli, O. and Guitter, E. Meanders and the Temperley-Lieb algebra. Comm. Math. Phys. 186 (1997), no. 1, 1-59.
Di Francesco, P., Guitter, E. and Jacobsen, J. L. Exact meander asymptotics: a numerical check. Nuclear Phys. B 580 (2000), no. 3, 757-795.
Franz, Reinhard O. W. A partial order for the set of meanders. Ann. Comb. 2 (1998), no. 1, 7-18.
Franz, Reinhard O. W. and Earnshaw, Berton A. A constructive enumeration of meanders. Ann. Comb. 6 (2002), no. 1, 7-17.
Isakov, N. M. and Yarmolenko, V. I. Bounded meander approximations. (Russian) Qualitative and approximate methods for the investigation of operator equations (Russian), 71-76, 162, Yaroslav. Gos. Univ., 1981.
Lando, S. K. and Zvonkin, A. K. Plane and projective meanders. Conference on Formal Power Series and Algebraic Combinatorics (Bordeaux, 1991).
Lando, S. K. and Zvonkin, A. K. Meanders. In Selected translations. Selecta Math. Soviet. 11 (1992), no. 2, 117-144.
Makeenko, Y., Strings, matrix models and meanders. Theory of elementary particles (Buckow, 1995). Nuclear Phys. B Proc. Suppl. 49 (1996), 226-237.
A. Panayotopoulos, On Meandric Colliers, Mathematics in Computer Science, (2018). https://doi.org/10.1007/s11786-018-0389-6.
A. Phillips, Simple Alternating Transit Mazes, unpublished. Abridged version appeared as La topologia dei labirinti, in M. Emmer, editor, L'Occhio di Horus: Itinerari nell'Imaginario Matematico. Istituto della Enciclopedia Italia, Rome, 1989, pp. 57-67.
J. A. Reeds and L. A. Shepp, An upper bound on the meander constant, preprint, May 25, 1999. [Obtains upper bound of 13.01]
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 = 0..55 (first 44 terms from Iwan Jensen)
V. I. Arnold, Problem: continue the sequence 1, 1, 2, 3, 8, 14, 42, 81..., Manuscript.
David Bevan, Open Meanders [From _David Bevan_, Jun 25 2010]
CombOS - Combinatorial Object Server, Generate meanders and stamp foldings
P. Di Francesco, O. Golinelli and E. Guitter, Meander, folding and arch statistics, arXiv:hep-th/9506030, 1995; Combinatorics and physics (Marseilles, 1995). Math. Comput. Modelling 26 (1997), no. 8-10, 97-147.
Di Francesco, P., Golinelli, O. and Guitter, E., Meanders: exact asymptotics, Nuclear Phys. B 570 (2000), no. 3, 699-712.
Di Francesco, P., Golinelli, O. and Guitter, E., Meanders: a direct enumeration approach, arXiv:cond-mat/9910453 [cond-mat.stat-mech], 1999-2000; Nuclear Phys. B 482 (1996), no. 3, 497-535.
Andrew Howroyd, C# Software for the enumeration of meanders
Benedict Irwin, On the Number of k-Crossing Partitions, Univ. of Cambridge (2021).
I. Jensen, Home page
I. Jensen, A transfer matrix approach to the enumeration of plane meanders, arXiv:cond-mat/0008178 [cond-mat.stat-mech], 2000.
I. Jensen, A transfer matrix approach to the enumeration of plane meanders, J. Phys. A 33, 5953-5963 (2000).
I. Jensen, Enumeration of plane meanders, arXiv:cond-mat/9910313 [cond-mat.stat-mech], 1999.
I. Jensen, Open meanders, a(n) for n = 0..43
I. Jensen and A. J. Guttmann, Critical exponents of plane meanders J. Phys. A 33, L187-L192 (2000).
M. La Croix, Approaches to the Enumerative Theory of Meanders [From _Gerald McGarvey_, Oct 26 2008]
S. K. Lando and A. K. Zvonkin, Plane and projective meanders, Séries Formelles et Combinatoire Algébrique. Laboratoire Bordelais de Recherche Informatique, Université Bordeaux I, 1991, pp. 287-303. (Annotated scanned copy)
S. K. Lando and A. K. Zvonkin, Plane and projective meanders, Theoretical Computer Science Vol. 117, pp. 227-241, 1993.
S. Legendre, Foldings and Meanders, Aust. J. Comb. 58(2), 275-291, 2014; and also on arXiv, arXiv:1302.2025 [math.CO], 2013.
A. Panayotopoulos, P. Vlamos, Partitioning the Meandering Curves, Mathematics in Computer Science (2015) p 1-10.
A. Phillips, Mazes
A. Phillips, Simple, Alternating, Transit Mazes
Frank Ruskey, Information on Stamp Foldings
J. Sawada and R. Li, Stamp foldings, semi-meanders, and open meanders: fast generation algorithms, Electronic Journal of Combinatorics, Volume 19 No. 2 (2012), P#43 (16 pages).
M. Skrzypczak and P. Pokorski, Illustration of a(10)
N. J. A. Sloane, Illustration of initial terms
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).

a(2n) is A005315. Cf. A076875, A076906, A076907, A077014, A077054, A077055, A077056, A078591.

A005315 Closed meandric numbers (or meanders): number of ways a loop can cross a road 2n times.

Original entry on oeis.org

1, 1, 2, 8, 42, 262, 1828, 13820, 110954, 933458, 8152860, 73424650, 678390116, 6405031050, 61606881612, 602188541928, 5969806669034, 59923200729046, 608188709574124, 6234277838531806, 64477712119584604, 672265814872772972, 7060941974458061392

Offset: 0

N. J. A. Sloane, J. A. Reeds (reeds(AT)idaccr.org)

There is a 1-to-1 correspondence between loops crossing a road 2n times and lines crossing a road 2n-1 times.

S. K. Lando and A. K. Zvonkin, Plane and projective meanders, Séries Formelles et Combinatoire Algébrique. Laboratoire Bordelais de Recherche Informatique, Université Bordeaux I, 1991, pp. 287-303.
S. K. Lando and A. K. Zvonkin, Meanders, Selecta Mathematica Sovietica, Vol. 11, Number 2, pp. 117-144, 1992.
A. Phillips, Simple Alternating Transit Mazes, preprint. Abridged version appeared as "La topologia dei labirinti," in M. Emmer, editor, L'Occhio di Horus: Itinerari nell'Imaginario Matematico. Istituto della Enciclopedia Italia, Rome, 1989, pp. 57-67.
V. R. Pratt, personal communication.
J. A. Reeds and L. A. Shepp, An upper bound on the meander constant, preprint, May 25, 1999. [Obtains upper bound of 13.01]
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
For additional references, see A005316.

Andrew Howroyd, Table of n, a(n) for n = 0..28 (first 24 terms from Iwan Jensen)
Oswin Aichholzer, Carlos Alegría Galicia, Irene Parada, Alexander Pilz, Javier Tejel, Csaba D. Tóth, Jorge Urrutia, and Birgit Vogtenhuber, Hamiltonian meander paths and cycles on bichromatic point sets, XVIII Spanish Meeting on Computational Geometry (Girona, 2019).
V. I. Arnol'd, A branched covering of CP^2->S^4, hyperbolicity and projective topology [ Russian ], Sibir. Mat. Zhurn., 29 (No. 2, 1988), 36-47 = Siberian Math. J., 29 (1988), 717-725.
Roland Bacher, Meander algebras
David Bevan, Random Closed Meanders - _David Bevan_, Jun 25 2010
Alexander E. Black, Kevin Liu, Alex Mcdonough, Garrett Nelson, Michael C. Wigal, Mei Yin, and Youngho Yoo, Sampling planar tanglegrams and pairs of disjoint triangulations, arXiv:2304.05318 [math.CO], 2023.
B. Bobier and J. Sawada, A fast algorithm to generate open meandric systems and meanders, Transactions on Algorithms, Vol. 6 No. 2 (2010) article #42, 12 pages.
P. Di Francesco, O. Golinelli and E. Guitter, Meander, folding and arch statistics, arXiv:hep-th/9506030, 1995.
Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, 2009; see page 525.
Reinhard O. W. Franz, and Berton A. Earnshaw, A constructive enumeration of meanders, Ann. Comb. 6 (2002), no. 1, 7-17.
Erich Friedman, Illustration of initial terms
Motohisa Fukuda, Ion Nechita, Enumerating meandric systems with large number of components, arXiv preprint arXiv:1609.02756 [math.CO], 2016.
Iwan Jensen, Home page
Iwan Jensen, Closed meanders, a(n) for n = 1..24
Iwan Jensen, Enumeration of plane meanders, arXiv:cond-mat/9910313 [cond-mat.stat-mech], 1999.
Iwan Jensen, A transfer matrix approach to the enumeration of plane meanders, J. Phys. A 33, 5953-5963 (2000).
Iwan Jensen and A. J. Guttmann, Critical exponents of plane meanders J. Phys. A 33, L187-L192 (2000).
Michael La Croix, Approaches to the Enumerative Theory of Meanders, 2003.
S. K. Lando and A. K. Zvonkin, Plane and projective meanders, Séries Formelles et Combinatoire Algébrique. Laboratoire Bordelais de Recherche Informatique, Université Bordeaux I, 1991, pp. 287-303. (Annotated scanned copy)
S. K. Lando and A. K. Zvonkin, Plane and projective meanders, Theoretical Computer Science Vol. 117, pp. 227-241, 1993.
A. Panayotopoulos, On Meandric Colliers, Mathematics in Computer Science, (2018).
A. Panayotopoulos and P. Tsikouras, Meanders and Motzkin Words, J. Integer Seqs., Vol. 7, 2004.
A. Phillips, Mazes
A. Phillips, Simple, Alternating, Transit Mazes
J. A. Reeds, D. E. Knuth, & N. J. A. Sloane, Email Correspondence
J. Reeds, L. Shepp, & D. McIlroy, Numerical bounds for the Arnol'd "meander" constant, Preprint.
M. A. Sainte-Laguë, Les Réseaux (ou Graphes), Mémorial des Sciences Mathématiques, Fasc. 18, Gauthier-Villars, Paris, 1926, p. 47.
N. J. A. Sloane, My favorite integer sequences, in Sequences and their Applications (Proceedings of SETA '98).

These are the odd-numbered terms of A005316. Cf. A077054. For nonisomorphic solutions, see A077460.

A column of triangle A008828.

A005316 = Cases[Import["https://oeis.org/A005316/b005316.txt", "Table"], {, }][[All, 2]];
a[n_] := If[n == 0, 1, A005316[[2n]]];
a /@ Range[0, 28] (* Jean-François Alcover, Sep 25 2019 *)

a(n) = A005316(2n-1) for n>0.

A077056 Total number of "humps" in all A005316(2n) open meanders with 2n crossings.

Original entry on oeis.org

0, 1, 4, 22, 140, 992, 7584, 61420, 520320, 4570292, 41354416, 383609434, 3634231140, 35059333218, 343580813492, 3413862553800, 34336784362232, 349131316634164, 3584622273967324, 37128374058146138, 387630493693010928, 4076329834240413392, 43150916852592230992

Offset: 0

N. J. A. Sloane and Jon Wild, Nov 29 2002

nonn

A "hump" is a local maxima of the upper envelope of the part of the meander that extends above the East-West road.

A "hump" can also be described as an exterior top arch. - Andrew Howroyd, Feb 01 2025

			The three open meanders with 4 crossings have respectively 2, 1 and 1 humps, so a(2) = 4.

Cf. A005316 (open meanders), A077054, A380369.

a(n) = Sum_{k=1..n} k*A380369(n,k). - Andrew Howroyd, Feb 01 2025

a(9)-a(20) from Andrew Howroyd, Nov 22 2015
a(21)-a(22) from Andrew Howroyd, Feb 01 2025
a(0) corrected by Andrew Howroyd, Feb 02 2025

A086031 Number of nonisomorphic ways a loop can cross two parallel roads 2n times.

Original entry on oeis.org

1, 1, 3, 7, 37, 207, 1470, 11169, 91166, 776841, 6865598, 62443973

Offset: 0

N. J. A. Sloane and Jon Wild, Aug 25 2003

nonn

There is no obligation to cross the lower road (cf. A077054).

Cf. A077054. Isomorphism classes from A085973.

A380369 Triangle read by rows: T(n,k) is the number of open meanders with 2n crossings and k exterior top arches, 0 <= k <= n.

Original entry on oeis.org

1, 0, 1, 0, 2, 1, 0, 7, 6, 1, 0, 36, 32, 12, 1, 0, 221, 202, 94, 20, 1, 0, 1530, 1417, 728, 220, 30, 1, 0, 11510, 10752, 5854, 2090, 445, 42, 1, 0, 92114, 86554, 48942, 19300, 5160, 812, 56, 1, 0, 773259, 729716, 423778, 178478, 54758, 11396, 1372, 72, 1, 0, 6743122, 6384353, 3781926, 1669062, 561514, 138866, 23072, 2184, 90, 1

Offset: 0

Andrew Howroyd, Feb 01 2025

			Triangle begins:
  1;
  0,     1;
  0,     2,     1;
  0,     7,     6,     1;
  0,    36,    32,    12,     1;
  0,   221,   202,    94,    20,    1;
  0,  1530,  1417,   728,   220,   30,   1;
  0, 11510, 10752,  5854,  2090,  445,  42,  1;
  0, 92114, 86554, 48942, 19300, 5160, 812, 56, 1;
  ...
The T(2,1) = 2 open meanders are:
         __           __
        /  \         /  \
   ... / /\ \..  .. / /\ \ ...
      / /  \/       \/  \ \
The T(2,2) = 1 open meander is:
   ... /\../\ ...
      /  \/  \

Andrew Howroyd, Table of n, a(n) for n = 0..230

Row sums are A077054.
Main diagonal is A000012.
Second diagonal is A002378.
Cf. A005316, A006660 (bisection gives column 1), A077056 (total number of exterior top arches), A259689 (for semi-meanders), A259974.

A077056(n) = Sum_{k=1..n} k*T(n,k).

T(n,1) = A006660(2*n + 1).

A085973 Number of ways a loop can cross two parallel roads 2n times.

Original entry on oeis.org

3, 2, 5, 22, 123, 800, 5754, 44514, 363893, 3106288, 27457050, 249768040, 2327398572, 22135606604, 214270565106, 2106151496858, 20982672402385, 211545853142240, 2155553788108702, 22174250217880984, 230075164780356214

Offset: 0

N. J. A. Sloane and Jon Wild, Aug 25 2003

nonn

There is no obligation to cross the lower road (cf. A077054).

Cf. A077054, A086031.

A005315 = Cases[Import["https://oeis.org/A005315/b005315.txt", "Table"], {, }][[All, 2]];
A005316 = Cases[Import["https://oeis.org/A005316/b005316.txt", "Table"], {, }][[All, 2]];
a[n_] := If[n == 0, 3, A005315[[n + 1]] + A005316[[2 n + 1]]];
a /@ Range[0, 20] (* Jean-François Alcover, Sep 08 2019 *)

a(n) = A077054(n) + A005315(n) for n >= 1. - Andrew Howroyd, Nov 26 2015

a(13)-a(20) from Andrew Howroyd, Nov 26 2015

A368054 Irregular triangle read by rows: T(n,k) is the number of k-crossing partitions on 2n nodes, where all partition terms alternate in parity, counted up to reflection.

Original entry on oeis.org

1, 1, 3, 0, 1, 14, 0, 8, 10, 2, 2, 81, 0, 59, 162, 70, 66, 82, 22, 19, 6, 7, 0, 2, 538, 0, 454, 1952, 1229, 1208, 2516, 1803, 1181, 1148, 998, 478, 370, 279, 125, 76, 26, 13, 3, 3, 3926, 0, 3658, 21608, 17083, 17811, 48542, 51306, 40081, 51660, 59023, 42327

Offset: 0

John Tyler Rascoe, Dec 09 2023

The 0-crossing partitions counted in A005316 all have terms that alternate in parity. Also, for an even number of nodes the partitions 1432 and 2341 count the same meandric path. This triangle aims to reduce the total number of k-crossing partitions considered from (2*n)! to (n!)^2, see Irwin link.

			Triangle begins:
       k=0  1   2    3   4   5   6   7   8   9  10  11  12
  n=0:   1;
  n=1:   1;
  n=2:   3, 0,  1;
  n=3:  14, 0,  8,  10,  2,  2;
  n=4:  81, 0, 59, 162, 70, 66, 82, 22, 19,  6,  7,  0,  2;
  ...
Row n = 3 counts the following k-crossing partitions.
T(3,0) = 14:   T(3,2) = 8:    T(3,3) = 10:   T(3,4) = 2:    T(3,5) = 2:
(1,2,3,4,5,6)  (3,4,1,6,5,2)  (1,2,5,6,3,4)  (3,2,5,6,1,4)  (3,6,1,4,5,2)
(1,2,3,6,5,4)  (3,4,5,6,1,2)  (1,4,3,6,5,2)  (3,6,1,2,5,4)  (5,2,3,6,1,4)
(1,2,5,4,3,6)  (3,6,5,4,1,2)  (1,4,5,2,3,6)
(1,4,3,2,5,6)  (5,2,1,6,3,4)  (1,6,3,2,5,4)
(1,4,5,6,3,2)  (5,4,3,6,1,2)  (3,2,5,4,1,6)
(1,6,3,4,5,2)  (5,6,1,2,3,4)  (3,4,1,2,5,6)
(1,6,5,2,3,4)  (5,6,1,4,3,2)  (3,6,5,2,1,4)
(1,6,5,4,3,2)  (5,6,3,2,1,4)  (5,2,1,4,3,6)
(3,2,1,4,5,6)                 (5,4,1,6,3,2)
(3,2,1,6,5,4)                 (5,6,3,4,1,2)
(3,4,5,2,1,6)
(5,2,3,4,1,6)
(5,4,1,2,3,6)
(5,4,3,2,1,6)

Benedict Irwin, On the Number of k-Crossing Partitions, Univ. of Cambridge (2021).
John Tyler Rascoe, Python program.

Cf. A077054 (column k=0), A001044 (row sums).

Cf. A005316, A008828, A287220.

Python
```
# see linked program
```

cp's OEIS Frontend

A005316 Meandric numbers: number of ways a river can cross a road n times.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Extensions

A005315 Closed meandric numbers (or meanders): number of ways a loop can cross a road 2n times.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A077056 Total number of "humps" in all A005316(2n) open meanders with 2n crossings.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A086031 Number of nonisomorphic ways a loop can cross two parallel roads 2n times.

Views

Author

Keywords

Comments

Crossrefs

A380369 Triangle read by rows: T(n,k) is the number of open meanders with 2n crossings and k exterior top arches, 0 <= k <= n.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A085973 Number of ways a loop can cross two parallel roads 2n times.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

Formula

Extensions

A368054 Irregular triangle read by rows: T(n,k) is the number of k-crossing partitions on 2n nodes, where all partition terms alternate in parity, counted up to reflection.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A378944 Triangle read by rows: T(n,k) = number of stamp foldings with stamp #1 first, n stamps and stamp #2 covered by exactly one fold. k = the stamp number before the fold covering stamp #2 divided by 2. See examples.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula