cp's OEIS Frontend

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

See also A019538: version with n > 0 and k > 0. - Philippe Deléham, Nov 03 2008

From Peter Bala, Jul 21 2014: (Start)

T(n,k) gives the number of (k-1)-dimensional faces in the interior of the first barycentric subdivision of the standard (n-1)-dimensional simplex. For example, the barycentric subdivision of the 1-simplex is o--o--o, with 1 interior vertex and 2 interior edges, giving T(2,1) = 1 and T(2,2) = 2.

This triangle is used when calculating the face vectors of the barycentric subdivision of a simplicial complex. Let S be an n-dimensional simplicial complex and write f_k for the number of k-dimensional faces of S, with the usual convention that f_(-1) = 1, so that F := (f_(-1), f_0, f_1,...,f_n) is the f-vector of S. If M(n) denotes the square matrix formed from the first n+1 rows and n+1 columns of the present triangle, then the vector F*M(n) is the f-vector of the first barycentric subdivision of the simplicial complex S (Brenti and Welker, Lemma 2.1). For example, the rows of Pascal's triangle A007318 (but with row and column indexing starting at -1) are the f-vectors for the standard n-simplexes. It follows that A007318*A131689, which equals A028246, is the array of f-vectors of the first barycentric subdivision of standard n-simplexes. (End)

This triangle T(n, k) appears in the o.g.f. G(n, x) = Sum_{m>=0} S(n, m)*x^m with S(n, m) = Sum_{j=0..m} j^n for n >= 1 as G(n, x) = Sum_{k=1..n} (x^k/(1 - x)^(k+2))*T(n, k). See also the Eulerian triangle A008292 with a Mar 31 2017 comment for a rewritten form. For the e.g.f. see A028246 with a Mar 13 2017 comment. - Wolfdieter Lang, Mar 31 2017

T(n,k) = the number of alignments of length k of n strings each of length 1. See Slowinski. An example is given below. Cf. A122193 (alignments of strings of length 2) and A299041 (alignments of strings of length 3). - Peter Bala, Feb 04 2018

The row polynomials R(n,x) are the Fubini polynomials. - Emanuele Munarini, Dec 05 2020

From Gus Wiseman, Feb 18 2022: (Start)

Also the number of patterns of length n with k distinct parts (or with maximum part k), where we define a pattern to be a finite sequence covering an initial interval of positive integers. For example, row n = 3 counts the following patterns:

(1,1,1) (1,2,2) (1,2,3)

(2,1,2) (1,3,2)

(2,2,1) (2,1,3)

(1,1,2) (2,3,1)

(1,2,1) (3,1,2)

(2,1,1) (3,2,1)

(End)

Regard A048994 as a lower-triangular matrix and divide each term A048994(n,k) by n!, then this is the matrix inverse. Because Sum_{k=0..n} (A048994(n,k) * x^n / n!) = A007318(x,n), Sum_{k=0..n} (A131689(n,k) * A007318(x,k)) = x^n. - Natalia L. Skirrow, Mar 23 2023

T(n,k) is the number of ordered partitions of [n] into k blocks. - Alois P. Heinz, Feb 21 2025

From Peter Bala, Mar 08 2018: (Start)

The table entries T(n,k) are the coefficients when expressing the polynomial C(x+2,2)^p of degree 2*p in terms of falling factorials: C(x+2,2)^p = Sum_{k = 0..2*p} T(p,k)*C(x,k). It follows that Sum_{i = 0..n-1} C(i+2,2)^p = Sum_{k = 0..2*p} T(p,k)*C(n,k+1).

The sum of the p-th powers of the triangular numbers is also given by Sum_{i = 0..n-1} C(i+2,2)^p = Sum_{k = 2..2*p} A122193(p,k)*C(n+2,k+1) for p >= 1. (End)

A generalization of the Stirling2 numbers S_{1,1} from A008277.

The g.f. for column k=2*K is (x^K)*pe(K,x)*d(k,x) and for k=2*K+1 it is (x^K)*po(K,x)*2*(K+1)*K*d(k,x), K>= 1, with d(k,x) := 1/product(1-p*(p-1)*x,p=2..k) and the row polynomials pe(n,x) := sum(A089275(n,m)*x^m,m=0..n-1) and po(n,x) := sum(A089276(n,m)*x^m,m=0..n-1). - Wolfdieter Lang, Nov 07 2003

The formula for the k-th column sequence is given in A089511.

Codara et al., show that T(n,k) gives the number of k-colorings of the graph nK_2 (the disjoint union of n copies of the complete graph K_2). An example is given below. - Peter Bala, Aug 15 2013

From Peter Bala, Jan 30 2018: (Start)

Number of alignments of n strings of length 2 (see Slowinski).

Conjectures: a(n) == 1 (mod 12); for fixed k, the sequence a(n) (mod k) eventually becomes periodic with exact period a divisor of phi(k), where phi(k) is Euler's totient function A000010. (End)

An alignment of n strings of various lengths is a way of inserting blank characters into the n strings so that the resulting strings all have the same length. We don't allow insertion of a blank character into the same position in each of the n strings.

In this case, let s_1,...,s_n be n strings each of length 3 over an alphabet A. Let - be a gap symbol not in A and let A' = union of A and {-}. An alignment of the n strings is an n-tuple (s_1',...,s_n') of strings each of length >= 3 over the alphabet A' such that

