login
Triangle read by rows: T(n,k) is the number of k-element equivalence classes of closed meanders with 2n points.
0

%I #24 Dec 26 2020 16:06:00

%S 1,2,8,42,262,1820,4,13756,32,110394,280,928790,2328,4,8110104,21294,

%T 56,73040142,191396,540,24,674775338,1798624,5214,472,6370633938,

%U 17113152,48240,6482,32,61269105780,168043112,450616,83804,464,32,0,4

%N Triangle read by rows: T(n,k) is the number of k-element equivalence classes of closed meanders with 2n points.

%C Two closed meanders s and t with 2n points are equivalent iff their corresponding permutations s(1) s(2) ... s(2n) and t(1) t(2) ... t(2n) have the same absolute difference sequence, i.e. |s(i+1) - s(i)| = |t(i+1) - t(i)| for all i = 1,2,..,2n, where s(1) = t(1) = s(2n+1) = t(2n+1) = 1.

%H M. De Biasi, <a href="https://doi.org/10.37236/4086">Permutation Reconstruction from Differences</a>, Electronic Journal of Combinatorics, Volume 21 No. 4 (2014), P4.3 (23 pages).

%H A. Panayotopoulos, <a href="https://doi.org/10.1007/s11786-018-0389-6">On Meandric Colliers</a>, Mathematics in Computer Science, (2018).

%H J. Sawada and R. Li, <a href="https://doi.org/10.37236/2404">Stamp foldings, semi-meanders, and open meanders: fast generation algorithms</a>, Electronic Journal of Combinatorics, Volume 19 No. 2 (2012), P#43 (16 pages).

%F Sum_{k >= 1} k*T(n,k) = A005315(n) (closed meandric numbers).

%e Triangle begins:

%e 1;

%e 2;

%e 8;

%e 42;

%e 262;

%e 1820, 4;

%e 13756, 32;

%e 110394, 280;

%e 928790, 2328, 4;

%e 8110104, 21294, 56;

%e 73040142, 191396, 540, 24;

%e 674775338, 1798624, 5214, 472;

%e 6370633938, 17113152, 48240, 6482, 32;

%e 61269105780, 168043112, 450616, 83804, 464, 32, 0, 4;

%e ...

%e For n = 6 there exist four 2-element equivalence classes:

%e 1st class consists of permutations (1, 2, 5, 6, 7, 4, 3, 8, 9, 12, 11, 10) and (1, 2, 5, 4, 3, 6, 7, 12, 11, 8, 9, 10) having difference sequence: (1, 3, 1, 1, 3, 1, 5, 1, 3, 1, 1, 9).

%e 2nd class consists of permutations (1, 12, 9, 10, 11, 8, 7, 2, 3, 6, 5, 4) and (1, 12, 9, 8, 7, 10, 11, 6, 5, 2, 3, 4) having difference sequence: (11, 3, 1, 1, 3, 1, 5, 1, 3, 1, 1, 3).

%e 3rd class consists of permutations (1, 10, 9, 8, 11, 12, 7, 6, 3, 4, 5, 2) and (1, 10, 11, 12, 9, 8, 3, 4, 7, 6, 5, 2) having difference sequence: (9, 1, 1, 3, 1, 5, 1, 3, 1, 1, 3, 1).

%e 4th class consists of permutations (1, 4, 5, 6, 3, 2, 7, 8, 11, 10, 9, 12) and (1, 4, 3, 2, 5, 6, 11, 10, 7, 8, 9, 12) having difference sequence: (3, 1, 1, 3, 1, 5, 1, 3, 1, 1, 3, 11).

%Y Cf. A005315.

%K tabf,nonn

%O 1,2

%A _Gerasimos Pergaris_, Dec 06 2020