login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

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

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 25 22:13 EST 2018. Contains 299661 sequences. (Running on oeis4.)