login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A008299 Triangle T(n,k) of associated Stirling numbers of second kind, n>=2, 1<=k<=floor(n/2). 27
1, 1, 1, 3, 1, 10, 1, 25, 15, 1, 56, 105, 1, 119, 490, 105, 1, 246, 1918, 1260, 1, 501, 6825, 9450, 945, 1, 1012, 22935, 56980, 17325, 1, 2035, 74316, 302995, 190575, 10395, 1, 4082, 235092, 1487200, 1636635, 270270, 1, 8177, 731731, 6914908, 12122110 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,4

COMMENTS

T(n,k) is the number of set partitions of [n] into k blocks of size at least 2. Compare with A008277 (blocks of size at least 1) and A059022 (blocks of size at least 3). See also A200091. Reading the table by diagonals gives A134991. The row generating polynomials are the Mahler polynomials s_n(-x). See [Roman, 4.9]. - Peter Bala, Dec 04 2011

Row n gives coefficients of moments of Poisson distribution about the mean expressed as polynomials in lambda [Haight]. The coefficients of the moments about the origin are the Stirling numbers of the second kind, A008277. - N. J. A. Sloane, Jan 24 2020

Rows are of lengths 1,1,2,2,3,3,.... This corresponds to the fact that the diagonals are rows of the lower triangular matrix A134991. - Tom Copeland, May 01 2017; N. J. A. Sloane, Jan 24 2020.

For a relation to decomposition of spin correlators see Table 2 of the Delfino and Vito paper. - Tom Copeland, Nov 11 2012

REFERENCES

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 222.

Haight, Frank Avery. "Handbook of the Poisson distribution," John Wiley, 1967. See pages 6,7, but beware of errors. [Haight on page 7 gives five different ways to generate these numbers (see link)].

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 76.

S. Roman, The Umbral Calculus, Dover Publications, New York (2005), pp. 129-130.

LINKS

Vincenzo Librandi and Alois P. Heinz, Rows n = 2..200, flattened (rows n = 2..104 from Vincenzo Librandi)

Joerg Arndt and N. J. A. Sloane, Counting Words that are in "Standard Order"

P. Bala, Diagonals of triangles with generating function exp(t*F(x)).

J. Fernando Barbero G., Jesús Salas, Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013.

J. Fernando Barbero G., Jesús Salas, Eduardo J. S. Villaseñor, Generalized Stirling permutations and forests: Higher-order Eulerian and Ward numbers, Electronic Journal of Combinatorics 22(3) (2015), #P3.37.

T. Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms

T. Copeland, Short note on Lagrange inversion

Gesualdo Delfino and Jacopo Viti, Potts q-color field theory and scaling random cluster model, arXiv:1104.4323 [hep-th], 2011.

A. E. Fekete, Apropos two notes on notation, Amer. Math. Monthly, 101 (1994), 771-778.

F. A. Haight, Handbook of the Poisson distribution, John Wiley, 1967 [Annotated scan of page 7 only. Note that there is an error in the table.]

MathStackExchange, Mahler polynomials and the zeros of the incomplete gamma function, a MathStackExchange question by Tom Copeland, Jan 06 2016.

R. Paris, A uniform asymptotic expansion for the incomplete gamma function, Journal of Computational and Applied Mathematics, 148 (2002), p. 223-239 (See 332. From Tom Copeland, Jan 03 2016).

Andrew Elvey Price, Alan D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, arXiv:2001.01468 [math.CO], 2020.

L. M. Smiley, Completion of a Rational Function Sequence of Carlitz, arXiv:math/0006106 [math.CO], 2000.

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

Eric Weisstein's World of Mathematics, Mahler polynomial

Wikipedia, Mahler polynomials

FORMULA

T(n,k) = abs(A137375(n,k)).

E.g.f. with additional constant 1: exp(t*(exp(x)-1-x)) = 1+t*x^2/2!+t*x^3/3!+(t+3*t^2)*x^4/4!+....

Recurrence relation: T(n+1,k) = k*T(n,k) + n*T(n-1,k-1).

T(n,k) = A134991(n-k,k); A134991(n,k) = T(n+k,k).

More generally, if S_r(n,k) gives the number of set partitions of [n] into k blocks of size at least r then we have the recurrence S_r(n+1,k)=k*S_r(n,k)+binomial(n,r-1)*S_r(n-r+1,k-1) (for this sequence, r=2), with associated e.g.f.: sum(S_r(n,k)*u^k*(t^n/n!), n>=0, k>=0)=exp(u*(e^t-sum(t^i/i!, i=0..r-1))).

