A000478 -id:A000478 - cp's OEIS frontend

A008299 Triangle T(n,k) of associated Stirling numbers of second kind, n >= 2, 1 <= k <= floor(n/2).

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

Offset: 2

N. J. A. Sloane

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,..., a pattern typical of matrices whose diagonals are rows of another lower triangular matrix--in this instance those of A134991. - Tom Copeland, May 01 2017
For a relation to decomposition of spin correlators see Table 2 of the Delfino and Vito paper. - Tom Copeland, Nov 11 2012

			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.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 222.
Frank Avery Haight, "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.

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"
Peter Bala, Diagonals of triangles with generating function exp(t*F(x)).
J. Fernando Barbero G., Jesús Salas, and 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, and 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.
Fufa Beyene, Jörgen Backelin, Roberto Mantaci, and Samuel A. Fufa, Set Partitions and Other Bell Number Enumerated Objects, J. Int. Seq., Vol. 26 (2023), Article 23.1.8.
Gilles Bonnet and Anna Gusakova, Concentration inequalities for Poisson U-statistics, arXiv:2404.16756 [math.PR], 2024. See p. 17.
E. Rodney Canfield, J. William Helton, and Jared A. Hughes, Uniform Convergence of an Asymptotic Approximation to Associated Stirling Numbers, arXiv:2409.01489 [math.CO], 2024. See p. 12.
Tom Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms
Tom Copeland, Short note on Lagrange inversion
Robert Coquereaux and Jean-Bernard Zuber, Counting partitions by genus. II. A compendium of results, arXiv:2305.01100 [math.CO], 2023. See p. 3.
Daniel W. Cranston and Chun-Hung Liu, Proper Conflict-free Coloring of Graphs with Large Maximum Degree, arXiv:2211.02818 [math.CO], 2022.
Gesualdo Delfino and Jacopo Viti, Potts q-color field theory and scaling random cluster model, arXiv:1104.4323 [hep-th], 2011.
Ming-Jian Ding and Jiang Zeng, Proof of an explicit formula for a series from Ramanujan's Notebooks via tree functions, arXiv:2307.00566 [math.CO], 2023.
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.]
Mathematics Stack Exchange, Mahler polynomials and the zeros of the incomplete gamma function, a Mathematics Stack Exchange 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 and 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.
E. G. Santos, Counting non-attacking chess pieces placements: Bishops and Anassas, arXiv:2411.16492 [math.CO], 2024. See p. 2.
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.
Erik Vigren and Andreas Dieckmann, A New Result in Form of Finite Triple Sums for a Series from Ramanujan’s Notebooks, Symmetry (2022) Vol. 14, No. 6, 1090.
Eric Weisstein's World of Mathematics, Mahler polynomial
Wikipedia, Mahler polynomials

Rows: A000247 (k=2), A000478 (k=3), A058844 (k=4).
Row sums: A000296, diagonal: A259877.
Cf. A059022, A059023, A059024, A059025, A134991, A137375, A200091, A269939, A340556.

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
T := proc(n, k) option remember; if n < 0 then return 0 fi; if k = 0 then return k^n fi; k*T(n-1, k) + (n-1)*T(n-2, k-1) end:
seq(seq(T(n,k), k=1..n/2), n=2..9); # Peter Luschny, Feb 11 2021

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

