A180195 a(n) = (-1)^n*Sum((-1)^j*b(j), j=1..n), where b(n)=(n-1)!*(n^2 - n + 1) = A001564(n-1) (n>=1).

1, 2, 12, 66, 438, 3282, 27678, 259602, 2683758, 30338322, 372458478, 4936475922, 70266775278, 1069278031122, 17325341412078, 297824181275922, 5414097458148078, 103781942967323922, 2092232238097380078, 44254551017667611922, 979997194424697828078, 22675109031076772891922

Offset: 1

Author

Emeric Deutsch, Sep 09 2010

Keywords

• nonn

Comments

a(n) is the number of blocks of odd size in all permutations of [n].

a(n) is the number of blocks of even size in all permutations of [n+1].

A block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions. Example: a(2)=2 because in 12 and (2)(1) we have a total of 2 blocks of odd size (shown between parentheses). Also, in 123, 132, 213, (23)1, 3(12), and 321 we have a total of 2 blocks of even size (shown between parentheses).

Links

• A. N. Myers, Counting permutations by their rigid patterns, J. Combin. Theory, Series A, Vol. 99, No. 2 (2002), pp. 345-357.

Crossrefs

Cf. A001564, A180193, A180194.

Programs

Maple

b := proc (n) options operator, arrow: factorial(n-1)*(n^2-n+1) end proc: a := proc (n) options operator, arrow: (-1)^n*(sum((-1)^j*b(j), j = 1 .. n)) end proc; seq(a(n), n = 1 .. 20);

PARI

a(n) = (-1)^n*sum(j=1, n, (-1)^j*(j-1)!*(j^2-j+1)); \\ Michel Marcus, May 19 2024

Formula

a(n) = Sum(k*A180193(n,k), k>=0).

a(n) = Sum(k*A180194(n+1,k), k>=0).

Conjecture D-finite with recurrence a(n) +(-n-1)*a(n-1) -4*a(n-2) +(n-2)*a(n-3)=0. - R. J. Mathar, Jul 24 2022

Extensions

More terms from Michel Marcus, May 19 2024