%I #123 Mar 16 2024 15:20:06

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

%T 1800,720,0,1,126,1806,8400,16800,15120,5040,0,1,254,5796,40824,

%U 126000,191520,141120,40320,0,1,510,18150,186480,834120,1905120,2328480

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

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

%C See also A019538: version with n > 0 and k > 0. - _Philippe Deléham_, Nov 03 2008

%C From _Peter Bala_, Jul 21 2014: (Start)

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

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

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

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

%C The row polynomials R(n,x) are the Fubini polynomials. - _Emanuele Munarini_, Dec 05 2020

%C From _Gus Wiseman_, Feb 18 2022: (Start)

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

%C (1,1,1) (1,2,2) (1,2,3)

%C (2,1,2) (1,3,2)

%C (2,2,1) (2,1,3)

%C (1,1,2) (2,3,1)

%C (1,2,1) (3,1,2)

%C (2,1,1) (3,2,1)

%C (End)

%C 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. - _Nathan L. Skirrow_, Mar 23 2023

%H Vincenzo Librandi, <a href="/A131689/b131689.txt">Rows n = 0..100, flattened</a>

%H Peter Bala, <a href="/A131689/a131689.pdf">Deformations of the Hadamard product of power series</a>

%H F. Brenti and V. Welker, <a href="http://arxiv.org/abs/math/0606356">f-vectors of barycentric subdivisions</a>, arXiv:math/0606356 [math.CO], Math. Z., 259(4), 849-865, 2008.

%H M. Dukes and C. D. White, <a href="http://arxiv.org/abs/1603.01589">Web Matrices: Structural Properties and Generating Combinatorial Identities</a>, arXiv:1603.01589 [math.CO], 2016.

%H Germain Kreweras, <a href="http://archive.numdam.org/item/MSH_1963__3__31_0">Une dualité élémentaire souvent utile dans les problèmes combinatoires</a>, Mathématiques et Sciences Humaines 3 (1963): 31-41.

%H Jerry Metzger and Thomas Richards, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL18/Metzger/metz1.html">A Prisoner Problem Variation</a>, Journal of Integer Sequences, Vol. 18 (2015), Article 15.2.7.

%H Massimo Nocentini, <a href="https://flore.unifi.it/handle/2158/1217082">An algebraic and combinatorial study of some infinite sequences of numbers supported by symbolic and logic computation</a>, PhD Thesis, University of Florence, 2019. See Ex. 36.

%H J. B. Slowinski, <a href="http://www.neurociencias.org.ve/cont-cursos-laboratorio-de-neurociencias-luz/Slowinski1998%20phylogenetics.pdf">The Number of Multiple Alignments</a>, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:<a href="http://dx.doi.org/10.1006/mpev.1998.0522">10.1006/mpev.1998.0522</a>

%H M. Z. Spivey, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Spivey/spivey31.html">On Solutions to a General Combinatorial Recurrence</a>, J. Int. Seq. 14 (2011) # 11.9.7.

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Barycentric_subdivision">Barycentric subdivision</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Simplicial_complex">Simplicial complex</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Simplex">Simplex</a>

%H Gus Wiseman, <a href="/A102726/a102726.txt">Sequences counting and ranking compositions by the patterns they match or avoid</a>.

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

%F Sum_{k=0..n} T(n,k)*x^(n-k) = A000012(n), A000142(n), A000670(n), A122704(n) for x=-1, 0, 1, 2 respectively. - _Philippe Deléham_, Oct 09 2007

%F Sum_{k=0..n} (-1)^k*T(n,k)/(k+1) = Bernoulli numbers A027641(n)/A027642(n). - _Peter Luschny_, Sep 17 2011

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

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

%F T(n,k) = [t^k] (n! [x^n] (1/(1-t*(exp(x)-1)))). - _Peter Luschny_, Jan 23 2017

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

%e The triangle T(n,k) begins:

%e n\k 0 1 2 3 4 5 6 7 8 9 10 ...

%e 0: 1

%e 1: 0 1

%e 2: 0 1 2

%e 3: 0 1 6 6

%e 4: 0 1 14 36 24

%e 5: 0 1 30 150 240 120

%e 6: 0 1 62 540 1560 1800 720

%e 7: 0 1 126 1806 8400 16800 15120 5040

%e 8: 0 1 254 5796 40824 126000 191520 141120 40320

%e 9: 0 1 510 18150 186480 834120 1905120 2328480 1451520 362880

%e 10: 0 1 1022 55980 818520 5103000 16435440 29635200 30240000 16329600 3628800

%e ... reformatted and extended. - _Wolfdieter Lang_, Mar 31 2017

%e From _Peter Bala_, Feb 04 2018: (Start)

%e T(4,2) = 14 alignments of length 2 of 4 strings of length 1. Examples include

%e (i) A - (ii) A - (iii) A -

%e B - B - - B

%e C - - C - C

%e - D - D - D

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

%p A131689 := (n,k) -> Stirling2(n,k)*k!: # _Peter Luschny_, Sep 17 2011

%p # Alternatively:

%p A131689_row := proc(n) 1/(1-t*(exp(x)-1)); expand(series(%,x,n+1)); n!*coeff(%,x,n); PolynomialTools:-CoefficientList(%,t) end:

%p for n from 0 to 9 do A131689_row(n) od; # _Peter Luschny_, Jan 23 2017

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

%o (PARI) {T(n, k) = if( n<0, 0, sum(i=0, k, (-1)^(k + i) * binomial(k, i) * i^n))};

%o /* _Michael Somos_, Jul 08 2018 */

%o (Julia)

%o function T(n, k)

%o if k < 0 || k > n return 0 end

%o if n == 0 && k == 0 return 1 end

%o k*(T(n-1, k-1) + T(n-1, k))

%o end

%o for n in 0:7

%o println([T(n, k) for k in 0:n])

%o end

%o # _Peter Luschny_, Mar 26 2020

%o (SageMath)

%o @cached_function

%o def F(n): # Fubini polynomial

%o R.<x> = PolynomialRing(ZZ)

%o if n == 0: return R(1)

%o return R(sum(binomial(n, k)*F(n - k)*x for k in (1..n)))

%o for n in (0..9): print(F(n).list()) # _Peter Luschny_, May 21 2021

%Y Columns k=0..10 are A000007, A000012, A000918, A001117, A000919, A001118, A000920, A135456, A133068, A133360, A133132,

%Y Case m=1 of the polynomials defined in A278073.

%Y Cf. A000142 (diagonal), A000670 (row sums), A000012 (alternating row sums), A210029 (central terms).

%Y Cf. A001286, A037960, A037961, A037962, A037963.

%Y Cf. A008292, A028246 (o.g.f. and e.g.f. of sums of powers).

%Y Cf. A019538, A122193, A299041.

%Y A version for partitions is A116608, or by maximum A008284.

%Y A version for compositions is A235998, or by maximum A048004.

%Y Classes of patterns:

%Y - A000142 = strict

%Y - A005649 = anti-run, complement A069321

%Y - A019536 = necklace

%Y - A032011 = distinct multiplicities

%Y - A060223 = Lyndon

%Y - A226316 = (1,2,3)-avoiding, weakly A052709, complement A335515

%Y - A296975 = aperiodic

%Y - A345194 = alternating, up/down A350354, complement A350252

%Y - A349058 = weakly alternating

%Y - A351200 = distinct runs

%Y - A351292 = distinct run-lengths

%Y Cf. A007318, A097805, A335456, A335457, A344605, A349050.

%K nonn,tabl,easy

%O 0,6

%A _Philippe Deléham_, Sep 14 2007