{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 */

{ 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 */

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_{n>=0, k>=0} S_r(n,k)*u^k*(t^n/n!) = exp(u*(e^t - Sum_{i=0..r-1} t^i/i!)).
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
T(n, k) = Sum_{j=0..n-k} binomial(j, n-2*k)*E2(n-k, n-k-j) where E2(n, k) are the second-order Eulerian numbers A340556. - Peter Luschny, Feb 11 2021

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

A134991 Triangle of Ward numbers T(n,k) read by rows.

Original entry on oeis.org

1, 1, 3, 1, 10, 15, 1, 25, 105, 105, 1, 56, 490, 1260, 945, 1, 119, 1918, 9450, 17325, 10395, 1, 246, 6825, 56980, 190575, 270270, 135135, 1, 501, 22935, 302995, 1636635, 4099095, 4729725, 2027025, 1, 1012, 74316, 1487200, 12122110, 47507460, 94594500, 91891800, 34459425

Offset: 1

Tom Copeland, Feb 05 2008

This is the triangle of associated Stirling numbers of the second kind, A008299, read along the diagonals.
This is also a row-reversed version of A181996 (with an additional leading 1) - see the table on p. 92 in the Ward reference. A134685 is a refinement of the Ward table.
The first and second diagonals are A001147 and A000457 and appear in the diagonals of several OEIS entries. The polynomials also appear in Carlitz (p. 85), Drake et al. (p. 8) and Smiley (p. 7).
First few polynomials (with a different offset) are
  P(0,t) = 0
  P(1,t) = 1
  P(2,t) = t
  P(3,t) = t + 3*t^2
  P(4,t) = t + 10*t^2 + 15*t^3
  P(5,t) = t + 25*t^2 + 105*t^3 + 105*t^4
These are the "face" numbers of the tropical Grassmannian G(2,n),related to phylogenetic trees (with offset 0 beginning with P(2,t)). Corresponding h-vectors are A008517. - Tom Copeland, Oct 03 2011
A133314 applied to the derivative of A(x,t) implies (a.+b.)^n = 0^n, for (b_n)=P(n+1,t) and (a_0)=1, (a_1)=-t, and (a_n)=-(1+t) P(n,t) otherwise. E.g., umbrally, (a.+b.)^2 = a_2*b_0 + 2 a_1*b_1 + a_0*b_2 = 0. - Tom Copeland, Oct 08 2011
Beginning with the second column, the rows give the faces of the Whitehouse simplicial complex with the fourth-order complex being three isolated vertices and the fifth-order being the Petersen graph with 10 vertices and 15 edges (cf. Readdy). - Tom Copeland, Oct 03 2014
Stratifications of smooth projective varieties which are fine moduli spaces for stable n-pointed rational curves. Cf. pages 20 and 30 of the Kock and Vainsencher reference and references in A134685. - Tom Copeland, May 18 2017
Named after the American mathematician Morgan Ward (1901-1963). - Amiram Eldar, Jun 26 2021

			Triangle begins:
  1
  1   3
  1  10   15
  1  25  105  105
  1  56  490 1260   945
  1 119 1918 9450 17325 10395
  ...

Louis Comtet, Advanced Combinatorics, Reidel, 1974, page 222.

G. C. Greubel, Rows n = 1..65, flattened
J. Fernando Barbero G., Jesús Salas and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences, I: General Structure, Journal of Combinatorial Theory, Series A, Vol. 125 (2014), pp. 146-165; arXiv preprint, arXiv:1307.2010 [math.CO], 2013-2014.
J. Fernando Barbero G., Jesús Salas and Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. II. Applications, arXiv preprint arXiv:1307.5624 [math.CO], 2013.
J. Fernando Barbero G., Jesús Salas and Eduardo J. S. Villaseñor, Generalized Stirling permutations and forests: Higher-order Eulerian and Ward numbers, Electronic Journal of Combinatorics, Vol. 22, No. 3 (2015), #P3.37.
Andreas Blass, Natasha Dobrinen and Dilip Raghavan, The next best thing to a p-point, The Journal of Symbolic Logic, Vol. 80, No. 3 (2015), pp. 866-900; arXiv preprint, arXiv:1308.3790 [math.LO], 2013.
David Callan, Toufik Mansour, and Mark Shattuck Some identities for derangement and Ward number sequences and related bijections, Pure Mathematics and Applications, Vol. 25 (Edition 2), pp. 132-143, 2015.
L. Carlitz, The coefficients in an asymptotic expansion and certain related numbers, Duke Math. J., Vol. 35, No. 1 (1968), pp. 83-90.
Lane Clark, Asymptotic normality of the Ward numbers, Discrete Math. 203 (1999), no. 1-3, 41-48. [From _N. J. A. Sloane_, Feb 06 2012]
Tom Copeland, Generators, Inversion, and Matrix, Binomial, and Integral Transforms.
Robert Coquereaux and Jean-Bernard Zuber, Counting partitions by genus. II. A compendium of results, arXiv:2305.01100 [math.CO], 2023. See p. 3.
Bishal Deb and Alan D. Sokal, Higher-order Stirling cycle and subset triangles: Total positivity, continued fractions and real-rootedness, arXiv:2507.18959 [math.CO], 2025. See p. 6.
Satyan L. Devadoss, Daoji Huang and Dominic Spadacene, Polyhedral covers of tree space, SIAM Journal on Discrete Mathematics, Vol. 28, No. 3 (2014), pp. 1508-1514; arXiv preprint, arXiv:1311.0766 [math.CO], 2013.
S. Devadoss and J. Morava, Diagonalizing the genome I: navigation in tree spaces, arXiv:1009.3224v2 [math.AG], 2012.
S. Devadoss and O. Schuh, Cartography of Tree Space, Leonardo (MIT Press Direct), Vol. 53, Issue 3, 2019.
Andreas Dieckmann and Erik Vigren, A New Result in Form of Finite Triple Sums for a Series from Ramanujan's Notebooks, Symmetry (2022) Vol. 14, No. 6, 1090.
Ming-Jian Ding and Jiang Zeng, Proof of an explicit formula for a series from Ramanujan's Notebooks via tree functions, arXiv:2307.00566 [math.CO], 2023.
Brian Drake, Ira M. Gessel and Guoce Xin, Three Proofs and a Generalization of the Goulden-Litsyn-Shevelev Conjecture on a Sequence Arising in Algebraic Geometry, J. of Integer Sequences, Vol. 10 (2007), Article 07.3.7.
Joseph Felsenstein, The number of evolutionary trees, Systematic Biology, 27 (1978), pp. 27-33, 1978.
Giovanni Gaiffi, Nested sets, set partitions and Kirkman-Cayley dissection numbers, arXiv preprint arXiv:1404.3395 [math.CO], 2014.
David M. Jackson, Achim Kempf and Alejandro H. Morales, A robust generalization of the Legendre transform for QFT, Journal of Physics A: Mathematical and Theoretical, Vol. 50, No. 22 (2017), 225201; arXiv preprint, arXiv:1612.0046 [hep-th], 2017.
Bradley Robert Jones, On tree hook length formulae, Feynman rules and B-series, Master's thesis, Math Dept., Simon Fraser University, 2014. p. 23.
Joachim Kock and Israel Vainsencher, Kontsevich's Formula for Rational Plane Curves, Recife, 1999 (version 31/01/2003).
Toufik Mansour and Mark Shattuck, A polynomial generalization of some associated sequences related to set partitions, Periodica Mathematica Hungarica, Vol. 75, No. 2 (December 2017), pp. 398-412.
MathOverflow, Face numbers for tropical Grassmannian G'_2,7 simplicial complex?, 2011.
Andrew Elvey Price and 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.
Margaret A. Readdy, The pre-WDVV ring of physics and its topology, The Ramanujan Journal, Vol. 10, No. 2 (2005), pp. 269-281; preprint, 2002.
Lucas Randazzo, Arboretum for a generalisation of Ramanujan polynomials, The Ramanujan Journal, Vol. 54 (2019), pp. 1-14; arXiv preprint, arXiv:1905.02083 [math.CO], 2019.
Lucas Randazzo, Combinatoire bijective autour d'arbres et de chemins, doctoral thesis, Université Paris-Est, 2019.
Peter Regner, Phylogenetic Trees: Selected Combinatorial Problems, Master's Thesis, 2012, Institute of Discrete Mathematics and Geometry, TU Vienna, p. 52.
Fuquan Ren, Jean Yeh, and Roberta Rui Zhou, Context-Free Grammars for Several Triangular Arrays, Axioms, Vol. 11, Issue 6, 297, 2022.
E. G. Santos, Counting non-attacking chess pieces placements: Bishops and Anassas, arXiv:2411.16492 [math.CO], 2024. See p. 8.
Leonard M. Smiley, Completion of a Rational Function Sequence of Carlitz, arXiv:math/0006106 [math.CO], 2000.
Pierre Théorêt, Fonctions génératrices pour une classe d'équations aux différences partielles, Ann. Sci. Math. Quebec 19, 91-105 (1995).
Elena L. Wang and Guoce Xin, On Ward Numbers and Increasing Schröder Trees, arXiv:2507.15654 [math.CO], 2025. See p. 1.
Morgan Ward, The representations of Stirling's numbers and Stirling's polynomials as sums of factorials, Amer. J. Math., Vol. 56, No. 1 (1934), pp. 87-95.
Bao-Xuan Zhu, Coefficientwise Hankel-total positivity of row-generating polynomials for the m-Jacobi-Rogers triangle, arXiv:2202.03793 [math.CO], 2022.

The same as A269939, with column k = 0 removed.
A reshaped version of the triangle of associated Stirling numbers of the second kind, A008299.
A181996 is the mirror image.
Columns k = 2, 3, 4 are A000247, A000478, A058844.
Diagonal k = n is A001147.
Diagonal k = n - 1 is A000457.
Row sums are A000311.
Alternating row sums are signed factorials (-1)^(n-1)*A000142(n).
Cf. A112493.

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}]; row[n_] := Table[t[k, k-n], {k, n+1, 2*n}]; Table[row[n], {n, 1, 9}] // Flatten (* Jean-François Alcover, Apr 23 2014, after A008299 *)

