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

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, 0, 453, 5035, 8884, 2315, 0, 0, 0, 0, 1367, 23653, 74177, 46285, 2847, 0, 0, 0, 0, 4191, 106414, 546626, 667640, 143586, 0, 0, 0, 0, 0, 13015, 463740, 3658723, 7777935, 3896494, 209624, 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 A000255 (permutations with no substring [x,x+1]).

First column is A078481.

Links

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

Example

Triangle starts:
[ 1]  1,
[ 2]  1, 0,
[ 3]  3, 0, 0,
[ 4]  7, 4, 0, 0,
[ 5]  19, 29, 5, 0, 0,
[ 6]  53, 180, 76, 0, 0, 0,
[ 7]  153, 1004, 901, 61, 0, 0, 0,
[ 8]  453, 5035, 8884, 2315, 0, 0, 0, 0,
[ 9]  1367, 23653, 74177, 46285, 2847, 0, 0, 0, 0,
[10]  4191, 106414, 546626, 667640, 143586, 0, 0, 0, 0, 0,
[11]  13015, 463740, 3658723, 7777935, 3896494, 209624, 0, 0, 0, 0, 0,
[12]  40857, 1972339, 22712736, 77535694, 74678363, 13959422, 0, 0, ...,
[13]  129441, 8228981, 132804891, 685673340, 1131199122, 485204757, 23767241, 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), A185209 (genus of connected permutations).

Sequence in context: A046765 A046777 A227724 * A243163 A209490 A346879

Adjacent sequences: A218535 A218536 A218537 * A218539 A218540 A218541

Keyword

nonn,hard,tabl

Author

Joerg Arndt, Nov 01 2012

Status

approved