This site is supported by donations to The OEIS Foundation.

 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!)
 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 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.

Last modified November 18 17:56 EST 2017. Contains 294894 sequences.