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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A178516 Triangle read by rows: T(n,k) is the number of up-down permutations of {1,2,...,n} having genus k (see first comment for definition of genus). 4
1, 1, 0, 2, 0, 0, 2, 3, 0, 0, 6, 10, 0, 0, 0, 6, 38, 17, 0, 0, 0, 22, 142, 104, 4, 0, 0, 0, 22, 351, 778, 234, 0, 0, 0, 0, 90, 1419, 4086, 2235, 106, 0, 0, 0, 0, 90, 2856, 17402, 24357, 5816, 0, 0, 0, 0, 0, 394, 12208, 87434, 171305, 78705, 3746, 0, 0, 0, 0, 0, 394, 21676, 278062, 1053425, 1120648, 228560, 0 (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.

The sum of the entries in row n is A000111(n) (Euler or up-down numbers).

Apparently, row n contains ceil(n/2) nonzero entries.

T(2n-1,0)=T(2n,0)=A006318(n-1) (the large Schroeder numbers).

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

EXAMPLE

T(4,0)=2. From the fact that 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), it follows that the up-down permutations 2314 = (123)(4) and 1324 = (1)(23)(4) have genus 0, while 2413=(1243), 3412=(13)(24), and 1423=(1)(243) do not.

Triangle starts:

[ 1]  1,

[ 2]  1, 0,

[ 3]  2, 0, 0,

[ 4]  2, 3, 0, 0,

[ 5]  6, 10, 0, 0, 0,

[ 6]  6, 38, 17, 0, 0, 0,

[ 7]  22, 142, 104, 4, 0, 0, 0,

[ 8]  22, 351, 778, 234, 0, 0, 0, 0,

[ 9]  90, 1419, 4086, 2235, 106, 0, 0, 0, 0,

[10]  90, 2856, 17402, 24357, 5816, 0, 0, 0, 0, 0,

[11]  394, 12208, 87434, 171305, 78705, 3746, 0, 0, 0, 0, 0,

[12]  394, 21676, 278062, 1053425, 1120648, 228560, 0, 0, 0, 0, 0, 0,

...

MAPLE

n := 7: with(combinat): descents := proc (p) local A, i: A := {}: for i to nops(p)-1 do if p[i+1] < p[i] then A := `union`(A, {i}) else end if end do: A end proc; UD := proc (n) local ud, P, j: ud := {}: P := permute(n): for j to factorial(n) do if descents(P[j]) = {seq(2*k, k = 1 .. ceil((1/2)*n)-1)} then ud := `union`(ud, {P[j]}) else end if end do: ud end proc; inv := proc (p) local j, q: for j to nops(p) do q[p[j]] := j end do: [seq(q[i], i = 1 .. nops(p))] end proc: nrcyc := proc (p) local nrfp, pc: nrfp := proc (p) local ct, j: ct := 0: for j to nops(p) do if p[j] = j then ct := ct+1 else end if end do: ct end proc:

pc := convert(p, disjcyc): nops(pc)+nrfp(p) end proc: b := proc (p) local c: c := [seq(i+1, i = 1 .. nops(p)-1), 1]: [seq(c[p[j]], j = 1 .. nops(p))] end proc: gen := proc (p) options operator, arrow: (1/2)*nops(p)+1/2-(1/2)*nrcyc(p)-(1/2)*nrcyc(b(inv(p))) end proc: f[n] := sort(add(t^gen(UD(n)[j]), j = 1 .. nops(UD(n)))): seq(coeff(f[n], t, j), j = 0 .. ceil((1/2)*n)-1); # yields the entries in the specified row n

CROSSREFS

Cf. A177267.

Cf. A000111, A006318, A169816.

Sequence in context: A046742 A263138 A274637 * A174739 A280542 A274575

Adjacent sequences:  A178513 A178514 A178515 * A178517 A178518 A178519

KEYWORD

nonn,hard,tabl

AUTHOR

Emeric Deutsch, May 29 2010

EXTENSIONS

Terms beyond row 7 from Joerg Arndt, Nov 01 2012.

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 03:06 EST 2018. Contains 299630 sequences. (Running on oeis4.)