

A178517


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


3



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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

The genus g(p) of a permutation p of {1,2,...,n} is defined by g(p)=(1/2)[n+1z(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(n1) .


REFERENCES

S. Dulucq and R. Simion, Combinatorial statistics on alternating permutations, J. Algebraic Combinatorics, 8 (1998), 169191.


LINKS

Table of n, a(n) for n=1..61.


EXAMPLE

T(3,0)=4 because all nonderangements 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 DulucqSimion 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, ...,
...


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


CROSSREFS

Cf. A177267 (genus of all permutations).
Cf. A178514 (genus of derangements), A178515 (genus of involutions), A178516 (genus of updown permutations), A178518 (permutations of [n] having genus 0 and p(1)=k), A185209 (genus of connected permutations).
Cf. A002467, A106640.
Sequence in context: A271910 A249346 A035539 * A049207 A092219 A262227
Adjacent sequences: A178514 A178515 A178516 * A178518 A178519 A178520


KEYWORD

nonn,hard,tabl


AUTHOR

Emeric Deutsch, May 30 2010


EXTENSIONS

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


STATUS

approved



