The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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+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). REFERENCES S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191. LINKS 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. 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(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 *) CROSSREFS Cf. A000108. Sequence in context: A204851 A114292 A333724 * A299499 A190215 A190252 Adjacent sequences:  A178515 A178516 A178517 * A178519 A178520 A178521 KEYWORD nonn,tabl AUTHOR Emeric Deutsch, May 31 2010 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 1 07:45 EDT 2021. Contains 346384 sequences. (Running on oeis4.)