cp's OEIS Frontend

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

%I A218538 #8 Apr 10 2013 17:18:12
%S A218538 1,1,0,3,0,0,7,4,0,0,19,29,5,0,0,53,180,76,0,0,0,153,1004,901,61,0,0,
%T A218538 0,453,5035,8884,2315,0,0,0,0,1367,23653,74177,46285,2847,0,0,0,0,
%U A218538 4191,106414,546626,667640,143586,0,0,0,0,0,13015,463740,3658723,7777935,3896494,209624,0
%N A218538 Triangle read by rows: T(n,k) is the number of permutations of{1,2,...,n}  avoiding [x,x+1] having genus k (see first comment for definition of genus).
%C A218538 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 A218538 Row sums are A000255 (permutations with no substring [x,x+1]).
%C A218538 First column is A078481.
%e A218538 Triangle starts:
%e A218538 [ 1]  1,
%e A218538 [ 2]  1, 0,
%e A218538 [ 3]  3, 0, 0,
%e A218538 [ 4]  7, 4, 0, 0,
%e A218538 [ 5]  19, 29, 5, 0, 0,
%e A218538 [ 6]  53, 180, 76, 0, 0, 0,
%e A218538 [ 7]  153, 1004, 901, 61, 0, 0, 0,
%e A218538 [ 8]  453, 5035, 8884, 2315, 0, 0, 0, 0,
%e A218538 [ 9]  1367, 23653, 74177, 46285, 2847, 0, 0, 0, 0,
%e A218538 [10]  4191, 106414, 546626, 667640, 143586, 0, 0, 0, 0, 0,
%e A218538 [11]  13015, 463740, 3658723, 7777935, 3896494, 209624, 0, 0, 0, 0, 0,
%e A218538 [12]  40857, 1972339, 22712736, 77535694, 74678363, 13959422, 0, 0, ...,
%e A218538 [13]  129441, 8228981, 132804891, 685673340, 1131199122, 485204757, 23767241, 0, ...,
%e A218538 ...
%Y A218538 Cf. A177267 (genus of all permutations).
%Y A218538 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), A185209 (genus of connected permutations).
%K A218538 nonn,hard,tabl
%O A218538 1,4
%A A218538 _Joerg Arndt_, Nov 01 2012