A180193 -id:A180193 - cp's OEIS frontend

A180194 Triangle read by rows: T(n,k) is the number of permutations of [n] having k blocks of even length.

1, 1, 1, 1, 4, 2, 13, 10, 1, 63, 48, 9, 356, 293, 68, 3, 2403, 2036, 557, 44, 18655, 16213, 4902, 539, 11, 163988, 145068, 47203, 6356, 265, 1608667, 1442858, 495710, 76833, 4679, 53, 17415725, 15792362, 5659377, 971992, 75490, 1854, 206202408

Offset: 0

Emeric Deutsch, Sep 09 2010

A block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions. For example, the permutation 5412367 has 4 blocks: 5, 4, 123, and 67.

Number of entries in row n is 1+floor(n/2).

			T(3,1)=2 because we have (23)1 and 3(12) (the blocks of even length are shown between parentheses).
Triangle starts:
  1;
  1;
  1,1;
  4,2;
  13,10,1;
  63,48,9;
  356,293,68,3;

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

Cf. A000166, A000255, A180193, A180195

d[ -1] := 0: d[0] := 1: for n to 50 do d[n] := n*d[n-1]+(-1)^n end do: T := proc (n, k) if `mod`(n, 2) = 0 then sum(binomial(k+2*i, k)*binomial((1/2)*n+i-1, k+2*i-1)*(d[k+2*i]+d[k+2*i-1]), i = 0 .. (1/2)*n-k) else sum(binomial(k+2*i+1, k)*binomial((1/2)*n+i-1/2, k+2*i)*(d[k+2*i+1]+d[k+2*i]), i = 0 .. (1/2)*n-1/2-k) end if end proc: for n from 0 to 12 do seq(T(n, k), k = 0 .. floor((1/2)*n)) end do; # yields sequence in triangular form

T(n,k) = Sum(binomial(k+2i,k)*binomial(n/2+i-1,k+2i-1)*[d(k+2i)+d(k+2i-1)], i=0..n/2-k) if n is even,
T(n,k) = Sum(binomial(k+2i+1,k)*binomial(n/2-1/2+i,k+2i)*[d(k+2i+1)+d(k+2i)], i=0..n/2-1/2-k) if n is odd,
Here d(i)=A000166(i) are the derangement numbers.
Sum of entries in row n = n! = A000142(n).
T(2n,n) = d(n)+d(n-1) = A000255(n-1), where d(i)=A000166(n) are the derangement numbers.
T(2n+1,n) = d(n+2).
Sum(k*T(n,k), k>=0) = A180195(n-1).

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

Original entry on oeis.org

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

Offset: 1

Emeric Deutsch, Sep 09 2010

nonn

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

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

Cf. A001564, A180193, A180194.

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

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

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

More terms from Michel Marcus, May 19 2024

cp's OEIS Frontend

A180194 Triangle read by rows: T(n,k) is the number of permutations of [n] having k blocks of even length.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

cp's OEIS Frontend

A180194 Triangle read by rows: T(n,k) is the number of permutations of [n] having k blocks of even length.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Formula

Extensions

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