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!)
A178514 Triangle read by rows: T(n,k) is the number of derangements of {1,2,...,n} having genus k (see first comment for definition of genus). 5
0, 1, 0, 1, 1, 0, 3, 6, 0, 0, 6, 30, 8, 0, 0, 15, 130, 120, 0, 0, 0, 36, 525, 1113, 180, 0, 0, 0, 91, 2016, 8078, 4648, 0, 0, 0, 0, 232, 7476, 50316, 67408, 8064, 0, 0, 0, 0, 603, 27000, 281862, 719640, 305856, 0, 0, 0, 0, 0, 1585, 95535, 1459920, 6298930, 6223800, 604800, 0 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,7

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 A000166(n) (the derangement numbers).

The number of entries in row n is ceil(n/2).

T(n,0)=A005043(n) (the Riordan 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..62.

EXAMPLE

T(3,1)=1 because 312 is the only derangement of {1,2,3} with genus 1. Indeed, we have p=312=(132), cp'=231*231=312=(132) and so g(p)=(1/2)(3+1-1-1)=1, while for the other derangement of {1,2,3}, q=231=(123), we have cq'=231*312=123=(1)(2)(3) and so g(q)=(1/2)(3+1-1-3)=0.

Triangle starts:

[ 1]  0,

[ 2]  1, 0,

[ 3]  1, 1, 0,

[ 4]  3, 6, 0, 0,

[ 5]  6, 30, 8, 0, 0,

[ 6]  15, 130, 120, 0, 0, 0,

[ 7]  36, 525, 1113, 180, 0, 0, 0,

[ 8]  91, 2016, 8078, 4648, 0, 0, 0, 0,

[ 9]  232, 7476, 50316, 67408, 8064, 0, 0, 0, 0,

[10]  603, 27000, 281862, 719640, 305856, 0, 0, 0, 0, 0,

[11]  1585, 95535, 1459920, 6298930, 6223800, 604800, 0, 0, 0, 0, 0,

[12]  4213, 332530, 7117902, 47851540, 90052336, 30856320, 0, 0, 0, 0, 0, 0,

...

MAPLE

n := 7: 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: DER := {}: for i to factorial(n) do if nrfp(P[i]) = 0 then DER := `union`(DER, {P[i]}) else end if end do: f[n] := sort(add(t^gen(DER[j]), j = 1 .. nops(DER))): seq(coeff(f[n], t, j), j = 0 .. ceil((1/2)*n)-1); # yields the entries of the specified row n

CROSSREFS

Cf. A177267.

Cf. A000166, A005043.

Sequence in context: A068635 A156695 A175645 * A154924 A071105 A218113

Adjacent sequences:  A178511 A178512 A178513 * A178515 A178516 A178517

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 23 19:00 EST 2017. Contains 295128 sequences.