A161127 Triangle read by rows: T(n,k) is the number of fixed-point-free involutions of {1,2,...,2n} having k descents (n>=1; 1<=k<2n-1).

1, 1, 1, 1, 1, 3, 7, 3, 1, 1, 6, 27, 37, 27, 6, 1, 1, 10, 76, 220, 331, 220, 76, 10, 1, 1, 15, 176, 897, 2438, 3341, 2438, 897, 176, 15, 1, 1, 21, 357, 2885, 12825, 30807, 41343, 30807, 12825, 2885, 357, 21, 1, 1, 28, 658, 7871, 53312, 203927, 452931, 589569

Offset: 1

Author

Emeric Deutsch, Jun 09 2009

Keywords

• nonn
• tabf

Comments

Row n contains 2n-1 entries.

Sum of entries in row n = (2n-1)!! = A001147(n).

Sum_{k=1..2n-1} k*T(n,k) = A001879(n-1).

Examples

			T(3,2)=3 because we have 215634, 341265, and 351624.
Triangle starts:
  1;
  1,1,1;
  1,3,7,3,1;
  1,6,27,37,27,6,1;
  1,10,76,220,331,220,76,10,1;
  ...
		

Links

• J. Désarménien and D. Foata, Fonctions symetriques et series hypergeometriques basiques multivariees, Bull. Soc. Math. France, 113, 1985, 3-22.
• I. M. Gessel and C. Reutenauer, Counting permutations with given cycle structure and descent set, J. Combin. Theory, Ser. A, 64, 1993, 189-215.
• V. J. W. Guo and J. Zeng, The Eulerian distribution on involutions is indeed unimodal, J. Combin. Theory, Ser. A, 113, 2006, 1061-1071.

Crossrefs

Cf. A001147, A001879.

Programs

Maple

T := proc (n, k) if k <= 0 or n <= 0 then 0 elif n = 1 and k = 1 then 1 elif 2*n <= k then 0 else ((1/2)*(k*(k+1)+2*n-2)*T(n-1, k)+(1/2)*(2*(k-1)*(2*n-k-1)+2)*T(n-1, k-1)+(1/2)*((2*n-k)*(2*n-k+1)+2*n-2)*T(n-1, k-2))/n end if end proc: for n to 8 do seq(T(n, k), k = 1 .. 2*n-1) end do; # end of program
for n to 8 do P[n] := sort(expand(simplify((1-t)^(2*n+1)*(sum(binomial((1/2)*i*(i+1)+n-1, n)*t^i, i = 0 .. infinity))))) end do: for n to 8 do seq(coeff(P[n], t, j), j = 1 .. 2*n-1) end do; # end of program

Mathematica

T[n_, k_] := Which[k <= 0 || n <= 0, 0, n == 1 && k == 1, 1, 2n <= k, 0, True, ((1/2)*(k*(k + 1) + 2n - 2)*T[n - 1, k] + (1/2)*(2*(k - 1)*(2n - k - 1) + 2)*T[n - 1, k - 1] + (1/2)*((2n - k)*(2n - k + 1) + 2n - 2)*T[n - 1, k - 2])/n];
Table[T[n, k], {n, 1, 8}, {k, 1, 2n - 1}] // Flatten (* Jean-François Alcover, Sep 05 2024, after first Maple program *)

Formula

Recurrence: 2nT(n,k) = [k(k+1)+2n-2]T(n-1,k)+2[(k-1)(2n-k-1)+1]T(n-1,k-1)+[(2n-k)(2n-k+1)+2n-2]T(n-1,k-2) (k>=1, n>=2) (see Eq. (2.1) in the Guo-Zeng paper; see first Maple program).

Generating polynomial of row n is P(n,t) = (1 - t)^{2n+1}*Sum(C(j(j+1)/2 + n - 1, n)*t^j, j=0..oo) (see Eq. (2.2) in the Guo-Zeng paper; see 2nd Maple program).