A123515 Triangle read by rows: T(n,k) is the number of involutions of {1,2,...,n} with exactly k fixed points and which contain the pattern 231 exactly once (n>=4, 2<=k<=n-2).

1, 0, 2, 2, 0, 3, 0, 8, 0, 4, 5, 0, 18, 0, 5, 0, 26, 0, 32, 0, 6, 12, 0, 75, 0, 50, 0, 7, 0, 76, 0, 164, 0, 72, 0, 8, 28, 0, 264, 0, 305, 0, 98, 0, 9, 0, 208, 0, 680, 0, 510, 0, 128, 0, 10, 64, 0, 840, 0, 1460, 0, 791, 0, 162, 0, 11, 0, 544, 0, 2480, 0, 2772, 0, 1160, 0, 200, 0, 12

Offset: 4

Author

Emeric Deutsch, Oct 13 2006

Keywords

• nonn
• tabl

Comments

Also the number of involutions of {1,2,...,n} with exactly k fixed points and which contain the pattern 312 exactly once (n>=4, 2<=k<=n-2). Example: T(5,3)=2 because we have 15342 and 42315 (also the involution 52341 has 3 fixed points but it contains 3 times the pattern 312: 523, 524 and 534).

Examples

			T(5,3)=2 because we have 15342 and 42315 (also the involution 52341 has 3 fixed points but it contains 3 times the pattern 231: 231, 241 and 341).
Triangle starts:
   1;
   0,   2;
   2,   0,   3;
   0,   8,   0,    4;
   5,   0,  18,    0,    5;
   0,  26,   0,   32,    0,    6;
  12,   0,  75,    0,   50,    0,   7;
   0,  76,   0,  164,    0,   72,   0,    8;
  28,   0, 264,    0,  305,    0,  98,    0,   9;
   0, 208,   0,  680,    0,  510,   0,  128,   0,  10;
  64,   0, 840,    0, 1460,    0, 791,    0, 162,   0, 11;
   0, 544,   0, 2480,    0, 2772,   0, 1160,   0, 200,  0, 12;
		

Links

• G. C. Greubel, Rows n = 4..54 of the triangle, flattened
• E. Deutsch, A. Robertson and D. Saracino, Refined restricted involutions, European Journal of Combinatorics 28 (2007), 481-498 (see pp. 492 and 498).

Crossrefs

Cf. A045623, A120926, A123514, A112554.

Programs

Maple

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

Mathematica

T[n_, k_]:= ((1+(-1)^(n-k))/2)*2^((n-k-6)/2)*(k-1)* Sum[Binomial[2, j]*
  Binomial[(n+k-2*(j+2))/2, (n-k-2)/2], {j, 0, 2}];
Table[T[n, k], {n,4,16}, {k,2,n-2}]//Flatten (* G. C. Greubel, Jan 16 2022 *)

Sage

def A123515(n,k): return ((1+(-1)^(n+k))/2)*2^((n-k-6)/2)*(k-1)*sum( binomial(2, j)*binomial((n+k-2*j-2)/2, (n-k-2)/2) for j in (0..2) )
flatten([[A123515(n,k) for k in (2..n-2)] for n in (4..16)]) # G. C. Greubel, Jan 16 2022

Formula

T(n, k) = 2^((n-k-6)/2)*(k-1)*( binomial((n+k)/2-2, (n-k)/2-1) + 2*binomial((n+k)/2-3, (n-k)/2-1) + binomial((n+k)/2-4, (n-k)/2-1) ) for n>=4, n+k even; T(n,k) = 0 otherwise.

From G. C. Greubel, Jan 16 2022: (Start)

Sum_{k=2..n-4} T(n, k) = A045623(n).

Sum_{k=2..floor(n/2)} T(n-k+2, k) = (1/9)*[n=4] + (1+(-1)^n)*n*3^((n-8)/2). (End)