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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of the OEIS".
Other ways to donate

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 November 18 17:56 EST 2017. Contains 294894 sequences.