cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Previous Showing 41-50 of 261 results. Next

A019538 Triangle of numbers T(n,k) = k!*Stirling2(n,k) read by rows (n >= 1, 1 <= k <= n).

Original entry on oeis.org

1, 1, 2, 1, 6, 6, 1, 14, 36, 24, 1, 30, 150, 240, 120, 1, 62, 540, 1560, 1800, 720, 1, 126, 1806, 8400, 16800, 15120, 5040, 1, 254, 5796, 40824, 126000, 191520, 141120, 40320, 1, 510, 18150, 186480, 834120, 1905120, 2328480, 1451520, 362880, 1, 1022, 55980, 818520, 5103000, 16435440, 29635200, 30240000, 16329600, 3628800
Offset: 1

Views

Author

N. J. A. Sloane and Manfred Goebel (goebel(AT)informatik.uni-tuebingen.de), Dec 11 1996

Keywords

Comments

Number of ways n labeled objects can be distributed into k nonempty parcels. Also number of special terms in n variables with maximal degree k.
In older terminology these are called differences of 0. - Michael Somos, Oct 08 2003
Number of surjections (onto functions) from an n-element set to a k-element set.
Also coefficients (in ascending order) of so-called ordered Bell polynomials.
(k-1)!*Stirling2(n,k-1) is the number of chain topologies on an n-set having k open sets [Stephen].
Number of set compositions (ordered set partitions) of n items into k parts. Number of k dimensional 'faces' of the n dimensional permutohedron (see Simion, p. 162). - Mitch Harris, Jan 16 2007
Correction of comment before: Number of (n-k)-dimensional 'faces' of the permutohedron of order n (an (n-1)-dimensional polytope). - Tilman Piesk, Oct 29 2014
This array is related to the reciprocal of an e.g.f. as sketched in A133314. For example, the coefficient of the fourth-order term in the Taylor series expansion of 1/(a(0) + a(1) x + a(2) x^2/2! + a(3) x^3/3! + ...) is a(0)^(-5) * {24 a(1)^4 - 36 a(1)^2 a(2) a(0) + [8 a(1) a(3) + 6 a(2)^2] a(0)^2 - a(4) a(0)^3}. The unsigned coefficients characterize the P3 permutohedron depicted on page 10 in the Loday link with 24 vertices (0-D faces), 36 edges (1-D faces), 6 squares (2-D faces), 8 hexagons (2-D faces) and 1 3-D permutohedron. Summing coefficients over like dimensions gives A019538 and A090582. Compare to A133437 for the associahedron. - Tom Copeland, Sep 29 2008, Oct 07 2008
Further to the comments of Tom Copeland above, the permutohedron of type A_3 can be taken as the truncated octahedron. Its dual is the tetrakis hexahedron, a simplicial polyhedron, with f-vector (1,14,36,24) giving the fourth row of this triangle. See the Wikipedia entry and [Fomin and Reading p. 21]. The corresponding h-vectors of permutohedra of type A give the rows of the triangle of Eulerian numbers A008292. See A145901 and A145902 for the array of f-vectors for type B and type D permutohedra respectively. - Peter Bala, Oct 26 2008
Subtriangle of triangle in A131689. - Philippe Deléham, Nov 03 2008
Since T(n,k) counts surjective functions and surjective functions are "consistent", T(n,k) satisfies a binomial identity, namely, T(n,x+y) = Sum_{j=0..n} C(n,j)*T(j,x)*T(n-j,y). For definition of consistent functions and a generalized binomial identity, see "Toy stories and combinatorial identities" in the link section below. - Dennis P. Walsh, Feb 24 2012
T(n,k) is the number of labeled forests on n+k vertices satisfying the following two conditions: (i) each forest consists of exactly k rooted trees with roots labeled 1, 2, ..., k; (ii) every root has at least one child vertex. - Dennis P. Walsh, Feb 24 2012
The triangle is the inverse binomial transform of triangle A028246, deleting the left column and shifting up one row. - Gary W. Adamson, Mar 05 2012
See A074909 for associations among this array and the Bernoulli polynomials and their umbral compositional inverses. - Tom Copeland, Nov 14 2014
E.g.f. for the shifted signed polynomials is G(x,t) = (e^t-1)/[1+(1+x)(e^t-1)] = 1-(1+x)(e^t-1) + (1+x)^2(e^t-1)^2 - ... (see also A008292 and A074909), which has the infinitesimal generator g(x,u)d/du = [(1-x*u)(1-(1+x)u)]d/du, i.e., exp[t*g(x,u)d/du]u eval. at u=0 gives G(x,t), and dG(x,t)/dt = g(x,G(x,t)). The compositional inverse is log((1-xt)/(1-(1+x)t)). G(x,t) is a generating series associated to the generalized Hirzebruch genera. See the G. Rzadowski link for the relation of the derivatives of g(x,u) to solutions of the Riccatt differential equation, soliton solns. to the KdV equation, and the Eulerian and Bernoulli numbers. In addition A145271 connects products of derivatives of g(x,u) and the refined Eulerian numbers to the inverse of G(x,t), which gives the normalized, reverse face polynomials of the simplices (A135278, divided by n+1). See A028246 for the generator g(x,u)d/dx. - Tom Copeland, Nov 21 2014
For connections to toric varieties and Eulerian polynomials, see the Dolgachev and Lunts and the Stembridge links. - Tom Copeland, Dec 31 2015
See A008279 for a relation between the e.g.f.s enumerating the faces of permutahedra (this entry) and stellahedra. - Tom Copeland, Nov 14 2016
T(n, k) appears in a Worpitzky identity relating monomials to binomials: x^n = Sum_{k=1..n} T(n, k)*binomial(x,k), n >= 1. See eq. (11.) of the Worpitzky link on p. 209. The relation to the Eulerian numbers is given there in eqs. (14.) and (15.). See the formula below relating to A008292. See also Graham et al. eq. (6.10) (relating monomials to falling factorials) on p. 248 (2nd ed. p. 262). The Worpitzky identity given in the Graham et al. reference as eq. (6.37) (2nd ed. p. 269) is eq. (5.), p. 207, of Worpitzky. - Wolfdieter Lang, Mar 10 2017
T(n, m) is also the number of minimum clique coverings and minimum matchings in the complete bipartite graph K_{m,n}. - Eric W. Weisstein, Apr 26 2017
From the Hasan and Franco and Hasan papers: The m-permutohedra for m=1,2,3,4 are the line segment, hexagon, truncated octahedron and omnitruncated 5-cell. The first three are well-known from the study of elliptic models, brane tilings and brane brick models. The m+1 torus can be tiled by a single (m+2)-permutohedron. Relations to toric Calabi-Yau Kahler manifolds are also discussed. - Tom Copeland, May 14 2020
From Manfred Boergens, Jul 25 2021: (Start)
Number of n X k binary matrices with row sums = 1 and no zero columns. These matrices are a subset of the matrices defining A183109.
The distribution into parcels in the leading comment can be regarded as a covering of [n] by tuples (A_1,...,A_k) in P([n])^k with nonempty and disjoint A_j, with P(.) denoting the power set (corrected for clarity by Manfred Boergens, May 26 2024). For the non-disjoint case see A183109 and A218695.
For tuples with "nonempty" dropped see A089072. For tuples with "nonempty and disjoint" dropped see A092477 and A329943 (amendment by Manfred Boergens, Jun 24 2024). (End)

Examples

			The triangle T(n, k) begins:
  n\k 1    2     3      4       5        6        7        8        9      10
  1:  1
  2:  1    2
  3:  1    6     6
  4:  1   14    36     24
  5:  1   30   150    240     120
  6:  1   62   540   1560    1800      720
  7:  1  126  1806   8400   16800    15120     5040
  8:  1  254  5796  40824  126000   191520   141120    40320
  9:  1  510 18150 186480  834120  1905120  2328480  1451520   362880
  10: 1 1022 55980 818520 5103000 16435440 29635200 30240000 16329600 3628800
  ... Reformatted and extended - _Wolfdieter Lang_, Oct 04 2014
---------------------------------------------------------------------------
T(4,1) = 1: {1234}. T(4,2) = 14: {1}{234} (4 ways), {12}{34} (6 ways), {123}{4} (4 ways). T(4,3) = 36: {12}{3}{4} (12 ways), {1}{23}{4} (12 ways), {1}{2}{34} (12 ways). T(4,4) = 1: {1}{2}{3}{4} (1 way).

References

  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 89, ex. 1; also p. 210.
  • Miklos Bona, Combinatorics of Permutations, Chapman and Hall,2004, p.12.
  • G. Boole, A Treatise On The Calculus of Finite Differences, Dover Publications, 1960, p. 20.
  • H. T. Davis, Tables of the Mathematical Functions. Vols. 1 and 2, 2nd ed., 1963, Vol. 3 (with V. J. Fisher), 1962; Principia Press of Trinity Univ., San Antonio, TX, Vol. 2, p. 212.
  • R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, 1989, p. 155. Also eqs.(6.10) and (6.37).
  • Kiran S. Kedlaya and Andrew V. Sutherland, Computing L -Series of Hyperelliptic Curves in Algorithmic Number Theory Lecture Notes in Computer Science Volume 5011/2008.
  • T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Section 5.6.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 33.
  • J. F. Steffensen, Interpolation, 2nd ed., Chelsea, NY, 1950, see p. 54.
  • A. H. Voigt, Theorie der Zahlenreihen und der Reihengleichungen, Goschen, Leipzig, 1911, p. 31.
  • E. Whittaker and G. Robinson, The Calculus of Observations, Blackie, London, 4th ed., 1949; p. 7.

Links

Crossrefs

Row sums give A000670. Maximal terms in rows give A002869. Central terms T(2k-1,k) give A233734.
Diagonal is n! (A000142). 2nd diagonal is A001286. 3rd diagonal is A037960.
Cf. A000918, A000919, A001117, A001118, A008275, A008277, A008279, A048594, A059117, A059515, A074909, A084938, A089072, A092477, A183109, A218695, A329943.
Reflected version of A090582. A371568 is another version.
See also the two closely related triangles: A008277(n, k) = T(n, k)/k! (Stirling numbers of second kind) and A028246(n, k) = T(n, k)/k.
Cf. A033282 'faces' of the associahedron.
Cf. A008292, A047969, A145901, A145902. - Peter Bala, Oct 26 2008
Visible in the 3-D array in A249042.
See also A000182.

Programs

  • Haskell
    a019538 n k = a019538_tabl !! (n-1) !! (k-1)
a019538_row n = a019538_tabl !! (n-1)
a019538_tabl = iterate f [1] where
   f xs = zipWith (*) [1..] $ zipWith (+) ([0] ++ xs) (xs ++ [0])
-- Reinhard Zumkeller, Dec 15 2013
  • Maple
    with(combinat): A019538 := (n,k)->k!*stirling2(n,k);
  • Mathematica
    Table[k! StirlingS2[n, k], {n, 9}, {k, n}] // Flatten
  • PARI
    {T(n, k) = if( k<0 || k>n, 0, sum(i=0, k, (-1)^i * binomial(k, i) * (k-i)^n))}; /* Michael Somos, Oct 08 2003 */
  • Sage
    def T(n, k): return factorial(k)*stirling_number2(n,k) # Danny Rorabaugh, Oct 10 2015

Formula

