Even separable permutations

This example was computed jointly with Michael Albert and Mike Atkinson.

The even separable permutations can be described using the framework of "Simple permutations and algebraic generating functions." Consider the six properties: even/odd, even length/odd length, and sum decomposable/skew decomposable. Every permutation (of length at least 2) satisfies precisely one of each pair of these properties. Now we introduce generating functions to count them, where are subscripts are described by these rules:

• "1" means odd length, "2" means even length,
• "e" means even, "o" means odd,
• "p" means sum decomposable, "m" means skew decomposable,

so for example, g_1ep is the generating function for even sum decomposable separable permutations of odd length. For convenience, let us also introduce the f generating functions, which are sums of g generating functions; for example, f_1e=g_1ep+g_1em. We can now write down a system relating the g generating functions to each other and the f generating functions, which will contain equations such as the following.

g_1ep = (x+g_1em) f_2e + g_2em f_1e + g_1om f_2o + g_2om f_1o.

Our ultimate goal is to find f, defined by

f = f_2e + f_1e.

In order to find f (or rather, its minimal polynomial), we convert our equations into an ideal and use the Gröbner basis facilities of Singular by entering the following:

ring R = 0, (f1e, f2e, f1o, f2o, g1ep, g1em, g2ep, g2em, g1op, g1om,
            g2op, g2om, f, x), lp;
ideal I = (f - (f1e + f2e),
           f1e - (x + g1ep + g1em),
           f2e - (g2ep + g2em),
           f1o - (g1op + g1om),
           f2o - (g2op + g2om),
           g1ep - ((x+g1em)*f2e + g2em*f1e + g1om*f2o + g2om*f1o),
           g1em - ((x+g1ep)*f2e + g2ep*f1e + g1op*f2o + g2op*f1o),
           g2ep - ((x+g1em)*f1e + g2em*f2e + g1om*f1o + g2om*f2o),
           g2em - ((x+g1ep)*f1o + g2ep*f2e + g1op*f1e + g2op*f2o),
           g1op - ((x+g1em)*f2o + g2em*f1o + g1om*f2e + g2om*f1e),
           g1om - ((x+g1ep)*f2o + g2ep*f1o + g1op*f2e + g2op*f1e),
           g2op - ((x+g1em)*f1o + g2em*f2o + g1om*f1e + g2om*f2e),
           g2om - ((x+g1ep)*f1e + g2ep*f2o + g1op*f1o + g2op*f2e));
groebner(I);

Note that the order of the variables specified in the ring initialization command matters. Since we want to find the minimal polynomial for f, we need to specify it second-to-last, followed by x. Singular will return a (rather gigantic) Gröbner basis, the first term of which is the following minimal polynomial for f. There is no easy way to display this mess, but the Maple code is:

4096*f^12+(-24576+24576*x)*f^11+(-116736*x+65536+65536*x^2)*f^10+(-102400+235520*x+102400*x^3-235520*x^2)*f^9+(104000*x^4-259584*x+327040*x^2+103744-259584*x^3)*f^8+(163072*x-70912-196096*x^2+196096*x^3+71936*x^5-164096*x^4)*f^7+(34464*x^6-52288*x^5+27520*x^3+5600*x^2-48704*x+7296*x^4+32640)*f^6+(-5952*x+63776*x^2+480*x^6-9472-58688*x^5+11360*x^7-115040*x^3+113536*x^4)*f^5+(7312*x^7-34528*x^6+2484*x^8+59440*x^3-40248*x^2+56496*x^5-63284*x^4+1272+11792*x)*f^4+(-7344*x^3+10800*x^2-4848*x-472*x^4+328*x^9+2904*x^8+152*x^5+6656*x^6-8320*x^7+144)*f^3+(-429*x^2+882*x+528*x^9-554*x^8-2632*x^7+20*x^10-11750*x^5+10471*x^4-4484*x^3+8045*x^6-81)*f^2+(40*x^10+122*x^9+9+1961*x^7-3087*x^6+4129*x^5-874*x^8+2247*x^3-513*x^2-27*x-4007*x^4)*f-351*x^3-9*x+99*x^2+615*x^4-78*x^9-603*x^5+361*x^6-183*x^7+130*x^8+20*x^10

The first few terms of the sequence counting the even separable permutations are

1, 1, 3, 12, 48, 197, 903, 4298, 20862, 103049, 518859, 2647296, 13651092, 71039373, 372693519, 1968822294, 10463661690, 55909013009, 300159426963, 1618362990804, 8759313066840, 47574827600981, 259215937709463, 1416461710958242, 7760733971692470, 42624971294485657, 234643073935918683, 1294379447060696520, 7154203061169312444, 39614015909996567325.

(This is sequence A165328 in the On-Line Encyclopedia of Integer Sequences.)

It is interesting to note that for n congruent to 2 or 3 mod 4, these values are precisely the little Schröder numbers. This is because the number of separable permutations of length n is given by the large Schröder numbers, the separable permutations are closed under reversal, and for n congruent to 2 or 3 mod 4, reversing a permutation corresponds to multiplying it by an odd permutation; therefore for these values of n, precisely one-half of the separable permutations are even.

Also, the generating function d which counts the number of even separable permutations minus the number of odd separable permutations is only of degree 6 (and, in fact, can be solved by radicals):

2*d^6+(6*x-6)*d^5+(7*x^2-6*x+7)*d^4+(-4*x-4+4*x^3+4*x^2)*d^3+(6*x+x^4+6*x^3-7*x^2)*d^2+(-3*x+2*x^4+x^3-x^2+1)*d+x^4-x^3+3*x^2-x

This sequence begins

1, 0, 0, 2, 6, 0, 0, 38, 138, 0, 0, 1146, 4446, 0, 0, 41550, 166674, 0, 0, 1664434, 6812790, 0, 0, 70986742, 294509850, 0, 0, 3160755242, 13240781262, 0, 0,

and the fact that this is a sequence of positive numbers is curious.

< back to homepage