|
| |
|
|
A131689
|
|
Triangle of numbers T(n,k) = k!*Stirling2(n,k) = A000142(k)*A048993(n,k) read by rows, T(n, k) for 0 <= k <= n.
|
|
74
|
|
|
|
1, 0, 1, 0, 1, 2, 0, 1, 6, 6, 0, 1, 14, 36, 24, 0, 1, 30, 150, 240, 120, 0, 1, 62, 540, 1560, 1800, 720, 0, 1, 126, 1806, 8400, 16800, 15120, 5040, 0, 1, 254, 5796, 40824, 126000, 191520, 141120, 40320, 0, 1, 510, 18150, 186480, 834120, 1905120, 2328480
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,6
|
|
|
COMMENTS
|
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.
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
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)
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(n,k) = k*(T(n-1,k-1) + T(n-1,k)) with T(0,0)=1. Sum_{k=0..n} T(n,k)*x^k = (-1)^n*A000629(n), A033999(n), A000007(n), A000670(n), A004123(n+1), A032033(n), A094417(n), A094418(n), A094419(n) for x = -2, -1, 0, 1, 2, 3, 4, 5, 6 respectively. [corrected by Philippe Deléham, Feb 11 2013]
G.f.: F(x,t) = 1 + x*t + (x+x^2)*t^2/2! + (x+6*x^2+6*x^3)*t^3/3! + ... = Sum_{n>=0} R(n,x)*t^n/n!.
The row polynomials R(n,x) satisfy the recursion R(n+1,x) = (x+x^2)*R'(n,x) + x*R(n,x) where ' indicates differentiation with respect to x. - Philippe Deléham, Feb 11 2013
T(n,k) = [t^k] (n! [x^n] (1/(1-t*(exp(x)-1)))). - Peter Luschny, Jan 23 2017
The n-th row polynomial has the form x o x o ... o x (n factors), where o denotes the black diamond multiplication operator of Dukes and White. See also Bala, Example E8. - Peter Bala, Jan 08 2018
|
|
|
EXAMPLE
|
The triangle T(n,k) begins:
n\k 0 1 2 3 4 5 6 7 8 9 10 ...
0: 1
1: 0 1
2: 0 1 2
3: 0 1 6 6
4: 0 1 14 36 24
5: 0 1 30 150 240 120
6: 0 1 62 540 1560 1800 720
7: 0 1 126 1806 8400 16800 15120 5040
8: 0 1 254 5796 40824 126000 191520 141120 40320
9: 0 1 510 18150 186480 834120 1905120 2328480 1451520 362880
10: 0 1 1022 55980 818520 5103000 16435440 29635200 30240000 16329600 3628800
T(4,2) = 14 alignments of length 2 of 4 strings of length 1. Examples include
(i) A - (ii) A - (iii) A -
B - B - - B
C - - C - C
- D - D - D
There are C(4,1) = 4 alignments of type (i) with a single gap character - in column 1, C(4,2) = 6 alignments of type (ii) with two gap characters in column 1 and C(4,3) = 4 alignments of type (iii) with three gap characters in column 1, giving a total of 4 + 6 + 4 = 14 alignments. (End)
|
|
|
MAPLE
|
# Alternatively:
A131689_row := proc(n) 1/(1-t*(exp(x)-1)); expand(series(%, x, n+1)); n!*coeff(%, x, n); PolynomialTools:-CoefficientList(%, t) end:
|
|
|
MATHEMATICA
|
t[n_, k_] := k!*StirlingS2[n, k]; Table[t[n, k], {n, 0, 9}, {k, 0, n}] // Flatten (* Jean-François Alcover, Feb 25 2014 *)
T[n_, k_] := If[n <= 0 || k <= 0, Boole[n == 0 && k == 0], Sum[(-1)^(i + k) Binomial[k, i] i^(n + k), {i, 0, k}]]; (* Michael Somos, Jul 08 2018 *)
|
|
|
PROG
|
(PARI) {T(n, k) = if( n<0, 0, sum(i=0, k, (-1)^(k + i) * binomial(k, i) * i^n))};
(Julia)
function T(n, k)
if k < 0 || k > n return 0 end
if n == 0 && k == 0 return 1 end
k*(T(n-1, k-1) + T(n-1, k))
end
for n in 0:7
println([T(n, k) for k in 0:n])
end
(SageMath)
@cached_function
def F(n): # Fubini polynomial
R.<x> = PolynomialRing(ZZ)
if n == 0: return R(1)
return R(sum(binomial(n, k)*F(n - k)*x for k in (1..n)))
|
|
|
CROSSREFS
|
Columns k=0..10 are A000007, A000012, A000918, A001117, A000919, A001118, A000920, A135456, A133068, A133360, A133132,
Case m=1 of the polynomials defined in A278073.
Classes of patterns:
- A032011 = distinct multiplicities
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
