15
$\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 107 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 \\ \end{array} $$ The obvious question is what can be said about this sequence - for example, its asymptotics.

$\endgroup$
  • 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$ – Tobias Kildetoft Nov 3 '13 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 '13 at 11:28
  • 1
    $\begingroup$ This sequence is not in OEIS. Consider adding it there: oeis.org $\endgroup$ – Igor Pak Nov 3 '13 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 '13 at 18:11
  • 1
    $\begingroup$ As suggested by @IgorPak, I've put it in OEIS, it is now A230439 there $\endgroup$ – მამუკა ჯიბლაძე Nov 5 '13 at 19:28

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.