E.g.f. for the polynomials is A(x,t) = (x-t)/(t+1) + T{ (t/(t+1)) * exp[(x-t)/(t+1)] }, where T(x) is the Tree function, the e.g.f. of A000169. The compositional inverse in x (about x = 0) is B(x) = x + -t * [exp(x) - x - 1]. Special case t = 1 gives e.g.f. for A000311. These results are a special case of A134685 with u(x) = B(x).
From Tom Copeland, Oct 26 2008: (Start)
Umbral-Sheffer formalism gives, for m a positive integer and u = t/(t+1),
[P(.,t)+Q(.,x)]^m = [m Q(m-1,x) - t Q(m,x)]/(t+1) + sum(n>=1) { n^(n-1)[u exp(-u)]^n/n! [n/(t+1)+Q(.,x)]^m }, when the series is convergent for a sequence of functions Q(n,x).
Check: With t=1; Q(n,x)=0^n, for n>=0; and Q(-1,x)=0, then [P(.,1)+Q(.,x)]^m = P(m,1) = A000311(m).
(End)
Let h(x,t) = 1/(dB(x)/dx) = 1/(1-t*(exp(x)-1)), an e.g.f. in x for row polynomials in t of A019538, then the n-th row polynomial in t of the table A134991, P(n,t), is given by ((h(x,t)*d/dx)^n)x evaluated at x=0, i.e., A(x,t) = exp(x*P(.,t)) = exp(x*h(u,t)*d/du) u evaluated at u=0. Also, dA(x,t)/dx = h(A(x,t),t). - Tom Copeland, Sep 05 2011
The polynomials (1+t)/t*P(n,t) are the row polynomials of A112493. Let f(x) = (1+x)/(1-x*t). Then for n >= 0, P(n+1,t) is given by t/(1+t)*(f(x)*d/dx)^n(f(x)) evaluated at x = 0. - Peter Bala, Sep 30 2011
From Tom Copeland, Oct 04 2011: (Start)
T(n,k) = (k+1)*T(n-1,k) + (n+k+1)*T(n-1,k-1) with starting indices n=0 and k=0 beginning with P(2,t) (as suggested by a formula of David Speyer on MathOverflow).
T(n,k) = k*T(n-1,k) + (n+k-1)*T(n-1,k-1) with starting indices n=1 and k=1 of table (cf. Smiley above and Riordin ref.[10] therein).
P(n,t) = (1/(1+t))^n * Sum_{k>=1} k^(n+k-1)*(u*exp(-u))^k / k! with u=(t/(t+1)) for n>1; therefore, Sum_{k>=1} (-1)^k k^(n+k-1) x^k/k! = [1+LW(x)]^(-n) P{n,-LW(x)/[1+LW(x)]}, with LW(x) the Lambert W-Fct.
T(n,k) = Sum_{i=0..k} ((-1)^i binomial(n+k,i) Sum_{j=0..k-i} (-1)^j (k-i-j)^(n+k-i)/(j!(k-i-j)!)) from relation to A008299. (End)
The e.g.f. A(x,t) = -v * ( Sum_{j=>1} D(j-1,u) (-z)^j / j! ) where u = (x-t)/(1+t), v = 1+u, z = x/((1+t) v^2) and D(j-1,u) are the polynomials of A042977. dA/dx = 1/((1+t)(v-A)) = 1/(1-t*(exp(A)-1)). - Tom Copeland, Oct 06 2011
The general results on the convolution of the refined partition polynomials of A134685, with u_1 = 1 and u_n = -t otherwise, can be applied here to obtain results of convolutions of these polynomials. - Tom Copeland, Sep 20 2016
E.g.f.: C(u,t) = (u-t)/(1+t) - W( -((t*exp((u-t)/(1+t)))/(1+t)) ), where W is the principal value of the Lambert W-function. - Cheng Peng, Sep 11 2021
The function C(u,t) in the previous formula by Peng is precisely the function A(u,t) given in the initial 2008 formula of this section and the Oct 06 2011 formula from Copeland. As noted in A000169, Euler's tree function is T(x) = -LambertW(-x), where W(x) is the principal branch of Lambert's function, and T(x) is the e.g.f. of A000169. - Tom Copeland, May 13 2022

