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

%I #8 Nov 01 2012 11:13:03

%S 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,

%T 0,0,429,6768,16184,5712,0,0,0,0,1430,32354,128578,102917,8064,0,0,0,

%U 0,4862,151336,923799,1379384,369944,0,0,0,0,0,16796,696027,6164460,15283308,9233512,604800,0

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

%C 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 Row sums are A003319.

%C First column is A000108.

%e Triangle starts:

%e [ 1] 1,

%e [ 2] 1, 0,

%e [ 3] 2, 1, 0,

%e [ 4] 5, 8, 0, 0,

%e [ 5] 14, 49, 8, 0, 0,

%e [ 6] 42, 268, 151, 0, 0, 0,

%e [ 7] 132, 1375, 1760, 180, 0, 0, 0,

%e [ 8] 429, 6768, 16184, 5712, 0, 0, 0, 0,

%e [ 9] 1430, 32354, 128578, 102917, 8064, 0, 0, 0, 0,

%e [10] 4862, 151336, 923799, 1379384, 369944, 0, 0, 0, 0, 0,

%e [11] 16796, 696027, 6164460, 15283308, 9233512, 604800, 0, 0, 0, 0, 0,

%e [12] 58786, 3158280, 38863188, 147930256, 165848135, 36885312, 0, 0, ...,

%e [13] 208012, 14173566, 234193764, 1293232525, 2397551416, 1193273372, 68428800, 0, ...,

%e ...

%Y Cf. A177267 (genus of all permutations).

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

%K nonn,hard,tabl

%O 1,4

%A _Joerg Arndt_, Nov 01 2012