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

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

Offset: 1

Author

Emeric Deutsch, May 29 2010

Keywords

• nonn
• hard
• tabl

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

T(n,0) = A005043(n) (the Riordan numbers).

Examples

			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,
...
		

Links

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

Crossrefs

Cf. A177267.

Cf. A000166, A005043.

Programs

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

Extensions

Terms beyond row 7 from Joerg Arndt, Nov 01 2012