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