login
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)|).
10

%I #56 Feb 15 2021 22:34:52

%S 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,

%T 1,127,321,351,209,71,13,1,1,255,769,1023,769,351,97,15,1,1,511,1793,

%U 2815,2561,1471,545,127,17,1,1,1023,4097,7423,7937,5503,2561,799,161,19,1

%N 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)|).

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

%C Row-reversed variant of A119258. - _R. J. Mathar_, Jun 20 2011

%C Pairwise sums of row terms starting from the right yields triangle A038207. - _Gary W. Adamson_, Feb 06 2012

%C Riordan array (1/(1 - x), x/(1 - 2*x)). - _Philippe Deléham_, Jan 17 2014

%C 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

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

%H Peter Bala, <a href="/A264772/a264772_1.pdf">A 4-parameter family of embedded Riordan arrays</a>

%H Peter Bala, <a href="/A081577/a081577.pdf">A note on the diagonals of a proper Riordan Array</a>

%H Harry Crane, <a href="https://ajc.maths.uq.edu.au/pdf/61/ajc_v61_p057.pdf">Left-right arrangements, set partitions, and pattern avoidance</a>, Australasian Journal of Combinatorics, 61(1) (2015), 57-72.

%H A. Laradji and A. Umar, <a href="http://dx.doi.org/10.1016/j.jalgebra.2003.10.023">Combinatorial results for semigroups of order-preserving partial transformations</a>, Journal of Algebra 278, (2004), 342-359.

%H A. Laradji and A. Umar, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Umar/um.html">Combinatorial results for semigroups of order-decreasing partial transformations</a>, J. Integer Seq. 7 (2004), 04.3.8.

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

%F 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.

%F 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

%F From _Peter Bala_, Mar 05 2018 (Start):

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

%F 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! + ....

%F 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).

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

%F 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

%e 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}

%e Triangle T(n,k) (with rows n >= 0 and columns k = 0..n) begins:

%e 1;

%e 1, 1;

%e 1, 3, 1;

%e 1, 7, 5, 1;

%e 1, 15, 17, 7, 1;

%e 1, 31, 49, 31, 9, 1;

%e 1, 63, 129, 111, 49, 11, 1;

%e 1, 127, 321, 351, 209, 71, 13, 1;

%e 1, 255, 769, 1023, 769, 351, 97, 15, 1;

%e 1, 511, 1793, 2815, 2561, 1471, 545, 127, 17, 1;

%e 1, 1023, 4097, 7423, 7937, 5503, 2561, 799, 161, 19, 1;

%e ...

%e As to matrix M, top row of M^3 = (1, 7, 5, 1, 0, 0, 0, ...)

%p 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

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

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

%Y Cf. also A038207, A250118, A250119.

%Y Cf. A007318, A167374, A145661.

%K nonn,tabl,easy

%O 0,5

%A _Abdullahi Umar_, Aug 25 2008