A108723 Triangle read by rows: T(n,k) is number of permutations of [n] with ascending runs consisting of consecutive integers and having k fixed points.

1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 6, 0, 1, 0, 1, 10, 4, 0, 1, 0, 1, 26, 0, 4, 0, 1, 0, 1, 42, 16, 0, 4, 0, 1, 0, 1, 106, 0, 16, 0, 4, 0, 1, 0, 1, 170, 64, 0, 16, 0, 4, 0, 1, 0, 1, 426, 0, 64, 0, 16, 0, 4, 0, 1, 0, 1, 682, 256, 0, 64, 0, 16, 0, 4, 0, 1, 0, 1, 1706, 0, 256, 0, 64, 0, 16, 0, 4, 0, 1, 0, 1

Offset

0,7

Comments

T(n,0)=A061547(n). Sum of row n is 2^(n-1) (n>=1).

Links

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

Formula

T(n, 0)=(3/8)2^n + (1/24)(-2)^n - 2/3; T(n, n)=1; T(n, k)=2^(n-k-2) if k>0 and n-k is even; T(n, k)=0 if k>0 and n-k is odd or if k>n.

Example

T(3,0)=2 because we have (23)(1) and (3)(12); T(3,1)=1 because we have (3)(2)(1); T(3,3)=1 because we have (123) (the ascending runs are shown between parentheses).
Triangle begins:
1;
0,1;
1,0,1;
2,1,0,1;
6,0,1,0,1;
10,4,0,1,0,1;

Maple

T:=proc(n, k) if k=n then 1 elif k>n then 0 elif k=0 then 3*2^n/8+(-2)^n/24-2/3 elif k>0 and n-k mod 2 = 0 then 2^(n-k-2) else 0 fi end: for n from 0 to 13 do seq(T(n, k), k=0..n) od; # yields sequence in triangular form

Crossrefs

Cf. A061547.

Sequence in context: A180782 A213597 A302978 * A291584 A352451 A349618

Adjacent sequences: A108720 A108721 A108722 * A108724 A108725 A108726

Keyword

nonn,tabl

Author

Emeric Deutsch, Jun 21 2005

Status

approved