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).

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, 1848, 1764, 1848, 2145, 2860, 4862

Offset: 1

Author

Emeric Deutsch, May 31 2010

Keywords

• nonn
• 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.

Row sums are A000108 (Catalan numbers).

T(n,1) = A000108(n-1) (n >= 1).

T(n,2) = A000108(n-1) (n >= 2).

T(n,3) = A000108(n-2) (n >= 3).

T(n,n) = A000108(n-2) (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 Dulucq-Simion reference).

Examples

			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;
		

References

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

Crossrefs

Cf. A000108.

Programs

Maple

c := proc (n) options operator, arrow: binomial(2*n, n)/(n+1) end proc: a := proc (n, k) if k = 1 then c(n-1) elif k <= n then c(n-k+1)*c(k-2) 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[n-1]; t[n_, k_] := CatalanNumber[n-k+1] * CatalanNumber[k-2]; Table[t[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 10 2013 *)

Formula

T(n,1)=c(n-1); T(n,k) = c(n-k+1)*c(k-2) if 2 <= k <= n, where c(j) = binomial(2j,j)/(j+1) = A000108(j) are the Catalan numbers.

G.f. = G(t,z) = t*z*C(z)+t^2*z*(C(z)-1)*C(tz), where C(z) = (1-sqrt(1-4*z))/(2z) is the Catalan function.