A127160 Triangle T(n,k), 0<=k<=n, read by rows given by [0,1,2,3,4,5,6,...] DELTA [1,1,1,1,1,1,1,1,...] where DELTA is the operator defined in A084938.

1, 0, 1, 0, 1, 2, 0, 3, 7, 5, 0, 15, 39, 37, 14, 0, 105, 296, 326, 176, 42, 0, 945, 2838, 3458, 2228, 794, 132, 0, 10395, 32859, 43191, 31235, 13553, 3473, 429, 0, 135135, 445767, 622259, 489899, 241225, 76417, 14893, 1430

Offset: 0

Author

Philippe Deléham, Mar 25 2007

Keywords

• nonn
• tabl

Comments

This triangle enumerates fixed-point-free involutions in S_n by number of left-to-right maxima. For instance there are 15 fixed point free involutions on 6 elements: 3 have 1 left to right maxima, namely (1,6)(2,3)(4,5), (1,6)(2,4)(3,5) and (3,6)(2,5)(3,4); 7 have 2 left-to right maxima and 5 have 3 left to right maxima. - Robert Cori (rcori(AT)cs.brown.edu), Apr 25 2008

A053979*A130595 as infinite lower triangular matrices. - Philippe Deléham, Jan 06 2012

Examples

			Triangle begins:
1;
0, 1;
0, 1, 2;
0, 3, 7, 5;
0, 15, 39, 37, 14;
0, 105, 296, 326, 176, 42;
0, 945, 2838, 3458, 2228, 794, 132;
0, 10395, 32859, 43191, 31235, 13553, 3473, 429;
0, 135135, 445767, 622259, 489899, 241225, 76417, 14893, 1430;
		

Crossrefs

A053979.

Programs

Mathematica

nmax = 8;
DELTA[r_, s_, m_] := Module[{p, q, t, x, y}, q[k_] := x r[[k + 1]] + y s[[k + 1]]; p[0, ] = 1; p[, -1] = 0; p[n_ /; n >= 1, k_ /; k >= 0] := p[n, k] = p[n, k-1] + q[k] p[n-1, k+1] // Expand; t[n_, k_] := Coefficient[ p[n, 0], x^(n - k) y^k]; t[0, 0] = p[0, 0]; Table[t[n, k], {n, 0, m}, {k, 0, n}]];
DELTA[Range[0, nmax], Table[1, {nmax+1}], nmax] // Flatten (* Jean-François Alcover, Nov 12 2019 *)

Formula

Sum_{k=0..n} T(n,k)*x^(n-k) = A000012(n), A000108(n), A001147(n), A128709(n) for x = -1,0,1,2 respectively.

From Peter Bala, Dec 22 2011: (Start)

The o.g.f. in the form G(x,t) = x/(1 - t*x^2/(1 - (t+1)*x^2/(1 - (t+2)*x^2/(1 - (t+3)*x^2/(1 - ... ))))) = x + t*x^3 + (t+2*t^2)*x^5 + ... satisfies the Riccati differential equation (1 - (t-1)*x*G)*G = x + x^3*dG/dx. Writing G(x,t) = sum {n = 1..inf} R(n,t)*x^(2*n-1), the row generating polynomials R(n,t) satisfy the recurrence R(n+1,t) = (2*n-1)*R(n,t) + (t-1)*sum {k = 1..n} R(k,t)*R(n+1-k,t) with initial condition R(1,t) = 1.

G(x,t+1) = x + (1+t)*x^3 + (3+5*t+2*t^2)*x^5 + ... is an o.g.f. for A053979.

(End)

Extensions

Corrected and extended by Peter Bala, Dec 20 2011