18
$\begingroup$

One of the open problems in combinatorics is enumeration of meanders.

Here on MO I only could find them under the heading not-especially-famous-long-open-problems-which-anyone-can-understand.

Since my interest is in some particular kind of these, I will not give the definition in the general case.

These special ones first appeared in a paper by Dergachev and Kirillov "Index of Lie algebras of seaweed type".

Our meanders, unlike the general ones, can be described by pairs of compositions with equal sum. For example, 4+3+4=5+4+2 gives

this is the good meander corresponding to 4+3+4=5+4+2

Call this good: it consists of a single interval.

Here is another one, corresponding to 5+3+4=3+5+2+2:

and this is the bad meander encoded by 5+3+4=3+5+2+2

This is bad for two reasons: it is not connected, and it contains a non-interval (a cycle).

And here is a general (non-special) meander:

this is not ours, it does not correspond to any pair of compositions

One thus obtains a sequence of numbers $a(n)$, with the $n$th number equal to the number of pairs of compositions of $n$ which encode good special meanders.

There is a recurrence which was used by Martin Plechsmid to write a C program for calculating these numbers up to several dozens. This recurrence was first observed by D. I. Panyushev in "Inductive formulas for the index of seaweed Lie algebras". In short, it is this: suppose given $a_1+a_2+...+a_k=b_1+b_2+...+b_l$ with $a_1>b_1$, let $d=a_1-b_1$ and let $r$ be the smallest nonnegative residue of $b_1$ modulo $d$. Then, the meander corresponding to $a_1+...+a_k=b_1+...+b_l$ is good if and only if good is the one corresponding to $$ (d-r)+r+a_2+...+a_k=b_2+...+b_l $$ (in case $r$ is zero it must be discarded).

Here are the first 111 of the $a(n)$ $$ \begin{array}{rr} 1 & 1 \\ 2 & 2 \\ 3 & 6 \\ 4 & 14 \\ 5 & 34 \\ 6 & 68 \\ 7 & 150 \\ 8 & 296 \\ 9 & 586 \\ 10 & 1140 \\ 11 & 2182 \\ 12 & 4130 \\ 13 & 7678 \\ 14 & 14368 \\ 15 & 26068 \\ 16 & 48248 \\ 17 & 86572 \\ 18 & 158146 \\ 19 & 281410 \\ 20 & 509442 \\ 21 & 901014 \\ 22 & 1618544 \\ 23 & 2852464 \\ 24 & 5089580 \\ 25 & 8948694 \\ 26 & 15884762 \\ 27 & 27882762 \\ 28 & 49291952 \\ 29 & 86435358 \\ 30 & 152316976 \\ 31 & 266907560 \\ 32 & 469232204 \\ 33 & 821844316 \\ 34 & 1442300988 \\ 35 & 2525295380 \\ 36 & 4426185044 \\ 37 & 7747801190 \\ 38 & 13567867834 \\ 39 & 23745303556 \\ 40 & 41557384062 \\ 41 & 72719208250 \\ 42 & 127217086618 \\ 43 & 222583616898 \\ 44 & 389294870960 \\ 45 & 681055011606 \\ 46 & 1190969037432 \\ 47 & 2083373141104 \\ 48 & 3642902097800 \\ 49 & 6372107745996 \\ 50 & 11141529268952 \\ 51 & 19487429053968 \\ 52 & 34072922408612 \\ 53 & 59593329333396 \\ 54 & 104196373919102 \\ 55 & 182231390839818 \\ 56 & 318626594336984 \\ 57 & 557234724403516 \\ 58 & 974322146677446 \\ 59 & 1703911578212510 \\ 60 & 2979322259711846 \\ 61 & 5210178551385178 \\ 62 & 9110218849890570 \\ 63 & 15931493988982610 \\ 64 & 27857226815017550 \\ 65 & 48714664885792786 \\ 66 & 85181547848196296 \\ 67 & 148957642280387814 \\ 68 & 260466741606092886 \\ 69 & 455476513314908856 \\ 70 & 796449892337843592 \\ 71 & 1392738017582218730 \\ 72 & 2435366204142605618 \\ 73 & 4258661790160448532 \\ 74 & 7446802851854147060 \\ 75 & 13021983359977438148 \\ 76 & 22770642365898383396 \\ 77 & 39818175179779177288 \\ 78 & 69627468187243597212 \\ 79 & 121754707865610780058 \\ 80 & 212904995880239240452 \\ 81 & 372297678714099281570 \\ 82 & 651015082378846020240 \\ 83 & 1138400336916804107622 \\ 84 & 1990655971732690098044 \\ 85 & 3480966121609384598862 \\ 86 & 6086972571117750179712 \\ 87 & 10643994672706675232516 \\ 88 & 18612574887590099590878 \\ 89 & 32546894313258870888576 \\ 90 & 56913010148917999572282 \\ 91 & 99520946619696571486034 \\ 92 & 174027003616514242824506 \\ 93 & 304312275771039225380736 \\ 94 & 532134871943053489298230 \\ 95 & 930517331785546952850436 \\ 96 & 1627147003755362124099240 \\ 97 & 2845309257636125017979486 \\ 98 & 4975444158602380143431196 \\ 99 & 8700305413681034236853658 \\ 100 & 15213772506611898836430634 \\ 101 & 26603545989601689878278594 \\ 102 & 46520243198912300314978832 \\ 103 & 81347565971655249247976872 \\ 104 & 142248282928801736884996866 \\ 105 & 248742274995715373879042070 \\ 106 & 434962771573005719770576034 \\ 107 & 760597063369550445571334010 \\ 108 & 1330016842349701088401439208 \\ 109 & 2325732108141510145312701272 \\ 110 & 4066887817970878716400628884 \\ 111 & 7111557640719424745330990326 \end{array} $$ The obvious question is what can be said about this sequence - for example, its asymptotics.

$\endgroup$
5
  • 12
    $\begingroup$ Your question does not seem to contain an actual definition of these "special" meanders, at least not one I can decode from the examples. $\endgroup$ Nov 3, 2013 at 9:54
  • 2
    $\begingroup$ @TobiasKildetoft Yes you are right of course, what I said is too imprecise. Here is the formal definition. Assign to $a_1+...+a_k=b_1+...+b_l$ the following union of semicircles: upper half-plane semicircles with centers $(a_1+a_2+...+a_{i−1}+\frac{a_i+1}2,0)$ and radii $\frac{a_i+1}2-j$ for $1\leqslant i\leqslant k$ and $1\leqslant j<\frac{a_i+1}2$; and similar lower half-plane semicircles with centers $(b_1+b_2+...+b_{i−1}+\frac{b_i+1}2,0)$ and radii $\frac{b_i+1}2-j$ for $i\leqslant l$ and $j<\frac{b_i+1}2$. This is a "special" meander. It is good if what one obtains is a single interval. $\endgroup$ Nov 3, 2013 at 11:28
  • 1
    $\begingroup$ This sequence is not in OEIS. Consider adding it there: oeis.org $\endgroup$
    – Igor Pak
    Nov 3, 2013 at 18:07
  • 1
    $\begingroup$ @IgorPak I thought about this, but could not figure out how to give a concise description that would fit there. It would be great if somebody could come up with an equivalent shorter definition. $\endgroup$ Nov 3, 2013 at 18:11
  • 1
    $\begingroup$ As suggested by @IgorPak, I've put it in OEIS, it is now A230439 there $\endgroup$ Nov 5, 2013 at 19:28

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.