Reference to A181996 added by N. J. A. Sloane, Apr 05 2012

Further edits by N. J. A. Sloane, Jan 24 2020

A000247 a(n) = 2^n - n - 2.

Original entry on oeis.org

0, 3, 10, 25, 56, 119, 246, 501, 1012, 2035, 4082, 8177, 16368, 32751, 65518, 131053, 262124, 524267, 1048554, 2097129, 4194280, 8388583, 16777190, 33554405, 67108836, 134217699, 268435426, 536870881, 1073741792, 2147483615

Offset: 2

N. J. A. Sloane

Ways of placing n+1 labeled balls into 2 indistinguishable boxes with at least 2 balls in each box.
2^a(n) is an integer of the form 1/(2 - Sum_{i=1..m} i/2^i). - Benoit Cloitre, Oct 25 2002
Number of permutations avoiding 13-2 that contain the pattern 23-1 exactly twice.
Cost of ternary maximum height Huffman tree with N internal nodes (non-leaves) for minimizing absolutely ordered sequences of size n = 2N + 1. - Alex Vinokur (alexvn(AT)barak-online.net), Nov 02 2004
a(n) is the number of Dyck n-paths whose third upstep initiates the last long ascent, n >= 1. A long ascent is one consisting of 2 or more upsteps. For example, a(3)=3 counts UUDuUDDD, UDUDuUDD, UUDDuUDD (third upstep in small type). - David Callan, Dec 08 2004
Subsequence of A158581; A000120(a(n)) > 1. - Reinhard Zumkeller, Apr 16 2009
Number of vertices of the tropical Grassmannian simplicial complex G(2,n), related to phylogenetic trees. - Tom Copeland, Oct 03 2011
(Conjecture) Let a(2)=0. For n > 2, let N = 2*n + 1. For each n, define the n X n tridiagonal unit-primitive matrix (see [Jeffery]) A_{N,1}=[0,1,0,...,0; 1,0,1,0,...,0; 0,1,0,1,0,...,0; ...; 0,...,0,1,0,1; 0,...,0,1,1] associated with N. Define the n-dimensional column vectors V_N = [v_1,v_2,...,v_n]^T = [A_{N,1}]^n*[1,1,...,1]^T, where [.]^T denotes matrix transpose and [1,...,1] is the n-dimensional unit vector. Let (v_k)N denote the k-th element of V_N, k in {1,...,n}. Then a(n) = (v(n-2))N. - _L. Edson Jeffery, Jan 20 2012
For n>0, (a(n)) is row 3 of the convolution array A213568. - Clark Kimberling, Jun 20 2012
For n>2, a(n-2) is the number of connected induced (non-null) subgraphs of the n-centipede graph. - Giovanni Resta, May 04 2017
a(n) is the number of maximal boundary strata of the moduli space of stable rational curves with n+1 marked points. The closures of the maximal boundary strata are called the irreducible boundary divisors of the moduli space; see Cavalieri Section 2.1. - Harry Richman, Aug 13 2024

			a(3) = 4!/(2!*2!*2!) = 3.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 222.
