A112857 Triangle T(n,k) read by rows: number of Green's R-classes in the semigroup of order-preserving partial transformations (of an n-element chain) consisting of elements of height k (height(alpha) = |Im(alpha)|).

1, 1, 1, 1, 3, 1, 1, 7, 5, 1, 1, 15, 17, 7, 1, 1, 31, 49, 31, 9, 1, 1, 63, 129, 111, 49, 11, 1, 1, 127, 321, 351, 209, 71, 13, 1, 1, 255, 769, 1023, 769, 351, 97, 15, 1, 1, 511, 1793, 2815, 2561, 1471, 545, 127, 17, 1, 1, 1023, 4097, 7423, 7937, 5503, 2561, 799, 161, 19, 1

Offset: 0

Author

Abdullahi Umar, Aug 25 2008

Keywords

• nonn
• tabl
• easy

Comments

Sum of rows of T(n, k) is A007051; T(n,k) = |A118801(n,k)|.

Row-reversed variant of A119258. - R. J. Mathar, Jun 20 2011

Pairwise sums of row terms starting from the right yields triangle A038207. - Gary W. Adamson, Feb 06 2012

Riordan array (1/(1 - x), x/(1 - 2*x)). - Philippe Deléham, Jan 17 2014

Appears to coincide with the triangle T(n,m) (n >= 1, 1 <= m <= n) giving number of set partitions of [n], avoiding 1232, with m blocks [Crane, 2015]. See also A250118, A250119. - N. J. A. Sloane, Nov 25 2014

(A007318)^2 = A038207 = T*|A167374|. See A118801 for other relations to the Pascal matrix. - Tom Copeland, Nov 17 2016

Examples

			T(3,2) = 5 because in a regular semigroup of transformations the Green's R-classes coincide with convex partitions of subsets of {1,2,3} with convex classes (modulo the subsets): {1}, {2}/{1}, {3}/{2}, {3}/{1,2}, {3}/{1}, {2,3}
Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:
  1;
  1,    1;
  1,    3,    1;
  1,    7,    5,    1;
  1,   15,   17,    7,    1;
  1,   31,   49,   31,    9,    1;
  1,   63,  129,  111,   49,   11,    1;
  1,  127,  321,  351,  209,   71,   13,   1;
  1,  255,  769, 1023,  769,  351,   97,  15,   1;
  1,  511, 1793, 2815, 2561, 1471,  545, 127,  17,  1;
  1, 1023, 4097, 7423, 7937, 5503, 2561, 799, 161, 19, 1;
  ...
As to matrix M, top row of M^3 = (1, 7, 5, 1, 0, 0, 0, ...)
		

Links

• Peter Bala, A 4-parameter family of embedded Riordan arrays
• Peter Bala, A note on the diagonals of a proper Riordan Array
• Harry Crane, Left-right arrangements, set partitions, and pattern avoidance, Australasian Journal of Combinatorics, 61(1) (2015), 57-72.
• A. Laradji and A. Umar, Combinatorial results for semigroups of order-preserving partial transformations, Journal of Algebra 278, (2004), 342-359.
• A. Laradji and A. Umar, Combinatorial results for semigroups of order-decreasing partial transformations, J. Integer Seq. 7 (2004), 04.3.8.

Crossrefs

Cf. A007051, A118801, A135233, columns: A000225, A000337, A055580, A027608.

Cf. also A038207, A250118, A250119.

Cf. A007318, A167374, A145661, A029635.

Programs

Maple

A112857 := proc(n,k) if k=0 or k=n then 1; elif k <0 or k>n then 0; else 2*procname(n-1,k)+procname(n-1,k-1) ; end if; end proc: # R. J. Mathar, Jun 20 2011

Mathematica

Table[Abs[1 + (-1)^k*2^(n - k + 1)*Sum[ Binomial[n - 2 j - 2, k - 2 j - 1], {j, 0, Floor[k/2]}]] - 4 Boole[And[n == 1, k == 0]], {n, 0, 10}, {k, 0, n}] // Flatten (* Michael De Vlieger, Nov 24 2016 *)

Formula

T(n,k) = Sum_{j = k..n} C(n,j)*C(j-1,k-1).

T(n,k) = 2*T(n-1,k) + T(n-1,k-1) for n >= 2 and 1 <= k <= n-1 with T(n,0) = 1 = T(n,n) for n >= 0.

n-th row = top row of M^n, deleting the zeros, where M is an infinite square production matrix with (1,1,1,...) as the superdiagonal and (1,2,2,2,...) as the main diagonal. - Gary W. Adamson, Feb 06 2012

From Peter Bala, Mar 05 2018 (Start):

The following remarks are particular cases of more general results for Riordan arrays of the form (f(x), x/(1 - k*x)).

Let R(n,x) denote the n-th row polynomial of this triangle. The polynomial R(n,2*x) has the e.g.f. Sum_{k = 0..n} T(n,k)*(2*x)^k/k!. The e.g.f. for the n-th diagonal of the triangle (starting at n = 0 for the main diagonal) equals exp(x) * the e.g.f. for the polynomial R(n,2*x). For example, when n = 3 we have exp(x)*(1 + 7*(2*x) + 5*(2*x)^2/2! + (2*x)^3/3!) = 1 + 15*x + 49*x^2/2! + 111*x^3/3! + 209*x^4/4! + ....

Let P(n,x) = Sum_{k = 0..n} T(n,k)*x^(n-k) denote the n-th row polynomial in descending powers of x. Then P(n,x) is the n-th degree Taylor polynomial of the function (1 + 2*x)^n/(1 + x) about 0. For example, for n = 4 we have (1 + 2*x)^4/(1 + x) = x^4 + 15*x^3 + 17*x^2 + 7*x + 1 + O(x^5).

See A118801 for a signed version of this triangle and A145661 for a signed version of the row reversed triangle. (End)

Bivariate o.g.f.: Sum_{n,k>=0} T(n,k)*x^n*y^k = (1 - 2*x)/((1 - x)*(1 - 2*x - x*y)). - Petros Hadjicostas, Feb 14 2021

The matrix inverse of the Lucas triangle A029635 is -T(n, k)/(-2)^(n-k+1). - Peter Luschny, Dec 22 2024