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,6

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

Links

Table of n, a(n) for n=0..44.

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)

Example

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;

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 *)

Crossrefs

A053979.

Sequence in context: A332356 A309655 A260591 * A334847 A131330 A022833

Adjacent sequences: A127157 A127158 A127159 * A127161 A127162 A127163

Keyword

nonn,tabl

Author

Philippe Deléham, Mar 25 2007

Extensions

Corrected and extended by Peter Bala, Dec 20 2011

Status

approved