(a) the strings s_i', 1 <= i <= n, have the same length. This common length is called the length of the alignment.

(b) deleting the gap symbols from s_i' yields the string s_i for 1 <= i <= n

(c) there is no value j such that all the strings s_i', 1 <= i <= n have a gap symbol at position j.

By writing the strings s_i' one under another we can consider an alignment of n strings as an n X L matrix, where L, the length of the alignment, ranges from a minimum value of 3 to a maximum value of 3*n. Each row of the matrix has 3 characters from the alphabet A and (L - 3) gap characters.

For example,

s_1' = ABC------

s_2' = ---DEF---

s_3' = ------GHI

is an alignment (of maximum length L = 9) of three strings s_1 = ABC, s_2 = DEF and s_3 = GHI each of length 3.

For the number of alignments of length k of n strings of length 1 (resp. 2) see A131689 (resp. A122193).

Triangle here T_3(n,m) is such that C(n,m)^3 = Sum_{j=0..n} C(n,j)*T_3(j,m).

Equivalently, lower triangular matrix T_3 such that

|| C(n,m)^3 || = A181583 = P * T_3 = A007318 * T_3.

T_3(n,m) = 0 for n < m and for 3*m < n. In fact:

C(x,m)^q and C(x,m), with m nonnegative and q positive integer, are polynomial in x of degree m*q and m respectively, and C(x,m) is a divisor of C(x,m)^q.

Therefore the Newton series will give C(x,m)^q = T_q(m,m)*C(x,m) + T_q(m+1,m)*C(x,m+1) + ... + T_q(q*m,m)*C(x,q*m), where T_q(n,m) is the n-th forward finite difference of C(x,m)^q at x = 0.

Example:

C(x,2)^3 = x^3*(x-1)^3 / 8 = 1*C(x,2) + 24*C(x,3) + 114*C(x,4) + 180*C(x,5) + 90*C(x,6);

C(5,2)^3 = C(5,3)^3 = 1000 = 1*C(5,2) + 24*C(5,3) + 114*C(5,4) + 180*C(5,5) = 1*C(5,3) + 60*C(5,4) + 690*C(5,5).

So we get the expansion of the 3rd power of the binomial coefficient in terms of the binomial coefficients on the same row.

T_1 is the unitary matrix,

T_2 is the transpose of A109983,

T_3 is this sequence,

T_4, T_5 are A262705, A262706.

A122193(n,k) equals the number of arrangements on a line of n (nondegenerate) finite closed intervals having k distinct endpoints. The entries T(n,k) of the present table satisfy T(n,k) = A122193(n,k) + A122193(n,k+1). Proof. In an arrangement contributing to T(n,k) either the intervals are all nondegenerate, and there are A122193(n,k) arrangements of this type, or at least one of the intervals in the arrangement is degenerate. The following argument to show there are A122193(n,k+1) arrangements of the latter type is taken from the solution to the problem posed in the 'IBM Ponder This' link.

In an arrangement of n nondegenerate finite closed intervals having k+1 distinct endpoints, the rightmost point is the right endpoint of one or more intervals. If we move each of these right endpoints to coincide with their corresponding left endpoint then we obtain an arrangement of n finite closed intervals with k distinct endpoints, where at least one of the intervals has zero length. The reverse mapping is clear: given an arrangement of n finite closed intervals with k distinct endpoints, where at least one of the intervals has zero length, take each interval of zero length and move all the right endpoints of these degenerate intervals to a single new rightmost point. This produces an arrangement of n nondegenerate finite closed intervals having k+1 distinct endpoints. (End proof)

Most of the properties of the present table now follow from the properties of A122193.

Reading the table by antidiagonals produces A059515.

Triangle here T_4(n,m) is such that C(n,m)^4 = Sum_{j=0..n} C(n,j)*T_4(j,m).

Equivalently, lower triangular matrix T_4 such that

|| C(n,m)^4 || = A202750 = P * T_4 = A007318 * T_4.

T_4(n,m) = 0 for n < m and for 4*m < n.

Refer to comment to A262704.

Example:

C(x,2)^4 = x^4*(x-1)^4 /16 = 1*C(x,2) + 78*C(x,3) + 978*C(x,4) + 4320*C(x,5) + 8460*C(x,6) + 7560*C(x,7) + 2520*C(x,8);

C(5,2)^4 = C(5,3)^4 = 10000 = 1*C(5,2) + 78*C(5,3) + 978*C(5,4) + 4320*C(5,5) = 1*C(5,3) + 252*C(5,4) + 8730*C(5,5).

Triangle here T_5(n,m) is such that C(n,m)^5 = Sum_{j=0..n} C(n,j)*T_5(j,m).

Equivalently, lower triangular matrix T_5 such that

|| C(n,m)^5 || = P * T_5 = A007318 * T_5.

T_5(n,m) = 0 for n < m and for 5*m < n.

Refer to comment to A262704.

Example:

C(x,2)^5 = x^5*(x-1)^5/32 = 1*C(x,2) + 240*C(x,3) + 6810*C(x,4) + 63540*C(x,5) + 271170*C(x,6) + 604800*C(x,7) + 730800*C(x,8) + 453600*C(x,9) + 113400*C(x,10);

C(5,2)^5 = C(5,3)^5 = 100000 = 1*C(5,2) + 240*C(5,3) + 6810*C(5,4) + 63540*C(5,5) = 1*C(5,3) + 1020*C(5,4) + 94890*C(5,5).