T(n, k) = k*(T(n-1, k-1)+T(n-1, k)) with T(0, 0) = 1 [or T(1, 1) = 1]. - Henry Bottomley, Mar 02 2001
E.g.f.: (y*(exp(x)-1) - exp(x))/(y*(exp(x)-1) - 1). - Vladeta Jovovic, Jan 30 2003
Equals [0, 1, 0, 2, 0, 3, 0, 4, 0, 5, ...] DELTA [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...] where DELTA is Deléham's operator defined in A084938.
T(n, k) = Sum_{j=0..k} (-1)^(k-j)*j^n*binomial(k, j). - Mario Catalani (mario.catalani(AT)unito.it), Nov 28 2003. See Graham et al., eq. (6.19), p. 251. For a proof see Bert Seghers, Jun 29 2013.
Sum_{k=0..n} T(n, k)(-1)^(n-k) = 1, Sum_{k=0..n} T(n, k)(-1)^k = (-1)^n. - Mario Catalani (mario.catalani(AT)unito.it), Dec 11 2003
O.g.f. for n-th row: polylog(-n, x/(1+x))/(x+x^2). - Vladeta Jovovic, Jan 30 2005
E.g.f.: 1 / (1 + t*(1-exp(x))). - Tom Copeland, Oct 13 2008
From Peter Bala, Oct 26 2008: (Start)
O.g.f. as a continued fraction: 1/(1 - x*t/(1 - (x + 1)*t/(1 - 2*x*t/(1 - 2*(x + 1)*t/(1 - ...))))) = 1 + x*t + (x + 2*x^2)*t^2 + (x + 6*x^2 + 6*x^3)*t^3 + ... .
The row polynomials R(n,x), which begin R(1,x) = x, R(2,x) = x + 2*x^2, R(3,x) = x + 6*x^2 + 6*x^3, satisfy the recurrence x*d/dx ((x + 1)*R(n,x)) = R(n+1,x). It follows that the zeros of R(n,x) are real and negative (apply Corollary 1.2 of [Liu and Wang]).
Since this is the triangle of f-vectors of the (simplicial complexes dual to the) type A permutohedra, whose h-vectors form the Eulerian number triangle A008292, the coefficients of the polynomial (x-1)^n*R(n,1/(x-1)) give the n-th row of A008292. For example, from row 3 we have x^2 + 6*x + 6 = 1 + 4*y + y^2, where y = x + 1, producing [1,4,1] as the third row of A008292. The matrix product A008292 * A007318 gives the mirror image of this triangle (see A090582).
For n,k >= 0, T(n+1,k+1) = Sum_{j=0..k} (-1)^(k-j)*binomial(k,j)*[(j+1)^(n+1) - j^(n+1)]. The matrix product of Pascal's triangle A007318 with the current array gives (essentially) A047969. This triangle is also related to triangle A047969 by means of the S-transform of [Hetyei], a linear transformation of polynomials whose value on the basis monomials x^k is given by S(x^k) = binomial(x,k). The S-transform of the shifted n-th row polynomial Q(n,x) := R(n,x)/x is S(Q(n,x)) = (x+1)^n - x^n. For example, from row 3 we obtain S(1 + 6*x + 6*x^2) = 1 + 6*x + 6*x*(x-1)/2 = 1 + 3*x + 3*x^2 = (x+1)^3 - x^3. For fixed k, the values S(Q(n,k)) give the nonzero entries in column (k-1) of the triangle A047969 (the Hilbert transform of the Eulerian numbers). (End)
E.g.f.: (exp(x)-1)^k = sum T(n,k)x^n/n!. - Vladimir Kruchinin, Aug 10 2010
T(n,k) = Sum_{i=1..k} A(n,i)*Binomial(n-i,k-i) where A(n,i) is the number of n-permutations that have i ascending runs, A008292.
From Tom Copeland, Oct 11 2011: (Start)
With e.g.f. A(x,t) = -1 + 1/(1+t*(1-exp(x))), the comp. inverse in x is B(x,t) = log(((1+t)/t) - 1/(t(1+x))).
With h(x,t) = 1/(dB/dx)= (1+x)((1+t)(1+x)-1), the row polynomial P(n,t) is given by (h(x,t)*d/dx)^n x, eval. at x=0, A=exp(x*h(y,t)*d/dy) y, eval. at y=0, and dA/dx = h(A(x,t),t), with P(0,t)=0.
(A factor of -1/n! was removed by Copeland on Aug 25 2016.) (End)
The term linear in x of [x*h(d/dx,t)]^n 1 gives the n-th row polynomial. (See A134685.) - Tom Copeland, Nov 07 2011
Row polynomials are given by D^n(1/(1-x*t)) evaluated at x = 0, where D is the operator (1+x)*d/dx. - Peter Bala, Nov 25 2011
T(n,x+y) = Sum_{j=0..n} binomial(n,j)*T(j,x)*T(n-j,y). - Dennis P. Walsh, Feb 24 2012
Let P be a Rota-Baxter operator of weight 1 satisfying the identity P(x)*P(y) = P(P(x)*y) + P(x*P(y)) + P(x*y). Then P(1)^2 = P(1) + 2*P^2(1). More generally, Guo shows that P(1)^n = Sum_{k=1..n} T(n,k)*P^k(1). - Peter Bala, Jun 08 2012
Sum_{i=1..n} (-1)^i*T(n,i)/i = 0, for n > 1. - Leonid Bedratyuk, Aug 09 2012
T(n, k) = Sum_{j=0..k} (-1)^j*binomial(k, j)*(k-j)^n. [M. Catalani's re-indexed formula from Nov 28 2003] Proof: count the surjections of [n] onto [k] with the inclusion-exclusion principle, as an alternating sum of the number of functions from [n] to [k-j]. - Bert Seghers, Jun 29 2013
n-th row polynomial = 1/(1 + x)*( Sum_{k>=0} k^n*(x/(1 + x))^k ), valid for x in the open interval (-1/2, inf). See Tanny link. Cf. A145901. - Peter Bala, Jul 22 2014
T(n,k) = k * A141618(n,k-1) / binomial(n,k-1). - Tom Copeland, Oct 25 2014
Sum_{n>=0} n^k*a^n = Sum_{i=1..k} (a / (1 - a))^i * T(k, i)/(1-a) for |a| < 1. - David A. Corneth, Mar 09 2015
From Peter Bala, May 26 2015: (Start)
The row polynomials R(n,x) satisfy (1 + x)*R(n,x) = (-1)^n*x*R(n,-(1 + x)).
For a fixed integer k, the expansion of the function A(k,z) := exp( Sum_{n >= 1} R(n,k)*z^n/n ) has integer coefficients and satisfies the functional equation A(k,z)^(k + 1) = BINOMIAL(A(k,z))^k, where BINOMIAL(F(z))= 1/(1 - z)*F(z/(1 - z)) denotes the binomial transform of the o.g.f. F(z). Cf. A145901. For cases see A084784 (k = 1), A090352 (k = 2), A090355 (k = 3), A090357 (k = 4), A090362 (k = 5) and A084785 (k = -2 with z -> -z).
A(k,z)^(k + 1) = A(-(k + 1),-z)^k and hence BINOMIAL(A(k,z)) = A(-(k + 1),-z). (End)
From Tom Copeland, Oct 19 2016: (Start)
Let a(1) = 1 + x + B(1) = x + 1/2 and a(n) = B(n) = (B.)^n, where B(n) are the Bernoulli numbers defined by e^(B.t) = t / (e^t-1), then t / e^(a.t) = t / [(x + 1) * t + exp(B.t)] = (e^t - 1) /[ 1 + (x + 1) (e^t - 1)] = exp(p.(x)t), where (p.(x))^n = p_n(x) are the shifted, signed row polynomials of this array: p_0(x) = 0, p_1(x) = 1, p_2(x) = -(1 + 2 x), p_3(x) = 1 + 6 x + 6 x^2, ... and p_n(x) = n * b(n-1), where b(n) are the partition polynomials of A133314 evaluated with these a(n).
Sum_{n > 0} R(n,-1/2) x^n/n! = 2 * tanh(x/2), where R(n,x) = Sum_{k = 1..n} T(n,k) x^(k-1) are the shifted row polynomials of this entry, so R(n,-1/2) = 4 * (2^(n+1)-1) B(n+1)/(n+1). (Cf. A000182.)
(End)
Also the Bernoulli numbers are given by B(n) = Sum_{k =1..n} (-1)^k T(n,k) / (k+1). - Tom Copeland, Nov 06 2016
G.f. for column k: k! x^k / Product_{i=1..k} (1-i*x). - Robert A. Russell, Sep 25 2018
a(j) <= A183109(j). - Manfred Boergens, Jul 25 2021

A000669 Number of series-reduced planted trees with n leaves. Also the number of essentially series series-parallel networks with n edges; also the number of essentially parallel series-parallel networks with n edges.

Original entry on oeis.org

1, 1, 2, 5, 12, 33, 90, 261, 766, 2312, 7068, 21965, 68954, 218751, 699534, 2253676, 7305788, 23816743, 78023602, 256738751, 848152864, 2811996972, 9353366564, 31204088381, 104384620070, 350064856815, 1176693361956, 3963752002320
Offset: 1

Views

Author

N. J. A. Sloane and John Riordan

Keywords

Comments

Also the number of unlabeled connected cographs on n nodes. - N. J. A. Sloane and Eric W. Weisstein, Oct 21 2003
A cograph is a simple graph which contains no path of length 3 as an induced subgraph. - Michael Somos, Apr 19 2014
Also called "hierarchies" by Genitrini (2016). - N. J. A. Sloane, Mar 24 2017

Examples

			G.f. = x + x^2 + 2*x^3 + 5*x^4 + 12*x^5 + 33*x^6 + 90*x^7 + 261*x^8 + ...
a(4)=5 with the following series-reduced planted trees: (oooo), (oo(oo)), (o(ooo)), (o(o(oo))), ((oo)(oo)). - _Michael Somos_, Jul 25 2003

References

  • N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 43.
  • A. Brandstaedt, V. B. Le and J. P. Spinrad, Graph Classes: A Survey, SIAM Publications, 1999. (For definition of cograph)
  • A. Cayley, Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 3, p. 246.
  • D. E. Knuth, The Art of Computer Programming, 3rd ed. 1997, Vol. 1, p. 589, Answers to Exercises Section 2.3.4.4 5.
  • L. F. Meyers, Corrections and additions to Tree Representations in Linguistics. Report 3, 1966, p. 138. Project on Linguistic Analysis, Ohio State University Research Foundation, Columbus, Ohio.
  • L. F. Meyers and W. S.-Y. Wang, Tree Representations in Linguistics. Report 3, 1963, pp. 107-108. Project on Linguistic Analysis, Ohio State University Research Foundation, Columbus, Ohio.
  • J. Riordan and C. E. Shannon, The number of two-terminal series-parallel networks, J. Math. Phys., 21 (1942), 83-93 (the numbers called a_n in this paper). Reprinted in Claude Elwood Shannon: Collected Papers, edited by N. J. A. Sloane and A. D. Wyner, IEEE Press, NY, 1993, pp. 560-570.
  • 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).

Links

Crossrefs

Equals (1/2)*A000084 for n >= 2.
Cf. A000055, A000311, A001678, A007827, A363064.
Cf. A000311, labeled hierarchies on n points.
Column 1 of A319254.
Main diagonal of A292085.
Row sums of A292086.

Programs

  • Maple
    Method 1: a := [1,1]; for n from 3 to 30 do L := series( mul( (1-x^k)^(-a[k]),k=1..n-1)/(1-x^n)^b, x,n+1); t1 := coeff(L,x,n); R := series( 1+2*add(a[k]*x^k,k=1..n-1)+2*b*x^n, x, n+1); t2 := coeff(R,x,n); t3 := solve(t1-t2,b); a := [op(a),t3]; od: A000669 := n-> a[n];
Method 2, more efficient: with(numtheory): M := 1001; a := array(0..M); p := array(0..M); a[1] := 1; a[2] := 1; a[3] := 2; p[1] := 1; p[2] := 3; p[3] := 7;
Method 2, cont.: for m from 4 to M do t1 := divisors(m); t3 := 0; for d in t1 minus {m} do t3 := t3+d*a[d]; od: t4 := p[m-1]+2*add(p[k]*a[m-k],k=1..m-2)+t3; a[m] := t4/m; p[m] := t3+t4; od: # A000669 := n-> a[n]; A058757 := n->p[n];
# Method 3:
b:= proc(n, i) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(a(i)+j-1, j)*
       b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> `if`(n<2, n, b(n, n-1)):
seq(a(n), n=1..40);  # Alois P. Heinz, Jan 28 2016
  • Mathematica
    b[n_, i_] := b[n, i] = If[n==0, 1, If[i<1, 0, Sum[Binomial[a[i]+j-1, j]* b[n-i*j, i-1], {j, 0, n/i}]]];
a[n_] := If[n<2, n, b[n, n-1]];
Array[a, 40] (* Jean-François Alcover, Jan 08 2021, after Alois P. Heinz *)
  • PARI
    {a(n) = my(A, X); if( n<2, n>0, X = x + x * O(x^n); A = 1 / (1 - X); for(k=2, n, A /= (1 - X^k)^polcoeff(A, k)); polcoeff(A, n)/2)}; /* Michael Somos, Jul 25 2003 */
  • Sage
    from collections import Counter
def A000669_list(n):
    list = [1] + [0] * (n - 1)
    for i in range(1, n):
        for p in Partitions(i + 1, min_length=2):
            m = Counter(p)
            list[i] += prod(binomial(list[s - 1] + m[s] - 1, m[s]) for s in m)
    return list
print(A000669_list(20)) # M. Eren Kesim, Jun 21 2021

Formula

Product_{k>0} 1/(1-x^k)^a_k = 1+x+2*Sum_{k>1} a_k*x^k.
a(n) ~ c * d^n / n^(3/2), where d = 3.560839309538943329526129172709667..., c = 0.20638144460078903185013578707202765... [Ravelomanana and Thimonier, 2001]. - Vaclav Kotesovec, Aug 25 2014
Consider a nontrivial partition p of n. For each size s of a part occurring in p, compute binomial(a(s)+m-1, m) where m is the multiplicity of s. Take the product of this expression over all s. Take the sum of this new expression over all p to obtain a(n). - Thomas Anton, Nov 22 2018

Extensions

Sequence crossreference fixed by Sean A. Irvine, Sep 15 2009

A001190 Wedderburn-Etherington numbers: unlabeled binary rooted trees (every node has outdegree 0 or 2) with n endpoints (and 2n-1 nodes in all).

Original entry on oeis.org

0, 1, 1, 1, 2, 3, 6, 11, 23, 46, 98, 207, 451, 983, 2179, 4850, 10905, 24631, 56011, 127912, 293547, 676157, 1563372, 3626149, 8436379, 19680277, 46026618, 107890609, 253450711, 596572387, 1406818759, 3323236238, 7862958391, 18632325319, 44214569100, 105061603969
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Also number of n-node binary rooted trees (every node has outdegree <= 2) where root has degree 0 (only for n=1) or 1.
a(n+1) is the number of rooted trees with n nodes where the outdegree of every node is <= 2, see example. These trees are obtained by removing the root of the trees in the comment above. - Joerg Arndt, Jun 29 2014
Number of interpretations of x^n (or number of ways to insert parentheses) when multiplication is commutative but not associative. E.g., a(4) = 2: x(x*x^2) and x^2*x^2. a(5) = 3: (x*x^2)x^2, x(x*x*x^2) and x(x^2*x^2). [If multiplication is non-commutative then the answer is A000108(n-1). - Jianing Song, Apr 29 2022]
Number of ways to place n stars in a single bound stable hierarchical multiple star system; i.e., taking only the configurations from A003214 where all stars are included in single outer parentheses. - Piet Hut, Nov 07 2003
Number of colorations of Kn (complete graph of order n) with n-1 colors such that no triangle is three-colored. Two edge-colorations C1 and C2 of G are isomorphic iff exists an automorphism f (isomorphism between G an G) such that: f sends same-colored edges of C1 on same-colored edges of C2 and f^(-1) sends same-colored edges of C2 on same-colored edges of C1. - Abraham Gutiérrez, Nov 12 2012
For n>1, a(n) is the number of (not necessarily distinct) unordered pairs of free unlabeled trees having a total of n nodes. See the first entry in formula section. - Geoffrey Critzer, Nov 09 2014
Named after the English mathematician Ivor Etherington (1908-1994) and the Scottish mathematician Joseph Wedderburn (1882-1948). - Amiram Eldar, May 29 2021

