A123514 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 321 exactly once (n>=3; 1<=k<=n-2).

1, 0, 2, 4, 0, 3, 0, 10, 0, 4, 14, 0, 18, 0, 5, 0, 40, 0, 28, 0, 6, 48, 0, 81, 0, 40, 0, 7, 0, 150, 0, 140, 0, 54, 0, 8, 165, 0, 330, 0, 220, 0, 70, 0, 9, 0, 550, 0, 616, 0, 324, 0, 88, 0, 10, 572, 0, 1287, 0, 1040, 0, 455, 0, 108, 0, 11, 0, 2002, 0, 2548, 0, 1638, 0, 616, 0, 130, 0, 12

Offset

3,3

Links

G. C. Greubel, Rows n = 3..53 of the triangle, flattened

E. Deutsch, A. Robertson and D. Saracino, Refined restricted involutions, European Journal of Combinatorics 28 (2007), 481-498 (see pp. 493 and 498).

Formula

T(n,k) = k*(k+3)*binomial(n+1,(n-k-2)/2)/(n+1), for n>=3, 1<=k<=n-2, n-k even.

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

Sum_{k=1..n-2} T(n, k) = A191389(n+1).

Sum_{k=1..floor((n-1)/2)} T(n-k, k) = ((1-(-1)^n)/2)*(12/(n+9))*binomial(n+2, (n- 3)/2). (End)

Example

T(4,2)=2 because we have 1432 and 3214 (also 4231 is an involution with 2 fixed points but contains twice the pattern 321: 421 and 431).
Triangle starts:
    1;
    0,   2;
    4,   0,    3;
    0,  10,    0,   4;
   14,   0,   18,   0,    5;
    0,  40,    0,  28,    0,   6;
   48,   0,   81,   0,   40,   0,   7;
    0, 150,    0, 140,    0,  54,   0,  8;
  165,   0,  330,   0,  220,   0,  70,  0,   9;
    0, 550,    0, 616,    0, 324,   0, 88,   0, 10;
  572,   0, 1287,   0, 1040,   0, 455,  0, 108,  0, 11;

Maple

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

Mathematica

T[n_, k_]:= ((1+(-1)^(n-k))/2)*k*(k+3)*Binomial[n+1, (n-k-2)/2]/(n+1);
Table[T[n, k], {n, 3, 15}, {k, n-2}]//Flatten (* G. C. Greubel, Jan 15 2022 *)

Prog

(Magma)
A123514:= func< n, k | ((1+(-1)^(n-k))/(2*(n+1)))*k*(k+3)*Binomial(n+1, Floor((n-k-2)/2)) >;
[A123514(n, k): k in [1..n-2], n in [3..15]]; // G. C. Greubel, Jan 15 2022
(Sage)
def A123514(n, k): return ((1+(-1)^(n-k))/(2*(n+1)))*k*(k+3)*binomial(n+1, (n-k-2)//2)
flatten([[A123514(n, k) for k in (1..n-2)] for n in (3..15)]) # G. C. Greubel, Jan 15 2022

Crossrefs

Cf. A003517, A112554, A123515, A191389.

Sequence in context: A281765 A155517 A325490 * A064178 A018220 A004580

Adjacent sequences: A123511 A123512 A123513 * A123515 A123516 A123517

Keyword

nonn,tabl

Author

Emeric Deutsch, Oct 13 2006

Status

approved