A180194 -id:A180194 - cp's OEIS frontend

A180193 Triangle read by rows: T(n,k) is the number of permutations of [n] having k blocks of odd length (0<=k<=n).

1, 0, 1, 1, 0, 1, 0, 3, 0, 3, 2, 0, 11, 0, 11, 0, 14, 0, 53, 0, 53, 6, 0, 96, 0, 309, 0, 309, 0, 78, 0, 724, 0, 2119, 0, 2119, 24, 0, 852, 0, 6070, 0, 16687, 0, 16687, 0, 504, 0, 9300, 0, 56418, 0, 148329, 0, 148329, 120, 0, 8040, 0, 106170, 0, 577556, 0, 1468457, 0

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.

			T(3,1)=3 because we have (123), 23(1), and (3)12 (the blocks of odd length are shown between parentheses). T(4,0)=2 because we have 1234 and 3412.
Triangle starts:
  1;
  0,1;
  1,0,1;
  0,3,0,3;
  2,0,11,0,11;
  0,14,0,53,0,53;

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, A001564, A180194, 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+k, 2) = 1 then 0 else sum(binomial(k+j, j)*binomial((1/2)*n+(1/2)*k-1, k+j-1)*(d[k+j]+d[k+j-1]), j = 0 .. (1/2)*n-(1/2)*k) end if end proc; for n from 0 to 10 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form

T(n,k) = Sum(binomial(k+j,j)*binomial((n+k+2)/2,k+j-1)*[d(k+j)+d(k+j-1)], j=0..(n-k)/2) if n and k are of the same parity; T(n,k)=0 if n and k have opposite parities (0<=k<=n).
T(n,n) = T(n,n-2) = d(n)+d(n-1) = A000255(n-1), where d(i)=A000166(i) are the derangement numbers.
T(2n+1,1) = A001564(n).
Sum(k*T(n,k),k>=0) = A180195(n).
Sum of entries in row n = n! = A000142(n).

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

A180193 Triangle read by rows: T(n,k) is the number of permutations of [n] having k blocks of odd length (0<=k<=n).

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

A180193 Triangle read by rows: T(n,k) is the number of permutations of [n] having k blocks of odd length (0<=k<=n).

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