A178516 Triangle read by rows: T(n,k) is the number of up-down permutations of {1,2,...,n} having genus k (see first comment for definition of genus).

1, 1, 0, 2, 0, 0, 2, 3, 0, 0, 6, 10, 0, 0, 0, 6, 38, 17, 0, 0, 0, 22, 142, 104, 4, 0, 0, 0, 22, 351, 778, 234, 0, 0, 0, 0, 90, 1419, 4086, 2235, 106, 0, 0, 0, 0, 90, 2856, 17402, 24357, 5816, 0, 0, 0, 0, 0, 394, 12208, 87434, 171305, 78705, 3746, 0, 0, 0, 0, 0, 394, 21676, 278062, 1053425, 1120648, 228560, 0

Offset: 1

Author

Emeric Deutsch, May 29 2010

Keywords

• nonn
• hard
• tabl

Comments

The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p) = (1/2)*(n + 1 - z(p) - z(cp')), where p' is the inverse permutation of p, c = 234...n1 = (1,2,...,n), and z(q) is the number of cycles of the permutation q.

The sum of the entries in row n is A000111(n) (Euler or up-down numbers).

Apparently, row n contains ceiling(n/2) nonzero entries.

T(2n-1,0) = T(2n,0) = A006318(n-1) (the large Schroeder numbers).

Examples

			T(4,0)=2. From the fact that a permutation p of {1,2,...,n} has genus 0 if and only if the cycle decomposition of p gives a noncrossing partition of {1,2,...,n} and each cycle of p is increasing (see Lemma 2.1 of the Dulucq-Simion reference), it follows that the up-down permutations 2314 = (123)(4) and 1324 = (1)(23)(4) have genus 0, while 2413 = (1243), 3412 = (13)(24), and 1423 = (1)(243) do not.
Triangle starts:
[ 1]   1,
[ 2]   1,     0,
[ 3]   2,     0,      0,
[ 4]   2,     3,      0,       0,
[ 5]   6,    10,      0,       0,       0,
[ 6]   6,    38,     17,       0,       0,      0,
[ 7]  22,   142,    104,       4,       0,      0, 0,
[ 8]  22,   351,    778,     234,       0,      0, 0, 0,
[ 9]  90,  1419,   4086,    2235,     106,      0, 0, 0, 0,
[10]  90,  2856,  17402,   24357,    5816,      0, 0, 0, 0, 0,
[11] 394, 12208,  87434,  171305,   78705,   3746, 0, 0, 0, 0, 0,
[12] 394, 21676, 278062, 1053425, 1120648, 228560, 0, 0, 0, 0, 0, 0,
...
		

Links

• S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191.

Crossrefs

Cf. A177267.

Cf. A000111, A006318, A169816.

Programs

Maple

n := 7: with(combinat): descents := proc (p) local A, i: A := {}: for i to nops(p)-1 do if p[i+1] < p[i] then A := `union`(A, {i}) else end if end do: A end proc; UD := proc (n) local ud, P, j: ud := {}: P := permute(n): for j to factorial(n) do if descents(P[j]) = {seq(2*k, k = 1 .. ceil((1/2)*n)-1)} then ud := `union`(ud, {P[j]}) else end if end do: ud end proc; inv := proc (p) local j, q: for j to nops(p) do q[p[j]] := j end do: [seq(q[i], i = 1 .. nops(p))] end proc: nrcyc := proc (p) local nrfp, pc: nrfp := proc (p) local ct, j: ct := 0: for j to nops(p) do if p[j] = j then ct := ct+1 else end if end do: ct end proc:
pc := convert(p, disjcyc): nops(pc)+nrfp(p) end proc: b := proc (p) local c: c := [seq(i+1, i = 1 .. nops(p)-1), 1]: [seq(c[p[j]], j = 1 .. nops(p))] end proc: gen := proc (p) options operator, arrow: (1/2)*nops(p)+1/2-(1/2)*nrcyc(p)-(1/2)*nrcyc(b(inv(p))) end proc: f[n] := sort(add(t^gen(UD(n)[j]), j = 1 .. nops(UD(n)))): seq(coeff(f[n], t, j), j = 0 .. ceil((1/2)*n)-1); # yields the entries in the specified row n

Extensions

Terms beyond row 7 from Joerg Arndt, Nov 01 2012