F. N. David and D. E. Barton, Combinatorial Chance. Hafner, NY, 1962, p. 296.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 76.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 2..300
Renzo Cavalieri, Moduli spaces of pointed rational curves, (2016).
Antal E. Fekete, Apropos Two Notes on Notation, The Amer. Math. Monthly, Vol. 101, No. 8 (Oct., 1994), pp. 771-778. See p. 776.
Robert Israel et al, Primes 2^n - n - 2, Mathematics StackExchange.
L. E. Jeffery, Unit-primitive matrices
T. Mansour, Restricted permutations by patterns of type 2-1, arXiv:math/0202219 [math.CO], 2002.
Mathoverflow, Face numbers for tropical Grassmannian G'_2,7 simplicial complex?
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Erik Vigren and Andreas Dieckmann, A New Result in Form of Finite Triple Sums for a Series from Ramanujan's Notebooks, Symmetry (2022) Vol. 14, No. 6, 1090.
Alex Vinokur, Fibonacci-like polynomials produced by m-ary Huffman codes for absolutely ordered sequences, arXiv:cs/0411002 [cs.DM], 2004.
Eric Weisstein's World of Mathematics, Centipede Graph
Eric Weisstein's World of Mathematics, Connected Dominating Set
Eric Weisstein's World of Mathematics, Vertex-Induced Subgraph
Index entries for linear recurrences with constant coefficients, signature (4,-5,2).

Cf. A000478 (3 boxes), A058844 (4 boxes).

List([2..40], n-> 2^n -n-2); # G. C. Greubel, Jul 26 2019

[2^n -n-2: n in [2..40]]; // G. C. Greubel, Jul 26 2019

A000247:=(-3+2*z)/((2*z-1)*(z-1)**2); # Simon Plouffe in his 1992 dissertation

LinearRecurrence[{4,-5,2}, {0,3,10}, 40] (* Harvey P. Dale, Aug 23 2011 *)
Table[2^n -n-2, {n,2,40}] (* Eric W. Weisstein, Aug 09 2017 *)

A000247(n):=2^n-n-2$
makelist(A000247(n),n,2,30); /* Martin Ettl, Nov 08 2012 */

a(n)=2^n-n-2 \\ Charles R Greathouse IV, Sep 28 2015

[2^n -n-2 for n in (2..40)] # G. C. Greubel, Jul 26 2019

E.g.f.: (exp(x)-1-x)*(exp(x)-1).
G.f.: x^3*(3-2*x)/((1-2*x)*(1-x)^2).
a(n) = 2*a(n-1) + n + 3 = a(n-1) + 2^(n-1) - 1 = A000295(n) - 1 = A000295(n+1) - 2^(n+1).
A107907(a(n)) = A000225(n). - Reinhard Zumkeller, May 28 2005
Starting (3, 10, 25, 56, ...) = binomial transform of [3, 7, 8, 8, 8, ...]. - Gary W. Adamson, Nov 07 2007
a(2)=0, a(3)=3, a(4)=10, a(n) = 4*a(n-1) - 5*a(n-2) + 2*a(n-3). - Harvey P. Dale, Aug 23 2011
a(n) = (Sum_{k=2..floor(n/2)} binomial(n+1,k)) + if(n odd, binomial(n+1,(n+1)/2)/2, 0).
a(n) = Sum_{k=0..n-3} Sum_{i=0..n-1} C(i,k). - Wesley Ivan Hurt, Sep 20 2017

Additional comments from Michael Steyer, Dec 02 2000
More terms from Larry Reeves (larryr(AT)acm.org), Dec 04 2000
I recently changed the beginning of this sequence so the formulas etc. may need to be adjusted. - N. J. A. Sloane, Jan 24 2006
Formulas and comments adjusted for offset by Franklin T. Adams-Watters, Nov 10 2011

A058844 Number of ways of placing n labeled balls into 4 indistinguishable boxes with at least 2 balls in each box.

