login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A180192 Triangle read by rows: T(n,k) is the number of permutations of [n] having k fixed blocks. 1
1, 0, 1, 1, 1, 2, 4, 0, 9, 12, 3, 44, 57, 18, 1, 265, 321, 123, 11, 1854, 2176, 888, 120, 2, 14833, 17008, 7218, 1208, 53, 133496, 150505, 65460, 12550, 860, 9, 1334961, 1485465, 657690, 137970, 12405, 309, 14684570, 16170036, 7257240, 1623440 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,6

COMMENTS

A fixed block of a permutation p is a maximal sequence of consecutive fixed points of p. For example, the permutation 213458769 has 3 fixed blocks: 345, 7, and 9.

Row n has 1+ceil(n/2) entries.

T(n,0) = d(n) = A000166(n).

T(n,1) = A177265(n).

T(2n-1,n) = d(n-1).

T(2n,n) = d(n+1)+d(n) = A000255(n).

Sum of entries in row n = n! = A000142(n).

Sum(k*T(n,k), k>=0) = (n-1)!*(n-1) = A001563(n-1).

LINKS

Alois P. Heinz, Rows n = 0..200, flattened

FORMULA

T(n,k) = Sum(binom(j-1,k-1)*binom(n+1-j,k)*d(n-j), j=k..n+1-k), where d(i)=A000166(i) are the derangement numbers.

The term binom(j-1,k-1)*binom(n+1-j,k)*d(n-j) in the above sum gives the number of permutations of [n] having k fixed blocks and a total number of j fixed points.

EXAMPLE

T(4,2)=3 because we have (1)4(3)2, (1)32(4), and 3(2)1(4) (the fixed blocks are shown between parentheses).

Triangle starts:

1;

0,1;

1,1;

2,4,0;

9,12,3;

44,57,18,1;

265,321,123,11;

MAPLE

d[0] := 1: for n to 50 do d[n] := n*d[n-1]+(-1)^n end do: T := proc (n, k) options operator, arrow: sum(binomial(j-1, k-1)*binomial(n+1-j, k)*d[n-j], j = k .. n+1-k) end proc: for n from 0 to 11 do seq(T(n, k), k = 0 .. ceil((1/2)*n)) end do; # yields sequence in triangular form

CROSSREFS

Cf. A000142, A000166, A000255, A001563, A177265.

Sequence in context: A071607 A095059 A021419 * A066529 A052080 A261754

Adjacent sequences:  A180189 A180190 A180191 * A180193 A180194 A180195

KEYWORD

nonn,tabf

AUTHOR

Emeric Deutsch, Sep 08 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 June 19 06:47 EDT 2019. Contains 324218 sequences. (Running on oeis4.)