login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A180193 Triangle read by rows: T(n,k) is the number of permutations of [n] having k blocks of odd length (0<=k<=n). 2
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,8

COMMENTS

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.

Sum of entries in row n = n! = A000142(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).

REFERENCES

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

LINKS

Table of n, a(n) for n=0..64.

FORMULA

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

EXAMPLE

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;

MAPLE

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

CROSSREFS

Cf. A000166, A000255, A001564, A180194, A180195

Sequence in context: A085919 A105824 A171911 * A229964 A309722 A070298

Adjacent sequences:  A180190 A180191 A180192 * A180194 A180195 A180196

KEYWORD

nonn,tabl

AUTHOR

Emeric Deutsch, Sep 09 2010

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 13 03:43 EDT 2021. Contains 342934 sequences. (Running on oeis4.)