OFFSET
4,3
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).
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).
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)
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 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;
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 *)
PROG
(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
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Oct 13 2006
STATUS
approved