T(n,k) = Sum_{i=0..k} (-1)^i*binomial(n, i)*[sum_{j=0..k-i} (-1)^j*(k -i -j)^(n-i)/(j!*(k-i-j)!)]. - David Wasserman, Jun 13 2007

G.f.: (R(0)-1)/(x^2*y), where R(k) = 1 - (k+1)*y*x^2/( (k+1)*y*x^2 -(1- k*x)*(1-x - k*x)/R(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 09 2013

T(n,k) = Sum_{i=0..min(n,k)} (-1)^i * binomial(n,i) * stirling2(n-i,k-i) = Sum_{i=0..min(n,k)} (-1)^i * A007318(n,i) * A008277(n-i,k-i). - Max Alekseyev, Feb 27 2017

EXAMPLE

There are 3 ways of partitioning a set N of cardinality 4 into 2 blocks each of cardinality at least 2, so T(4,2)=3. Table begins:

1;

1;

1, 3;

1, 10;

1, 25, 15;

1, 56, 105;

1, 119, 490, 105;

1, 246, 1918, 1260;

1, 501, 6825, 9450, 945;

1, 1012, 22935, 56980, 17325;

1, 2035, 74316, 302995, 190575, 10395;

1, 4082, 235092, 1487200, 1636635, 270270;

1, 8177, 731731, 6914908, 12122110, 4099095, 135135;

...

Reading the table by diagonals produces the triangle A134991.

MAPLE

A008299 := proc(n, k) local i, j, t1; if k<1 or k>floor(n/2) then t1 := 0; else

t1 := add( (-1)^i*binomial(n, i)*add( (-1)^j*(k - i - j)^(n - i)/(j!*(k - i - j)!), j = 0..k - i), i = 0..k); fi; t1; end; # N. J. A. Sloane, Dec 06 2016

G:= exp(lambda*(exp(x)-1-x)):

S:= series(G, x, 21):

seq(seq(coeff(coeff(S, x, n)*n!, lambda, k), k=1..floor(n/2)), n=2..20); # Robert Israel, Jan 15 2020

MATHEMATICA

t[n_, k_] := Sum[ (-1)^i*Binomial[n, i]*Sum[ (-1)^j*(k - i - j)^(n - i)/(j!*(k - i - j)!), {j, 0, k - i}], {i, 0, k}]; Flatten[ Table[ t[n, k], {n, 2, 14}, {k, 1, Floor[n/2]}]] (* Jean-François Alcover, Oct 13 2011, after David Wasserman *)

Table[Sum[Binomial[n, k - j] StirlingS2[n - k + j, j] (-1)^(j + k), {j, 0, k}], {n, 15}, {k, n/2}] // Flatten (* Eric W. Weisstein, Nov 13 2018 *)

PROG

(PARI) {T(n, k) = if( n < 1 || 2*k > n, n==0 && k==0, sum(i=0, k, (-1)^i * binomial( n, i) * sum(j=0, k-i, (-1)^j * (k-i-j)^(n-i) / (j! * (k-i-j)!))))}; /* Michael Somos, Oct 19 2014 */

(PARI) { T(n, k) = sum(i=0, min(n, k), (-1)^i * binomial(n, i) * stirling(n-i, k-i, 2) ); } /* Max Alekseyev, Feb 27 2017 */

CROSSREFS

Rows: A000247 (k=2), A000478 (k=3), A058844 (k=4).

Row sums: A000296, diagonal: A259877.

Cf. A059022, A059023, A059024, A059025, A134991, A137375, A200091, A269939.

Sequence in context: A019427 A325830 A331155 * A016478 A135573 A257254

Adjacent sequences:  A008296 A008297 A008298 * A008300 A008301 A008302

KEYWORD

nonn,tabf,nice,easy

AUTHOR

N. J. A. Sloane

EXTENSIONS

Formula and cross-references from Barbara Haas Margolius (margolius(AT)math.csuohio.edu), Dec 14 2000

Edited by Peter Bala, Dec 04 2011

Edited by N. J. A. Sloane, Jan 24 2020

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 24 19:14 EDT 2020. Contains 334580 sequences. (Running on oeis4.)