This site is supported by donations to The OEIS Foundation.

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

 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)=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)=(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: 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

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 January 15 20:47 EST 2019. Contains 319184 sequences. (Running on oeis4.)