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

Author

Joerg Arndt, Nov 01 2012

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.

Row sums are A003319.

First column is A000108.

Examples

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