Original entry on oeis.org

105, 1260, 9450, 56980, 302995, 1487200, 6914908, 30950920, 134779645, 575156036, 2417578670, 10046531276, 41388056231, 169371383384, 689568172832, 2796362035104, 11305163394129, 45595968007260, 183557935474290, 737897437077060, 2963015460969915

Offset: 8

Michael Steyer, Dec 02 2000

			a(8) = 8!/(2!*2!*2!*2!*4!) = 105.

T. D. Noe, Table of n, a(n) for n=8..200
Daniel J. Bernstein and Andreas Hülsing, Decisional second-preimage resistance: When does SPR imply PRE?, (2019).
Erik Vigren and Andreas Dieckmann, A New Result in Form of Finite Triple Sums for a Series from Ramanujan's Notebooks, Symmetry (2022) Vol. 14, No. 6, 1090.

Cf. A000247 (2 boxes), A000478 (3 boxes).

[(4^n-3^(n-1)*(4*n+12)+2^(n-1)*(12+9*n+3*n^2)-4*n^3-8*n-4)/24 : n in [8..25]]; // Wesley Ivan Hurt, Oct 28 2014

A058844:=n->(4^n-3^(n-1)*(4*n+12)+2^(n-1)*(12+9*n+3*n^2)-4*n^3-8*n-4)/24: seq(A058844(n), n=8..25); # Wesley Ivan Hurt, Oct 28 2014

Table[(4^n - 3^(n - 1) (4 n + 12) + 2^(n - 1) (12 + 9 n + 3 n^2) - 4 n^3 - 8 n - 4)/24, {n, 8, 25}] (* Wesley Ivan Hurt, Oct 28 2014 *)
offset = 8; terms = 21; egf = (Exp[x]-1-x)^4/4!; Drop[CoefficientList[egf + O[x]^(terms+offset), x]*Range[0, terms+offset-1]!, offset] (* Jean-François Alcover, May 07 2017 *)

a(n)=(4^n - 3^(n-1)*(4*n+12) + 2^(n-1)*(12+9*n+3*n^2) - 4*n^3 - 8*n - 4)/24 \\ Charles R Greathouse IV, Oct 28 2014

E.g.f.: ((exp(x) - 1 - x)^4)/4!.
G.f.: x^8*(288*x^6 - 1560*x^5 + 3500*x^4 - 4130*x^3 + 2625*x^2 - 840*x + 105) / ((1 - x)^4*(1 - 2*x)^3*(1 - 3*x)^2*(1 - 4*x)).
a(n) = (4^n-3^(n-1)(4n+12)+2^(n-1)(12+9n+3n^2)-4n^3-8n-4)/24. - David Wasserman, Jun 06 2007

More terms from James Sellers, Dec 06 2000

A272352 a(n) is the number of ways of putting n labeled balls into 2 indistinguishable boxes such that each box contains at least 3 balls.

Original entry on oeis.org

10, 35, 91, 210, 456, 957, 1969, 4004, 8086, 16263, 32631, 65382, 130900, 261953, 524077, 1048344, 2096898, 4194027, 8388307, 16776890, 33554080, 67108485, 134217321, 268435020, 536870446, 1073741327, 2147483119, 4294966734, 8589933996, 17179868553

Offset: 6

Vincenzo Librandi, May 11 2016

			For n=6, label the balls A, B, C, D, E, and F. Then each box must contain exactly 3 balls, and the 10 ways are ABC/DEF, ABD/CEF, ABE/CDF, ABF/CDE, ACD/BEF, ACE/BDF, ACF/BDE, ADE/BCF, ADF/BCE, AEF/BCD. - _Michael B. Porter_, Jul 01 2016

Vincenzo Librandi, Table of n, a(n) for n = 6..1000
I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637 [math.CO], 2013 (page 16).
Index entries for linear recurrences with constant coefficients, signature (5,-9,7,-2).

Cf. A000478, A058844, A261724, A272982, column 2 of A059022.

Column k=3 of A201385 (shifted).

[(2^n-2-2*n-2*Binomial(n,2))/2: n in [6..50]];

Table[1/2 (2^n - 2 - 2 n - 2 Binomial[n, 2]), {n, 6, 40}]
LinearRecurrence[{5,-9,7,-2},{10,35,91,210},30] (* Harvey P. Dale, Mar 29 2018 *)

G.f.: x^6*(10 - 15*x + 6*x^2)/((1 - x)^3*(1 - 2*x)).
a(n) = (2^n - 2 - 2*n - 2*binomial(n, 2))/2.
a(n) = 5*a(n-1) - 9*a(n-2) + 7*a(n-3) - 2*a(n-4), for n > 3.
E.g.f.: (2 - 2*exp(x) + 2*x + x^2)^2/8. - Stefano Spezia, Jul 25 2021

A261724 a(n) is the number of ways of putting n labeled balls into 4 indistinguishable boxes such that each box contains at least 3 balls.

Original entry on oeis.org

