login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 59th year, we have over 358,000 sequences, and we’ve crossed 10,300 citations (which often say “discovered thanks to the OEIS”).

Other ways to Give
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 63
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.

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)

REFERENCES

Massimo Nocentini, "An algebraic and combinatorial study of some infinite sequences of numbers supported by symbolic and logic computation", PhD Thesis, University of Florence, 2019. See Ex. 36.

LINKS

Vincenzo Librandi, Rows n = 0..100, flattened

P. Bala, Deformations of the Hadamard product of power series

F. Brenti and V. Welker, f-vectors of barycentric subdivisions, arXiv:math/0606356 [math.CO], Math. Z., 259(4), 849-865, 2008.

M. Dukes, C. D. White, Web Matrices: Structural Properties and Generating Combinatorial Identities, arXiv:1603.01589 [math.CO], 2016.

Germain Kreweras, Une dualité élémentaire souvent utile dans les problèmes combinatoires, Mathématiques et Sciences Humaines 3 (1963): 31-41.

Jerry Metzger and Thomas Richards, A Prisoner Problem Variation, Journal of Integer Sequences, Vol. 18 (2015), Article 15.2.7.

J. B. Slowinski, The Number of Multiple Alignments, Molecular Phylogenetics and Evolution 10:2 (1998), 264-266. doi:10.1006/mpev.1998.0522

M. Z. Spivey, On Solutions to a General Combinatorial Recurrence, J. Int. Seq. 14 (2011) # 11.9.7.

Wikipedia, Barycentric subdivision

Wikipedia, Simplicial complex

Wikipedia, Simplex

Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

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]

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

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

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

... reformatted and extended. - Wolfdieter Lang, Mar 31 2017

From Peter Bala, Feb 04 2018: (Start)

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

A131689 := (n, k) -> Stirling2(n, k)*k!: # Peter Luschny, Sep 17 2011

# Alternatively:

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

for n from 0 to 9 do A131689_row(n) od; # Peter Luschny, Jan 23 2017

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))};

/* Michael Somos, Jul 08 2018 */

(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

# Peter Luschny, Mar 26 2020

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

for n in (0..9): print(F(n).list()) # Peter Luschny, May 21 2021

CROSSREFS

Case m=1 of the polynomials defined in A278073.

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

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

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

Cf. A019538, A122193, A299041.

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

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

Classes of patterns:

- A000142 = strict

- A005649 = anti-run, complement A069321

- A019536 = necklace

- A032011 = distinct multiplicities

- A060223 = Lyndon

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

- A296975 = aperiodic

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

- A349058 = weakly alternating

- A351200 = distinct runs

- A351292 = distinct run-lengths

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

Sequence in context: A089949 A085845 A138106 * A278075 A114329 A241011

Adjacent sequences: A131686 A131687 A131688 * A131690 A131691 A131692

KEYWORD

nonn,tabl,easy

AUTHOR

Philippe Deléham, Sep 14 2007

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 3 07:58 EST 2022. Contains 358515 sequences. (Running on oeis4.)