cp's OEIS Frontend

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

%I A178514 #15 Nov 25 2019 00:59:00
%S A178514 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,
%T A178514 0,91,2016,8078,4648,0,0,0,0,232,7476,50316,67408,8064,0,0,0,0,603,
%U A178514 27000,281862,719640,305856,0,0,0,0,0,1585,95535,1459920,6298930,6223800,604800,0
%N 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).
%C A178514 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.
%C A178514 The sum of the entries in row n is A000166(n) (the derangement numbers).
%C A178514 The number of entries in row n is ceiling(n/2).
%C A178514 T(n,0) = A005043(n) (the Riordan numbers).
%H A178514 S. Dulucq and R. Simion, <a href="http://dx.doi.org/10.1023/A:1008689811936">Combinatorial statistics on alternating permutations</a>, J. Algebraic Combinatorics, 8, 1998, 169-191.
%e A178514 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.
%e A178514 Triangle starts:
%e A178514 [ 1]    0,
%e A178514 [ 2]    1,      0,
%e A178514 [ 3]    1,      1,       0,
%e A178514 [ 4]    3,      6,       0,        0,
%e A178514 [ 5]    6,     30,       8,        0,        0,
%e A178514 [ 6]   15,    130,     120,        0,        0,        0,
%e A178514 [ 7]   36,    525,    1113,      180,        0,        0, 0,
%e A178514 [ 8]   91,   2016,    8078,     4648,        0,        0, 0, 0,
%e A178514 [ 9]  232,   7476,   50316,    67408,     8064,        0, 0, 0, 0,
%e A178514 [10]  603,  27000,  281862,   719640,   305856,        0, 0, 0, 0, 0,
%e A178514 [11] 1585,  95535, 1459920,  6298930,  6223800,   604800, 0, 0, 0, 0, 0,
%e A178514 [12] 4213, 332530, 7117902, 47851540, 90052336, 30856320, 0, 0, 0, 0, 0, 0,
%e A178514 ...
%p A178514 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
%Y A178514 Cf. A177267.
%Y A178514 Cf. A000166, A005043.
%K A178514 nonn,hard,tabl
%O A178514 1,7
%A A178514 _Emeric Deutsch_, May 29 2010
%E A178514 Terms beyond row 7 from _Joerg Arndt_, Nov 01 2012