A178517 Triangle read by rows: T(n,k) is the number of non-derangement permutations of {1,2,...,n} having genus k (see first comment for definition of genus).

1, 1, 0, 4, 0, 0, 11, 4, 0, 0, 36, 40, 0, 0, 0, 117, 290, 48, 0, 0, 0, 393, 1785, 1008, 0, 0, 0, 0, 1339, 9996, 12712, 1440, 0, 0, 0, 0, 4630, 52584, 123858, 48312, 0, 0, 0, 0, 0, 16193, 264720, 1027446, 904840, 80640, 0, 0, 0, 0, 0, 57201, 1290135, 7627158, 12449800, 3807936, 0

Offset: 1

Author

Emeric Deutsch, May 30 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 A002467(n).

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

T(n,0) = A106640(n-1) .

Examples

			T(3,0)=4 because all non-derangements of {1,2,3}, namely 123=(1)(2)(3), 132=(1)(23), 213=(12)(3), and 321=(13)(2) have genus 0. 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).
Triangle starts:
[ 1]  1,
[ 2]  1, 0,
[ 3]  4, 0, 0,
[ 4]  11, 4, 0, 0,
[ 5]  36, 40, 0, 0, 0,
[ 6]  117, 290, 48, 0, 0, 0,
[ 7]  393, 1785, 1008, 0, 0, 0, 0,
[ 8]  1339, 9996, 12712, 1440, 0, 0, 0, 0,
[ 9]  4630, 52584, 123858, 48312, 0, 0, 0, 0, 0,
[10]  16193, 264720, 1027446, 904840, 80640, 0, 0, 0, 0, 0,
[11]  57201, 1290135, 7627158, 12449800, 3807936, 0, 0, 0, 0, 0, 0,
[12]  203799, 6133930, 52188774, 140356480, 96646176, 7257600, 0, ...,
[13]  731602, 28603718, 335517468, 1373691176, 1749377344, 448306560, 0, ...,
...
		

References

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

Crossrefs

Cf. A177267 (genus of all permutations).

Cf. A178514 (genus of derangements), A178515 (genus of involutions), A178516 (genus of up-down permutations), A178518 (permutations of [n] having genus 0 and p(1)=k), A185209 (genus of connected permutations).

Cf. A002467, A106640.

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

Extensions

Terms beyond row 7 from Joerg Arndt, Nov 01 2012.