15400, 200200, 1611610, 10335325, 57962905, 297797500, 1439774336, 6662393738, 29844199346, 130445781284, 559533979466, 2365296391535, 9885290914059, 40944327590760, 168389163468240, 688631376550260, 2803570746766140, 11373212443859760, 46006062639998890

Offset: 12

Vincenzo Librandi, May 17 2016

Linear recurrence signature is given by the terms of A255002 after -1. - Bruno Berselli, May 20 2016

Colin Barker, Table of n, a(n) for n = 12..1000
I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637 [math.CO], 2013 (third formula on page 16 is incorrect).
Index entries for linear recurrences with constant coefficients, signature (30, -415, 3514, -20386, 85924, -272198, 661180, -1244717, 1822478, -2068955, 1802474, -1181760, 563888, -184752, 37152, -3456).

Cf. A000478, A058844, A272352, A272982, column 4 of A059022.

[(1/12)*(-3^(n-2)*(n^2+5*n+18)+(1/64)*(2^(2*n+5)+3*2^n*(n^4+2*n^3+19*n^2+42*n+64)-16*(n^6-9*n^5+43*n^4-91*n^3+112*n^2-32*n+8))): n in [12..40]];

Table[(1/12) (-(3^(n - 2) (n^2 + 5 n + 18)) + (1/64) (2^(2 n + 5) + 3 2^n (n^4 + 2 n^3 + 19 n^2 + 42 n + 64) - 16 (n^6 - 9 n^5 + 43 n^4 - 91 n^3 + 112 n^2 - 32 n + 8))), {n, 12, 40}]

Vec(x^12*(15400 -261800*x +1996610*x^2 -9045575*x^3 +27162905*x^4 -57079715*x^5 +86268721*x^6 -94696602*x^7 +75062256*x^8 -41952000*x^9 +15705360*x^10 -3538080*x^11 +362880*x^12) / ((1 -x)^7*(1 -2*x)^5*(1 -3*x)^3*(1 -4*x)) + O(x^30)) \\ Colin Barker, May 24 2016

a(n) = (1/12)*(-3^(n - 2)*(n^2 + 5*n + 18) + (1/64)*(2^(2*n + 5) + 3*2^n*(n^4 + 2*n^3 + 19*n^2 + 42*n + 64) - 16*(n^6 - 9*n^5 + 43*n^4 - 91*n^3 + 112*n^2 - 32*n + 8))).

G.f.: x^12*(15400 -261800*x +1996610*x^2 -9045575*x^3 +27162905*x^4 -57079715*x^5 +86268721*x^6 -94696602*x^7 +75062256*x^8 -41952000*x^9 +15705360*x^10 -3538080*x^11 +362880*x^12) / ((1 -x)^7*(1 -2*x)^5*(1 -3*x)^3*(1 -4*x)). - Colin Barker, May 24 2016

Definition, data and formula corrected by Istvan Mezo and Bruno Berselli, May 20 2016

A272982 a(n) is the number of ways of putting n labeled balls into 3 indistinguishable boxes such that each box contains at least 3 balls.

Original entry on oeis.org

280, 2100, 10395, 42735, 158301, 549549, 1827826, 5903898, 18682014, 58257810, 179765973, 550478241, 1676305723, 5083927299, 15372843684, 46383762084, 139730030100, 420448298400, 1264071094975, 3798101973315, 11406989362185, 34248214131465, 102803026929030, 308533903071390

Offset: 9

Vincenzo Librandi, May 12 2016

			For n=9, label the balls A through I. The box containing ball A can contain 8*7/2 = 28 combinations of other balls. There are 6 balls for the other two boxes, so there are A272352(6) = 10 combinations for those two boxes. Thus, a(9) = 28*10 = 280. - _Michael B. Porter_, Jul 01 2016

Vincenzo Librandi, Table of n, a(n) for n = 9..1000
I. Mezo, Periodicity of the last digits of some combinatorial sequences, arXiv preprint arXiv:1308.1637 [math.CO], 2013 (second formula on page 16 is incorrect).
Index entries for linear recurrences with constant coefficients, signature (14,-85,294,-639,906,-839,490,-164,24).

Cf. A000478, A058844, A261724, A272352, column 3 of A059022.

[(1/3)*(1/16)*(6*n^4-12*n^3-3*2^n*n^2+42*n^2-9*2^n*n+12*n+8*3^n-3*2^(n+3)+24): n in [9..40]];

Table[(1/3) (1/16) (6 n^4 - 12 n^3 - 3 2^n n^2 + 42 n^2 - 9 2^n n + 12 n + 8 3^n - 3 2^(n + 3) + 24), {n, 9, 40}]
CoefficientList[Series[(280 - 1820*x + 4795*x^2 - 6615*x^3 + 5106*x^4 - 2100*x^5 + 360*x^6)/((1 - 3*x)*(1 - 2*x)^3*(1 - x)^5), {x, 0, 40}], x] (* Stefano Spezia, Oct 04 2018 *)