Examples

			G.f. = x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 11*x^7 + 23*x^8 + 46*x^9 + 98*x^10 + ...
From _Joerg Arndt_, Jun 29 2014: (Start)
The a(6+1) = 11 rooted trees with 6 nodes as described in the comment are:
:           level sequence       outdegrees (dots for zeros)
:     1:  [ 0 1 2 3 4 5 ]    [ 1 1 1 1 1 . ]
:  O--o--o--o--o--o
:
:     2:  [ 0 1 2 3 4 4 ]    [ 1 1 1 2 . . ]
:  O--o--o--o--o
:           .--o
:
:     3:  [ 0 1 2 3 4 3 ]    [ 1 1 2 1 . . ]
:  O--o--o--o--o
:        .--o
:
:     4:  [ 0 1 2 3 4 2 ]    [ 1 2 1 1 . . ]
:  O--o--o--o--o
:     .--o
:
:     5:  [ 0 1 2 3 4 1 ]    [ 2 1 1 1 . . ]
:  O--o--o--o--o
:  .--o
:
:     6:  [ 0 1 2 3 3 2 ]    [ 1 2 2 . . . ]
:  O--o--o--o
:        .--o
:     .--o
:
:     7:  [ 0 1 2 3 3 1 ]    [ 2 1 2 . . . ]
:  O--o--o--o
:        .--o
:  .--o
:
:     8:  [ 0 1 2 3 2 3 ]    [ 1 2 1 . 1 . ]
:  O--o--o--o
:     .--o--o
:
:     9:  [ 0 1 2 3 2 1 ]    [ 2 2 1 . . . ]
:  O--o--o--o
:     .--o
:  .--o
:
:    10:  [ 0 1 2 3 1 2 ]    [ 2 1 1 . 1 . ]
:  O--o--o--o
:  .--o--o
:
:    11:  [ 0 1 2 2 1 2 ]    [ 2 2 . . 1 . ]
:  O--o--o
:     .--o
:  .--o--o
:
(End)

References

  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 307.
  • Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 55.
  • Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 295-316.
  • A. Gutiérrez-Sánchez, Shen-colored tournaments, thesis, UNAM, 2012.
  • 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).
  • Richard P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.52.
  • Richard P. Stanley, Catalan Numbers, Cambridge, 2015, p. 133.

Links

Crossrefs

Cf. A000108, A001699, A002658, A003214, A006894, A006961, A088325.
Cf. A086317, A086318, A240943.
Cf. A292553, A292554, A292555, A292556.
Column k=2 of A292085 and of A299038.
Column k=1 of A319539 and of A319541.

Programs

  • Maple
    A001190 := proc(n) option remember; local s,k; if n<=1 then RETURN(n); elif n <=3 then RETURN(1); else s := 0; if n mod 2 = 0 then s := A001190(n/2)*(A001190(n/2)+1)/2; for k from 1 to n/2-1 do s := s+A001190(k)*A001190(n-k); od; RETURN(s); else for k from 1 to (n-1)/2 do s := s+A001190(k)*A001190(n-k); od; RETURN(s); fi; fi; end;
N := 40: G001190 := add(A001190(n)*x^n,n=0..N);
spec := [S,{S=Union(Z,Prod(Z,Set(S,card=2)))},unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);
# alternative Maple program:
a:= proc(n) option remember; `if`(n<2, n, `if`(n::odd, 0,
      (t-> t*(1-t)/2)(a(n/2)))+add(a(i)*a(n-i), i=1..n/2))
    end:
