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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A178515 Triangle read by rows: T(n,k) is the number of involutions of {1,2,...,n} having genus k (see first comment for definition of genus). 5
1, 2, 0, 4, 0, 0, 9, 1, 0, 0, 21, 5, 0, 0, 0, 51, 25, 0, 0, 0, 0, 127, 105, 0, 0, 0, 0, 0, 323, 420, 21, 0, 0, 0, 0, 0, 835, 1596, 189, 0, 0, 0, 0, 0, 0, 2188, 5880, 1428, 0, 0, 0, 0, 0, 0, 0, 5798, 21120, 8778, 0, 0, 0, 0, 0, 0, 0, 0, 15511, 74415, 48741, 1485, 0, 0, 0, 0, 0, 0, 0, 0, 41835, 258115, 249249, 19305, 0 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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 A000085(n).

T(n,0)=A001006(n) (the Motzkin 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..83.

EXAMPLE

T(4,1)=1 because p=3412 is the only involution of {1,2,3,4} with genus 1. This follows easily 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). [Also, for p=3412=(13)(24) we have cp'=2341*3412=4123=(1432) and so g(p)=(1/2)(4+1-2-1)=1.]

Triangle starts:

[ 1]  1,

[ 2]  2, 0,

[ 3]  4, 0, 0,

[ 4]  9, 1, 0, 0,

[ 5]  21, 5, 0, 0, 0,

[ 6]  51, 25, 0, 0, 0, 0,

[ 7]  127, 105, 0, 0, 0, 0, 0,

[ 8]  323, 420, 21, 0, 0, 0, 0, 0,

[ 9]  835, 1596, 189, 0, 0, 0, 0, 0, 0,

[10]  2188, 5880, 1428, 0, 0, 0, 0, 0, 0, 0,

[11]  5798, 21120, 8778, 0, 0, 0, 0, 0, 0, 0, 0,

[12]  15511, 74415, 48741, 1485, 0, 0, 0, 0, 0, 0, 0, 0,

[13]  41835, 258115, 249249, 19305, 0, 0, 0, 0, 0, 0, 0, 0, 0,

[14]  113634, 883883, 1201200, 191763, 0, 0, 0, 0, 0, 0, 0, ...,

[15]  310572, 2994355, 5519514, 1525095, 0, 0, 0, 0, 0, 0, 0, ...,

[16]  853467, 10051860, 24408384, 10667800, 225225, 0, 0, 0, ...,

[17]  2356779, 33479460, 104552448, 67581800, 3828825, 0, 0, ...,

...

MAPLE

n := 8: with(combinat): P := permute(n): 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: 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: nrcyc := proc (p) local pc: 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; INV := {}: for i to factorial(n) do if inv(P[i]) = P[i] then INV := `union`(INV, {P[i]}) else end if end do: f[n] := sort(add(t^gen(INV[j]), j = 1 .. nops(INV))): seq(coeff(f[n], t, j), j = 0 .. degree(f[n])); # yields the entries of the specified row n

CROSSREFS

Cf. A177267.

Cf. A000085, A001006.

Sequence in context: A249093 A102392 A227311 * A051517 A289359 A053118

Adjacent sequences:  A178512 A178513 A178514 * A178516 A178517 A178518

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 21 13:32 EST 2018. Contains 317449 sequences. (Running on oeis4.)