Vec(x^9*(280 - 1820*x + 4795*x^2 - 6615*x^3 + 5106*x^4 - 2100*x^5 + 360*x^6)/((1 - 3*x)*(1 - 2*x)^3*(1 - x)^5) + O(x^40)) \\ Stefano Spezia, Oct 04 2018

G.f.: x^9*(280 - 1820*x + 4795*x^2 - 6615*x^3 + 5106*x^4 - 2100*x^5 + 360*x^6)/((1 - 3*x)*(1 - 2*x)^3*(1 - x)^5).
a(n) = (1/3)*(1/16)*(6*n^4 - 12*n^3 - 3*2^n*n^2 + 42*n^2 - 9*2^n*n + 12*n + 8*3^n - 3*2^(n+3) + 24).
a(n) = 3*a(n-1) + C(n-1,2)*(2^(n-4) + 2 - n - C(n-3, 2)), a(n)=0, n < 9. - Vladimir Kruchinin, Oct 04 2018

Data, formulas and programs corrected for erroneous formula in Mezo's paper by Bruno Berselli, May 21 2016

A224541 Number of doubly-surjective functions f:[n]->[3].

Original entry on oeis.org

90, 630, 2940, 11508, 40950, 137610, 445896, 1410552, 4390386, 13514046, 41278068, 125405532, 379557198, 1145747538, 3452182656, 10388002848, 31230066186, 93828607686, 281775226860, 845929656900, 2539047258150, 7619759016090, 22864712861880, 68605412870088

Offset: 6

Dennis P. Walsh, Apr 09 2013

Third column of A200091.
Also, a(n) is (i) the number of length-n words on the alphabet A, B, and C with each letter occurring at least twice; (ii) the number of ways to distribute n different toys to 3 different children so that each child gets at least 2 toys; (iii) the number of ways to put n numbered balls into 3 labeled boxes so that each box gets at least 2 balls; (iv) the number of n-digit positive integers consisting only of the digits 1, 2, and 3 with each of these digits appearing at least twice. A doubly-surjective function f has size at least 2 for each pre-image set, that is, |f^-1(y)|>=2 for each element y of the codomain.[Note that a surjective function has |f^-1(y)|>=1.] The triangle A200091 provides the number of doubly-surjective functions f:[n]->[k].  Column 3 of triangle A200091 is a(n).
Sequence A052515 is the number of doubly-surjective functions f:[n]->[2] with exponential generating function (exp(x)-x-1)^2. In general, the number of doubly-surjective functions f:[n]->[k] has exponential generating function (exp(x)-x-1)^k.

			For n=6 we have a(6)=90 since there are 90 six-digit  positive integers using only digits 1, 2, and 3 with each of those digits appearing at least twice. The first 30 of the ninety, namely those with initial digit 1, are given below:
112233, 112323, 112332, 113223, 113232, 113322,
121233, 121323, 121332, 122133, 122313, 122331,
123123, 123132, 123213, 123231, 123312, 123321,
131223, 131232, 131322, 132123, 132132, 132213,
132231, 132312, 132321, 133122, 133212, 133221.

Dennis Walsh, Notes on doubly-surjective finite functions

Cf. A052515, the number of doubly-surjective functions f:[n]->[2].

seq(3^n-3*2^n-3*n*2^(n-1)+3+3*n+3*n^2, n=6..40);

With[{nn=40},Drop[CoefficientList[Series[(Exp[x]-x-1)^3,{x,0,nn}],x] Range[0,nn]!,6]] (* Harvey P. Dale, Oct 01 2015 *)

x='x+O('x^66); Vec(serlaplace((exp(x)-x-1)^3)) \\ Joerg Arndt, Apr 10 2013

a(n) = 3^n-3*2^n-3*n*2^(n-1)+3+3*n+3*n^2.
E.g.f.: (exp(x)-x-1)^3.
From Alois P. Heinz, Apr 10 2013: (Start)
a(n) = 6*A000478(n).
G.f.: -6*(12*x^3-40*x^2+45*x-15)*x^6 / ((3*x-1)*(2*x-1)^2*(x-1)^3).
(End)

cp's OEIS Frontend

A008299 Triangle T(n,k) of associated Stirling numbers of second kind, n >= 2, 1 <= k <= floor(n/2).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A134991 Triangle of Ward numbers T(n,k) read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A000247 a(n) = 2^n - n - 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

Maxima

PARI

Sage

Formula

Extensions

A058844 Number of ways of placing n labeled balls into 4 indistinguishable boxes with at least 2 balls in each box.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A272352 a(n) is the number of ways of putting n labeled balls into 2 indistinguishable boxes such that each box contains at least 3 balls.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A261724 a(n) is the number of ways of putting n labeled balls into 4 indistinguishable boxes such that each box contains at least 3 balls.

Views

Author

Keywords

Comments

Links

A384374 Expansion of e.g.f. exp(x)(exp(x) - 1)(exp(x) - x - 1)^2.