seq(a(n), n=0..40);  # Alois P. Heinz, Aug 28 2017
  • Mathematica
    terms = 35; A[] = 0; Do[A[x] = x + (1/2)*(A[x]^2 + A[x^2]) + O[x]^terms // Normal, terms]; CoefficientList[A[x], x] (* Jean-François Alcover, Jul 22 2011, updated Jan 10 2018 *)
a[n_?OddQ] := a[n] = Sum[a[k]*a[n-k], {k, 1, (n-1)/2}]; a[n_?EvenQ] := a[n] = Sum[a[k]*a[n-k], {k, 1, n/2-1}] + (1/2)*a[n/2]*(1+a[n/2]); a[0]=0; a[1]=1; Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Jun 13 2012, after recurrence formula *)
a[ n_] := If[ n < 0, 0, SeriesCoefficient[ Nest[ 1 - Sqrt[1 - 2 x - (# /. x -> x^2)] &, 0, BitLength @ n], {x, 0, n}]]; (* Michael Somos, Apr 25 2013 *)
  • PARI
    {a(n) = local(A, m); if( n<0, 0, m=1; A = O(x); while( m<=n, m*=2; A = 1 - sqrt(1 - 2*x - subst(A, x, x^2))); polcoeff(A, n))}; /* Michael Somos, Sep 06 2003 */
  • PARI
    {a(n) = local(A); if( n<4, n>0, A = vector(n, i, 1); for( i=4, n, A[i] = sum( j=1, (i-1)\2, A[j] * A[i-j]) + if( i%2, 0, A[i/2] * (A[i/2] + 1)/2)); A[n])}; /* Michael Somos, Mar 25 2006 */
  • Python
    from functools import lru_cache
@lru_cache(maxsize=None)
def A001190(n):
    if n <= 1: return n
    m = n//2 + n % 2
    return sum(A001190(i+1)*A001190(n-1-i) for i in range(m-1)) + (1 - n % 2)*A001190(m)*(A001190(m)+1)//2 # Chai Wah Wu, Jan 14 2022

Formula

G.f. satisfies A(x) = x + (1/2)*(A(x)^2 + A(x^2)) [de Bruijn and Klarner].
G.f. also satisfies A(x) = 1 - sqrt(1 - 2*x - A(x^2)). - Michael Somos, Sep 06 2003
a(2n-1) = a(1)a(2n-2) + a(2)a(2n-3) + ... + a(n-1)a(n), a(2n) = a(1)a(2n-1) + a(2)a(2n-2) + ... + a(n-1)a(n+1) + a(n)(a(n)+1)/2.
Given g.f. A(x), then B(x) = -1 + A(x) satisfies 0 = f(B(x), B(x^2), B(x^4)) where f(u, v, w) = (u^2 + v)^2 + 2*(v^2 + w). - Michael Somos, Oct 22 2006
The radius of convergence of the g.f. is A240943 = 1/A086317 ~ 0.4026975... - Jean-François Alcover, Jul 28 2014, after Steven R. Finch.
a(n) ~ A086318 * A086317^(n-1) / n^(3/2). - Vaclav Kotesovec, Apr 19 2016

A003422 Left factorials: !n = Sum_{k=0..n-1} k!.

Original entry on oeis.org

0, 1, 2, 4, 10, 34, 154, 874, 5914, 46234, 409114, 4037914, 43954714, 522956314, 6749977114, 93928268314, 1401602636314, 22324392524314, 378011820620314, 6780385526348314, 128425485935180314, 2561327494111820314, 53652269665821260314, 1177652997443428940314
Offset: 0

Views

Author

N. J. A. Sloane, R. K. Guy

Keywords

Comments

Number of {12, 12*, 1*2, 21*}- and {12, 12*, 21, 21*}-avoiding signed permutations in the hyperoctahedral group.
a(n) is the number of permutations on [n] that avoid the patterns 2n1 and n12. An occurrence of a 2n1 pattern is a (scattered) subsequence a-n-b with a > b. - David Callan, Nov 29 2007
Also, numbers left over after the following sieving process: At step 1, keep all numbers of the set N = {0, 1, 2, ...}. In step 2, keep only every second number after a(2) = 2: N' = {0, 1, 2, 4, 6, 8, 10, ...}. In step 3, keep every third of the numbers following a(3) = 4, N" = {0, 1, 2, 4, 10, 16, 22, ...}. In step 4, keep every fourth of the numbers beyond a(4) = 10: {0, 1, 2, 4, 10, 34, 58, ...}, and so on. - M. F. Hasler, Oct 28 2010
If s(n) is a second-order recurrence defined as s(0) = x, s(1) = y, s(n) = n*(s(n - 1) - s(n - 2)), n > 1, then s(n) = n*y - n*a(n - 1)*x. - Gary Detlefs, May 27 2012
a(n) is the number of lists of {1, ..., n} with (1st element) = (smallest element) and (k-th element) <> (k-th smallest element) for k > 1, where a list means an ordered subset. a(4) = 10 because we have the lists: [1], [2], [3], [4], [1, 3, 2], [1, 4, 2], [1, 4, 3], [2, 4, 3], [1, 3, 4, 2], [1, 4, 2, 3]. Cf. A000262. - Geoffrey Critzer, Oct 04 2012
Consider a tree graph with 1 vertex. Add an edge to it with another vertex. Now add 2 edges with vertices to this vertex, and then 3 edges to each open vertex of the tree (not the first one!), and the next stage is to add 4 edges, and so on. The total number of vertices at each stage give this sequence (see example). - Jon Perry, Jan 27 2013
Additive version of the superfactorials A000178. - Jon Perry, Feb 09 2013
Repunits in the factorial number system (see links). - Jon Perry, Feb 17 2013
Whether n|a(n) only for 1 and 2 remains an open problem. A published 2004 proof was retracted in 2011. This is sometimes known as Kurepa's conjecture. - Robert G. Wilson v, Jun 15 2013, corrected by Jeppe Stig Nielsen, Nov 07 2015.
!n is not always squarefree for n > 3. Miodrag Zivkovic found that 54503^2 divides !26541. - Arkadiusz Wesolowski, Nov 20 2013
a(n) gives the position of A007489(n) in A227157. - Antti Karttunen, Nov 29 2013
Matches the total domination number of the Bruhat graph from n = 2 to at least n = 5. - Eric W. Weisstein, Jan 11 2019
For the connection with Kurepa trees, see A. Petojevic, The {K_i(z)}{i=1..oo} functions, Rocky Mtn. J. Math., 36 (2006), 1637-1650. - _Aleksandar Petojevic, Jun 29 2018
This sequence converges in the p-adic topology, for every prime number p. - Harry Richman, Aug 13 2024

Examples

			!5 = 0! + 1! + 2! + 3! + 4! = 1 + 1 + 2 + 6 + 24 = 34.
x + 2*x^2 + 4*x^3 + 10*x^4 + 34*x^5 + 154*x^6 + 874*x^7 + 5914*x^8 + 46234*x^9 + ...
From _Arkadiusz Wesolowski_, Aug 06 2012: (Start)
Illustration of initial terms:
.
. o        o         o            o                         o
.          o         o            o                         o
.                   o o          o o                       o o
.                              ooo ooo                   ooo ooo
.                                             oooo oooo oooo oooo oooo oooo
.
. 1        2         4            10                        34
.
(End)
The tree graph. The total number of vertices at each stage is 1, 2, 4, 10, ...
    0 0
    |/
    0-0
   /
0-0
   \
    0-0
    |\
    0 0
- _Jon Perry_, Jan 27 2013

References

  • Richard K. Guy, Unsolved Problems Number Theory, Section B44.
  • D. Kurepa, On the left factorial function !n. Math. Balkanica 1 1971 147-153.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Equals A007489(n-1)+1 for n>=1. Cf. A000142, A014144, A005165.
Twice A014288. See also A049782, A100612.
Cf. A102639, A102411, A102412, A101752, A094216, A094638, A008276, A000166, A000110, A000204, A000045, A000108, A135722, A227157, A000178, A137338, A232845, A357145.

Programs

  • Haskell
    a003422 n = a003422_list !! n
a003422_list = scanl (+) 0 a000142_list
-- Reinhard Zumkeller, Dec 27 2011
  • Maple
    A003422 := proc(n) local k; add(k!,k=0..n-1); end proc:
# Alternative, using the Charlier polynomials A137338:
C := proc(n, x) option remember; if n > 0 then (x-n)*C(n-1, x) - n*C(n-2, x)
elif n = 0 then 1 else 0 fi end: A003422 := n -> (-1)^(n+1)*C(n-1, -1):
seq(A003422(n), n=0..22); # Peter Luschny, Nov 28 2018
# third Maple program:
a:= proc(n) option remember; `if`(n=0, 0, a(n-1)+(n-1)!) end:
seq(a(n), n=0..23);  # Alois P. Heinz, Feb 24 2022
  • Mathematica
    Table[Sum[i!, {i, 0, n - 1}], {n, 0, 20}] (* Stefan Steinerberger, Mar 31 2006 *)
Join[{0}, Accumulate[Range[0, 25]!]] (* Harvey P. Dale, Nov 19 2011 *)
a[0] = 0; a[1] = 1; a[n_] := a[n] = n*a[n - 1] - (n - 1)*a[n - 2]; Array[a, 23, 0] (* Robert G. Wilson v, Jun 15 2013 *)
a[n_] := (-1)^n*n!*Subfactorial[-n-1]-Subfactorial[-1]; Table[a[n] // FullSimplify, {n, 0, 22}] (* Jean-François Alcover, Jan 09 2014 *)
RecurrenceTable[{a[n] == n a[n - 1] - (n - 1) a[n - 2], a[0] == 0, a[1] == 1}, a, {n, 0, 10}] (* Eric W. Weisstein, Jan 11 2019 *)
Range[0, 20]! CoefficientList[Series[(ExpIntegralEi[1] - ExpIntegralEi[1 - x]) Exp[x - 1], {x, 0, 20}], x] (* Eric W. Weisstein, Jan 11 2019 *)
Table[(-1)^n n! Subfactorial[-n - 1] - Subfactorial[-1], {n, 0, 20}] // FullSimplify (* Eric W. Weisstein, Jan 11 2019 *)
Table[(I Pi + ExpIntegralEi[1] + (-1)^n n! Gamma[-n, -1])/E, {n, 0, 20}] // FullSimplify (* Eric W. Weisstein, Jan 11 2019 *)
  • Maxima
    makelist(sum(k!,k,0,n-1), n, 0, 20); /* Stefano Spezia, Jan 11 2019 */
  • PARI
    a003422(n)=sum(k=0,n-1,k!) \\ Charles R Greathouse IV, Jun 15 2011
  • Python
    from itertools import count, islice
def A003422_gen(): # generator of terms
    yield from (0,1)
    c, f = 1, 1
    for n in count(1):
        yield (c:= c + (f:= f*n))
A003422_list = list(islice(A003422_gen(),20)) # Chai Wah Wu, Jun 22 2022
  • Python
    def a(n):
    if n == 0: return 0
    s = f = 1
    for k in range(1, n):
        f *= k
        s += f
    return round(s)
print([a(n) for n in range(24)])  # Peter Luschny, Mar 05 2024

Formula

D-finite with recurrence: a(n) = n*a(n - 1) - (n - 1)*a(n - 2). - Henry Bottomley, Feb 28 2001
Sequence is given by 1 + 1*(1 + 2*(1 + 3*(1 + 4*(1 + ..., terminating in n*(1)...). - Jon Perry, Jun 01 2004
a(n) = Sum_{k=0..n-1} P(n, k) / C(n, k). - Ross La Haye, Sep 20 2004
E.g.f.: (Ei(1) - Ei(1 - x))*exp(-1 + x) where Ei(x) is the exponential integral. - Djurdje Cvijovic and Aleksandar Petojevic, Apr 11 2000
a(n) = Integral_{x = 0..oo} [(x^n - 1)/(x - 1)]*exp(-x) dx. - Gerald McGarvey, Oct 12 2007
A007489(n) = !(n + 1) - 1 = a(n + 1) - 1. - Artur Jasinski, Nov 08 2007. Typos corrected by Antti Karttunen, Nov 29 2013
Starting (1, 2, 4, 10, 34, 154, ...), = row sums of triangle A135722. - Gary W. Adamson, Nov 25 2007
a(n) = a(n - 1) + (n - 1)! for n >= 2. - Jaroslav Krizek, Jun 16 2009
E.g.f. A(x) satisfies the differential equation A'(x) = A(x) + 1/(1 - x). - Vladimir Kruchinin, Jan 19 2011
a(n + 1) = p(-1) where p(x) is the unique degree-n polynomial such that p(k) = A182386(k) for k = 0, 1, ..., n. - Michael Somos, Apr 27 2012
From Sergei N. Gladkovskii, May 09 2013 to Oct 22 2013: (Start)
Continued fractions:
G.f.: x/(1-x)*Q(0) where Q(k) = 1 + (2*k + 1)*x/( 1 - 2*x*(k+1)/(2*x*(k+1) + 1/Q(k+1))).
G.f.: G(0)*x/(1-x)/2 where G(k) = 1 + 1/(1 - x*(k+1)/(x*(k+1) + 1/G(k+1))).
G.f.: 2*x/(1-x)/G(0) where G(k) = 1 + 1/(1 - 1/(1 - 1/(2*x*(k+1)) + 1/G(k+1))).
G.f.: W(0)*x/(1+sqrt(x))/(1-x) where W(k) = 1 + sqrt(x)/(1 - sqrt(x)*(k+1)/(sqrt(x)*(k+1) + 1/W(k+1))).
G.f.: B(x)*(1+x)/(1-x) where B(x) is the g.f. of A153229.
G.f.: x/(1-x) + x^2/(1-x)/Q(0) where Q(k) = 1 - 2*x*(2*k+1) - x^2*(2*k+1)*(2*k+2)/(1 - 2*x*(2*k+2) - x^2*(2*k+2)*(2*k+3)/Q(k+1)).
G.f.: x*(1+x)*B(x) where B(x) is the g.f. of A136580. (End)
a(n) = (-1)^(n+1)*C(n-1, -1) where C(n, x) are the Charlier polynomials (with parameter a=1) as given in A137338. (Evaluation at x = 1 gives A232845.) - Peter Luschny, Nov 28 2018
a(n) = (a(n-3)*(n-2)^2*(n-3)! + a(n-1)^2)/a(n-2) (empirical). - Gary Detlefs, Feb 25 2022
a(n) = signum(n)/b(1,n) with b(i,n) = i - [iMohammed Bouras, Sep 07 2022
Sum_{n>=1} 1/a(n) = A357145. - Amiram Eldar, Oct 01 2022

A008279 Triangle T(n,k) = n!/(n-k)! (0 <= k <= n) read by rows, giving number of permutations of n things k at a time.

Original entry on oeis.org

1, 1, 1, 1, 2, 2, 1, 3, 6, 6, 1, 4, 12, 24, 24, 1, 5, 20, 60, 120, 120, 1, 6, 30, 120, 360, 720, 720, 1, 7, 42, 210, 840, 2520, 5040, 5040, 1, 8, 56, 336, 1680, 6720, 20160, 40320, 40320, 1, 9, 72, 504, 3024, 15120, 60480, 181440, 362880, 362880
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Also called permutation coefficients.
Also falling factorials triangle A068424 with column a(n,0)=1 and row a(0,1)=1 otherwise a(0,k)=0, added. - Wolfdieter Lang, Nov 07 2003
The higher-order exponential integrals E(x,m,n) are defined in A163931; for information about the asymptotic expansion of E(x,m=1,n) see A130534. The asymptotic expansions for n = 1, 2, 3, 4, ..., lead to the right hand columns of the triangle given above. - Johannes W. Meijer, Oct 16 2009
The number of injective functions from a set of size k to a set of size n. - Dennis P. Walsh, Feb 10 2011
The number of functions f from {1,2,...,k} to {1,2,...,n} that satisfy f(x) >= x for all x in {1,2,...,k}. - Dennis P. Walsh, Apr 20 2011
T(n,k) = A181511(n,k) for k=1..n-1. - Reinhard Zumkeller, Nov 18 2012
The e.g.f.s enumerating the faces of the permutohedra / permutahedra, Perm(s,t;x) = [e^(sx)-1]/[s-t(e^(sx)-1)], (cf. A090582 and A019538) and the stellahedra / stellohedra, St(s,t;x) = [s e^((s+t)x)]/[s-t(e^(sx)-1)], (cf. A248727) given in Toric Topology satisfy exp[u*d/dt] St(s,t;x) = St(s,u+t;x) = [e^(ux)/(1-u*Perm(s,t;x))]*St(s,t;x), where e^(ux)/(1-uy) is a bivariate e.g.f. for the row polynomials of this entry and A094587. Equivalently, d/dt St = (x+Perm)*St and d/dt Perm = Perm^2, or d/dt log(St) = x + Perm and d/dt log(Perm) = Perm. - Tom Copeland, Nov 14 2016
T(n, k)/n! are the coefficients of the n-th exponential Taylor polynomial, or truncated exponentials, which was proved to be irreducible by Schur. See Coleman link. - Michel Marcus, Feb 24 2020
Given a generic choice of k+2 residues, T(n, k) is the number of meromorphic differentials on the Riemann sphere having a zero of order n and these prescribed residues at its k+2 poles. - Quentin Gendron, Jan 16 2025

Examples

			Triangle begins:
  1;
  1,  1;
  1,  2,  2;
  1,  3,  6,   6;
  1,  4, 12,  24,   24;
  1,  5, 20,  60,  120,   120;
  1,  6, 30, 120,  360,   720,    720;
  1,  7, 42, 210,  840,  2520,   5040,   5040;
  1,  8, 56, 336, 1680,  6720,  20160,  40320,   40320;
  1,  9, 72, 504, 3024, 15120,  60480, 181440,  362880,  362880;
  1, 10, 90, 720, 5040, 30240, 151200, 604800, 1814400, 3628800, 3628800;
  ...
For example, T(4,2)=12 since there are 12 injective functions f:{1,2}->{1,2,3,4}. There are 4 choices for f(1) and then, since f is injective, 3 remaining choices for f(2), giving us 12 ways to construct an injective function. - _Dennis P. Walsh_, Feb 10 2011
For example, T(5,3)=60 since there are 60 functions f:{1,2,3}->{1,2,3,4,5} with f(x) >= x. There are 5 choices for f(1), 4 choices for f(2), and 3 choices for f(3), giving us 60 ways to construct such a function. - _Dennis P. Walsh_, Apr 30 2011

References

  • CRC Standard Mathematical Tables and Formulae, 30th ed., 1996, p. 176; 31st ed., p. 215, Section 3.3.11.1.
  • Maple V Reference Manual, p. 490, numbperm(n,k).

Links

Crossrefs

Row sums give A000522.
Cf. A001497, A001498, A136572.
T(n,0)=A000012, T(n,1)=A000027, T(n+1,2)=A002378, T(n,3)=A007531, T(n,4)=A052762, and T(n,n)=A000142.
Cf. A019538, A090582, A094587, A248727.

Programs

  • Haskell
    a008279 n k = a008279_tabl !! n !! k
a008279_row n = a008279_tabl !! n
a008279_tabl = iterate f [1] where
   f xs = zipWith (+) ([0] ++ zipWith (*) xs [1..]) (xs ++ [0])
-- Reinhard Zumkeller, Dec 15 2013, Nov 18 2012
  • Magma
    /* As triangle */ [[Factorial(n)/Factorial(n-k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Oct 11 2015
  • Maple
    with(combstruct): for n from 0 to 10 do seq(count(Permutation(n),size=m), m = 0 .. n) od; # Zerinvary Lajos, Dec 16 2007
seq(seq(n!/(n-k)!,k=0..n),n=0..10); # Dennis P. Walsh, Apr 20 2011
seq(print(seq(pochhammer(n-k+1,k),k=0..n)),n=0..6); # Peter Luschny, Mar 26 2015
  • Mathematica
    Table[CoefficientList[Series[(1 + x)^m, {x, 0, 20}], x]* Table[n!, {n, 0, m}], {m, 0, 10}] // Grid (* Geoffrey Critzer, Mar 16 2010 *)
Table[ Pochhammer[n - k + 1, k], {n, 0, 9}, {k, 0, n}] // Flatten (* or *)
Table[ FactorialPower[n, k], {n, 0, 9}, {k, 0, n}] // Flatten  (* Jean-François Alcover, Jul 18 2013, updated Jan 28 2016 *)
  • PARI
    {T(n, k) = if( k<0 || k>n, 0, n!/(n-k)!)}; /* Michael Somos, Nov 14 2002 */
  • PARI
    {T(n, k) = my(A, p); if( k<0 || k>n, 0, if( n==0, 1, A = matrix(n, n, i, j, x + (i==j)); polcoeff( sum(i=1, n!, if( p = numtoperm(n, i), prod(j=1, n, A[j, p[j]]))), k)))}; /* Michael Somos, Mar 05 2004 */
  • Python
    from math import factorial, isqrt, comb
def A008279(n): return factorial(a:=(m:=isqrt(k:=n+1<<1))-(k<=m*(m+1)))//factorial(a-n+comb(a+1,2)) # Chai Wah Wu, Nov 13 2024
  • Sage
    for n in range(8): [falling_factorial(n,k) for k in (0..n)] # Peter Luschny, Mar 26 2015

Formula

E.g.f.: Sum T(n,k) x^n/n! y^k = exp(x)/(1-x*y). - Vladeta Jovovic, Aug 19 2002
Equals A007318 * A136572. - Gary W. Adamson, Jan 07 2008
T(n, k) = n*T(n-1, k-1) = k*T(n-1, k-1)+T(n-1, k) = n*T(n-1, k)/(n-k) = (n-k+1)*T(n, k-1). - Henry Bottomley, Mar 29 2001
T(n, k) = n!/(n-k)! if n >= k >= 0, otherwise 0.
G.f. for k-th column k!*x^k/(1-x)^(k+1), k >= 0.
E.g.f. for n-th row (1+x)^n, n >= 0.
Sum T(n, k)x^k = permanent of n X n matrix a_ij = (x+1 if i=j, x otherwise). - Michael Somos, Mar 05 2004
Ramanujan psi_1(k, x) polynomials evaluated at n+1. - Ralf Stephan, Apr 16 2004
E.g.f.: Sum T(n,k) x^n/n! y^k/k! = e^{x+xy}. - Franklin T. Adams-Watters, Feb 07 2006
The triangle is the binomial transform of an infinite matrix with (1, 1, 2, 6, 24, ...) in the main diagonal and the rest zeros. - Gary W. Adamson, Nov 20 2006
G.f.: 1/(1-x-xy/(1-xy/(1-x-2xy/(1-2xy/(1-x-3xy/(1-3xy/(1-x-4xy/(1-4xy/(1-... (continued fraction). - Paul Barry, Feb 11 2009
T(n,k) = Sum_{j=0..k} binomial(k,j)*T(x,j)*T(y,k-j) for x+y = n. - Dennis P. Walsh, Feb 10 2011
From Dennis P. Walsh, Apr 20 2011: (Start)
E.g.f (with k fixed): x^k*exp(x).
G.f. (with k fixed): k!*x^k/(1-x)^(k+1). (End)
For n >= 2 and m >= 2, Sum_{k=0..m-2} S2(n, k+2)*T(m-2, k) = Sum_{p=0..n-2} m^p. S2(n,k) are the Stirling numbers of the second kind A008277. - Tony Foster III, Jul 23 2019

A008297 Triangle of Lah numbers.

Original entry on oeis.org

-1, 2, 1, -6, -6, -1, 24, 36, 12, 1, -120, -240, -120, -20, -1, 720, 1800, 1200, 300, 30, 1, -5040, -15120, -12600, -4200, -630, -42, -1, 40320, 141120, 141120, 58800, 11760, 1176, 56, 1, -362880, -1451520, -1693440, -846720, -211680, -28224, -2016, -72, -1, 3628800, 16329600, 21772800, 12700800
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

|a(n,k)| = number of partitions of {1..n} into k lists, where a list means an ordered subset.
Let N be a Poisson random variable with parameter (mean) lambda, and Y_1,Y_2,... independent exponential(theta) variables, independent of N, so that their density is given by (1/theta)*exp(-x/theta), x > 0. Set S=Sum_{i=1..N} Y_i. Then E(S^n), i.e., the n-th moment of S, is given by (theta^n) * L_n(lambda), n >= 0, where L_n(y) is the Lah polynomial Sum_{k=0..n} |a(n,k)| * y^k. - Shai Covo (green355(AT)netvision.net.il), Feb 09 2010
For y = lambda > 0, formula 2) for the Lah polynomial L_n(y) dated Feb 02 2010 can be restated as follows: L_n(lambda) is the n-th ascending factorial moment of the Poisson distribution with parameter (mean) lambda. - Shai Covo (green355(AT)netvision.net.il), Feb 10 2010
See A111596 for an expression of the row polynomials in terms of an umbral composition of the Bell polynomials and relation to an inverse Mellin transform and a generalized Dobinski formula. - Tom Copeland, Nov 21 2011
Also the Bell transform of the sequence (-1)^(n+1)*(n+1)! without column 0. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 28 2016
Named after the Slovenian mathematician and actuary Ivo Lah (1896-1979). - Amiram Eldar, Jun 13 2021

Examples

			|a(2,1)| = 2: (12), (21); |a(2,2)| = 1: (1)(2). |a(4,1)| = 24: (1234) (24 ways); |a(4,2)| = 36: (123)(4) (6*4 ways), (12)(34) (3*4 ways); |a(4,3)| = 12: (12)(3)(4) (6*2 ways); |a(4,4)| = 1: (1)(2)(3)(4) (1 way).
Triangle:
    -1;
     2,    1;
    -6,   -6,   -1;
    24,   36,   12,   1;
  -120, -240, -120, -20, -1; ...

References

  • Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 156.
  • Shai Covo, The moments of a compound Poisson process with exponential or centered normal jumps, J. Probab. Stat. Sci., Vol. 7, No. 1 (2009), pp. 91-100.
  • Theodore S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176; the sequence called {!}^{n+}. For a link to this paper see A000262.
  • John Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 44.
  • S. Gill Williamson, Combinatorics for Computer Science, Computer Science Press, 1985; see p. 176.

Links

Crossrefs

Same as A066667 and A105278 except for signs. Other variants: A111596 (differently signed triangle and (0,0)-based), A271703 (unsigned and (0,0)-based), A089231.
A293125 (row sums) and A000262 (row sums of unsigned triangle).
Columns 1-6 (unsigned): A000142, A001286, A001754, A001755, A001777, A001778.
A002868 gives maximal element (in magnitude) in each row.
A248045 (central terms, negated). A130561 is a natural refinement.
Cf. A007318, A048786, A001263, A008275, A008277, A048993, A094638, A130534.
Cf. A008296, A360177.

Programs

  • Haskell
    a008297 n k = a008297_tabl !! (n-1) !! (k-1)
a008297_row n = a008297_tabl !! (n-1)
a008297_tabl = [-1] : f [-1] 2 where
   f xs i = ys : f ys (i + 1) where
     ys = map negate $
          zipWith (+) ([0] ++ xs) (zipWith (*) [i, i + 1 ..] (xs ++ [0]))
-- Reinhard Zumkeller, Sep 30 2014
  • Maple
    A008297 := (n,m) -> (-1)^n*n!*binomial(n-1,m-1)/m!;
  • Mathematica
    a[n_, m_] := (-1)^n*n!*Binomial[n-1, m-1]/m!; Table[a[n, m], {n, 1, 10}, {m, 1, n}] // Flatten (* Jean-François Alcover, Dec 12 2012, after Maple *)
T[n_, n_] := (-1)^n; T[n_, k_]/;0Oliver Seipel, Dec 06 2024 *)
  • PARI
    T(n, m) = (-1)^n*n!*binomial(n-1, m-1)/m!
for(n=1,9, for(m=1,n, print1(T(n,m)", "))) \\ Charles R Greathouse IV, Mar 09 2016
  • Perl
    use bigint; use ntheory ":all"; my @L; for my $n (1..9) { push @L, map { stirling($n,$,3)*(-1)**$n } 1..$n; } say join(", ",@L); # _Dana Jacobsen, Mar 16 2017
  • Sage
    def A008297_triangle(dim): # computes unsigned T(n, k).
    M = matrix(ZZ,dim,dim)
    for n in (0..dim-1): M[n,n] = 1
    for n in (1..dim-1):
        for k in (0..n-1):
            M[n,k] = M[n-1,k-1]+(2+2*k)*M[n-1,k]+((k+1)*(k+2))*M[n-1,k+1]
    return M
A008297_triangle(9) # Peter Luschny, Sep 19 2012

Formula

a(n, m) = (-1)^n*n!*A007318(n-1, m-1)/m!, n >= m >= 1.
a(n+1, m) = (n+m)*a(n, m)+a(n, m-1), a(n, 0) := 0; a(n, m) := 0, n < m; a(1, 1)=1.
a(n, m) = ((-1)^(n-m+1))*L(1, n-1, m-1) where L(1, n, m) is the triangle of coefficients of the generalized Laguerre polynomials n!*L(n, a=1, x). These polynomials appear in the radial l=0 eigen-functions for discrete energy levels of the H-atom.
|a(n, m)| = Sum_{k=m..n} |A008275(n, k)|*A008277(k, m), where A008275 = Stirling numbers of first kind, A008277 = Stirling numbers of second kind. - Wolfdieter Lang
If L_n(y) = Sum_{k=0..n} |a(n, k)|*y^k (a Lah polynomial) then the e.g.f. for L_n(y) is exp(x*y/(1-x)). - Vladeta Jovovic, Jan 06 2001
E.g.f. for the k-th column (unsigned): x^k/(1-x)^k/k!. - Vladeta Jovovic, Dec 03 2002
a(n, k) = (n-k+1)!*N(n, k) where N(n, k) is the Narayana triangle A001263. - Philippe Deléham, Jul 20 2003
From Shai Covo (green355(AT)netvision.net.il), Feb 02 2010: (Start)
We have the following expressions for the Lah polynomial L_n(y) = Sum_{k=0..n} |a(n, k)|*y^k -- exact generalizations of results in A000262 for A000262(n) = L_n(1):
1) L_n(y) = y*exp(-y)*n!*M(n+1,2,y), n >= 1, where M (=1F1) is the confluent hypergeometric function of the first kind;
2) L_n(y) = exp(-y)* Sum_{m>=0} y^m*[m]^n/m!, n>=0, where [m]^n = m*(m+1)*...*(m+n-1) is the rising factorial;
3) L_n(y) = (2n-2+y)L_{n-1}(y)-(n-1)(n-2)L_{n-2}(y), n>=2;
4) L_n(y) = y*(n-1)!*Sum_{k=1..n} (L_{n-k}(y) k!)/((n-k)! (k-1)!), n>=1. (End)
The row polynomials are given by D^n(exp(-x*t)) evaluated at x = 0, where D is the operator (1-x)^2*d/dx. Cf. A008277 and A035342. - Peter Bala, Nov 25 2011
n!C(-xD,n) = Lah(n,:xD:) where C(m,n) is the binomial coefficient, xD= x d/dx, (:xD:)^k = x^k D^k, and Lah(n,x) are the row polynomials of this entry. E.g., 2!C(-xD,2)= 2 xD + x^2 D^2. - Tom Copeland, Nov 03 2012
From Tom Copeland, Sep 25 2016: (Start)
The Stirling polynomials of the second kind A048993 (A008277), i.e., the Bell-Touchard-exponential polynomials B_n[x], are umbral compositional inverses of the Stirling polynomials of the first kind signed A008275 (A130534), i.e., the falling factorials, (x)_n = n! binomial(x,n); that is, umbrally B_n[(x).] = x^n = (B.[x])_n.
An operational definition of the Bell polynomials is (xD_x)^n = B_n[:xD:], where, by definition, (:xD_x:)^n = x^n D_x^n, so (B.[:xD_x:])_n = (xD_x)_n = :xD_x:^n = x^n (D_x)^n.
Let y = 1/x, then D_x = -y^2 D_y; xD_x = -yD_y; and P_n(:yD_y:) = (-yD_y)_n = (-1)^n (1/y)^n (y^2 D_y)^n, the row polynomials of this entry in operational form, e.g., P_3(:yD_y:) = (-yD_y)_3 = (-yD_y) (yD_y-1) (yD_y-2) = (-1)^3 (1/y)^3 (y^2 D_y)^3 = -( 6 :yD_y: + 6 :yD_y:^2 + :yD_y:^3 ) = - ( 6 y D_y + 6 y^2 (D_y)^2 + y^3 (D_y)^3).
Therefore, P_n(y) = e^(-y) P_n(:yD_y:) e^y = e^(-y) (-1/y)^n (y^2 D_y)^n e^y = e^(-1/x) x^n (D_x)^n e^(1/x) = P_n(1/x) and P_n(x) = e^(-1/x) x^n (D_x)^n e^(1/x) = e^(-1/x) (:x D_x:)^n e^(1/x). (Cf. also A094638.) (End)
T(n,k) = Sum_{j=k..n} (-1)^j*A008296(n,j)*A360177(j,k). - Mélika Tebni, Feb 02 2023

A000311 Schroeder's fourth problem; also series-reduced rooted trees with n labeled leaves; also number of total partitions of n.

Original entry on oeis.org

0, 1, 1, 4, 26, 236, 2752, 39208, 660032, 12818912, 282137824, 6939897856, 188666182784, 5617349020544, 181790703209728, 6353726042486272, 238513970965257728, 9571020586419012608, 408837905660444010496, 18522305410364986906624
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is the number of labeled series-reduced rooted trees with n leaves (root has degree 0 or >= 2); a(n-1) = number of labeled series-reduced trees with n leaves. Also number of series-parallel networks with n labeled edges, divided by 2.
A total partition of n is essentially what is meant by the first part of the previous line: take the numbers 12...n, and partition them into at least two blocks. Partition each block with at least 2 elements into at least two blocks. Repeat until only blocks of size 1 remain. (See the reference to Stanley, Vol. 2.) - N. J. A. Sloane, Aug 03 2016
Polynomials with coefficients in triangle A008517, evaluated at 2. - Ralf Stephan, Dec 13 2004
Row sums of unsigned A134685. - Tom Copeland, Oct 11 2008
Row sums of A134991, which contains an e.g.f. for this sequence and its compositional inverse. - Tom Copeland, Jan 24 2018
From Gus Wiseman, Dec 28 2019: (Start)
Also the number of singleton-reduced phylogenetic trees with n labels. A phylogenetic tree is a series-reduced rooted tree whose leaves are (usually disjoint) nonempty sets. It is singleton-reduced if no non-leaf node covers only singleton branches. For example, the a(4) = 26 trees are:
{1,2,3,4} {{1},{2},{3,4}} {{1},{2,3,4}}
{{1},{2,3},{4}} {{1,2},{3,4}}
{{1,2},{3},{4}} {{1,2,3},{4}}
{{1},{2,4},{3}} {{1,2,4},{3}}
{{1,3},{2},{4}} {{1,3},{2,4}}
{{1,4},{2},{3}} {{1,3,4},{2}}
{{1,4},{2,3}}
{{{1},{2,3}},{4}}
{{{1,2},{3}},{4}}
{{1},{{2},{3,4}}}
{{1},{{2,3},{4}}}
{{{1},{2,4}},{3}}
{{{1,2},{4}},{3}}
{{1},{{2,4},{3}}}
{{{1,3},{2}},{4}}
{{{1},{3,4}},{2}}
{{{1,3},{4}},{2}}
{{{1,4},{2}},{3}}
{{{1,4},{3}},{2}}
(End)

Examples

			E.g.f.: A(x) = x + x^2/2! + 4*x^3/3! + 26*x^4/4! + 236*x^5/5! + 2752*x^6/6! + ...
where exp(A(x)) = 1 - x + 2*A(x), and thus
Series_Reversion(A(x)) = x - x^2/2! - x^3/3! - x^4/4! - x^5/5! - x^6/6! + ...
O.g.f.: G(x) = x + x^2 + 4*x^3 + 26*x^4 + 236*x^5 + 2752*x^6 + 39208*x^7 + ...
where
G(x) = x/2 + x/(2*(2-x)) + x/(2*(2-x)*(2-2*x)) + x/(2*(2-x)*(2-2*x)*(2-3*x)) + x/(2*(2-x)*(2-2*x)*(2-3*x)*(2-4*x)) + x/(2*(2-x)*(2-2*x)*(2-3*x)*(2-4*x)*(2-5*x)) + ...
From _Gus Wiseman_, Dec 28 2019: (Start)
A rooted tree is series-reduced if it has no unary branchings, so every non-leaf node covers at least two other nodes. The a(4) = 26 series-reduced rooted trees with 4 labeled leaves are the following. Each bracket (...) corresponds to a non-leaf node.
  (1234)  ((12)34)  ((123)4)
          (1(23)4)  (1(234))
          (12(34))  ((124)3)
          (1(24)3)  ((134)2)
          ((13)24)  (((12)3)4)
          ((14)23)  ((1(23))4)
                    ((12)(34))
                    (1((23)4))
                    (1(2(34)))
                    (((12)4)3)
                    ((1(24))3)
                    (1((24)3))
                    (((13)2)4)
                    ((13)(24))
                    (((13)4)2)
                    ((1(34))2)
                    (((14)2)3)
                    ((14)(23))
                    (((14)3)2)
(End)

References

  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 224.
  • J. Felsenstein, Inferring phyogenies, Sinauer Associates, 2004; see p. 25ff.
  • L. R. Foulds and R. W. Robinson, Enumeration of phylogenetic trees without points of degree two. Ars Combin. 17 (1984), A, 169-183. Math. Rev. 85f:05045
  • T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176.
  • J. Riordan, Combinatorial Identities, Wiley, 1968, p. 197.
  • E. Schroeder, Vier combinatorische Probleme, Z. f. Math. Phys., 15 (1870), 361-376.
  • 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).
  • R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see "total partitions", Example 5.2.5, Equation (5.27), and also Fig. 5-3 on page 14. See also the Notes on page 66.

Links

Crossrefs

Row sums of A064060 and A134991.
The unlabeled version is A000669.
Unlabeled phylogenetic trees are A141268.
The node-counting version is A060356, with unlabeled version A001678.
Phylogenetic trees with n labels are A005804.
Chains of set partitions are A005121, with maximal version A002846.
Inequivalent leaf-colorings of series-reduced rooted trees are A318231.
Cf. A001003, A007827, A005805, A006351, A000084.
For n >= 2, A000311(n) = A006351(n)/2 = A005640(n)/2^(n+1).
Cf. A000110, A000669 = unlabeled hierarchies, A119649.
Cf. A000670, A135494, A134685.
Cf. A048816, A196545, A213427, A316651, A316652, A330626, A330627.
Cf. A000169, A042977, A133314, A134685, A269939.

Programs

  • Maple
    M:=499; a:=array(0..500); a[0]:=0; a[1]:=1; a[2]:=1; for n from 0 to 2 do lprint(n,a[n]); od: for n from 2 to M do a[n+1]:=(n+2)*a[n]+2*add(binomial(n,k)*a[k]*a[n-k+1],k=2..n-1); lprint(n+1,a[n+1]); od:
Order := 50; t1 := solve(series((exp(A)-2*A-1),A)=-x,A); A000311 := n-> n!*coeff(t1,x,n);
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
      add(combinat[multinomial](n, n-i*j, i$j)/j!*
      a(i)^j*b(n-i*j, i-1), j=0..n/i)))
    end:
a:= n-> `if`(n<2, n, b(n, n-1)):
seq(a(n), n=0..40);  # Alois P. Heinz, Jan 28 2016
# faster program:
b:= proc(n, i) option remember;
    `if`(i=0 and n=0, 1, `if`(i<=0 or i>n, 0,
    i*b(n-1, i) + (n+i-1)*b(n-1, i-1))) end:
a:= n -> `if`(n<2, n, add(b(n-1, i), i=0..n-1)):
seq(a(n), n=0..40);  # Peter Luschny, Feb 15 2021
  • Mathematica
    nn = 19; CoefficientList[ InverseSeries[ Series[1+2a-E^a, {a, 0, nn}], x], x]*Range[0, nn]! (* Jean-François Alcover, Jul 21 2011 *)
a[ n_] := If[ n < 1, 0, n! SeriesCoefficient[ InverseSeries[ Series[ 1 + 2 x - Exp[x], {x, 0, n}]], n]]; (* Michael Somos, Jun 04 2012 *)
a[n_] := (If[n < 2,n,(column = ConstantArray[0, n - 1]; column[[1]] = 1; For[j = 3, j <= n, j++, column = column * Flatten[{Range[j - 2], ConstantArray[0, (n - j) + 1]}] + Drop[Prepend[column, 0], -1] * Flatten[{Range[j - 1, 2*j - 3], ConstantArray[0, n - j]}];]; Sum[column[[i]], {i, n - 1}]  )]); Table[a[n], {n, 0, 20}] (* Peter Regner, Oct 05 2012, after a formula by Felsenstein (1978) *)
multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] := b[n, i] = If[n == 0, 1, If[i<1, 0, Sum[multinomial[n, Join[{n-i*j}, Array[i&,j]]]/j!*a[i]^j *b[n-i*j, i-1], {j, 0, n/i}]]]; a[n_] := If[n<2, n, b[n, n-1]]; Table[ a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 07 2016, after Alois P. Heinz *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mtot[m_]:=Prepend[Join@@Table[Tuples[mtot/@p],{p,Select[sps[m],1Gus Wiseman, Dec 28 2019 *)
(* Lengthy but easy to follow *)
  lead[, n /; n < 3] := 0
  lead[h_, n_] := Module[{p, i},
        p = Position[h, {_}];
        Sum[MapAt[{#, n} &, h, p[[i]]], {i, Length[p]}]
        ]
  follow[h_, n_] := Module[{r, i},
        r = Replace[Position[h, {_}], {a__} -> {a, -1}, 1];
        Sum[Insert[h, n, r[[i]]], {i, Length[r]}]
        ]
  marry[, n /; n < 3] := 0
  marry[h_, n_] := Module[{p, i},
        p = Position[h, _Integer];
        Sum[MapAt[{#, n} &, h, p[[i]]], {i, Length[p]}]
        ]
  extend[a_ + b_, n_] := extend[a, n] + extend[b, n]
  extend[a_, n_] := lead[a, n] + follow[a, n] + marry[a, n]
  hierarchies[1] := hierarchies[1] = extend[hier[{}], 1]
  hierarchies[n_] := hierarchies[n] = extend[hierarchies[n - 1], n] (* Daniel Geisler, Aug 22 2022 *)
  • Maxima
    a(n):=if n=1 then 1 else sum((n+k-1)!*sum(1/(k-j)!*sum((2^i*(-1)^(i)*stirling2(n+j-i-1,j-i))/((n+j-i-1)!*i!),i,0,j),j,1,k),k,1,n-1); /* Vladimir Kruchinin, Jan 28 2012 */
  • PARI
    {a(n) = local(A); if( n<0, 0, for( i=1, n, A = Pol(exp(A + x * O(x^i)) - A + x - 1)); n! * polcoeff(A, n))}; /* Michael Somos, Jan 15 2004 */
  • PARI
    {a(n) = my(A); if( n<0, 0, A = O(x); for( i=1, n, A = intformal( 1 / (1 + x - 2*A))); n! * polcoeff(A, n))}; /* Michael Somos, Oct 25 2014 */
  • PARI
    {a(n) = n! * polcoeff(serreverse(1+2*x - exp(x +x^2*O(x^n))), n)}
for(n=0, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Oct 27 2014
  • PARI
    \p100 \\ set precision
{A=Vec(sum(n=0, 600, 1.*x/prod(k=0, n, 2 - k*x + O(x^31))))}
for(n=0, 25, print1(if(n<1,0,round(A[n])),", ")) \\ Paul D. Hanna, Oct 27 2014
  • Python
    from functools import lru_cache
from math import comb
@lru_cache(maxsize=None)
def A000311(n): return n if n <= 1 else -(n-1)*A000311(n-1)+comb(n,m:=n+1>>1)*(0 if n&1 else A000311(m)**2) + (sum(comb(n,i)*A000311(i)*A000311(n-i) for i in range(1,m))<<1) # Chai Wah Wu, Nov 10 2022

Formula

E.g.f. A(x) satisfies exp A(x) = 2*A(x) - x + 1.
a(0)=0, a(1)=a(2)=1; for n >= 2, a(n+1) = (n+2)*a(n) + 2*Sum_{k=2..n-1} binomial(n, k)*a(k)*a(n-k+1).
a(1)=1; for n>1, a(n) = -(n-1) * a(n-1) + Sum_{k=1..n-1} binomial(n, k) * a(k) * a(n-k). - Michael Somos, Jun 04 2012
From the umbral operator L in A135494 acting on x^n comes, umbrally, (a(.) + x)^n = (n * x^(n-1) / 2) - (x^n / 2) + Sum_{j>=1} j^(j-1) * (2^(-j) / j!) * exp(-j/2) * (x + j/2)^n giving a(n) = 2^(-n) * Sum_{j>=1} j^(n-1) * ((j/2) * exp(-1/2))^j / j! for n > 1. - Tom Copeland, Feb 11 2008
Let h(x) = 1/(2-exp(x)), an e.g.f. for A000670, then the n-th term of A000311 is given by ((h(x)*d/dx)^n)x evaluated at x=0, i.e., A(x) = exp(x*a(.)) = exp(x*h(u)*d/du) u evaluated at u=0. Also, dA(x)/dx = h(A(x)). - Tom Copeland, Sep 05 2011 (The autonomous differential eqn. here is also on p. 59 of Jones. - Tom Copeland, Dec 16 2019)
A134991 gives (b.+c.)^n = 0^n, for (b_n)=A000311(n+1) and (c_0)=1, (c_1)=-1, and (c_n)=-2* A000311(n) = -A006351(n) otherwise. E.g., umbrally, (b.+c.)^2 = b_2*c_0 + 2 b_1*c_1 + b_0*c_2 =0. - Tom Copeland, Oct 19 2011
a(n) = Sum_{k=1..n-1} (n+k-1)!*Sum_{j=1..k} (1/(k-j)!)*Sum_{i=0..j} 2^i*(-1)^i*Stirling2(n+j-i-1, j-i)/((n+j-i-1)!*i!), n>1, a(0)=0, a(1)=1. - Vladimir Kruchinin, Jan 28 2012
Using L. Comtet's identity and D. Wasserman's explicit formula for the associated Stirling numbers of second kind (A008299) one gets: a(n) = Sum_{m=1..n-1} Sum_{i=0..m} (-1)^i * binomial(n+m-1,i) * Sum_{j=0..m-i} (-1)^j * ((m-i-j)^(n+m-1-i))/(j! * (m-i-j)!). - Peter Regner, Oct 08 2012
G.f.: x/Q(0), where Q(k) = 1 - k*x - x*(k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 01 2013
G.f.: x*Q(0), where Q(k) = 1 - x*(k+1)/(x*(k+1) - (1-k*x)*(1-x-k*x)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 11 2013
a(n) ~ n^(n-1) / (sqrt(2) * exp(n) * (2*log(2)-1)^(n-1/2)). - Vaclav Kotesovec, Jan 05 2014
E.g.f. A(x) satisfies d/dx A(x) = 1 / (1 + x - 2 * A(x)). - Michael Somos, Oct 25 2014
O.g.f.: Sum_{n>=0} x / Product_{k=0..n} (2 - k*x). - Paul D. Hanna, Oct 27 2014
E.g.f.: (x - 1 - 2 LambertW(-exp((x-1)/2) / 2)) / 2. - Vladimir Reshetnikov, Oct 16 2015 (This e.g.f. is given in A135494, the entry alluded to in my 2008 formula, and in A134991 along with its compositional inverse. - Tom Copeland, Jan 24 2018)
a(0) = 0, a(1) = 1; a(n) = n! * [x^n] exp(Sum_{k=1..n-1} a(k)*x^k/k!). - Ilya Gutkovskiy, Oct 17 2017
a(n+1) = Sum_{k=0..n} A269939(n, k) for n >= 1. - Peter Luschny, Feb 15 2021

Extensions

Name edited by Gus Wiseman, Dec 28 2019

A000245 a(n) = 3*(2*n)!/((n+2)!*(n-1)!).

Original entry on oeis.org

0, 1, 3, 9, 28, 90, 297, 1001, 3432, 11934, 41990, 149226, 534888, 1931540, 7020405, 25662825, 94287120, 347993910, 1289624490, 4796857230, 17902146600, 67016296620, 251577050010, 946844533674, 3572042254128, 13505406670700, 51166197843852, 194214400834356
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

This sequence represents the expected saturation of a binary search tree (or BST) on n nodes times the number of binary search trees on n nodes, or alternatively, the sum of the saturation of all binary search trees on n nodes. - Marko Riedel, Jan 24 2002
1->12, 2->123, 3->1234 etc. starting with 1, gives A007001: 1, 12, 12123, 12123121231234... summing the digits gives this sequence. - Miklos Kristof, Nov 05 2002
a(n-1) = number of n-th generation vertices in the tree of sequences with unit increase labeled by 2 (cf. Zoran Sunic reference). - Benoit Cloitre, Oct 07 2003
With offset 1, number of permutations beginning with 12 and avoiding 32-1.
Number of lattice paths from (0,0) to (n,n) with steps E=(1,0) and N=(0,1) which touch but do not cross the line x-y=1. - Herbert Kociemba, May 24 2004
a(n) is the number of Dyck (n+1)-paths that start with UU. For example, a(2)=3 counts UUUDDD, UUDUDD, UUDDUD. - David Callan, Dec 08 2004
a(n) is the number of Dyck (n+2)-paths that start with UUDU. For example, a(2)=3 counts UUDUDDUD, UUDUDUDD, UUDUUDDD. - David Scambler, Feb 14 2011
Hankel transform is (0,-1,-1,0,1,1,0,-1,-1,0,...). Hankel transform of a(n+1) is (1,0,-1,-1,0,1,1,0,-1,-1,0,...). - Paul Barry, Feb 08 2008
Starting with offset 1 = row sums of triangle A154558. - Gary W. Adamson, Jan 11 2009
Starting with offset 1 equals INVERT transform of A014137, partial sums of the Catalan numbers: (1, 2, 4, 9, 23, ...). - Gary W. Adamson, May 15 2009
With offset 1, a(n) is the binomial transform of the shortened Motzkin numbers: 1, 2, 4, 9, 21, 51, 127, 323, ... (A001006). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Sep 07 2009
The Catalan sequence convolved with its shifted variant, e.g. a(5) = 90 = (1, 1, 2, 5, 14) dot (42, 14, 5, 2, 1) = (42 + 14 + 10 + 10 + 14 ) = 90. - Gary W. Adamson, Nov 22 2011
a(n+2) = A214292(2*n+3,n). - Reinhard Zumkeller, Jul 12 2012
With offset 3, a(n) is the number of permutations on {1,2,...,n} that are 123-avoiding, i.e., do not contain a three term monotone subsequence, for which the first ascent is at positions (3,4); see Connolly link. There it is shown in general that the k-th Catalan Convolution is the number of 123-avoiding permutations for which the first ascent is at (k, k+1). (For n=k, the first ascent is defined to be at positions (k,k+1) if the permutation is the decreasing permutation with no ascents.) - Anant Godbole, Jan 17 2014
With offset 3, a(n)=number of permutations on {1,2,...,n} that are 123-avoiding and for which the integer n is in the 3rd spot; see Connolly link. For example, there are 297 123-avoiding permutations on n=9 at which the element 9 is in the third spot. - Anant Godbole, Jan 17 2014
With offset 1, a(n) is the number of North-East paths from (0,0) to (n+1,n+1) that bounce off y = x to the right exactly once but do not cross y = x vertically. Details can be found in Section 4.4 in Pan and Remmel's link. - Ran Pan, Feb 01 2016
The total number of returns (downsteps which end on the line y=0) within the set of all Dyck paths from (0,0) to (2n,0). - Cheyne Homberger, Sep 05 2016
a(n) is the number of intervals of the form [s,w] that are distributive (equivalently, modular) lattices in the weak order on S_n, for a fixed simple reflection s. - Bridget Tenner, Jan 16 2020
a(n+2) is the number of coalescent histories for a pair (G,S) where G is a gene tree with 3-pseudocaterpillar shape and n leaves, S is a species tree with caterpillar shape and n leaves, and G and S have identical leaf labeling. - Noah A Rosenberg, Jun 15 2022
a(n) is the number of parking functions of size n avoiding the patterns 132, 213, and 312. - Lara Pudwell, Apr 10 2023
a(n) is the number of parking functions of size n avoiding the patterns 123 and 213. - Lara Pudwell, Apr 10 2023

References

  • Pierre de la Harpe, Topics in Geometric Group Theory, Univ. Chicago Press, 2000, p. 11, coefficients of P_3(z).
  • Ki Hang Kim, Douglas G. Rogers and Fred W. Roush, Similarity relations and semiorders. Proceedings of the Tenth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1979), pp. 577-594, Congress. Numer., XXIII-XXIV, Utilitas Math., Winnipeg, Man., 1979. MR0561081 (81i:05013)
  • C. Krishnamachary and M. Bheemasena Rao, Determinants whose elements are Eulerian, prepared Bernoullian and other numbers, J. Indian Math. Soc., Vol. 14 (1922), pp. 55-62, 122-138 and 143-146.
  • 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).

Links

Crossrefs

First differences of Catalan numbers A000108.
T(n, n+3) for n=0, 1, 2, ..., array T as in A047072.
Cf. A099364.
A diagonal of any of the essentially equivalent arrays A009766, A030237, A033184, A059365, A099039, A106566, A130020, A047072.
Cf. A002057, A000344, A003517, A000588, A003518, A003519, A001392, A001622.
Cf. A154558, A014137.
Column k=1 of A067323.

Programs

  • GAP
    Concatenation([0],List([1..30],n->3*Factorial(2*n)/(Factorial(n+2)*Factorial(n-1)))); # Muniru A Asiru, Aug 09 2018
  • Magma
    [0] cat [3*Factorial(2*n)/(Factorial(n+2)*Factorial(n-1)): n in [1..30]]; // Vincenzo Librandi, Feb 15 2016
  • Maple
    A000245 := n -> 3*binomial(2*n, n-1)/(n+2);
seq(A000245(n), n=0..27);
  • Mathematica
    Table[3(2n)!/((n+2)!(n-1)!),{n,0,30}] (* or *) Table[3*Binomial[2n,n-1]/(n+2),{n,0,30}] (* or *) Differences[CatalanNumber[Range[0,31]]] (* Harvey P. Dale, Jul 13 2011 *)
  • PARI
    a(n)=if(n<1,0,3*(2*n)!/(n+2)!/(n-1)!)
  • Sage
    [catalan_number(i+1) - catalan_number(i) for i in range(28)] # Zerinvary Lajos, May 17 2009
  • Sage
    def A000245_list(n) :
    D = [0]*(n+1); D[1] = 1
    b = False; h = 1; R = []
    for i in range(2*n-1) :
        if b :
            for k in range(h,0,-1) : D[k] += D[k-1]
            h += 1; R.append(D[2])
        else :
            for k in range(1,h, 1) : D[k] += D[k+1]
        b = not b
    return R
A000245_list(29) # Peter Luschny, Jun 03 2012

Formula

a(n) = A000108(n+1) - A000108(n).
G.f.: x*(c(x))^3 = (-1+(1-x)*c(x))/x, c(x) = g.f. for Catalan numbers. Also a(n) = 3*n*Catalan(n)/(n+2). - Wolfdieter Lang
For n > 1, a(n) = 3a(n-1) + Sum[a(k)*a(n-k-2), k=1,...,n-3]. - John W. Layman, Dec 13 2002; proved by Michael Somos, Jul 05 2003
G.f. is A(x) = C(x)*(1-x)/x-1/x = x(1+x*C(x)^2)*C(x)^2 where C(x) is g.f. for Catalan numbers, A000108.
G.f. satisfies x^2*A(x)^2 + (3*x-1)*A(x) + x = 0.
Series reversion of g.f. A(x) is -A(-x). - Michael Somos, Jan 21 2004
a(n+1) = Sum_{i+j+k=n} C(i)C(j)C(k) with i, j, k >= 0 and where C(k) denotes the k-th Catalan number. - Benoit Cloitre, Nov 09 2003
An inverse Chebyshev transform of x^2. - Paul Barry, Oct 13 2004
The sequence is 0, 0, 1, 0, 3, 0, 9, 0, ... with zeros restored. Second binomial transform of (-1)^n*A005322(n). The g.f. is transformed to x^2 under the Chebyshev transformation A(x)->(1/(1+x^2))A(x/(1+x^2)). For a sequence b(n), this corresponds to taking Sum_{k=0..floor(n/2)} C(n-k, k)(-1)^k*b(n-2k), or Sum_{k=0..n} C((n+k)/2, k)*b(k)*(-1)^((n-k)/2)*(1+(-1)^(n-k))/2. - Paul Barry, Oct 13 2004
G.f.: (c(x^2)*(1-x^2)-1)/x^2, c(x) the g.f. of A000108; a(n) = Sum_{k=0..n} (k+1)*C(n, (n-k)/2)*(-1)^k*(C(2,k)-2*C(1,k)+C(0, k))*(1+(-1)^(n-k))/(n+k+2). - Paul Barry, Oct 13 2004
a(n) = Sum_{k=0..n} binomial(n,k)*2^(n-k)*(-1)^(k+1)*binomial(k, floor((k-1)/2)). - Paul Barry, Feb 16 2006
E.g.f.: exp(2*x)*(Bessel_I(1,2x) - Bessel_I(2,2*x)). - Paul Barry, Jun 04 2007
a(n) = (1/Pi)*Integral_{x=0..4} x^n*(x-1)*sqrt(x*(4-x))/(2*x). - Paul Barry, Feb 08 2008
D-finite with recurrence: For n > 1, a(n+1) = 2*(2n+1)*(n+1)*a(n)/((n+3)*n). - Sean A. Irvine, Dec 09 2009
Let A be the Toeplitz matrix of order n defined by: A[i,i-1]=-1, A[i,j] = Catalan(j-i), (i<=j), and A[i,j] = 0, otherwise. Then, for n >= 2, a(n-1) = (-1)^(n-2)*coeff(charpoly(A,x),x^2). - Milan Janjic, Jul 08 2010
a(n) = sum of top row terms of M^(n-1), M = an infinite square production matrix as follows:
2, 1, 0, 0, 0, 0, ...
1, 1, 1, 0, 0, 0, ...
1, 1, 1, 1, 0, 0, ...
1, 1, 1, 1, 1, 0, ...
1, 1, 1, 1, 1, 1, ...
...
- Gary W. Adamson, Jul 14 2011
E.g.f.: exp(2*x)*(BesselI(2,2*x)) = Q(0) - 1 where Q(k) = 1 - 2*x/(k + 1 - 3*((k+1)^2)/((k^2) + 8*k + 9 - (k+2)*((k+3)^2)*(2*k+3)/((k+3)*(2*k+3) - 3*(k+1)/Q(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Dec 05 2011
a(n) = -binomial(2*n,n)/(n+1)*hypergeom([-1,n+1/2],[n+2],4). - Peter Luschny, Aug 15 2012
a(n) = Sum_{i=0..n-1} C(i)*C(n-i), where C(i) denotes the i-th Catalan number. - Dmitry Kruchinin, Mar 02 2013
a(n) = binomial(2*n-1, n) - binomial(2*n-1, n-3). - Johannes W. Meijer, Jul 31 2013
a(n) ~ 3*4^n/(n^(3/2)*sqrt(Pi)). - Vaclav Kotesovec, Feb 26 2016
a(n) = ((-1)^n/(n+1))*Sum_{i=0..n-1} (-1)^(i+1)*(n+1-i)*binomial(2*n+2,i), n>=0. - Taras Goy, Aug 09 2018
From Amiram Eldar, Jan 02 2022: (Start)
Sum_{n>=1} 1/a(n) = 14*Pi/(27*sqrt(3)) + 5/9.
Sum_{n>=1} (-1)^(n+1)/a(n) = 164*log(phi)/(75*sqrt(5)) + 7/25, where phi is the golden ratio (A001622). (End)
a(n) = 3*Sum_{k = 0..n-2} (-1)^k * binomial(2*n-k-1, n+1)*binomial(n+1, k)/(k + 1) for n >= 2. - Peter Bala, Sep 02 2024
a(n) = (3*n/(n+2))*A000108(n). - Taras Goy, Dec 20 2024

Extensions

I changed the description and added an initial 0, to make this coincide with the first differences of the Catalan numbers A000108. Some of the other lines will need to be changed as a result. - N. J. A. Sloane, Oct 31 2003

A002866 a(0) = 1; for n > 0, a(n) = 2^(n-1)*n!.

Original entry on oeis.org

1, 1, 4, 24, 192, 1920, 23040, 322560, 5160960, 92897280, 1857945600, 40874803200, 980995276800, 25505877196800, 714164561510400, 21424936845312000, 685597979049984000, 23310331287699456000, 839171926357180416000, 31888533201572855808000, 1275541328062914232320000
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Consider the set of n-1 odd numbers from 3 to 2n-1, i.e., {3, 5, ..., 2n-1}. There are 2^(n-1) subsets from {} to {3, 5, 7, ..., 2n-1}; a(n) = the sum of the products of terms of all the subsets. (Product for empty set = 1.) a(4) = 1 + 3 + 5 + 7 + 3*5 + 3*7 + 5*7 + 3*5*7 = 192. - Amarnath Murthy, Sep 06 2002
Also, a(n-1) is the number of ways to lace a shoe that has n pairs of eyelets such that there is a straight (horizontal) connection between all adjacent eyelet pairs. - Hugo Pfoertner, Jan 27 2003
This is also the denominator of the integral of ((1-x^2)^(n-1/2))/(Pi/4) where x ranges from 0 to 1. The numerator is (2*x)!/(x!*2^x). In both cases n starts at 1. E.g., the denominator when n=3 is 24 and the numerator is 15. - Al Hakanson (hawkuu(AT)excite.com), Oct 17 2003
Number of ways to use the elements of {1,...,n} once each to form a sequence of nonempty lists. - Bob Proctor, Apr 18 2005
Row sums of A131222. - Paul Barry, Jun 18 2007
Number of rotational symmetries of an n-cube. The number of all symmetries of an n-cube is A000165. See Egan for signed cycle notation, other notes, tables and animation. - Jonathan Vos Post, Nov 28 2007
1, 4, 24, 192, 1920, ... is the exponential (or binomial) convolution of 1, 1, 3, 15, 105, ... and 1, 3, 15, 105, 945 (A001147). - David Callan, Jul 25 2008
The n-th term of this sequence is the number of regions into which n-dimensional space is partitioned by the 2n hyperplanes of the form x_i=x_j and x_i=-x_j (for 1 <= i < j <= n). - Edward Scheinerman (ers(AT)jhu.edu), May 04 2008
a(n) is the number of ways to seat n churchgoers into pews and then linearly order the nonempty pews. - Geoffrey Critzer, Mar 16 2009
Equals the row sums of A156992. - Geoffrey Critzer, Mar 05 2010
From Gary W. Adamson, May 17 2010: (Start)
Next term in the series = (1, 3, 5, 7, ...) dot (1, 1, 4, 24, ...);
e.g., a(5) = 1920 = (1, 3, 5, 7, 9) dot (1, 1, 4, 24, 192) = (1 + 3 + 20 + 168 + 1728). (End)
a(n) is the number of ways to represent the permutations of {1,2,...,n} in cycle notation, taking into account that we can permute the order of all cycles and also have k ways to write a length-k cycle.
For positive n, a(n) equals the permanent of the n X n matrix with consecutive integers 1 to n along the main diagonal, consecutive integers 2 to n along the subdiagonal, and 1's everywhere else. - John M. Campbell, Jul 10 2011
From Dennis P. Walsh, Nov 26 2011: (Start)
Number of ways to arrange n books on consecutive bookshelves.
To derive a(n) = n!2^(n-1), we note that there are n! ways to arrange the books in a row. Then there are 2^(n-1) ways to place the arranged books on consecutive shelves since there are 2^(n-1) ordered partitions of n. Hence a(n) = n!2^(n-1).
Also, a(n) is the number of ways to stack n different alphabet blocks in contiguous stacks.
Furthermore, a(n) is the number of labeled, rooted forests that have (i) each root labeled larger than any nonroot, (ii) each root having exactly one child node, (iii) n non-root nodes, and (iv) each node in the forest with at most one child node.
Example: a(3)=24 since there are 24 arrangements of books b1, b2, and b3 on consecutive shelves, namely, |b1 b2 b3|, |b1 b3 b2|, |b2 b1 b3|, |b2 b3 b1|, |b3 b1 b2|, |b3 b2 b1|, |b1 b2||b3|, |b2 b1| |b3|, |b1 b3||b2|, |b3 b1||b2|, |b2 b3||b1|, |b3 b2||b1|, |b1||b2 b3|,|b1||b3 b2|, |b2||b1 b3|, |b2||b3 b1|, |b3||b1 b2|, |b3||b2 b1|, |b1||b2||b3|, |b1||b3||b2|, |b2||b1||b3|, |b2||b3||b1|, |b3||b1||b2|, and |b3||b2||b1|.
(End)
For n > 3, a(n) is the order of the Coxeter group (also called Weyl group) of type D_n. - Tom Edgar, Nov 05 2013

Examples

			For the shoe lacing: with the notation introduced in A078602 the a(3-1) = 4 "straight" lacings for 3 pairs of eyelets are: 125346, 125436, 134526, 143526. Their mirror images 134256, 143256, 152346, 152436 are not counted.
a(3) = 24 because the 24 rotations of a three-dimensional cube fall into four distinct classes:
(i) the identity, which leaves everything fixed;
(ii) 9 rotations which leave the centers of two faces fixed, comprising rotations of 90, 180 and 270 degrees for each of 3 pairs of faces;
(iii) 6 rotations which leave the centers of two edges fixed, comprising rotations of 180 degrees for each of 6 pairs of edges;
(iv) 8 rotations which leave two vertices fixed, comprising rotations of 120 and 240 degrees for each of 4 pairs of vertices. For an n-cube, rotations can be more complex. For example, in 4 dimensions a rotation can either act in a single plane, such as the x-y plane, while leaving any vectors orthogonal to that plane unchanged, or it can act in two orthogonal planes, performing rotations in both and leaving no vectors fixed. In higher dimensions, there will be room for more planes and more choices as to the number of planes in which a given rotation acts.

References

  • N. Bourbaki, Groupes et alg. de Lie, Chap. 4, 5, 6, p. 257.
  • A. P. Prudnikov, Yu. A. Brychkov and O.I. Marichev, "Integrals and Series", Volume 1: "Elementary Functions", Chapter 4: "Finite Sums", New York, Gordon and Breach Science Publishers, 1986-1992, Eq. (4.2.2.26)
  • 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).

Links

Crossrefs

Cf. A028371, A078602, A078698, A078702, A156992.
Bisections give A002671 and A274304.
Appears in A167584 (n >= 1); equals the row sums of A167594 (n >= 1). - Johannes W. Meijer, Nov 12 2009

Programs

  • FORTRAN
    See Pfoertner link.
  • Magma
    [1] cat [2^(n-1)*Factorial(n): n in [1..25]]; // G. C. Greubel, Jun 13 2019
  • Maple
    A002866 := n-> `if`(n=0,1,2^(n-1)*n!):
with(combstruct); SeqSeqL := [S, {S=Sequence(U,card >= 1), U=Sequence(Z,card >=1)},labeled];
seq(ceil(count(Subset(n))*count(Permutation(n))/2),n=0..17); # Zerinvary Lajos, Oct 16 2006
G(x):=(1-x)/(1-2*x): f[0]:=G(x): for n from 1 to 26 do f[n]:=diff(f[n-1],x) od:x:=0:seq(f[n],n=0..17); # Zerinvary Lajos, Apr 04 2009
  • Mathematica
    Join[{1},Table[2^(n-1) n!,{n,25}]] (* Harvey P. Dale, Sep 27 2013 *)
a[n_] := (-1)^n Hypergeometric2F1Regularized[1, -n, 2 - n, 2];
Table[a[n], {n, 0, 20}]  (* Peter Luschny, Apr 26 2024 *)
  • PARI
    a(n)=if(n,n!<<(n-1),1) \\ Charles R Greathouse IV, Jan 13 2012
  • PARI
    a(n) = if(n == 0, 1, 2^(n-1)*n!);
vector(25, n, a(n-1)) \\ Altug Alkan, Oct 18 2015
  • Sage
    [1] + [2^(n-1)*factorial(n) for n in (1..25)] # G. C. Greubel, Jun 13 2019

Formula

E.g.f.: (1 - x)/(1 - 2*x). - Paul Barry, May 26 2003, corrected Jun 18 2007
a(n) = n! * A011782(n).
For n >= 1, a(n) = Sum_{i=0..m/2} (-1)^i * binomial(n, i) * (n-2*i)^n. - Yong Kong (ykong(AT)curagen.com), Dec 28 2000
a(n) ~ 2^(1/2) * Pi^(1/2) * n^(3/2) * 2^n * e^(-n) * n^n*{1 + 13/12*n^(-1) + ...}. - Joe Keane (jgk(AT)jgk.org), Nov 23 2001
E.g.f. is B(A(x)), where B(x) = 1/(1 - x) and A(x) = x/(1 - x). - Geoffrey Critzer, Mar 16 2009
a(n) = Sum_{k=1..n} A156992(n,k). - Dennis P. Walsh, Nov 26 2011
a(n+1) = Sum_{k=0..n} A132393(n,k)*2^(n+k), n>0. - Philippe Deléham, Nov 28 2011
G.f.: 1 + x/(1 - 4*x/(1 - 2*x/(1 - 6*x/(1 - 4*x/(1 - 8*x/(1 - 6*x/(1 - 10*x/(1 - ... (continued fraction). - Philippe Deléham, Nov 29 2011
a(n) = 2*n*a(n-1) for n >= 2. - Dennis P. Walsh, Nov 29 2011
G.f.: (1 + 1/G(0))/2, where G(k) = 1 + 2*x*k - 2*x*(k + 1)/G(k+1); (continued fraction, Euler's 1st kind, 1-step). - Sergei N. Gladkovskii, Aug 02 2012
G.f.: 1 + x/Q(0), m=4, where Q(k) = 1 - m*x*(2*k + 1) - m*x^2*(2*k + 1)*(2*k + 2)/(1 - m*x*(2*k + 2) - m*x^2*(2*k + 2)*(2*k + 3)/Q(k+1)) ; (continued fraction). - Sergei N. Gladkovskii, Sep 23 2013
G.f.: 1 + x/(G(0) - x), where G(k) = 1 + x*(k+1) - 4*x*(k + 1)/(1 - x*(k + 2)/G(k+1)); (continued fraction). - Sergei N. Gladkovskii, Dec 24 2013
a(n) = Sum_{k=0..n} L(n,k)*k!; L(n,k) are the unsigned Lah numbers. - Peter Luschny, Oct 18 2014
a(n) = round(Sum_{k >= 1} log(k)^n/k^(3/2))/4, for n >= 1, which is related to the n-th derivative of zeta(x) evaluated at x = 3/2. - Richard R. Forberg, Jan 02 2015
a(n) = n!*hypergeom([-n+1], [], -1) for n>=1. - Peter Luschny, Apr 08 2015
From Amiram Eldar, Aug 04 2020: (Start)
Sum_{n >= 0} 1/a(n) = 2*sqrt(e) - 1.
Sum_{n >= 0} (-1)^n/a(n) = 2/sqrt(e) - 1. (End)

A001861 Expansion of e.g.f. exp(2*(exp(x) - 1)).

Original entry on oeis.org

1, 2, 6, 22, 94, 454, 2430, 14214, 89918, 610182, 4412798, 33827974, 273646526, 2326980998, 20732504062, 192982729350, 1871953992254, 18880288847750, 197601208474238, 2142184050841734, 24016181943732414, 278028611833689478, 3319156078802044158, 40811417293301014150
Offset: 0

Views

Author

N. J. A. Sloane, Simon Plouffe

Keywords

Comments

Values of Bell polynomials: ways of placing n labeled balls into n unlabeled (but 2-colored) boxes.
First column of the square of the matrix exp(P)/exp(1) given in A011971. - Gottfried Helms, Mar 30 2007
Base matrix in A011971, second power in A078937, third power in A078938, fourth power in A078939. - Gottfried Helms, Apr 08 2007
Equals row sums of triangle A144061. - Gary W. Adamson, Sep 09 2008
Equals eigensequence of triangle A109128. - Gary W. Adamson, Apr 17 2009
Hankel transform is A108400. - Paul Barry, Apr 29 2009
The number of ways of putting n labeled balls into a set of bags and then putting the bags into 2 labeled boxes. An example is given below. - Peter Bala, Mar 23 2013
The f-vectors of n-dimensional hypercube are given by A038207 = exp[M*B(.,2)] = exp[M*A001861(.)] where M = A238385-I and (B(.,x))^n = B(n,x) are the Bell polynomials (cf. A008277). - Tom Copeland, Apr 17 2014
Moments of the Poisson distribution with mean 2. - Vladimir Reshetnikov, May 17 2016
Exponential self-convolution of Bell numbers (A000110). - Vladimir Reshetnikov, Oct 06 2016

Examples

			a(2) = 6: The six ways of putting 2 balls into bags (denoted by { }) and then into 2 labeled boxes (denoted by [ ]) are
01: [{1,2}] [ ];
02: [ ] [{1,2}];
03: [{1}] [{2}];
04: [{2}] [{1}];
05: [{1} {2}] [ ];
06: [ ] [{1} {2}].
- _Peter Bala_, Mar 23 2013

References

  • 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).

Links

Crossrefs

For boxes of 1 color, see A000110, for 3 colors see A027710, for 4 colors see A078944, for 5 colors see A144180, for 6 colors see A144223, for 7 colors see A144263, for 8 colors see A221159.
First column of A078937.
Equals 2*A035009(n), n>0.
Row sums of A033306, A036073, A049020, and A144061.
Cf. A000110, A000587, A002871, A027710, A056857, A068199, A068200, A068201, A078937, A078938, A078944, A078945, A109128, A129323, A129324, A129325, A129327, A129328, A129329, A129331, A129332, A129333, A144180, A144223, A144263, A189233, A213170, A221159, A221176.

Programs

  • Magma
    [&+[2^k*StirlingSecond(n, k): k in [0..n]]: n in [0..25]]; // Vincenzo Librandi, May 18 2019
  • Maple
    A001861:=n->add(Stirling2(n,k)*2^k, k=0..n); seq(A001861(n), n=0..20); # Wesley Ivan Hurt, Apr 18 2014
# second Maple program:
b:= proc(n, m) option remember;
     `if`(n=0, 2^m, m*b(n-1, m)+b(n-1, m+1))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..25);  # Alois P. Heinz, Aug 04 2021
  • Mathematica
    Table[Sum[StirlingS2[n, k]*2^k, {k, 0, n}], {n, 0, 21}] (* Geoffrey Critzer, Oct 06 2009 *)
mx = 16; p = 1; Range[0, mx]! CoefficientList[ Series[ Exp[ (Exp[p*x] - p - 1)/p + Exp[x]], {x, 0, mx}], x] (* Robert G. Wilson v, Dec 12 2012 *)
Table[BellB[n, 2], {n, 0, 20}] (* Vaclav Kotesovec, Jan 06 2013 *)
  • PARI
    a(n)=if(n<0,0,n!*polcoeff(exp(2*(exp(x+x*O(x^n))-1)),n))
  • PARI
    {a(n)=polcoeff(sum(m=0, n, 2^m*x^m/prod(k=1,m,1-k*x +x*O(x^n))), n)} /* Paul D. Hanna, Feb 15 2012 */
  • PARI
    {a(n) = sum(k=0, n, 2^k*stirling(n, k, 2))} \\ Seiichi Manyama, Jul 28 2019
  • Sage
    expnums(30, 2) # Zerinvary Lajos, Jun 26 2008

Formula

a(n) = Sum_{k=0..n} 2^k*Stirling2(n, k). - Emeric Deutsch, Oct 20 2001
a(n) = exp(-2)*Sum_{k>=1} 2^k*k^n/k!. - Benoit Cloitre, Sep 25 2003
G.f. satisfies 2*(x/(1-x))*A(x/(1-x)) = A(x) - 1; twice the binomial transform equals the sequence shifted one place left. - Paul D. Hanna, Dec 08 2003
PE = exp(matpascal(5)-matid(6)); A = PE^2; a(n)=A[n,1]. - Gottfried Helms, Apr 08 2007
G.f.: 1/(1-2x-2x^2/(1-3x-4x^2/(1-4x-6x^2/(1-5x-8x^2/(1-6x-10x^2/(1-... (continued fraction). - Paul Barry, Apr 29 2009
O.g.f.: Sum_{n>=0} 2^n*x^n / Product_{k=1..n} (1-k*x). - Paul D. Hanna, Feb 15 2012
a(n) ~ exp(-2-n+n/LambertW(n/2))*n^n/LambertW(n/2)^(n+1/2). - Vaclav Kotesovec, Jan 06 2013
G.f.: (G(0) - 1)/(x-1)/2 where G(k) = 1 - 2/(1-k*x)/(1-x/(x-1/G(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 16 2013
G.f.: 1/Q(0) where Q(k) = 1 + x*k - x - x/(1 - 2*x*(k+1)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 07 2013
G.f.: ((1+x)/Q(0)-1)/(2*x), where Q(k) = 1 - (k+1)*x - 2*(k+1)*x^2/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 03 2013
G.f.: T(0)/(1-2*x), where T(k) = 1 - 2*x^2*(k+1)/( 2*x^2*(k+1) - (1-2*x-x*k)*(1-3*x-x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Oct 24 2013
a(n) = Sum_{k=0..n} A033306(n,k) = Sum_{k=0..n} binomial(n,k)*Bell(k)*Bell(n-k), where Bell = A000110 (see Motzkin, p. 170). - Danny Rorabaugh, Oct 18 2015
a(0) = 1 and a(n) = 2 * Sum_{k=0..n-1} binomial(n-1,k)*a(k) for n > 0. - Seiichi Manyama, Sep 25 2017 [corrected by Ilya Gutkovskiy, Jul 12 2020]
Previous Showing 41-50 of 261 results. Next

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.