

A178518


Triangle read by rows: T(n,k) is the number of permutations p of {1,2,...,n} having genus 0 and such that p(1)=k (see first comment for definition of genus).


4



1, 1, 1, 2, 2, 1, 5, 5, 2, 2, 14, 14, 5, 4, 5, 42, 42, 14, 10, 10, 14, 132, 132, 42, 28, 25, 28, 42, 429, 429, 132, 84, 70, 70, 84, 132, 1430, 1430, 429, 264, 210, 196, 210, 264, 429, 4862, 4862, 1430, 858, 660, 588, 588, 660, 858, 1430, 16796, 16796, 4862, 2860, 2145
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1z(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.
Row sums are A000108 (Catalan numbers).
T(n,1)=A000108(n1) (n>=1).
T(n,2)=A000108(n1) (n>=2).
T(n,3)=A000108(n2) (n>=3).
T(n,n)=A000108(n2) (n>=2).
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 DulucqSimion reference).


REFERENCES

S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169191.


LINKS

Table of n, a(n) for n=1..60.


FORMULA

T(n,1)=c(n1); T(n,k)=c(nk+1)c(k2) if 2<=k<=n, where c(j)=binom(2j,j)/(j+1)=A000108(j) are the Catalan numbers.
G.f. = G(t,z)=tzC(z)+t^2*z*[C(z)1]*C(tz), where C(z)=(1sqrt(14*z))/(2z) is the Catalan function.


EXAMPLE

T(4,3)=2 because we have 3214=(13)(2)(4) and 3241=(134)(2).
Triangle starts:
1;
1,1;
2,2,1;
5,5,2,2;
14,14,5,4,5;


MAPLE

c := proc (n) options operator, arrow: binomial(2*n, n)/(n+1) end proc: a := proc (n, k) if k = 1 then c(n1) elif k <= n then c(nk+1)*c(k2) else 0 end if end proc: for n to 11 do seq(a(n, k), k = 1 .. n) end do; # yields sequence in triangular form


MATHEMATICA

t[n_, 1] := CatalanNumber[n1]; t[n_, k_] := CatalanNumber[nk+1] * CatalanNumber[k2]; Table[t[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* JeanFrançois Alcover, Jul 10 2013 *)


CROSSREFS

Cf. A000108
Sequence in context: A280785 A204851 A114292 * A299499 A190215 A190252
Adjacent sequences: A178515 A178516 A178517 * A178519 A178520 A178521


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, May 31 2010


STATUS

approved



