login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A112857 Triangle 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
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

0,5

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

LINKS

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

P. Bala, A 4-parameter family of embedded Riordan arrays

P. 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, A. Umar, Combinatorial results for semigroups of order-preserving partial transformations, Journal of Algebra 278, (2004), 342-359.

A. Laradji, A. Umar, Combinatorial results for semigroups of order-decreasing partial transformations, J. Integer Seq. 7 (2004), 04.3.8

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) with T(n,0) = 1 = T(n,n).

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)

EXAMPLE

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}

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, ...)

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

CROSSREFS

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

Cf. also A038207, A250118, A250119.

Cf. A007318, A167374, A145661.

Sequence in context: A136621 A108625 A177992 * A118801 A080936 A094507

Adjacent sequences:  A112854 A112855 A112856 * A112858 A112859 A112860

KEYWORD

nonn,tabl,easy

AUTHOR

Abdullahi Umar, Aug 25 2008

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 22 20:51 EDT 2019. Contains 325226 sequences. (Running on oeis4.)