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

1, 1, 0, 2, 1, 0, 5, 8, 0, 0, 14, 49, 8, 0, 0, 42, 268, 151, 0, 0, 0, 132, 1375, 1760, 180, 0, 0, 0, 429, 6768, 16184, 5712, 0, 0, 0, 0, 1430, 32354, 128578, 102917, 8064, 0, 0, 0, 0, 4862, 151336, 923799, 1379384, 369944, 0, 0, 0, 0, 0, 16796, 696027, 6164460, 15283308, 9233512, 604800, 0

Offset

1,4

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.

Row sums are A003319.

First column is A000108.

Links

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

Example

Triangle starts:
[ 1]  1,
[ 2]  1, 0,
[ 3]  2, 1, 0,
[ 4]  5, 8, 0, 0,
[ 5]  14, 49, 8, 0, 0,
[ 6]  42, 268, 151, 0, 0, 0,
[ 7]  132, 1375, 1760, 180, 0, 0, 0,
[ 8]  429, 6768, 16184, 5712, 0, 0, 0, 0,
[ 9]  1430, 32354, 128578, 102917, 8064, 0, 0, 0, 0,
[10]  4862, 151336, 923799, 1379384, 369944, 0, 0, 0, 0, 0,
[11]  16796, 696027, 6164460, 15283308, 9233512, 604800, 0, 0, 0, 0, 0,
[12]  58786, 3158280, 38863188, 147930256, 165848135, 36885312, 0, 0, ...,
[13]  208012, 14173566, 234193764, 1293232525, 2397551416, 1193273372, 68428800, 0, ...,
...

Crossrefs

Cf. A177267 (genus of all permutations).

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

Sequence in context: A059720 A140589 A331955 * A316659 A241218 A266904

Adjacent sequences: A185206 A185207 A185208 * A185210 A185211 A185212

Keyword

nonn,hard,tabl

Author

Joerg Arndt, Nov 01 2012

Status

approved