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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A169816 Triangle read by rows: T(n,k) is the number of down-up permutations of {1,2,...,n} having genus k. 1
1, 1, 1, 1, 3, 2, 3, 12, 1, 11, 39, 11, 11, 116, 133, 12, 45, 449, 722, 169, 45, 996, 3857, 2832, 206 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

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) denotes 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 ceiling(n/2) entries.

T(2n,0) = T(2n+1,0) = A001003(n) (the little Schroeder numbers).

The Maple program yields the entries of row n (specified at the start of the program).

LINKS

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

S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8, 1998, 169-191.

EXAMPLE

T(3,1)=1 because 312 is the only down-up permutation of {1,2,3} with genus 1 (we have p=312=(132), cp'=231*231=312=(132) and so g(p) = (1/2)(3+1-1-1) = 1).

Triangle starts:

   1;

   1;

   1,   1;

   3,   2;

   3,  12,   1;

  11,  39,  11;

  11, 116, 133,  12;

MAPLE

n := 6: 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:

DU := proc (n) local du, P, j: du := {}: P := permute(n): for j to factorial(n) do if descents(P[j]) = {seq(2*k-1, k = 1 .. floor((1/2)*n))} then du := `union`(du, {P[j]}) else end if end do: du 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(DU(n)[j]), j = 1 .. nops(DU(n)))): seq(coeff(f[n], t, j), j = 0 .. ceil((1/2)*n)-1); # yields the entries of row n (specified at the start of the program)

CROSSREFS

Cf. A000111, A001003.

Sequence in context: A186102 A170848 A078017 * A291739 A057053 A081850

Adjacent sequences:  A169813 A169814 A169815 * A169817 A169818 A169819

KEYWORD

more,nonn,tabf

AUTHOR

Emeric Deutsch, May 28 2010

EXTENSIONS

Edited by R. J. Mathar, Jun 08 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.

License Agreements, Terms of Use, Privacy Policy. .

Last modified February 19 18:22 EST 2019. Contains 320327 sequences. (Running on oeis4.)