Displaying 1-10 of 24 results found.
Convolution of partition polynomials of A133437 related to solutions of the Burgers-Hopf equation.
+20
2
2, -10, 5, 42, -42, 3, 6, -168, 252, -56, -56, 7, 7, 660, -1320, 540, 360, -24, -144, -72, 4, 8, 8, -2574, 6435, -3960, -1980, 495, 1485, 495, -90, -90, -180, -90, 9, 9, 9, 10010, -30030, 25025, 10010, -5720, -11440, -2860, 165, 1980, 990, 1980, 660, -110, -110, -220, -220, -110, 5, 10, 10, 10
COMMENTS
See the formulas dated Sep 20 2016 at A133437 for a discussion of these convolution polynomials.
EXAMPLE
The first few partition polynomials are
P(1) = 0
P(2) = 0
P(3,u2) = 2 (2')^2
P(4,u2,u3) = -10 (2')^3 + 5 (2')(3')
P(5,u2,u3,u4) = 42 (2')^4 - 42 (1') (2')^2 (3') + 3 (3')^2 + 6 (2') (4')
P(6,u2,...,u5) = -168 (2')^5 + 252 (2')^3 (3') - 56 (2') (3')^2 - 56 (2')^2 (4') + 7 (3')(4') + 7 (2')(5')
P(7,u2,...,u6) = 660 (2')^6 - 1320 (2')^4 (3') + 540 (2')^2 (3')^2 + 360 (2')^3 (4') - (24 (3')^3 + 144 (2') (3') (4') + 72 (2')^2 (5')) + 4 (4')^2 + 8 (3') (5') + 8 (2') (6')
P(8,u2,...,u7) = -2574 (2')^7 + 6435 (2')^5 (3') - (3960 (2')^3 (3')^2 + 1980 (2')^4 (4')) + 495 (2') (3')^3 + 1485 (2')^2 (3') (4') + 495 (2')^3 (5') - (90 (3')^2 (4') + 90 (2') (4')^2 + 180 (2')(3')(5') + 90 (2')^2 (6')) + 9 (4')(5') + 9 (3')(6') + 9 (2')(7')
...
MATHEMATICA
rows[nn_] := With[{s = InverseSeries[t (1 + Sum[u[k] t^k, {k, nn}] + O[t]^(nn+1))]}, Table[(Length[p]-1) Coefficient[s, t^(n+1) Product[u[w], {w, p}]], {n, nn}, {p, Most@Reverse@Sort[Sort /@ IntegerPartitions[n]]}]];
Double factorial of odd numbers: a(n) = (2*n-1)!! = 1*3*5*...*(2*n-1).
(Formerly M3002 N1217)
+10
628
1, 1, 3, 15, 105, 945, 10395, 135135, 2027025, 34459425, 654729075, 13749310575, 316234143225, 7905853580625, 213458046676875, 6190283353629375, 191898783962510625, 6332659870762850625, 221643095476699771875, 8200794532637891559375, 319830986772877770815625
COMMENTS
The solution to Schröder's third problem.
Number of fixed-point-free involutions in symmetric group S_{2n} (cf. A000085). a(n-2) is the number of full Steiner topologies on n points with n-2 Steiner points. [corrected by Lyle Ramshaw, Jul 20 2022] a(n) is also the number of perfect matchings in the complete graph K(2n). - Ola Veshta (olaveshta(AT)my-deja.com), Mar 25 2001
Number of ways to choose n disjoint pairs of items from 2*n items. - Ron Zeno (rzeno(AT)hotmail.com), Feb 06 2002
Number of ways to choose n-1 disjoint pairs of items from 2*n-1 items (one item remains unpaired). - Bartosz Zoltak, Oct 16 2012 For n >= 1 a(n) is the number of permutations in the symmetric group S_(2n) whose cycle decomposition is a product of n disjoint transpositions. - Ahmed Fares (ahmedfares(AT)my-deja.com), Apr 21 2001
a(n) is the number of distinct products of n+1 variables with commutative, nonassociative multiplication. - Andrew Walters (awalters3(AT)yahoo.com), Jan 17 2004. For example, a(3)=15 because the product of the four variables w, x, y and z can be constructed in exactly 15 ways, assuming commutativity but not associativity: 1. w(x(yz)) 2. w(y(xz)) 3. w(z(xy)) 4. x(w(yz)) 5. x(y(wz)) 6. x(z(wy)) 7. y(w(xz)) 8. y(x(wz)) 9. y(z(wx)) 10. z(w(xy)) 11. z(x(wy)) 12. z(y(wx)) 13. (wx)(yz) 14. (wy)(xz) 15. (wz)(xy).
a(n) = E(X^(2n)), where X is a standard normal random variable (i.e., X is normal with mean = 0, variance = 1). So for instance a(3) = E(X^6) = 15, etc. See Abramowitz and Stegun or Hoel, Port and Stone. - Jerome Coleman, Apr 06 2004
Second Eulerian transform of 1,1,1,1,1,1,... The second Eulerian transform transforms a sequence s to a sequence t by the formula t(n) = Sum_{k=0..n} E(n,k)s(k), where E(n,k) is a second-order Eulerian number ( A008517). - Ross La Haye, Feb 13 2005 Integral representation as n-th moment of a positive function on the positive axis, in Maple notation: a(n) = int(x^n*exp(-x/2)/sqrt(2*Pi*x), x=0..infinity), n=0,1... . - Karol A. Penson, Oct 10 2005 a(n) is the number of binary total partitions of n+1 (each non-singleton block must be partitioned into exactly two blocks) or, equivalently, the number of unordered full binary trees with n+1 labeled leaves (Stanley, ex 5.2.6). - Mitch Harris, Aug 01 2006 a(n) is the Pfaffian of the skew-symmetric 2n X 2n matrix whose (i,j) entry is i for i<j. - David Callan, Sep 25 2006 a(n) is the number of increasing ordered rooted trees on n+1 vertices where "increasing" means the vertices are labeled 0,1,2,...,n so that each path from the root has increasing labels. Increasing unordered rooted trees are counted by the factorial numbers A000142. - David Callan, Oct 26 2006 Number of perfect multi Skolem-type sequences of order n. - Emeric Deutsch, Nov 24 2006 a(n) = total weight of all Dyck n-paths ( A000108) when each path is weighted with the product of the heights of the terminal points of its upsteps. For example with n=3, the 5 Dyck 3-paths UUUDDD, UUDUDD, UUDDUD, UDUUDD, UDUDUD have weights 1*2*3=6, 1*2*2=4, 1*2*1=2, 1*1*2=2, 1*1*1=1 respectively and 6+4+2+2+1=15. Counting weights by height of last upstep yields A102625. - David Callan, Dec 29 2006 a(n) is the number of increasing ternary trees on n vertices. Increasing binary trees are counted by ordinary factorials ( A000142) and increasing quaternary trees by triple factorials ( A007559). - David Callan, Mar 30 2007 From Tom Copeland, Nov 13 2007, clarified in first and extended in second paragraph, Jun 12 2021: (Start) a(n) has the e.g.f. (1-2x)^(-1/2) = 1 + x + 3*x^2/2! + ..., whose reciprocal is (1-2x)^(1/2) = 1 - x - x^2/2! - 3*x^3/3! - ... = b(0) - b(1)*x - b(2)*x^2/2! - ... with b(0) = 1 and b(n+1) = -a(n) otherwise. By the formalism of A133314, Sum_{k=0..n} binomial(n,k)*b(k)*a(n-k) = 0^n where 0^0 := 1. In this sense, the sequence a(n) is essentially self-inverse. See A132382 for an extension of this result. See A094638 for interpretations. This sequence aerated has the e.g.f. e^(t^2/2) = 1 + t^2/2! + 3*t^4/4! + ... = c(0) + c(1)*t + c(2)*t^2/2! + ... and the reciprocal e^(-t^2/2); therefore, Sum_{k=0..n} cos(Pi k/2)*binomial(n,k)*c(k)*c(n-k) = 0^n; i.e., the aerated sequence is essentially self-inverse. Consequently, Sum_{k=0..n} (-1)^k*binomial(2n,2k)*a(k)*a(n-k) = 0^n. (End)
This is also the number of ways of arranging the elements of n distinct pairs, assuming the order of elements is significant but the pairs are not distinguishable, i.e., arrangements which are the same after permutations of the labels are equivalent.
If this sequence and A000680 are denoted by a(n) and b(n) respectively, then a(n) = b(n)/n! where n! = the number of ways of permuting the pair labels. For example, there are 90 ways of arranging the elements of 3 pairs [1 1], [2 2], [3 3] when the pairs are distinguishable: A = { [112233], [112323], ..., [332211] }.
By applying the 6 relabeling permutations to A, we can partition A into 90/6 = 15 subsets: B = { {[112233], [113322], [221133], [223311], [331122], [332211]}, {[112323], [113232], [221313], [223131], [331212], [332121]}, ....}
Each subset or equivalence class in B represents a unique pattern of pair relationships. For example, subset B1 above represents {3 disjoint pairs} and subset B2 represents {1 disjoint pair + 2 interleaved pairs}, with the order being significant (contrast A132101). (End) a(n) is the number of adjacent transpositions in all fixed-point-free involutions of {1,2,...,2n}. Example: a(2)=3 because in 2143=(12)(34), 3412=(13)(24), and 4321=(14)(23) we have 2 + 0 + 1 adjacent transpositions.
(End)
(1, 3, 15, 105, ...) = INVERT transform of A000698 starting (1, 2, 10, 74, ...). - Gary W. Adamson, Oct 21 2009 a(n) = (-1)^(n+1)*H(2*n,0), where H(n,x) is the probabilists' Hermite polynomial. The generating function for the probabilists' Hermite polynomials is as follows: exp(x*t-t^2/2) = Sum_{i>=0} H(i,x)*t^i/i!. - Leonid Bedratyuk, Oct 31 2009 a(n) is the number of subsets of {1,...,n^2} that contain exactly k elements from {1,...,k^2} for k=1,...,n. For example, a(3)=15 since there are 15 subsets of {1,2,...,9} that satisfy the conditions, namely, {1,2,5}, {1,2,6}, {1,2,7}, {1,2,8}, {1,2,9}, {1,3,5}, {1,3,6}, {1,3,7}, {1,3,8}, {1,3,9}, {1,4,5}, {1,4,6}, {1,4,7}, {1,4,8}, and {1,4,9}. - Dennis P. Walsh, Dec 02 2011 For n>0: a(n) is also the determinant of the symmetric n X n matrix M defined by M(i,j) = min(i,j)^2 for 1 <= i,j <= n. - Enrique Pérez Herrero, Jan 14 2013 a(n) is also the numerator of the mean value from 0 to Pi/2 of sin(x)^(2n). - Jean-François Alcover, Jun 13 2013 For n>1: a(n) is the numerator of M(n)/M(1) where the numbers M(i) have the property that M(n+1)/M(n) ~ n-1/2 (for example, large Kendell-Mann numbers, see A000140 or A181609, as n --> infinity). - Mikhail Gaichenkov, Jan 14 2014 a(n) = the number of upper-triangular matrix representations required for the symbolic representation of a first order central moment of the multivariate normal distribution of dimension 2(n-1), i.e., E[X_1*X_2...*X_(2n-2)|mu=0, Sigma]. See vignette for symmoments R package on CRAN and Phillips reference below. - Kem Phillips, Aug 10 2014 For n>1: a(n) is the number of Feynman diagrams of order 2n (number of internal vertices) for the vacuum polarization with one charged loop only, in quantum electrodynamics. - Robert Coquereaux, Sep 15 2014 Aerated with intervening zeros (1,0,1,0,3,...) = a(n) (cf. A123023), the e.g.f. is e^(t^2/2), so this is the base for the Appell sequence A099174 with e.g.f. e^(t^2/2) e^(x*t) = exp(P(.,x),t) = unsigned A066325(x,t), the probabilist's (or normalized) Hermite polynomials. P(n,x) = (a. + x)^n with (a.)^n = a_n and comprise the umbral compositional inverses for A066325(x,t) = exp(UP(.,x),t), i.e., UP(n,P(.,t)) = x^n = P(n,UP(.,t)), where UP(n,t) are the polynomials of A066325 and, e.g., (P(.,t))^n = P(n,t). - Tom Copeland, Nov 15 2014 a(n) = the number of relaxed compacted binary trees of right height at most one of size n. A relaxed compacted binary tree of size n is a directed acyclic graph consisting of a binary tree with n internal nodes, one leaf, and n pointers. It is constructed from a binary tree of size n, where the first leaf in a post-order traversal is kept and all other leaves are replaced by pointers. These links may point to any node that has already been visited by the post-order traversal. The right height is the maximal number of right-edges (or right children) on all paths from the root to any leaf after deleting all pointers. The number of unbounded relaxed compacted binary trees of size n is A082161(n). See the Genitrini et al. link. - Michael Wallner, Jun 20 2017 Also the number of distinct adjacency matrices in the n-ladder rung graph. - Eric W. Weisstein, Jul 22 2017 a(n) = the number of essentially different ways of writing a probability distribution taking n+1 values as a sum of products of binary probability distributions. See comment of Mitch Harris above. This is because each such way corresponds to a full binary tree with n+1 leaves, with the leaves labeled by the values. (This comment is due to Niko Brummer.)
Also the number of binary trees with root labeled by an (n+1)-set S, its n+1 leaves by the singleton subsets of S, and other nodes labeled by subsets T of S so that the two daughter nodes of the node labeled by T are labeled by the two parts of a 2-partition of T. This also follows from Mitch Harris' comment above, since the leaf labels determine the labels of the other vertices of the tree.
(End)
a(n) is the n-th moment of the chi-squared distribution with one degree of freedom (equivalent to Coleman's Apr 06 2004 comment). - Bryan R. Gillespie, Mar 07 2021 Let b(n) = 0 for n odd and b(2k) = a(k); i.e., let the sequence b(n) be an aerated version of this entry. After expanding the differential operator (x + D)^n and normal ordering the resulting terms, the integer coefficient of the term x^k D^m is n! b(n-k-m) / [(n-k-m)! k! m!] with 0 <= k,m <= n and (k+m) <= n. E.g., (x+D)^2 = x^2 + 2xD + D^2 + 1 with D = d/dx. The result generalizes to the raising (R) and lowering (L) operators of any Sheffer polynomial sequence by replacing x by R and D by L and follows from the disentangling relation e^{t(L+R)} = e^{t^2/2} e^{tR} e^{tL}. Consequently, these are also the coefficients of the reordered 2^n permutations of the binary symbols L and R under the condition LR = RL + 1. E.g., (L+R)^2 = LL + LR + RL + RR = LL + 2RL + RR + 1. (Cf. A344678.) - Tom Copeland, May 25 2021 Lando and Zvonkin present several scenarios in which the double factorials occur in their role of enumerating perfect matchings (pairings) and as the nonzero moments of the Gaussian e^(x^2/2).
Speyer and Sturmfels (p. 6) state that the number of facets of the abstract simplicial complex known as the tropical Grassmannian G'''(2,n), the space of phylogenetic T_n trees (see A134991), or Whitehouse complex is a shifted double factorial. These are also the unsigned coefficients of the x[2]^m terms in the partition polynomials of A134685 for compositional inversion of e.g.f.s, a refinement of A134991. a(n)*2^n = A001813(n) and A001813(n)/(n+1)! = A000108(n), the Catalan numbers, the unsigned coefficients of the x[2]^m terms in the partition polynomials A133437 for compositional inversion of o.g.f.s, a refinement of A033282, A126216, and A086810. Then the double factorials inherit a multitude of analytic and combinatoric interpretations from those of the Catalan numbers, associahedra, and the noncrossing partitions of A134264 with the Catalan numbers as unsigned-row sums. (End) Connections among the Catalan numbers A000108, the odd double factorials, values of the Riemann zeta function and its derivative for integer arguments, and series expansions of the reduced action for the simple harmonic oscillator and the arc length of the spiral of Archimedes are given in the MathOverflow post on the Riemann zeta function. - Tom Copeland, Oct 02 2021 b(n) = a(n) / (n! 2^n) = Sum_{k = 0..n} (-1)^n binomial(n,k) (-1)^k a(k) / (k! 2^k) = (1-b.)^n, umbrally; i.e., the normalized double factorial a(n) is self-inverse under the binomial transform. This can be proved by applying the Euler binomial transformation for o.g.f.s Sum_{n >= 0} (1-b.)^n x^n = (1/(1-x)) Sum_{n >= 0} b_n (x / (x-1))^n to the o.g.f. (1-x)^{-1/2} = Sum_{n >= 0} b_n x^n. Other proofs are suggested by the discussion in Watson on pages 104-5 of transformations of the Bessel functions of the first kind with b(n) = (-1)^n binomial(-1/2,n) = binomial(n-1/2,n) = (2n)! / (n! 2^n)^2. - Tom Copeland, Dec 10 2022
REFERENCES
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, Tenth Printing, 1972, (26.2.28).
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 317.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 228, #19.
Hoel, Port and Stone, Introduction to Probability Theory, Section 7.3.
F. K. Hwang, D. S. Richards and P. Winter, The Steiner Tree Problem, North-Holland, 1992, see p. 14.
C. Itzykson and J.-B. Zuber, Quantum Field Theory, McGraw-Hill, 1980, pages 466-467.
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 Example 5.2.6 and also p. 178.
R. Vein and P. Dale, Determinants and Their Applications in Mathematical Physics, Springer-Verlag, New York, 1999, p. 73.
G. Watson, The Theory of Bessel Functions, Cambridge Univ. Press, 1922.
LINKS
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]. O. Bodini, M. Dien, X. Fontaine, A. Genitrini, and H. K. Hwang, Increasing Diamonds, in LATIN 2016: 12th Latin American Symposium, Ensenada, Mexico, April 11-15, 2016, Proceedings Pages pp. 207-219 2016 DOI 10.1007/978-3-662-49529-2_16; Lecture Notes in Computer Science Series Volume 9644. Peter J. Cameron, Some treelike objects Quart. J. Math. Oxford Ser. 38 (1987), 155-183. MR0891613 (89a:05009). See p. 155. Paul W. Haggard, On Legendre numbers, International Journal of Mathematics and Mathematical Sciences, vol. 8, Article ID 787189, 5 pages, 1985. See Table 1 p. 408. M. Kauers and S.-L. Ko, Problem 11545, Amer. Math. Monthly, 118 (2011), p. 84. Eric Weisstein's World of Mathematics, Erf
FORMULA
E.g.f.: 1 / sqrt(1 - 2*x).
D-finite with recurrence: a(n) = a(n-1)*(2*n-1) = (2*n)!/(n!*2^n) = A010050(n)/ A000165(n). a(n) ~ sqrt(2) * 2^n * (n/e)^n.
Rational part of numerator of Gamma(n+1/2): a(n) * sqrt(Pi) / 2^n = Gamma(n+1/2). - Yuriy Brun, Ewa Dominowska (brun(AT)mit.edu), May 12 2001
With interpolated zeros, the sequence has e.g.f. exp(x^2/2). - Paul Barry, Jun 27 2003 The Ramanujan polynomial psi(n+1, n) has value a(n). - Ralf Stephan, Apr 16 2004 Log(1 + x + 3*x^2 + 15*x^3 + 105*x^4 + 945*x^5 + 10395*x^6 + ...) = x + 5/2*x^2 + 37/3*x^3 + 353/4*x^4 + 4081/5*x^5 + 55205/6*x^6 + ..., where [1, 5, 37, 353, 4081, 55205, ...] = A004208. - Philippe Deléham, Jun 20 2006 1/3 + 2/15 + 3/105 + ... = 1/2. [Jolley eq. 216]
Sum_{j=1..n} j/a(j+1) = (1 - 1/a(n+1))/2. [Jolley eq. 216]
1/1 + 1/3 + 2/15 + 6/105 + 24/945 + ... = Pi/2. - Gary W. Adamson, Dec 21 2006 a(n) = (1/sqrt(2*Pi))*Integral_{x>=0} x^n*exp(-x/2)/sqrt(x). - Paul Barry, Jan 28 2008 G.f.: 1/(1-x-2x^2/(1-5x-12x^2/(1-9x-30x^2/(1-13x-56x^2/(1- ... (continued fraction). - Paul Barry, Sep 18 2009 a(n) = (-1)^n*subs({log(e)=1,x=0},coeff(simplify(series(e^(x*t-t^2/2),t,2*n+1)),t^(2*n))*(2*n)!). - Leonid Bedratyuk, Oct 31 2009 G.f.: 1/(1-x/(1-2x/(1-3x/(1-4x/(1-5x/(1- ...(continued fraction). - Aoife Hennessy (aoife.hennessy(AT)gmail.com), Dec 02 2009
The g.f. of a(n+1) is 1/(1-3x/(1-2x/(1-5x/(1-4x/(1-7x/(1-6x/(1-.... (continued fraction). - Paul Barry, Dec 04 2009 E.g.f.: A(x) = 1 - sqrt(1-2*x) satisfies the differential equation A'(x) - A'(x)*A(x) - 1 = 0. - Vladimir Kruchinin, Jan 17 2011 a(n) = (1/2)*Sum_{i=1..n} binomial(n+1,i)*a(i-1)*a(n-i). See link above. - Dennis P. Walsh, Dec 02 2011 a(n) = Sum_{k=0..n} (-1)^k*binomial(2*n,n+k)*Stirling_1(n+k,k) [Kauers and Ko].
a(n) = A035342(n, 1), n >= 1 (first column of triangle). a(n) = A001497(n, 0) = A001498(n, n), first column, resp. main diagonal, of Bessel triangle. a(n) = upper left term of M^n and sum of top row terms of M^(n-1), where M = a variant of the (1,2) Pascal triangle (Cf. A029635) as the following production matrix: 1, 2, 0, 0, 0, ...
1, 3, 2, 0, 0, ...
1, 4, 5, 2, 0, ...
1, 5, 9, 7, 2, ...
...
For example, a(3) = 15 is the left term in top row of M^3: (15, 46, 36, 8) and a(4) = 105 = (15 + 46 + 36 + 8).
(End)
G.f.: A(x) = 1 + x/(W(0) - x); W(k) = 1 + x + x*2*k - x*(2*k + 3)/W(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 17 2011 a(n) = Sum_{i=1..n} binomial(n,i-1)*a(i-1)*a(n-i). - Dennis P. Walsh, Dec 02 2011 a(n) = (-1)^n*Sum_{k=0..n} 2^(n-k)*s(n+1,k+1), where s(n,k) are the Stirling numbers of the first kind, A048994. - Mircea Merca, May 03 2012 a(n) = (2*n)_4! = Gauss_factorial(2*n,4) = Product_{j=1..2*n, gcd(j,4)=1} j. - Peter Luschny, Oct 01 2012 G.f.: (1 - 1/Q(0))/x where Q(k) = 1 - x*(2*k - 1)/(1 - x*(2*k + 2)/Q(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Mar 19 2013 G.f.: 1 + x/Q(0), where Q(k) = 1 + (2*k - 1)*x - 2*x*(k + 1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 01 2013 G.f.: 2/G(0), where G(k) = 1 + 1/(1 - 2*x*(2*k + 1)/(2*x*(2*k + 1) - 1 + 2*x*(2*k + 2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, May 31 2013 G.f.: G(0)/2, where G(k) = 1 + 1/(1 - x/(x + 1/(2*k + 1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 01 2013 G.f.: G(0), where G(k) = 1 + 2*x*(4*k + 1)/(4*k + 2 - 2*x*(2*k + 1)*(4*k + 3)/(x*(4*k + 3) + 2*(k + 1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Jun 22 2013 a(n) = (2*n - 3)*a(n-2) + (2*n - 2)*a(n-1), n > 1. - Ivan N. Ianakiev, Jul 08 2013 G.f.: G(0), where G(k) = 1 - x*(k+1)/(x*(k+1) - 1/G(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Aug 04 2013 a(n) = 2*a(n-1) + (2n-3)^2*a(n-2), a(0) = a(1) = 1. - Philippe Deléham, Oct 27 2013 G.f. of reciprocals: Sum_{n>=0} x^n/a(n) = 1F1(1; 1/2; x/2), confluent hypergeometric Function. - R. J. Mathar, Jul 25 2014 0 = a(n)*(+2*a(n+1) - a(n+2)) + a(n+1)*(+a(n+1)) for all n in Z. - Michael Somos, Sep 18 2014 a(n) = (-1)^n / a(-n) = 2*a(n-1) + a(n-1)^2 / a(n-2) for all n in Z. - Michael Somos, Sep 18 2014 Recurrence equation: a(n) = (3*n - 2)*a(n-1) - (n - 1)*(2*n - 3)*a(n-2) with a(1) = 1 and a(2) = 3.
The sequence b(n) = A087547(n), beginning [1, 4, 52, 608, 12624, ... ], satisfies the same second-order recurrence equation. This leads to the generalized continued fraction expansion lim_{n -> infinity} b(n)/a(n) = Pi/2 = 1 + 1/(3 - 6/(7 - 15/(10 - ... - n*(2*n - 1)/((3*n + 1) - ... )))). (End) E.g.f of the sequence whose n-th element (n = 1,2,...) equals a(n-1) is 1-sqrt(1-2*x). - Stanislav Sykora, Jan 06 2017 Sum_{n >= 1} a(n)/(2*n-1)! = exp(1/2). - Daniel Suteu, Feb 06 2017 a(n) = (Product_{k=0..n-2} binomial(2*(n-k),2))/n!. - Stefano Spezia, Nov 13 2018 a(n) = Sum_{i=0..n-1} Sum_{j=0..n-i-1} C(n-1,i)*C(n-i-1,j)*a(i)*a(j)*a(n-i-j-1), a(0)=1, - Vladimir Kruchinin, May 06 2020 Sum_{n>=1} 1/a(n) = sqrt(e*Pi/2)*erf(1/sqrt(2)), where erf is the error function.
Sum_{n>=1} (-1)^(n+1)/a(n) = sqrt(Pi/(2*e))*erfi(1/sqrt(2)), where erfi is the imaginary error function. (End)
G.f. of reciprocals: R(x) = Sum_{n>=0} x^n/a(n) satisfies (1 + x)*R(x) = 1 + 2*x*R'(x). - Werner Schulte, Nov 04 2024
EXAMPLE
a(3) = 1*3*5 = 15.
There are a(3)=15 involutions of 6 elements without fixed points:
#: permutation transpositions
01: [ 1 0 3 2 5 4 ] (0, 1) (2, 3) (4, 5)
02: [ 1 0 4 5 2 3 ] (0, 1) (2, 4) (3, 5)
03: [ 1 0 5 4 3 2 ] (0, 1) (2, 5) (3, 4)
04: [ 2 3 0 1 5 4 ] (0, 2) (1, 3) (4, 5)
05: [ 2 4 0 5 1 3 ] (0, 2) (1, 4) (3, 5)
06: [ 2 5 0 4 3 1 ] (0, 2) (1, 5) (3, 4)
07: [ 3 2 1 0 5 4 ] (0, 3) (1, 2) (4, 5)
08: [ 3 4 5 0 1 2 ] (0, 3) (1, 4) (2, 5)
09: [ 3 5 4 0 2 1 ] (0, 3) (1, 5) (2, 4)
10: [ 4 2 1 5 0 3 ] (0, 4) (1, 2) (3, 5)
11: [ 4 3 5 1 0 2 ] (0, 4) (1, 3) (2, 5)
12: [ 4 5 3 2 0 1 ] (0, 4) (1, 5) (2, 3)
13: [ 5 2 1 4 3 0 ] (0, 5) (1, 2) (3, 4)
14: [ 5 3 4 1 2 0 ] (0, 5) (1, 3) (2, 4)
15: [ 5 4 3 2 1 0 ] (0, 5) (1, 4) (2, 3)
(End)
G.f. = 1 + x + 3*x^2 + 15*x^3 + 105*x^4 + 945*x^5 + 10395*x^6 + 135135*x^7 + ...
MAPLE
f := n->(2*n)!/(n!*2^n);
G(x):=(1-2*x)^(-1/2): f[0]:=G(x): for n from 1 to 29 do f[n]:=diff(f[n-1], x) od: x:=0: seq(f[n], n=0..19); # Zerinvary Lajos, Apr 03 2009; aligned with offset by Johannes W. Meijer, Aug 11 2009 series(hypergeom([1, 1/2], [], 2*x), x=0, 20); # Mark van Hoeij, Apr 07 2013
MATHEMATICA
a[ n_] := 2^n Gamma[n + 1/2] / Gamma[1/2]; (* Michael Somos, Sep 18 2014 *) a[ n_] := If[ n < 0, (-1)^n / a[-n], SeriesCoefficient[ Product[1 - (1 - x)^(2 k - 1), {k, n}], {x, 0, n}]]; (* Michael Somos, Jun 27 2017 *)
PROG
(PARI) {a(n) = if( n<0, (-1)^n / a(-n), (2*n)! / n! / 2^n)}; /* Michael Somos, Sep 18 2014 */ (PARI) x='x+O('x^33); Vec(serlaplace((1-2*x)^(-1/2))) \\ Joerg Arndt, Apr 24 2011 (Magma) I:=[1, 3]; [1] cat [n le 2 select I[n] else (3*n-2)*Self(n-1)-(n-1)*(2*n-3)*Self(n-2): n in [1..25] ]; // Vincenzo Librandi, Feb 19 2015 (Haskell)
a001147 n = product [1, 3 .. 2 * n - 1]
a001147_list = 1 : zipWith (*) [1, 3 ..] a001147_list
(Sage) [rising_factorial(n+1, n)/2^n for n in (0..15)] # Peter Luschny, Jun 26 2012 (Python)
from sympy import factorial2
def a(n): return factorial2(2 * n - 1)
(GAP) A001147 := function(n) local i, s, t; t := 1; i := 0; Print(t, ", "); for i in [1 .. n] do t := t*(2*i-1); Print(t, ", "); od; end; A001147(100); # Stefano Spezia, Nov 13 2018 (Maxima)
a(n):=if n=0 then 1 else sum(sum(binomial(n-1, i)*binomial(n-i-1, j)*a(i)*a(j)*a(n-i-j-1), j, 0, n-i-1), i, 0, n-1); /* Vladimir Kruchinin, May 06 2020 */
CROSSREFS
Cf. A086677; A055142 (for this sequence, |a(n+1)| + 1 is the number of distinct products which can be formed using commutative, nonassociative multiplication and a nonempty subset of n given variables). Cf. A079267, A000698, A029635, A161198, A076795, A123023, A161124, A051125, A181983, A099174, A087547, A028338 (first column). Cf. A082161 (relaxed compacted binary trees of unbounded right height). Cf. A000108, A001813, A033282, A060540, A086810, A094638, A126216, A133437, A134264, A134685, A134991, A344678.
KEYWORD
nonn,easy,nice,core,changed
EXTENSIONS
Removed erroneous comments: neither the number of n X n binary matrices A such that A^2 = 0 nor the number of simple directed graphs on n vertices with no directed path of length two are counted by this sequence (for n = 3, both are 13). - Dan Drake, Jun 02 2009
a(n) = binomial(3*n,n)/(2*n+1) (enumerates ternary trees and also noncrossing trees).
(Formerly M2926 N1174)
+10
496
1, 1, 3, 12, 55, 273, 1428, 7752, 43263, 246675, 1430715, 8414640, 50067108, 300830572, 1822766520, 11124755664, 68328754959, 422030545335, 2619631042665, 16332922290300, 102240109897695, 642312451217745, 4048514844039120, 25594403741131680, 162250238001816900
COMMENTS
Smallest number of straight line crossing-free spanning trees on n points in the plane.
Number of dissections of some convex polygon by nonintersecting diagonals into polygons with an odd number of sides and having a total number of 2n+1 edges (sides and diagonals). - Emeric Deutsch, Mar 06 2002 Number of lattice paths of n East steps and 2n North steps from (0,0) to (n,2n) and lying weakly below the line y=2x. - David Callan, Mar 14 2004 With interpolated zeros, this has g.f. 2*sqrt(3)*sin(arcsin(3*sqrt(3)*x/2)/3)/(3*x) and a(n) = C(n+floor(n/2),floor(n/2))*C(floor(n/2),n-floor(n/2))/(n+1). This is the first column of the inverse of the Riordan array (1-x^2,x(1-x^2)) (essentially reversion of y-y^3). - Paul Barry, Feb 02 2005 Number of 12312-avoiding matchings on [2n].
Number of complete ternary trees with n internal nodes, or 3n edges.
Number of rooted plane trees with 2n edges, where every vertex has even outdegree ("even trees").
a(n) is the number of noncrossing partitions of [2n] with all blocks of even size. E.g.: a(2)=3 counts 12-34, 14-23, 1234. - David Callan, Mar 30 2007 Pfaff-Fuss-Catalan sequence C^{m}_n for m=3, see the Graham et al. reference, p. 347. eq. 7.66.
Also 3-Raney sequence, see the Graham et al. reference, p. 346-7.
The number of lattice paths from (0,0) to (2n,0) using an Up-step=(1,1) and a Down-step=(0,-2) and staying above the x-axis. E.g., a(2) = 3; UUUUDD, UUUDUD, UUDUUD. - Charles Moore (chamoore(AT)howard.edu), Jan 09 2008
a(n) is (conjecturally) the number of permutations of [n+1] that avoid the patterns 4-2-3-1 and 4-2-5-1-3 and end with an ascent. For example, a(4)=55 counts all 60 permutations of [5] that end with an ascent except 42315, 52314, 52413, 53412, all of which contain a 4-2-3-1 pattern and 42513. - David Callan, Jul 22 2008 With B(x,t)=x+t*x^3, the comp. inverse in x about 0 is A(x,t) = Sum_{j>=0} a(j) (-t)^j x^(2j+1). Let U(x,t)=(x-A(x,t))/t. Then DU(x,t)/Dt=dU/dt+U*dU/dx=0 and U(x,0)=x^3, i.e., U is a solution of the inviscid Burgers's, or Hopf, equation. Also U(x,t)=U(x-t*U(x,t),0) and dB(x,t)/dt = U(B(x,t),t) = x^3 = U(x,0). The characteristics for the Hopf equation are x(t) = x(0) + t*U(x(t),t) = x(0) + t*U(x(0),0) = x(0) + t*x(0)^3 = B(x(0),t). These results apply to all the Fuss-Catalan sequences with 3 replaced by n>0 and 2 by n-1 (e.g., A000108 with n=2 and A002293 with n=4), see also A086810, which can be generalized to A133437, for associahedra. - Tom Copeland, Feb 15 2014 Number of intervals (i.e., ordered pairs (x,y) such that x<=y) in the Kreweras lattice (noncrossing partitions ordered by refinement) of size n, see the Bernardi & Bonichon (2009) and Kreweras (1972) references. - Noam Zeilberger, Jun 01 2016 Number of sum-indecomposable (4231,42513)-avoiding permutations. Conjecturally, number of sum-indecomposable (2431,45231)-avoiding permutations. - Alexander Burstein, Oct 19 2017 a(n) is the number of topologically distinct endstates for the game Planted Brussels Sprouts on n vertices, see Ji and Propp link. - Caleb Ji, May 14 2018 Number of complete quadrillages of 2n+2-gons. See Baryshnikov p. 12. See also Nov. 10 2014 comments in A134264. - Tom Copeland, Jun 04 2018 a(n) is the number of 2-regular words on the alphabet [n] that avoid the patterns 231 and 221. Equivalently, this is the number of 2-regular tortoise-sortable words on the alphabet [n] (see the Defant and Kravitz link). - Colin Defant, Sep 26 2018 a(n) is the number of Motzkin paths of length 3n with n steps of each type, with the condition that (1, 0) and (1, 1) steps alternate (starting with (1, 0)). - Helmut Prodinger, Apr 08 2019 a(n) is the number of uniquely sorted permutations of length 2n+1 that avoid the patterns 312 and 1342. - Colin Defant, Jun 08 2019 The compositional inverse o.g.f. pair in Copeland's comment above are related to a pair of quantum fields in Balduf's thesis by Theorem 4.2 on p. 92. - Tom Copeland, Dec 13 2019 The sequences of Fuss-Catalan numbers, of which this is the first after the Catalan numbers A000108 (the next is A002293), appear in articles on random matrices and quantum physics. See Banica et al., Collins et al., and Mlotkowski et al. Interpretations of these sequences in terms of the cardinality of specific sets of noncrossing partitions are provided by A134264. - Tom Copeland, Dec 21 2019 Call C(p, [alpha], g) the number of partitions of a cyclically ordered set with p elements, of cyclic type [alpha], and of genus g (the genus g Faa di Bruno coefficients of type [alpha]). This sequence counts the genus 0 partitions (non-crossing, or planar, partitions) of p = 3n into n parts of length 3: a(n) = C(3n, [3^n], 0). For genus 1 see A371250, for genus 2 see A371251. - Robert Coquereaux, Mar 16 2024 a(n) is the total number of down steps before the first up step in all 2_1-Dyck paths of length 3*n for n > 0. A 2_1-Dyck path is a lattice path with steps (1,2), (1,-1) that starts and ends at y = 0 and does not go below the line y = -1. - Sarah Selkirk, May 10 2020 a(n) is the number of pairs (A<=B) of noncrossing partitions of [n]. - Francesca Aicardi, May 28 2022 a(n) is the number of parking functions of size n avoiding the patterns 231 and 321. - Lara Pudwell, Apr 10 2023 Number of rooted polyominoes composed of n square cells of the hyperbolic regular tiling with Schläfli symbol {4,oo}. A rooted polyomino has one external edge identified, and chiral pairs are counted as two. A stereographic projection of the {4,oo} tiling on the Poincaré disk can be obtained via the Christensson link. - Robert A. Russell, Jan 27 2024 This is instance k = 3 of the family {C(k, n)}_{n>=0} given in a comment in A130564. - Wolfdieter Lang, Feb 05 2024 The number of Apollonian networks (planar 3-trees) with n+3 vertices with a given base triangle. - Allan Bickle, Feb 20 2024 Number of rooted polyominoes composed of n tetrahedral cells of the hyperbolic regular tiling with Schläfli symbol {3,3,oo}. A rooted polyomino has one external face identified, and chiral pairs are counted as two. a(n) = T(n) in the second Beineke and Pippert link. - Robert A. Russell, Mar 20 2024
REFERENCES
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 23.
I. M. H. Etherington, On non-associative combinations, Proc. Royal Soc. Edinburgh, 59 (Part 2, 1938-39), 153-162.
I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. Part II is by A. Erdelyi and I. M. H. Etherington, and is on pages vii-xiv of the same issue.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, pp. 200, 347. See also the Pólya-Szegő reference.
W. Kuich, Languages and the enumeration of planted plane trees. Nederl. Akad. Wetensch. Proc. Ser. A 73 = Indag. Math. 32, (1970), 268-280.
T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, p. 98.
G. Pólya and G. Szegő, Problems and Theorems in Analysis, Springer-Verlag, New York, Heidelberg, Berlin, 2 vols., 1972, Vol. 1, problem 211, p. 146 with solution on p. 348.
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
N. V. Alexeev, Number of trees in a random graph, Probabilistic methods in discrete mathematics, Extended abstracts of the 10th International Petrozavodsk Conference (Russia, 2019), 12-13. (in Russian) T. Banica, S. Belinschi, M. Capitaine, and B. Collins, Free Bessel laws, arXiv:0710.5931 [math.PR], 2008. Y. Baryshnikov, On Stokes sets, New developments in singularity theory (Cambridge, 2000): 65-86. Kluwer Acad. Publ., Dordrecht, 2001. L. W. Beineke and R. E. Pippert, Enumerating labeled k-dimensional trees and ball dissections, pp. 12-26 of Proceedings of Second Chapel Hill Conference on Combinatorial Mathematics and Its Applications, University of North Carolina, Chapel Hill, 1970. Reprinted in Math. Annalen, 191 (1971), 87-98. Peter J. Cameron and Liam Stott, Trees and cycles, arXiv:2010.14902 [math.CO], 2020. See p. 33. I. M. H. Etherington, Some problems of non-associative combinations (I), Edinburgh Math. Notes, 32 (1940), pp. i-vi. [Annotated scanned copy]. Part II [not scanned] is by A. Erdelyi and I. M. H. Etherington, and it is on pages vii-xiv of the same issue. D. Merlini, R. Sprugnoli and M. C. Verri, The tennis ball problem, J. Combin. Theory, A 99 (2002), 307-344, (T_n for s=3).
FORMULA
G.f.: (2/sqrt(3*x))*sin((1/3)*arcsin(sqrt(27*x/4))).
E.g.f.: hypergeom([1/3, 2/3], [1, 3/2], 27/4*x).
Integral representation as n-th moment of a positive function on [0, 27/4]: a(n) = Integral_{x=0..27/4} (x^n*((1/12) * 3^(1/2) * 2^(1/3) * (2^(1/3)*(27 + 3 * sqrt(81 - 12*x))^(2/3) - 6 * x^(1/3))/(Pi * x^(2/3)*(27 + 3 * sqrt(81 - 12*x))^(1/3)))), n >= 0. This representation is unique. (End)
G.f. A(x) satisfies A(x) = 1+x*A(x)^3 = 1/(1-x*A(x)^2) [Cyvin (1998)]. - Ralf Stephan, Jun 30 2003 a(n) = n-th coefficient in expansion of power series P(n), where P(0) = 1, P(k+1) = 1/(1 - x*P(k)^2).
G.f. Rev(x/c(x))/x, where c(x) is the g.f. of A000108 (Rev=reversion of). - Paul Barry, Mar 26 2010 Let M = the production matrix:
1, 1
2, 2, 1
3, 3, 2, 1
4, 4, 3, 2, 1
5, 5, 4, 3, 2, 1
...
a(n) = upper left term in M^n. Top row terms of M^n = (n+1)-th row of triangle A143603, with top row sums generating A006013: (1, 2, 7, 30, 143, 728, ...). (End) Recurrence: a(0)=1; a(n) = Sum_{i=0..n-1, j=0..n-1-i} a(i)a(j)a(n-1-i-j) for n >= 1 (counts ternary trees by subtrees of the root). - David Callan, Nov 21 2011 G.f.: 1 + 6*x/(Q(0) - 6*x); Q(k) = 3*x*(3*k + 1)*(3*k + 2) + 2*(2*(k^2) + 5*k +3) - 6*x*(2*(k^2) + 5*k + 3)*(3*k + 4)*(3*k + 5)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, Nov 27 2011 D-finite with recurrence: 2*n*(2n+1)*a(n) - 3*(3n-1)*(3n-2)*a(n-1) = 0. - R. J. Mathar, Dec 14 2011 G.f.: F([2/3,4/3], [3/2], 27/4*x) / F([2/3,1/3], [1/2], (27/4)*x) where F() is the hypergeometric function. - Joerg Arndt, Sep 01 2012 0 = a(n)*(-3188646*a(n+2) + 20312856*a(n+3) - 11379609*a(n+4) + 1437501*a(n+5)) + a(n+1)*(177147*a(n+2) - 2247831*a(n+3) + 1638648*a(n+4) - 238604*a(n+5)) + a(n+2)*(243*a(n+2) + 31497*a(n+3) - 43732*a(n+4) + 8288*a(n+5)) for all integer n. - Michael Somos, Jun 03 2016 a(n) ~ 3^(3*n + 1/2)/(sqrt(Pi)*4^(n+1)*n^(3/2)). - Ilya Gutkovskiy, Nov 21 2016 Given g.f. A(x), then A(1/8) = -1 + sqrt(5), A(2/27) = (-1 + sqrt(3))*3/2, A(4/27) = 3/2, A(3/64) = -2 + 2*sqrt(7/3), A(5/64) = (-1 + sqrt(5))*2/sqrt(5), etc. A(n^2/(n+1)^3) = (n+1)/n if n > 1. - Michael Somos, Jul 17 2018 A(x) = exp( Sum_{n >= 1} (1/3)*binomial(3*n,n)*x^n/n ).
The sequence defined by b(n) := [x^n] A(x)^n = A224274(n) for n >= 1 and satisfies the congruence b(p) == b(1) (mod p^3) for prime p >= 3. Cf. A060941. (End) G.f.: 1/sqrt(B(x)+(1-6*x)/(9*B(x))+1/3), with B(x):=((27*x^2-18*x+2)/54-(x*sqrt((-(4-27*x))*x))/(2*3^(3/2)))^(1/3). - Vladimir Kruchinin, Sep 28 2021 a(n) = hypergeom([1 - n, -2*n], [2], 1). Row sums of A108767. - Peter Bala, Aug 30 2023 G.f.: z*exp(3*z*hypergeom([1, 1, 4/3, 5/3], [3/2, 2, 2], (27*z)/4)) + 1.
G.f.: hypergeometric([1/3, 2/3], [3/2], (3^3/2^2)*x). See the e.g.f. above. - Wolfdieter Lang, Feb 04 2024
EXAMPLE
a(2) = 3 because the only dissections with 5 edges are given by a square dissected by any of the two diagonals and the pentagon with no dissecting diagonal.
G.f. = 1 + x + 3*x^2 + 12*x^3 + 55*x^4 + 273*x^5 + 1428*x^6 + 7752*x^7 + 43263*x^8 + ...
MAPLE
with(combstruct): BB:=[T, {T=Prod(Z, F), F=Sequence(B), B=Prod(F, Z, F)}, unlabeled]:seq(count(BB, size=i), i=0..22); # Zerinvary Lajos, Apr 22 2007 with(combstruct):BB:=[S, {B = Prod(S, S, Z), S = Sequence(B)}, labelled]: seq(count(BB, size=n)/n!, n=0..21); # Zerinvary Lajos, Apr 25 2008 n:=30:G:=series(RootOf(g = 1+x*g^3, g), x=0, n+1):seq(coeff(G, x, k), k=0..n); # Robert FERREOL, Apr 03 2015 alias(PS=ListTools:-PartialSums): A001764List := proc(m) local A, P, n;
A := [1, 1]; P := [1]; for n from 1 to m - 2 do P := PS(PS([op(P), P[-1]]));
A := [op(A), P[-1]] od; A end: A001764List(25); # Peter Luschny, Mar 26 2022
MATHEMATICA
InverseSeries[Series[y-y^3, {y, 0, 24}], x] (* then a(n)=y(2n+1)=ways to place non-crossing diagonals in convex (2n+4)-gon so as to create only quadrilateral tiles *) (* Len Smiley, Apr 08 2000 *) Table[Binomial[3n, n]/(2n+1), {n, 0, 25}] (* Harvey P. Dale, Jul 24 2011 *)
PROG
(PARI) {a(n) = if( n<0, 0, (3*n)! / n! / (2*n + 1)!)};
(PARI) {a(n) = if( n<0, 0, polcoeff( serreverse( x - x^3 + O(x^(2*n + 2))), 2*n + 1))};
(PARI) {a(n) = my(A); if( n<0, 0, A = 1 + O(x); for( m=1, n, A = 1 + x * A^3); polcoeff(A, n))};
(PARI) b=vector(22); b[1]=1; for(n=2, 22, for(i=1, n-1, for(j=1, n-1, for(k=1, n-1, if((i-1)+(j-1)+(k-1)-(n-2), NULL, b[n]=b[n]+b[i]*b[j]*b[k]))))); a(n)=b[n+1]; print1(a(0)); for(n=1, 21, print1(", ", a(n))) \\ Gerald McGarvey, Oct 08 2008 (PARI) Vec(1 + serreverse(x / (1+x)^3 + O(x^30))) \\ Gheorghe Coserea, Aug 05 2015 (Sage)
D = [0]*(n+1); D[1] = 1
R = []; b = false; h = 1
for i in range(2*n) :
for k in (1..h) : D[k] += D[k-1]
if not b : R.append(D[h])
else : h += 1
b = not b
return R
(Haskell)
a001764 n = a001764_list !! n
a001764_list = 1 : [a258708 (2 * n) n | n <- [1..]]
(GAP) List([0..25], n->Binomial(3*n, n)/(2*n+1)); # Muniru A Asiru, Oct 31 2018 (Python)
from math import comb
CROSSREFS
Cf. A001762, A001763, A002294 - A002296, A006013, A025174, A063548, A064017, A072247, A072248, A134264, A143603, A258708, A256311, A188687 (binomial transform), A346628 (inverse binomial transform).
a(n) = n*(n+3)/2.
(Formerly M1356 N0522)
+10
259
0, 2, 5, 9, 14, 20, 27, 35, 44, 54, 65, 77, 90, 104, 119, 135, 152, 170, 189, 209, 230, 252, 275, 299, 324, 350, 377, 405, 434, 464, 495, 527, 560, 594, 629, 665, 702, 740, 779, 819, 860, 902, 945, 989, 1034, 1080, 1127, 1175, 1224, 1274, 1325, 1377, 1430, 1484, 1539, 1595, 1652, 1710, 1769
COMMENTS
For n >= 1, a(n) is the maximal number of pieces that can be obtained by cutting an annulus with n cuts. See illustration. - Robert G. Wilson vn(n-3)/2 (n >= 3) is the number of diagonals of an n-gon. - Antreas P. Hatzipolakis (xpolakis(AT)otenet.gr)
n(n-3)/2 (n >= 4) is the degree of the third-smallest irreducible presentation of the symmetric group S_n (cf. James and Kerber, Appendix 1).
a(n) is also the multiplicity of the eigenvalue (-2) of the triangle graph Delta(n+1). (See p. 19 in Biggs.) - Felix Goldberg (felixg(AT)tx.technion.ac.il), Nov 25 2001
For n > 3, a(n-3) = dimension of the traveling salesman polytope T(n). - Benoit Cloitre, Aug 18 2002 Coefficient of x^2 in (1 + x + 2*x^2)^n. - Michael Somos, May 26 2004 a(n) is the number of "prime" n-dimensional polyominoes. A "prime" n-polyomino cannot be formed by connecting any other n-polyominoes except for the n-monomino and the n-monomino is not prime. E.g., for n=1, the 1-monomino is the line of length 1 and the only "prime" 1-polyominoes are the lines of length 2 and 3. This refers to "free" n-dimensional polyominoes, i.e., that can be rotated along any axis. - Bryan Jacobs (bryanjj(AT)gmail.com), Apr 01 2005
Solutions to the quadratic equation q(m, r) = (-3 +- sqrt(9 + 8(m - r))) / 2, where m - r is included in a(n). Let t(m) = the triangular number ( A000217) less than some number k and r = k - t(m). If k is neither prime nor a power of two and m - r is included in A000096, then m - q(m, r) will produce a value that shares a divisor with k. - Andrew S. Plewe, Jun 18 2005 Sum_{k=2..n+1} 4/(k*(k+1)*(k-1)) = ((n+3)*n)/((n+2)*(n+1)). Numerator(Sum_{k=2..n+1} 4/(k*(k+1)*(k-1))) = (n+3)*n/2. - Alexander Adamchuk, Apr 11 2006 Number of rooted trees with n+3 nodes of valence 1, no nodes of valence 2 and exactly two other nodes. I.e., number of planted trees with n+2 leaves and exactly two branch points. - Theo Johnson-Freyd (theojf(AT)berkeley.edu), Jun 10 2007
If X is an n-set and Y a fixed 2-subset of X then a(n-2) is equal to the number of (n-2)-subsets of X intersecting Y. - Milan Janjic, Jul 30 2007 For n >= 1, a(n) is the number of distinct shuffles of the identity permutation on n+1 letters with the identity permutation on 2 letters (12). - Camillia Smith Barnes, Oct 04 2008 If s(n) is a sequence defined as s(1) = x, s(n) = kn + s(n-1) + p for n > 1, then s(n) = a(n-1)*k + (n-1)*p + x. - Gary Detlefs, Mar 04 2010 a(n) = m such that the (m+1)-th triangular number minus the m-th triangular number is the (n+1)-th triangular number: (m+1)(m+2)/2 - m(m+1)/2 = (n+1)(n+2)/2. - Zak Seidov, Jan 22 2012 For n >= 1, number of different values that Sum_{k=1..n} c(k)*k can take where the c(k) are 0 or 1. - Joerg Arndt, Jun 24 2012 On an n X n chessboard (n >= 2), the number of possible checkmate positions in the case of king and rook versus a lone king is 0, 16, 40, 72, 112, 160, 216, 280, 352, ..., which is 8*a(n-2). For a 4 X 4 board the number is 40. The number of positions possible was counted including all mirror images and rotations for all four sides of the board. - Jose Abutal, Nov 19 2013 If k = a(i-1) or k = a(i+1) and n = k + a(i), then C(n, k-1), C(n, k), C(n, k+1) are three consecutive binomial coefficients in arithmetic progression and these are all the solutions. There are no four consecutive binomial coefficients in arithmetic progression. - Michael Somos, Nov 11 2015 a(n-1) is also the number of independent components of a symmetric traceless tensor of rank 2 and dimension n >= 1. - Wolfdieter Lang, Dec 10 2015 Let phi_(D,rho) be the average value of a generic degree D monic polynomial f when evaluated at the roots of the rho-th derivative of f, expressed as a polynomial in the averaged symmetric polynomials in the roots of f. [See the Wojnar et al. link] The "last" term of phi_(D,rho) is a multiple of the product of all roots of f; the coefficient is expressible as a polynomial h_D(N) in N:=D-rho. These polynomials are of the form h_D(N)= ((-1)^D/(D-1)!)*(D-N)*N^chi*g_D(N) where chi = (1 if D is odd, 0 if D is even) and g_D(N) is a monic polynomial of degree (D-2-chi). Then a(n) are the negated coefficients of the next to the highest order term in the polynomials N^chi*g_D(N), starting at D=3. - Gregory Gerard Wojnar, Jul 19 2017 For n >= 2, a(n) is the number of summations required to solve the linear regression of n variables (n-1 independent variables and 1 dependent variable). - Felipe Pedraza-Oropeza, Dec 07 2017 For n >= 2, a(n) is the number of sums required to solve the linear regression of n variables: 5 for two variables (sums of X, Y, X^2, Y^2, X*Y), 9 for 3 variables (sums of X1, X2, Y1, X1^2, X1*X2, X1*Y, X2^2, X2*Y, Y^2), and so on. - Felipe Pedraza-Oropeza, Jan 11 2018 a(n) is the area of a triangle with vertices at (n, n+1), ((n+1)*(n+2)/2, (n+2)*(n+3)/2), ((n+2)^2, (n+3)^2). - J. M. Bergot, Jan 25 2018 Number of terms less than 10^k: 1, 4, 13, 44, 140, 446, 1413, 4471, 14141, 44720, 141420, 447213, ... - Muniru A Asiru, Jan 25 2018 a(n) is also the number of irredundant sets in the (n+1)-path complement graph for n > 2. - Eric W. Weisstein, Apr 11 2018 a(n) is also the largest number k such that the largest Dyck path of the symmetric representation of sigma(k) has exactly n peaks, n >= 1. (Cf. A237593.) - Omar E. Pol, Sep 04 2018 For n > 0, a(n) is the number of facets of associahedra. Cf. A033282 and A126216 and their refinements A111785 and A133437 for related combinatorial and analytic constructs. See p. 40 of Hanson and Sha for a relation to projective spaces and string theory. - Tom Copeland, Jan 03 2021 For n > 0, a(n) is the number of bipartite graphs with 2n or 2n+1 edges, no isolated vertices, and a stable set of cardinality 2. - Christian Barrientos, Jun 13 2022 For n >= 2, a(n-2) is the number of permutations in S_n which are the product of two different transpositions of adjacent points. - Zbigniew Wojciechowski, Mar 31 2023 a(n) represents the optimal stop-number to achieve the highest running score for the Greedy Pig game with an (n-1)-sided die with a loss on a 1. The total at which one should stop is a(s-1), e.g. for a 6-sided die, one should pass the die at 20. See Sparks and Haran. - Nicholas Stefan Georgescu, Jun 09 2024
REFERENCES
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards Applied Math. Series 55, 1964 (and various reprintings), Table 22.7, p. 797.
Norman Biggs, Algebraic Graph Theory, 2nd ed. Cambridge University Press, 1993.
G. James and A. Kerber, The Representation Theory of the Symmetric Group, Encyclopedia of Maths. and its Appls., Vol. 16, Addison-Wesley, 1981, Reading, MA, U.S.A.
D. G. Kendall et al., Shape and Shape Theory, Wiley, 1999; see p. 4.
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
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]. Maria J. Rodriguez, Black holes in all, The KIAS Newsletter, Vol.3, pp.29-34, Korea Institute for Advanced Study, Dec. 2010.
FORMULA
G.f.: A(x) = x*(2-x)/(1-x)^3. a(n) = binomial(n+1, n-1) + binomial(n, n-1).
Connection with triangular numbers: a(n) = A000217(n+1) - 1. a(n) = a(n-1) + n + 1. - Bryan Jacobs (bryanjj(AT)gmail.com), Apr 01 2005
a(n) = 2*t(n) - t(n-1) where t() are the triangular numbers, e.g., a(5) = 2*t(5) - t(4) = 2*15 - 10 = 20. - Jon Perry, Jul 23 2003 a(n) = 3*a(n-1) - 3*a(n-2) + a(n-3). - Paul Curtz, Jan 02 2008 Starting (2, 5, 9, 14, ...) = binomial transform of (2, 3, 1, 0, 0, 0, ...). - Gary W. Adamson, Jul 03 2008 For n >= 0, a(n+2) = b(n+1) - b(n), where b(n) is the sequence A005586. - K.V.Iyer, Apr 27 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>=1, a(n-1)=coeff(charpoly(A,x),x^(n-2)). - Milan Janjic, Jul 08 2010 E.g.f.: F(x) = 1/2*x*exp(x)*(x+4) satisfies the differential equation F''(x) - 2*F'(x) + F(x) = exp(x). - Peter Bala, Mar 14 2012 G.f.: -U(0) where U(k) = 1 - 1/((1-x)^2 - x*(1-x)^4/(x*(1-x)^2 - 1/U(k+1))); (continued fraction, 3-step). - Sergei N. Gladkovskii, Sep 27 2012 a(n-1) = (1/n!)*Sum_{j=0..n} binomial(n,j)*(-1)^(n-j)*j^n*(j-1). - Vladimir Kruchinin, Jun 06 2013 a(n+1) = A127672(4+n, n), n >= 0, where A127672 gives the coefficients of the Chebyshev C polynomials. See the Abramowitz-Stegun reference. - Wolfdieter Lang, Dec 10 2015 Dirichlet g.f.: (zeta(s-2) + 3*zeta(s-1))/2. - Ilya Gutkovskiy, Jun 30 2016 Sum_{n>=1} (-1)^(n+1)/a(n) = 4*log(2)/3 - 5/9. - Amiram Eldar, Jan 10 2021 Product_{n>=1} (1 + 1/a(n)) = 3.
Product_{n>=1} (1 - 1/a(n)) = 3*cos(sqrt(17)*Pi/2)/(4*Pi). (End)
EXAMPLE
G.f. = 2*x + 5*x^2 + 9*x^3 + 14*x^4 + 20*x^5 + 27*x^6 + 35*x^7 + 44*x^8 + 54*x^9 + ...
MATHEMATICA
LinearRecurrence[{3, -3, 1}, {0, 2, 5}, 60] (* Harvey P. Dale, Apr 30 2013 *)
PROG
(PARI) first(n) = Vec(x*(2-x)/(1-x)^3 + O(x^n), -n) \\ Iain Fox, Dec 12 2017 (Haskell)
a000096 n = n * (n + 3) `div` 2
a000096_list = [x | x <- [0..], a023531 x == 1]
(GAP) a := List([0..1000], n -> n*(n+3)/2); # Muniru A Asiru, Jan 25 2018
CROSSREFS
Cf. numbers of the form n*(n*k-k+4)/2 listed in A226488. Similar sequences are listed in A316466.
Triangle of numbers T(n,k) = k!*Stirling2(n,k) read by rows (n >= 1, 1 <= k <= n).
+10
159
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
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 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 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.
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
Xavier Bultel, Jannik Dreier, Matthieu Giraud, Marie Izaute, Timothée Kheyrkhah, Pascal Lafourcade, Dounia Lakhzoum, Vincent Marlin, and Ladislav Motá, Security Analysis and Psychological Study of Authentication Methods with PIN Codes, RCIS 2018 - IEEE 12th International Conference on Research Challenges in Information Science, 2018. Vincent Pilaud and V. Pons, Permutrees, arXiv preprint arXiv:1606.09643 [math.CO], 2016-2017. P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260. P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260. [Annotated scanned copy] Eric Weisstein's World of Mathematics, Matching
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 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) 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. 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 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 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 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)
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
EXAMPLE
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
---------------------------------------------------------------------------
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).
MAPLE
with(combinat): A019538 := (n, k)->k!*stirling2(n, k);
MATHEMATICA
Table[k! StirlingS2[n, k], {n, 9}, {k, n}] // Flatten
PROG
(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 */ (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])
(Sage) def T(n, k): return factorial(k)*stirling_number2(n, k) # Danny Rorabaugh, Oct 10 2015
CROSSREFS
Cf. A000918, A000919, A001117, A001118, A008275, A008277, A008279, A048594, A059117, A059515, A074909, A084938, A089072, A092477, A183109, A218695, A329943. 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. Visible in the 3-D array in A249042.
KEYWORD
nonn, tabl, easy, nice, changed
AUTHOR
N. J. A. Sloane, Manfred Goebel (goebel(AT)informatik.uni-tuebingen.de), Dec 11 1996
Running sum of Pascal's triangle ( A007318), or beheaded Pascal's triangle read by beheaded rows.
+10
59
1, 1, 2, 1, 3, 3, 1, 4, 6, 4, 1, 5, 10, 10, 5, 1, 6, 15, 20, 15, 6, 1, 7, 21, 35, 35, 21, 7, 1, 8, 28, 56, 70, 56, 28, 8, 1, 9, 36, 84, 126, 126, 84, 36, 9, 1, 10, 45, 120, 210, 252, 210, 120, 45, 10, 1, 11, 55, 165, 330, 462, 462, 330, 165, 55, 11
COMMENTS
This sequence counts the "almost triangular" partitions of n. A partition is triangular if it is of the form 0+1+2+...+k. Examples: 3=0+1+2, 6=0+1+2+3. An "almost triangular" partition is a triangular partition with at most 1 added to each of the parts. Examples: 7 = 1+1+2+3 = 0+2+2+3 = 0+1+3+3 = 0+1+2+4. Thus a(7)=4. 8 = 1+2+2+3 = 1+1+3+3 = 1+1+2+4 = 0+2+3+3 = 0+2+2+4 = 0+1+3+4 so a(8)=6. - Moshe Shmuel Newman, Dec 19 2002 The "almost triangular" partitions are the ones cycled by the operation of "Bulgarian solitaire", as defined by Martin Gardner.
Start with A007318 - I (I = Identity matrix), then delete right border of zeros. - Gary W. Adamson, Jun 15 2007 Also the number of increasing acyclic functions from {1..n-k+1} to {1..n+2}. A function f is acyclic if for every subset B of the domain the image of B under f does not equal B. For example, T(3,1)=4 since there are exactly 4 increasing acyclic functions from {1,2,3} to {1,2,3,4,5}: f1={(1,2),(2,3),(3,4)}, f2={(1,2),(2,3),(3,5)}, f3={(1,2),(2,4),(3,5)} and f4={(1,3),(2,4),(4,5)}. - Dennis P. Walsh, Mar 14 2008 Second Bernoulli polynomials are (from A164555 instead of A027641) B2(n,x) = 1; 1/2, 1; 1/6, 1, 1; 0, 1/2, 3/2, 1; -1/30, 0, 1, 2, 1; 0, -1/6, 0, 5/3, 5/2, 1; ... . Then (B2(n,x)/ A002260) = 1; 1/2, 1/2; 1/6, 1/2, 1/3; 0, 1/4, 1/2, 1/4; -1/30, 0, 1/3, 1/2, 1/5; 0, -1/12, 0, 5/12, 1/2, 1/6; ... . See (from Faulhaber 1631) Jacob Bernoulli Summae Potestatum (sum of powers) in A159688. Inverse polynomials are 1; -1, 2; 1, -3, 3; -1, 4, -6, 4; ... = A074909 with negative even diagonals. Reflected A053382/ A053383 = reflected B(n,x) = RB(n,x) = 1; -1/2, 1; 1/6, -1, 1; 0, 1/2, -3/2, 1; ... . A074909 is inverse of RB(n,x)/ A002260 = 1; -1/2, 1/2; 1/6, -1/2, 1/3; 0, 1/4, -1/2, 1/4; ... . - Paul Curtz, Jun 21 2010 A054143 is the fission of the polynomial sequence (p(n,x)) given by p(n,x) = x^n + x^(n-1) + ... + x + 1 by the polynomial sequence ((x+1)^n). See A193842 for the definition of fission. - Clark Kimberling, Aug 07 2011
For a closed-form formula for arbitrary left and right borders of Pascal-like triangles see A228196. - Boris Putievskiy, Aug 19 2013 From A238363, the operator equation d/d(:xD:)f(xD)={exp[d/d(xD)]-1}f(xD) = f(xD+1)-f(xD) follows. Choosing f(x) = x^n and using :xD:^n/n! = binomial(xD,n) and (xD)^n = Bell(n,:xD:), the Bell polynomials of A008277, it follows that the lower triangular matrix [padded A074909] B) = [St2]*[dP]*[St2]^(-1)
C) = [St1]^(-1)*[dP]*[St1],
T(n,k) generated by m-gon expansions in the case of odd m with "vertex to side" version or even m with "vertex to vertes" version. Refer to triangle expansions in A061777 and A101946 (and their companions for m-gons) which are "vertex to vertex" and "vertex to side" versions respectively. The label values at each iteration can be arranged as a triangle. Any m-gon can also be arranged as the same triangle with conditions: (i) m is odd and expansion is "vertex to side" version or (ii) m is even and expansion is "vertex to vertex" version. m*Sum_{i=1..k} T(n,k) gives the total label value at the n-th iteration. See also A247976. Vertex to vertex: A061777, A247618, A247619, A247620. Vertex to side: A101946, A247903, A247904, A247905. - Kival Ngaokrajang Sep 28 2014 With P(n,x) = [(x+1)^(n+1)-x^(n+1)], the row polynomials of this entry, Up(n,x) = P(n,x)/(n+1) form an Appell sequence of polynomials that are the umbral compositional inverses of the Bernoulli polynomials B(n,x), i.e., B[n,Up(.,x)] = x^n = Up[n,B(.,x)] under umbral substitution, e.g., B(.,x)^n = B(n,x).
The e.g.f. for the Bernoulli polynomials is [t/(e^t - 1)] e^(x*t), and for Up(n,x) it's exp[Up(.,x)t] = [(e^t - 1)/t] e^(x*t).
Another g.f. is G(t,x) = log[(1-x*t)/(1-(1+x)*t)] = log[1 + t /(1 + -(1+x)t)] = t/(1-t*Up(.,x)) = Up(0,x)*t + Up(1,x)*t^2 + Up(2,x)*t^3 + ... = t + (1+2x)/2 t^2 + (1+3x+3x^2)/3 t^3 + (1+4x+6x^2+4x^3)/4 t^4 + ... = -log(1-t*P(.,x)), expressed umbrally.
The inverse, Ginv(t,x), in t of the g.f. may be found in A008292 from Copeland's list of formulas (Sep 2014) with a=(1+x) and b=x. This relates these two sets of polynomials to algebraic geometry, e.g., elliptic curves, trigonometric expansions, Chebyshev polynomials, and the combinatorics of permutahedra and their duals. Ginv(t,x) = [e^((1+x)t) - e^(xt)] / [(1+x) * e^((1+x)t) - x * e^(xt)] = [e^(t/2) - e^(-t/2)] / [(1+x)e^(t/2) - x*e^(-t/2)] = (e^t - 1) / [1 + (1+x) (e^t - 1)] = t - (1 + 2 x) t^2/2! + (1 + 6 x + 6 x^2) t^3/3! - (1 + 14 x + 36 x^2 + 24 x^3) t^4/4! + ... = -exp[-Perm(.,x)t], where Perm(n,x) are the reverse face polynomials, or reverse f-vectors, for the permutahedra, i.e., the face polynomials for the duals of the permutahedra. Cf. A090582, A019538, A049019, A133314, A135278. With L(t,x) = t/(1+t*x) with inverse L(t,-x) in t, and Cinv(t) = e^t - 1 with inverse C(t) = log(1 + t). Then Ginv(t,x) = L[Cinv(t),(1+x)] and G(t,x) = C[L[t,-(1+x)]]. Note L is the special linear fractional (Mobius) transformation.
Connections among the combinatorics of the permutahedra, simplices (cf. A135278), and the associahedra can be made through the Lagrange inversion formula (LIF) of A133437 applied to G(t,x) (cf. A111785 and the Schroeder paths A126216 also), and similarly for the LIF A134685 applied to Ginv(t,x) involving the simplicial Whitehouse complex, phylogenetic trees, and other structures. (See also the LIFs A145271 and A133932). (End) R = x - exp[-[B(n+1)/(n+1)]D] = x - exp[zeta(-n)D] is the raising operator for this normalized sequence UP(n,x) = P(n,x) / (n+1), that is, R UP(n,x) = UP(n+1,x), where D = d/dx, zeta(-n) is the value of the Riemann zeta function evaluated at -n, and B(n) is the n-th Bernoulli number, or constant B(n,0) of the Bernoulli polynomials. The raising operator for the Bernoulli polynomials is then x + exp[-[B(n+1)/(n+1)]D]. [Note added Nov 25 2014: exp[zeta(-n)D] is abbreviation of exp(a.D) with (a.)^n = a_n = zeta(-n)]. - Tom Copeland, Nov 17 2014 The diagonals T(n, n-m), for n >= m, give the m-th iterated partial sum of the positive integers; that is A000027(n+1), A000217(n), A000292(n-1), A000332(n+1), A000389(n+1), A000579(n+1), A000580(n+1), A000581(n+1), A000582(n+1), ... . - Wolfdieter Lang, May 21 2015 The transpose gives the numerical coefficients of the Maurer-Cartan form matrix for the general linear group GL(n,1) (cf. Olver, but note that the formula at the bottom of p. 6 has an error--the 12 should be a 15). - Tom Copeland, Nov 05 2015 The left invariant Maurer-Cartan form polynomial on p. 7 of the Olver paper for the group GL^n(1) is essentially a binomial convolution of the row polynomials of this entry with those of A133314, or equivalently the row polynomials generated by the product of the e.g.f. of this entry with that of A133314, with some reindexing. - Tom Copeland, Jul 03 2018 The first column of the inverse matrix is the sequence of Bernoulli numbers, which follows from the umbral definition of the Bernoulli polynomials (B.(0) + x)^n = B_n(x) evaluated at x = 1 and the relation B_n(0) = B_n(1) for n > 1 and -B_1(0) = 1/2 = B_1(1), so the Bernoulli numbers can be calculated using Cramer's rule acting on this entry's matrix and, therefore, from the ratios of volumes of parallelepipeds determined by the columns of this entry's square submatrices. - Tom Copeland, Jul 10 2018 Umbrally composing the row polynomials with B_n(x), the Bernoulli polynomials, gives (B.(x)+1)^(n+1) - (B.(x))^(n+1) = d[x^(n+1)]/dx = (n+1)*x^n, so multiplying this entry as a lower triangular matrix (LTM) by the LTM of the coefficients of the Bernoulli polynomials gives the diagonal matrix of the natural numbers. Then the inverse matrix of this entry has the elements B_(n,k)/(k+1), where B_(n,k) is the coefficient of x^k for B_n(x), and the e.g.f. (1/x) (e^(xt)-1)/(e^t-1). (End)
FORMULA
T(n, k) = Sum_{i=0..n} C(i, n-k) = C(n+1, k).
Row n has g.f. (1+x)^(n+1)-x^(n+1).
E.g.f.: ((1+x)*e^t - x) e^(x*t). The row polynomials p_n(x) satisfy dp_n(x)/dx = (n+1)*p_(n-1)(x). - Tom Copeland, Jul 10 2018 T(n, k) = T(n-1, k-1) + T(n-1, k) for k: 0<k<n, T(n, 0)=1, T(n, n)=n. - Reinhard Zumkeller, Apr 18 2005 T(n,k) = T(n-1,k) + 2*T(n-1,k-1) - T(n-2,k-1) - T(n-2,k-2), T(0,0)=1, T(1,0)=1, T(1,1)=2, T(n,k)=0 if k<0 or if k>n. - Philippe Deléham, Dec 27 2013 G.f. for column k (with leading zeros): x^(k-1)*(1/(1-x)^(k+1)-1), k >= 0. - Wolfdieter Lang, Nov 04 2014 Up(n, x+y) = (Up(.,x)+ y)^n = Sum_{k=0..n} binomial(n,k) Up(k,x)*y^(n-k), where Up(n,x) = ((x+1)^(n+1)-x^(n+1)) / (n+1) = P(n,x)/(n+1) with P(n,x) the n-th row polynomial of this entry. dUp(n,x)/dx = n * Up(n-1,x) and dP(n,x)/dx = (n+1)*P(n-1,x). - Tom Copeland, Nov 14 2014 The o.g.f. GF(x,t) = x / ((1-t*x)*(1-(1+t)x)) = x + (1+2t)*x^2 + (1+3t+3t^2)*x^3 + ... has the inverse GFinv(x,t) = (1+(1+2t)x-sqrt(1+(1+2t)*2x+x^2))/(2t(1+t)x) in x about 0, which generates the row polynomials (mod row signs) of A033282. The reciprocal of the o.g.f., i.e., x/GF(x,t), gives the free cumulants (1, -(1+2t) , t(1+t) , 0, 0, ...) associated with the moments defined by GFinv, and, in fact, these free cumulants generate these moments through the noncrossing partitions of A134264. The associated e.g.f. and relations to Grassmannians are described in A248727, whose polynomials are the basis for an Appell sequence of polynomials that are umbral compositional inverses of the Appell sequence formed from this entry's polynomials (distinct from the one described in the comments above, without the normalizing reciprocal). - Tom Copeland, Jan 07 2015 T(n, k) = (1/k!) * Sum_{i=0..k} Stirling1(k,i)*(n+1)^i, for 0<=k<=n. - Ridouane Oudra, Oct 23 2022
EXAMPLE
T(4,2) = 0+0+1+3+6 = 10 = binomial(5, 2).
Triangle T(n,k) begins:
n\k 0 1 2 3 4 5 6 7 8 9 10 11
0: 1
1: 1 2
2: 1 3 3
3: 1 4 6 4
4: 1 5 10 10 5
5: 1 6 15 20 15 6
6: 1 7 21 35 35 21 7
7: 1 8 28 56 70 56 28 8
8: 1 9 36 84 126 126 84 36 9
9: 1 10 45 120 210 252 210 120 45 10
10: 1 11 55 165 330 462 462 330 165 55 11
11: 1 12 66 220 495 792 924 792 495 220 66 12
.
Can be seen as the square array A(n, k) = binomial(n + k + 1, n) read by descending antidiagonals. A(n, k) is the number of monotone nondecreasing functions f: {1,2,..,k} -> {1,2,..,n}. - Peter Luschny, Aug 25 2019 [0] 1, 1, 1, 1, 1, 1, 1, 1, 1, ... A000012[1] 2, 3, 4, 5, 6, 7, 8, 9, 10, ... A000027[2] 3, 6, 10, 15, 21, 28, 36, 45, 55, ... A000217[3] 4, 10, 20, 35, 56, 84, 120, 165, 220, ... A000292[4] 5, 15, 35, 70, 126, 210, 330, 495, 715, ... A000332[5] 6, 21, 56, 126, 252, 462, 792, 1287, 2002, ... A000389[6] 7, 28, 84, 210, 462, 924, 1716, 3003, 5005, ... A000579[7] 8, 36, 120, 330, 792, 1716, 3432, 6435, 11440, ... A000580[8] 9, 45, 165, 495, 1287, 3003, 6435, 12870, 24310, ... A000581[9] 10, 55, 220, 715, 2002, 5005, 11440, 24310, 48620, ... A000582
MAPLE
if k > n or k < 0 then
0;
else
binomial(n+1, k) ;
end if;
MATHEMATICA
Flatten[Join[{1}, Table[Sum[Binomial[k, m], {k, 0, n}], {n, 0, 12}, {m, 0, n}] ]] (* or *) Flatten[Join[{1}, Table[Binomial[n, m], {n, 12}, {m, n}]]]
PROG
(Haskell)
a074909 n k = a074909_tabl !! n !! k
a074909_row n = a074909_tabl !! n
a074909_tabl = iterate
(\row -> zipWith (+) ([0] ++ row) (row ++ [1])) [1]
(GAP) Flat(List([0..10], n->List([0..n], k->Binomial(n+1, k)))); # Muniru A Asiru, Jul 10 2018 (Magma) /* As triangle */ [[Binomial(n+1, k): k in [0..n]]: n in [0.. 15]]; // Vincenzo Librandi, Jul 22 2018 (Python)
from math import comb, isqrt
def A074909(n): return comb(r:=(m:=isqrt(k:=n+1<<1))+(k>m*(m+1)), n-comb(r, 2)) # Chai Wah Wu, Nov 12 2024
CROSSREFS
The number of acyclic functions is A058127. Cf. A008292, A090582, A019538, A049019, A133314, A135278, A133437, A111785, A126216, A134685, A133932, A248727, A033282, A134264.
EXTENSIONS
I added an initial 1 at the suggestion of Paul Barry, which makes the triangle a little nicer but may mean that some of the formulas will now need adjusting. - N. J. A. Sloane, Feb 11 2003 Formula section edited, checked and corrected by Wolfdieter Lang, Nov 04 2014
a(n) = 2^n*E(n, 1) where E(n, x) are the Euler polynomials.
+10
54
1, 1, 0, -2, 0, 16, 0, -272, 0, 7936, 0, -353792, 0, 22368256, 0, -1903757312, 0, 209865342976, 0, -29088885112832, 0, 4951498053124096, 0, -1015423886506852352, 0, 246921480190207983616, 0, -70251601603943959887872, 0, 23119184187809597841473536, 0
COMMENTS
Previous name was: a(n) = Sum_{k=0..n-1} (-1)^(k)*C(n-1,k)*a(n-1-k)*a(k) for n>0 with a(0)=1.
Factorials have a similar recurrence: f(n) = Sum_{k=0..n-1} C(n-1,k)*f(n-1-k)*f(k), n > 0.
Related to A102573: letting T(q,r) be the coefficient of n^(r+1) in the polynomial 2^(q-n)/n times Sum_{k=0..n} binomial(n,k)*k^q, then A155585(x) = Sum_{k=0..x-1} T(x,k)*(-1)^k. See Mathematica code below. - John M. Campbell, Nov 16 2011 For the difference table and the relation to the Seidel triangle see A239005. - Paul Curtz, Mar 06 2014 Let z(t) = 2/(e^(2t)+1) = 1 + tanh(-t) = e.g.f.(-t) for this sequence = 1 - t + 2*t^3/3! - 16*t^5/5! + ... .
dlog(z(t))/dt = -z(-t), so the raising operators that generate Appell polynomials associated with this sequence, A081733, and its reciprocal, A119468, contain z(-d/dx) = e.g.f.(d/dx) as the differential operator component. dz(t)/dt = z*(z-2), so the assorted relations to a Ricatti equation, the Eulerian numbers A008292, and the Bernoulli numbers in the Rzadkowski link hold. From Michael Somos's formula below (drawing on the Edwards link), y(t,1)=1 and x(t,1) = (1-e^(2t))/(1+e^(2t)), giving z(t) = 1 + x(t,1). Compare this to the formulas in my list in A008292 (Sep 14 2014) with a=1 and b=-1, A) A(t,1,-1) = A(t) = -x(t,1) = (e^(2t)-1)/(1+e^(2t)) = tanh(t) = t + -2*t^3/3! + 16*t^5/5! + -272*t^7/7! + ... = e.g.f.(t) - 1 (see A000182 and A000111) B) Ainv(t) = log((1+t)/(1-t))/2 = tanh^(-1)(t) = t + t^3/3 + t^5/5 + ..., the compositional inverse of A(t)
C) dA/dt = (1-A^2), relating A(t) to a Weierstrass elliptic function
D) ((1-t^2)d/dt)^n t evaluated at t=0, a generator for the sequence A(t)
F) FGL(x,y)= (x+y)/(1+xy) = A(Ainv(x) + Ainv(y)), a related formal group law corresponding to the Lorentz FGL (Lorentz transformation--addition of parallel velocities in special relativity) and the Atiyah-Singer signature and the elliptic curve (1-t^2)*s = t^3 in Tate coordinates according to the Lenart and Zainoulline link and the Buchstaber and Bunkova link (pp. 35-37) in A008292. A133437 maps the reciprocal odd natural numbers through the refined faces of associahedra to a(n).
A145271 links the differential relations to the geometry of flow maps, vector fields, and thereby formal group laws. See Mathworld for links of tanh to other geometries and statistics.
Since the a(n) are related to normalized values of the Bernoulli numbers and the Riemann zeta and Dirichlet eta functions, there are links to Witten's work on volumes of manifolds in two-dimensional quantum gauge theories and the Kervaire-Milnor formula for homotopy groups of hyperspheres (see my link below).
See A101343, A111593 and A059419 for this and the related generator (1 + t^2) d/dt and associated polynomials. (End) With the exception of the first term (1), entries are the alternating sums of the rows of the Eulerian triangle, A008292. - Gregory Gerard Wojnar, Sep 29 2018
FORMULA
Sequence of absolute values is A009006 (e.g.f. 1+tan(x)). O.g.f.: Sum_{n>=0} n! * x^n / Product_{k=1..n} (1 + 2*k*x). - Paul D. Hanna, Jul 20 2011 a(n) = 2^n*E_{n}(1) where E_{n}(x) are the Euler polynomials. - Peter Luschny, Jan 26 2009 a(n) = EL_{n}(-1) where EL_{n}(x) are the Eulerian polynomials. - Peter Luschny, Aug 03 2010 a(n+1) = (4^n-2^n)*B_n(1)/n, where B_{n}(x) are the Bernoulli polynomials (B_n(1) = B_n for n <> 1). - Peter Luschny, Apr 22 2009 G.f.: 1/(1-x+x^2/(1-x+4*x^2/(1-x+9*x^2/(1-x+16*x^2/(1-...))))) (continued fraction). - Paul Barry, Mar 30 2010 G.f.: -log(x/(exp(x)-1))/x = Sum_{n>=0} a(n)*x^n/(2^(n+1)*(2^(n+1)-1)*n!). - Vladimir Kruchinin, Nov 05 2011 E.g.f.: exp(x)/cosh(x) = 2/(1+exp(-2*x)) = 2/(G(0) + 1); G(k) = 1 - 2*x/(2*k + 1 - x*(2*k+1)/(x - (k+1)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 10 2011 E.g.f. is x(t,1) + y(t,1) where x(t,a) and y(t,a) satisfy y(t,a)^2 = (a^2 - x(t,a)^2) / (1 - a^2 * x(t,a)^2) and dx(t,a) / dt = y(t,a) * (1 - a * x(t,a)^2) and are the elliptic functions of Edwards. - Michael Somos, Jan 16 2012 E.g.f.: 1/(1 - x/(1+x/(1 - x/(3+x/(1 - x/(5+x/(1 - x/(7+x/(1 - x/(9+x/(1 +...))))))))))), a continued fraction. - Paul D. Hanna, Feb 11 2012 E.g.f. satisfies: A(x) = Sum_{n>=0} Integral( A(-x) dx )^n / n!. - Paul D. Hanna, Nov 25 2013 a(n) = Sum_{k=1..n} Sum_{j=0..k} (-1)^(j+1)*binomial(n+1,k-j)*j^n for n > 0. - Peter Luschny, Jul 23 2012 Continued fractions:
G.f.: 1 + x/T(0) where T(k) = 1 + (k+1)*(k+2)*x^2/T(k+1).
E.g.f.: exp(x)/cosh(x) = 1 + x/S(0) where S(k) = (2*k+1) + x^2/S(k+1).
E.g.f.: 1 + x/(U(0)+x) where U(k) = 4*k+1 - x/(1 + x/(4*k+3 - x/(1 + x/U(k+1)))).
E.g.f.: 1 + tanh(x) = 4*x/(G(0)+2*x) where G(k) = 1 - (k+1)/(1 - 2*x/(2*x + (k+1)^2/G(k+1)));
G.f.: 1 + x/G(0) where G(k) = 1 + 2*x^2*(2*k+1)^2 - x^4*(2*k+1)*(2*k+2)^2*(2*k+3)/G(k+1) (due to Stieltjes).
E.g.f.: 1 + x/(G(0) + x) where G(k) = 1 - 2*x/(1 + (k+1)/G(k+1)).
G.f.: 2 - 1/Q(0) where Q(k) = 1 + x*(k+1)/( 1 - x*(k+1)/Q(k+1)).
G.f.: 2 - 1/Q(0) where Q(k) = 1 + x*k^2 + x/(1 - x*(k+1)^2/Q(k+1)).
G.f.: 1/Q(0) where Q(k) = 1 - 2*x + x*(k+1)/(1-x*(k+1)/Q(k+1)).
G.f.: 1/Q(0) where Q(k) = 1 - x*(k+1)/(1 + x*(k+1)/Q(k+1)).
E.g.f.: 1 + x*Q(0) where Q(k) = 1 - x^2/( x^2 + (2*k+1)*(2*k+3)/Q(k+1)).
G.f.: 2 - T(0)/(1+x) where T(k) = 1 - x^2*(k+1)^2/(x^2*(k+1)^2 + (1+x)^2/T(k+1)).
E.g.f.: 1/(x - Q(0)) where Q(k) = 4*k^2 - 1 + 2*x + x^2*(2*k-1)*(2*k+3)/Q(k+1). (End)
G.f.: 1 / (1 - b(1)*x / (1 - b(2)*x / (1 - b(3)*x / ... ))) where b = A001057. - Michael Somos, Jan 03 2013 a(n) is the binomial transform of A122045(n). a(n) is the row sum of A081658. For fractional Euler numbers see A238800. a(n) is the Akiyama-Tanigawa transform applied to 1, 0, -1/2, -1/2, -1/4, 0, ... = A046978(n+3)/ A016116(n). (End) a(n) = 2^(2*n+1)*(zeta(-n,1/2) - zeta(-n, 1)), where zeta(a, z) is the generalized Riemann zeta function. - Peter Luschny, Mar 11 2015 a(n) = 2^(n + 1)*(2^(n + 1) - 1)*Bernoulli(n + 1, 1)/(n + 1). (From Bill Gosper, Oct 28 2015) - N. J. A. Sloane, Oct 28 2015 [See the above comment from Peter Luschny, Apr 22 2009.] a(n) = -(n mod 2)*((-1)^n + Sum_{k=1..n-1} (-1)^k*C(n,k)*a(n-k)) for n >= 1. - Peter Luschny, Jun 01 2016 a(n) = (-2)^n*F_{n}(-1/2), where F_{n}(x) is the Fubini polynomial. - Peter Luschny, May 21 2021
EXAMPLE
E.g.f.: 1 + x - 2*x^3/3! + 16*x^5/5! - 272*x^7/7! + 7936*x^9/9! -+ ... = exp(x)/cosh(x).
O.g.f.: 1 + x - 2*x^3 + 16*x^5 - 272*x^7 + 7936*x^9 - 353792*x^11 +- ...
O.g.f.: 1 + x/(1+2*x) + 2!*x^2/((1+2*x)*(1+4*x)) + 3!*x^3/((1+2*x)*(1+4*x)*(1+6*x)) + ...
MAPLE
a := proc(n) option remember; `if`(n::even, 0^n, -(-1)^n - add((-1)^k*binomial(n, k) *a(n-k), k = 1..n-1)) end: # Peter Luschny, Jun 01 2016 # Or via the recurrence of the Fubini polynomials:
F := proc(n) option remember; if n = 0 then return 1 fi;
expand(add(binomial(n, k)*F(n-k)*x, k = 1..n)) end:
a := n -> (-2)^n*subs(x = -1/2, F(n)):
MATHEMATICA
a[m_] := Sum[(-2)^(m - k) k! StirlingS2[m, k], {k, 0, m}] (* Peter Luschny, Apr 29 2009 *) poly[q_] := 2^(q-n)/n*FunctionExpand[Sum[Binomial[n, k]*k^q, {k, 0, n}]]; T[q_, r_] := First[Take[CoefficientList[poly[q], n], {r+1, r+1}]]; Table[Sum[T[x, k]*(-1)^k, {k, 0, x-1}], {x, 1, 16}] (* John M. Campbell, Nov 16 2011 *) f[n_] := (-1)^n 2^(n+1) PolyLog[-n, -1]; f[0] = -f[0]; Array[f, 27, 0] (* Robert G. Wilson v, Jun 28 2012 *)
PROG
(PARI) a(n)=if(n==0, 1, sum(k=0, n-1, (-1)^(k)*binomial(n-1, k)*a(n-1-k)*a(k)))
(PARI) a(n)=local(X=x+x*O(x^n)); n!*polcoeff(exp(X)/cosh(X), n)
(PARI) a(n)=polcoeff(sum(m=0, n, m!*x^m/prod(k=1, m, 1+2*k*x+x*O(x^n))), n) \\ Paul D. Hanna, Jul 20 2011 (PARI) {a(n) = local(A); if( n<0, 0, A = x * O(x^n); n! * polcoeff( 1 + sinh(x + A) / cosh(x + A), n))} /* Michael Somos, Jan 16 2012 */ (PARI) a(n)=local(A=1+x); for(i=1, n, A=sum(k=0, n, intformal(subst(A, x, -x)+x*O(x^n))^k/k!)); n!*polcoeff(A, n)
(Sage)
if n == 0 : return 1
return add(add((-1)^(j+1)*binomial(n+1, k-j)*j^n for j in (0..k)) for k in (1..n))
(Sage)
def A155585_list(n): # Akiyama-Tanigawa algorithm A = [0]*(n+1); R = []
for m in range(n+1) :
d = divmod(m+3, 4)
A[m] = 0 if d[1] == 0 else (-1)^d[0]/2^(m//2)
for j in range(m, 0, -1) :
A[j - 1] = j * (A[j - 1] - A[j])
R.append(A[0])
return R
(Python)
from sympy import bernoulli
def A155585(n): return (((2<<(m:=n+1))-2)*bernoulli(m)<<m-2)//(m>>1) if n&1 else (0 if n else 1) # Chai Wah Wu, Apr 14 2023
Coefficients for expansion of (g(x)d/dx)^n g(x); refined Eulerian numbers for calculating compositional inverse of h(x) = (d/dx)^(-1) 1/g(x); iterated derivatives as infinitesimal generators of flows.
+10
41
1, 1, 1, 1, 1, 4, 1, 1, 11, 4, 7, 1, 1, 26, 34, 32, 15, 11, 1, 1, 57, 180, 122, 34, 192, 76, 15, 26, 16, 1, 1, 120, 768, 423, 496, 1494, 426, 294, 267, 474, 156, 56, 42, 22, 1, 1, 247, 2904, 1389, 4288, 9204, 2127, 496, 5946, 2829, 5142, 1206, 855, 768, 1344, 1038, 288, 56, 98, 64, 29, 1
COMMENTS
For more detail, including connections to Legendre transformations, rooted trees, A139605, A139002 and A074060, see Mathemagical Forests p. 9. For connections to the h-polynomials associated to the refined f-polynomials of permutohedra see my comments in A008292 and A049019. Given analytic functions F(x) and FI(x) such that F(FI(x))=FI(F(x))=x about 0, i.e., they are compositional inverses of each other, then, with g(x) = 1/dFI(x)/dx, a flow function W(s,x) can be defined with the following relations:
W(s,x) = exp(s g(x)d/dx)x = F(s+FI(x)) <flow fct.>,
W(s,0) = F(s) <orbit of the flow>,
W(0,x) = x <identity property>,
dW(0,x)/ds = g(x) = F'[FI(x)] <infinitesimal generator>, implying
dW(0,F(x))/ds = g(F(x)) = F'(x) <autonomous diff. eqn.>, and
W(s,W(r,x)) = F(s+FI(F(r+FI(x)))) = F(s+r+FI(x)) = W(s+r,x) <group property>. (See MF link below.) (End)
dW(s,x)/ds - g(x)dW(s,x)/dx = 0, so (1,-g(x)) are the components of a vector orthogonal to the gradient of W and, therefore, tangent to the contour of W, at (s,x) <tangency property>. - Tom Copeland, Oct 26 2011 Though A139605 contains A145271, the op. of A145271 contains that of A139605 in the sense that exp(s g(x)d/dx) w(x) = w(F(s+FI(x))) = exp((exp(s g(x)d/dx)x)d/du)w(u) evaluated at u=0. This is reflected in the fact that the forest of rooted trees assoc. to (g(x)d/dx)^n, FOR_n, can be generated by removing the single trunk of the planted rooted trees of FOR_(n+1). - Tom Copeland, Nov 29 2011 Related to formal group laws for elliptic curves (see Hoffman). - Tom Copeland, Feb 24 2012 The functional equation W(s,x) = F(s+FI(x)), or a restriction of it, is sometimes called the Abel equation or Abel's functional equation (see Houzel and Wikipedia) and is related to Schröder's functional equation and Koenigs functions for compositional iterates (Alexander, Goryainov and Kudryavtseva). - Tom Copeland, Apr 04 2012 g(W(s,x)) = F'(s + FI(x)) = dW(s,x)/ds = g(x) dW(s,x)/dx, connecting the operators here to presentations of the Koenigs / Königs function and Loewner / Löwner evolution equations of the Contreras et al. papers. - Tom Copeland, Jun 03 2018 The autonomous differential equation above also appears with a change in variable of the form x = log(u) in the renormalization group equation, or Beta function. See Wikipedia, Zinn-Justin equations 2.10 and 3.11, and Krajewski and Martinetti equation 21. - Tom Copeland, Jul 23 2020 A variant of these partition polynomials appears on p. 83 of Petreolle et al. with the indeterminates e_n there related to those given in the examples below by e_n = n!*(n'). The coefficients are interpreted as enumerating certain types of trees. See also A190015. - Tom Copeland, Oct 03 2022
REFERENCES
D. S. Alexander, A History of Complex Dynamics: From Schröder to Fatou to Julia, Friedrich Vieweg & Sohn, 1994.
T. Mansour and M. Schork, Commutation Relations, Normal Ordering, and Stirling Numbers, Chapman and Hall/CRC, 2015.
LINKS
C. Houzel, The Work of Niels Henrik Abel, The Legacy of Niels Henrik Abel-The Abel Bicentennial, Oslo 2002 (Editors O. Laudal and R Piene), Springer-Verlag (2004), pp. 24-25.
FORMULA
Let R = g(x)d/dx; then
R^0 g(x) = 1 (0')^1
R^1 g(x) = 1 (0')^1 (1')^1
R^2 g(x) = 1 (0')^1 (1')^2 + 1 (0')^2 (2')^1
R^3 g(x) = 1 (0')^1 (1')^3 + 4 (0')^2 (1')^1 (2')^1 + 1 (0')^3 (3')^1
R^4 g(x) = 1 (0')^1 (1')^4 + 11 (0')^2 (1')^2 (2')^1 + 4 (0')^3 (2')^2 + 7 (0')^3 (1')^1 (3')^1 + 1 (0')^4 (4')^1
R^5 g(x) = 1 (0') (1')^5 + 26 (0')^2 (1')^3 (2') + (0')^3 [34 (1') (2')^2 + 32 (1')^2 (3')] + (0')^4 [ 15 (2') (3') + 11 (1') (4')] + (0')^5 (5')
R^6 g(x) = 1 (0') (1')^6 + 57 (0')^2 (1')^4 (2') + (0')^3 [180 (1')^2 (2')^2 + 122 (1')^3 (3')] + (0')^4 [ 34 (2')^3 + 192 (1') (2') (3') + 76 (1')^2 (4')] + (0')^5 [15 (3')^2 + 26 (2') (4') + 16 (1') (5')] + (0')^6 (6')
where (j')^k = ((d/dx)^j g(x))^k. And R^(n-1) g(x) evaluated at x=0 is the n-th Taylor series coefficient of the compositional inverse of h(x) = (d/dx)^(-1) 1/g(x), with the integral from 0 to x.
The partitions are in reverse order to those in Abramowitz and Stegun p. 831. Summing over coefficients with like powers of (0') gives A008292. Confer A190015 for another way to compute numbers for the array for each partition. - Tom Copeland, Oct 17 2014 Equivalent matrix computation: Multiply the n-th diagonal (with n=0 the main diagonal) of the lower triangular Pascal matrix by g_n = (d/dx)^n g(x) to obtain the matrix VP with VP(n,k) = binomial(n,k) g_(n-k). Then R^n g(x) = (1, 0, 0, 0, ...) [VP * S]^n (g_0, g_1, g_2, ...)^T, where S is the shift matrix A129185, representing differentiation in the divided powers basis x^n/n!. - Tom Copeland, Feb 10 2016 (An evaluation removed by author on Jul 19 2016. Cf. A139605 and A134685.) Also, R^n g(x) = (1, 0, 0, 0, ...) [VP * S]^(n+1) (0, 1, 0, ...)^T in agreement with A139605. - Tom Copeland, Jul 21 2016 A recursion relation for computing each partition polynomial of this entry from the lower order polynomials and the coefficients of the cycle index polynomials of A036039 is presented in the blog entry "Formal group laws and binomial Sheffer sequences". - Tom Copeland, Feb 06 2018 A formula for computing the polynomials of each row of this matrix is presented as T_{n,1} on p. 196 of the Ihara reference in A139605. - Tom Copeland, Mar 25 2020 Indeterminate substitutions as illustrated in A356145 lead to [E] = [L][P] = [P][E]^(-1)[P] = [P][RT] and [E]^(-1) = [P][L] = [P][E][P] = [RT][P], where [E] contains the refined Eulerian partition polynomials of this entry; [E]^(-1), A356145, the inverse set to [E]; [P], the permutahedra polynomials of A133314; [L], the classic Lagrange inversion polynomials of A134685; and [RT], the reciprocal tangent polynomials of A356144. Since [L]^2 = [P]^2 = [RT]^2 = [I], the substitutional identity, [L] = [E][P] = [P][E]^(-1) = [RT][P], [RT] = [E]^(-1)[P] = [P][L][P] = [P][E], and [P] = [L][E] = [E][RT] = [E]^(-1)[L] = [RT][E]^(-1). - Tom Copeland, Oct 05 2022
EXAMPLE
Let h(x) = log((1+a*x)/(1+b*x))/(a-b); then, g(x) = 1/(dh(x)/dx) = (1+ax)(1+bx), so (0')=1, (1')=a+b, (2')=2ab, evaluated at x=0, and higher order derivatives of g(x) vanish. Therefore, evaluated at x=0,
R^0 g(x) = 1
R^1 g(x) = a+b
R^2 g(x) = (a+b)^2 + 2ab = a^2 + 4 ab + b^2
R^3 g(x) = (a+b)^3 + 4*(a+b)*2ab = a^3 + 11 a^2*b + 11 ab^2 + b^3
R^4 g(x) = (a+b)^4 + 11*(a+b)^2*2ab + 4*(2ab)^2
= a^4 + 26 a^3*b + 66 a^2*b^2 + 26 ab^3 + b^4,
etc., and these bivariate Eulerian polynomials ( A008292) are the first few coefficients of h^(-1)(x) = (e^(ax) - e^(bx))/(a*e^(bx) - b*e^(ax)), the inverse of h(x). (End) Triangle starts:
1;
1;
1, 1;
1, 4, 1;
1, 11, 4, 7, 1;
1, 26, 34, 32, 15, 11, 1;
1, 57, 180, 122, 34, 192, 76, 15, 26, 16, 1;
1, 120, 768, 423, 496, 1494, 426, 294, 267, 474, 156, 56, 42, 22, 1;
1, 247, 2904, 1389, 4288, 9204, 2127, 496, 5946, 2829, 5142, 1206, 855, 768, 1344, 1038, 288, 56, 98, 64, 29, 1;
MAPLE
with(LinearAlgebra): with(ListTools):
A145271_row := proc(n) local b, M, V, U, G, R, T;
if n < 2 then return 1 fi;
b := (n, k) -> `if`(k=1 or k>n+1, 0, binomial(n-1, k-2)*g[n-k+1]);
M := n -> Matrix(n, b):
V := n -> Vector[row]([1, seq(0, i=2..n)]):
U := n -> VectorMatrixMultiply(V(n), M(n)^(n-1)):
G := n -> Vector([seq(g[i], i=0..n-1)]);
R := n -> VectorMatrixMultiply(U(n), G(n)):
T := Reverse([op(sort(expand(R(n+1))))]);
seq(subs({seq(g[i]=1, i=0..n)}, T[j]), j=1..nops(T)) end:
CROSSREFS
Cf. ( A133437, A086810, A181289) = (LIF, reduced LIF, associated g(x)), where LIF is a Lagrange inversion formula. Similarly for ( A134264, A001263, A119900), ( A134685, A134991, A019538), ( A133932, A111999, A007318).
EXTENSIONS
R^5 and R^6 formulas and terms a(19)-a(29) added by Tom Copeland, Jul 11 2016
Triangle read by rows: T(n, k) is the number of diagonal dissections of a convex n-gon into k+1 regions.
+10
36
1, 1, 2, 1, 5, 5, 1, 9, 21, 14, 1, 14, 56, 84, 42, 1, 20, 120, 300, 330, 132, 1, 27, 225, 825, 1485, 1287, 429, 1, 35, 385, 1925, 5005, 7007, 5005, 1430, 1, 44, 616, 4004, 14014, 28028, 32032, 19448, 4862, 1, 54, 936, 7644, 34398, 91728, 148512, 143208, 75582, 16796
COMMENTS
T(n+3, k) is also the number of compatible k-sets of cluster variables in Fomin and Zelevinsky's cluster algebra of finite type A_n. Take a row of this triangle regarded as a polynomial in x and rewrite as a polynomial in y := x+1. The coefficients of the polynomial in y give a row of the triangle of Narayana numbers A001263. For example, x^2 + 5*x + 5 = y^2 + 3*y + 1. - Paul Boddington, Mar 07 2003 Number of standard Young tableaux of shape (k+1,k+1,1^(n-k-3)), where 1^(n-k-3) denotes a sequence of n-k-3 1's (see the Stanley reference).
Number of k-dimensional 'faces' of the n-dimensional associahedron (see Simion, p. 168). - Mitch Harris, Jan 16 2007 For relation to Lagrange inversion or series reversion and the geometry of associahedra or Stasheff polytopes (and other combinatorial objects) see A133437. - Tom Copeland, Sep 29 2008 Row generating polynomials 1/(n+1)*Jacobi_P(n,1,1,2*x+1). Row n of this triangle is the f-vector of the simplicial complex dual to an associahedron of type A_n [Fomin & Reading, p. 60]. See A001263 for the corresponding array of h-vectors for associahedra of type A_n. See A063007 and A080721 for the f-vectors for associahedra of type B and type D respectively. - Peter Bala, Oct 28 2008 f-vectors of secondary polytopes for Grobner bases for optimization and integer programming (see De Loera et al. and Thomas). - Tom Copeland, Oct 11 2011 From Devadoss and O'Rourke's book: The Fulton-MacPherson compactification of the configuration space of n free particles on a line segment with a fixed particle at each end is the n-Dim Stasheff associahedron whose refined f-vector is given in A133437 which reduces to A033282. - Tom Copeland, Nov 29 2011 The general results on the convolution of the refined partition polynomials of A133437, 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 The signed triangle t(n, k) =(-1)^k* T(n+2, k-1), n >= 1, k = 1..n, seems to be obtainable from the partition array A111785 (in Abramowitz-Stegun order) by adding the entries corresponding to the partitions of n with the number of parts k. E.g., triangle t, row n=4: -1, (6+3) = 9, -21, 14. - Wolfdieter Lang, Mar 17 2017 The preceding conjecture by Lang is true. It is implicit in Copeland's 2011 comments in A086810 on the relations among a gf and its compositional inverse for that entry and inversion through A133437 (a differently normalized version of A111785), whose integer partitions are the same as those for A134685. (An inversion pair in Copeland's 2008 formulas below can also be used to prove the conjecture.) In addition, it follows from the relation between the inversion formula of A111785/ A133437 and the enumeration of distinct faces of associahedra. See the MathOverflow link concernimg Loday and the Aguiar and Ardila reference in A133437 for proofs of the relations between the partition polynomials for inversion and enumeration of the distinct faces of the A_n associahedra, or Stasheff polytopes. - Tom Copeland, Dec 21 2017 The rows seem to give (up to sign) the coefficients in the expansion of the integer-valued polynomial (x+1)*(x+2)^2*(x+3)^2*...*(x+n)^2*(x+n+1)/(n!*(n+1)!) in the basis made of the binomial(x+i,i). - F. Chapoton, Oct 07 2022 Chapoton's observation above is correct: the precise expansion is (x+1)*(x+2)^2*(x+3)^2*...*(x+n)^2*(x+n+1)/ (n!*(n+1)!) = Sum_{k = 0..n-1} (-1)^k*T(n+2,n-k-1)*binomial(x+2*n-k,2*n-k), as can be verified using the WZ algorithm. For example, n = 4 gives (x+1)*(x+2)^2*(x+3)^2*(x+4)^2*(x+5)/(4!*5!) = 14*binomial(x+8,8) - 21*binomial(x+7,7) + 9*binomial(x+6,6) - binomial(x+5,5). - Peter Bala, Jun 24 2023
REFERENCES
S. Devadoss and J. O'Rourke, Discrete and Computational Geometry, Princeton Univ. Press, 2011 (See p. 241.)
Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994. Exercise 7.50, pages 379, 573.
T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Section 5.8.
LINKS
A. Cayley, On the partitions of a polygon, Proc. London Math. Soc., 22 (1891), 237-262 = Collected Mathematical Papers. Vols. 1-13, Cambridge Univ. Press, London, 1889-1897, Vol. 13, pp. 93ff. (See p. 239.) G. Kreweras, Sur les hiérarchies de segments, Cahiers du Bureau Universitaire de Recherche Opérationnelle, Institut de Statistique, Université de Paris, #20 (1973). (Annotated scanned copy) Vincent Pilaud and V. Pons, Permutrees, arXiv:1606.09643 [math.CO], 2016-2017.
FORMULA
G.f. G = G(t, z) satisfies (1+t)*G^2 - z*(1-z-2*t*z)*G + t*z^4 = 0.
T(n, k) = binomial(n-3, k)*binomial(n+k-1, k)/(k+1) for n >= 3, 0 <= k <= n-3.
Two g.f.s (f1 and f2) for A033282 and their inverses (x1 and x2) can be derived from the Drake and Barry references. 1. a: f1(x,t) = y = {1 - (2t+1) x - sqrt[1 - (2t+1) 2x + x^2]}/[2x (t+1)] = t x + (t + 2 t^2) x^2 + (t + 5 t^2 + 5 t^3) x^3 + ...
b: x1 = y/[t + (2t+1)y + (t+1)y^2] = y {1/[t/(t+1) + y] - 1/(1+y)} = (y/t) - (1+2t)(y/t)^2 + (1+ 3t + 3t^2)(y/t)^3 +...
2. a: f2(x,t) = y = {1 - x - sqrt[(1-x)^2 - 4xt]}/[2(t+1)] = (t/(t+1)) x + t x^2 + (t + 2 t^2) x^3 + (t + 5 t^2 + 5 t^3) x^4 + ...
b: x2 = y(t+1) [1- y(t+1)]/[t + y(t+1)] = (t+1) (y/t) - (t+1)^3 (y/t)^2 + (t+1)^4 (y/t)^3 + ...
c: y/x2(y,t) = [t/(t+1) + y] / [1- y(t+1)] = t/(t+1) + (1+t) y + (1+t)^2 y^2 + (1+t)^3 y^3 + ...
x2(y,t) can be used along with the Lagrange inversion for an o.g.f. ( A133437) to generate A033282 and show that A133437 is a refinement of A033282, i.e., a refinement of the f-polynomials of the associahedra, the Stasheff polytopes. y/x2(y,t) can be used along with the indirect Lagrange inversion ( A134264) to generate A033282 and show that A134264 is a refinement of A001263, i.e., a refinement of the h-polynomials of the associahedra. f1[x,t](t+1) gives a generator for A088617. f1[xt,1/t](t+1) gives a generator for A060693, with inverse y/[1 + t + (2+t) y + y^2]. f1[x(t-1),1/(t-1)]t gives a generator for A001263, with inverse y/[t + (1+t) y + y^2]. The unsigned coefficients of x1(y t,t) are A074909, reverse rows of A135278. (End) G.f.: 1/(1-x*y-(x+x*y)/(1-x*y/(1-(x+x*y)/(1-x*y/(1-(x+x*y)/(1-x*y/(1-.... (continued fraction). - Paul Barry, Feb 06 2009 Let h(t) = (1-t)^2/(1+(u-1)*(1-t)^2) = 1/(u + 2*t + 3*t^2 + 4*t^3 + ...), then a signed (n-1)-th row polynomial of A033282 is given by u^(2n-1)*(1/n!)*((h(t)*d/dt)^n) t, evaluated at t=0, with initial n=2. The power series expansion of h(t) is related to A181289 (cf. A086810). - Tom Copeland, Sep 06 2011 With a different offset, the row polynomials equal 1/(1 + x)*Integral_{0..x} R(n,t) dt, where R(n,t) = Sum_{k = 0..n} binomial(n,k)*binomial(n+k,k)*t^k are the row polynomials of A063007. - Peter Bala, Jun 23 2016 n-th row polynomial = ( LegendreP(n-1,2*x + 1) - LegendreP(n-3,2*x + 1) )/((4*n - 6)*x*(x + 1)), n >= 3. - Peter Bala, Feb 22 2017 n*T(n+1, k) = (4n-6)*T(n, k-1) + (2n-3)*T(n, k) - (n-3)*T(n-1, k) for n >= 4. - Fang Lixing, May 07 2019
EXAMPLE
The triangle T(n, k) begins:
n\k 0 1 2 3 4 5 6 7 8 9
3: 1
4: 1 2
5: 1 5 5
6: 1 9 21 14
7: 1 14 56 84 42
8: 1 20 120 300 330 132
9: 1 27 225 825 1485 1287 429
10: 1 35 385 1925 5005 7007 5005 1430
11: 1 44 616 4004 14014 28028 32032 19448 4862
12: 1 54 936 7644 34398 91728 148512 143208 75582 16796
MAPLE
T:=(n, k)->binomial(n-3, k)*binomial(n+k-1, k)/(k+1): seq(seq(T(n, k), k=0..n-3), n=3..12); # Muniru A Asiru, Nov 24 2018
MATHEMATICA
t[n_, k_] = Binomial[n-3, k]*Binomial[n+k-1, k]/(k+1);
PROG
(PARI) Q=(1+z-(1-(4*w+2+O(w^20))*z+z^2+O(z^20))^(1/2))/(2*(1+w)*z); for(n=3, 12, for(m=1, n-2, print1(polcoef(polcoef(Q, n-2, z), m, w), ", "))) \\ Hugo Pfoertner, Nov 19 2018 (PARI) for(n=3, 12, for(k=0, n-3, print1(binomial(n-3, k)*binomial(n+k-1, k)/(k+1), ", "))) \\ G. C. Greubel, Nov 19 2018 (Magma) [[Binomial(n-3, k)*Binomial(n+k-1, k)/(k+1): k in [0..(n-3)]]: n in [3..12]]; // G. C. Greubel, Nov 19 2018 (Sage) [[ binomial(n-3, k)*binomial(n+k-1, k)/(k+1) for k in (0..(n-3))] for n in (3..12)] # G. C. Greubel, Nov 19 2018
CROSSREFS
Cf. diagonals: A000012, A000096, A033275, A033276, A033277, A033278, A033279; A000108, A002054, A002055, A002056, A007160, A033280, A033281; row sums: A001003 (Schroeder numbers, first term omitted). See A086810 for another version. Cf. A019538 'faces' of the permutohedron. Cf. A063007 (f-vectors type B associahedra), A080721 (f-vectors type D associahedra), A126216 (mirror image). Cf. A248727 for a relation to f-polynomials of simplices. Cf. A111785 (contracted partition array, unsigned; see a comment above).
EXTENSIONS
Missing factor of 2 for expansions of f1 and f2 added by Tom Copeland, Apr 12 2009
Coefficients T(j, k) of a partition transform for Lagrange compositional inversion of a function or generating series in terms of the coefficients of the power series for its reciprocal. Enumeration of noncrossing partitions and primitive parking functions. T(n,k) for n >= 1 and 1 <= k <= A000041(n-1), an irregular triangle read by rows.
+10
36
1, 1, 1, 1, 1, 3, 1, 1, 4, 2, 6, 1, 1, 5, 5, 10, 10, 10, 1, 1, 6, 6, 3, 15, 30, 5, 20, 30, 15, 1, 1, 7, 7, 7, 21, 42, 21, 21, 35, 105, 35, 35, 70, 21, 1, 1, 8, 8, 8, 4, 28, 56, 56, 28, 28, 56, 168, 84, 168, 14, 70, 280, 140, 56, 140, 28, 1, 1, 9, 9, 9, 9, 36, 72
COMMENTS
Coefficients are listed in Abramowitz and Stegun order ( A036036). Given an invertible function f(t) analytic about t=0 (or a formal power series) with f(0)=0 and Df(0) not equal to 0, form h(t) = t / f(t) and let h_n denote the coefficient of t^n in h(t).
Lagrange inversion gives the compositional inverse about t=0 as g(t) = Sum_{j>=1} ( t^j * (1/j) * Sum_{permutations s with s(1) + s(2) + ... + s(j) = j - 1} h_s(1) * h_s(2) * ... * h_s(j) ) = t * T(1,1) * h_0 + Sum_{j>=2} ( t^j * Sum_{k=1..(# of partitions for j-1)} T(j,k) * H(j-1,k ; h_0,h_1,...) ), where H(j-1,k ; h_0,h_1,...) is the k-th partition for h_1 through h_(j-1) corresponding to n=j-1 on page 831 of Abramowitz and Stegun (ordered as in A&S) with (h_0)^(j-m)=(h_0)^(n+1-m) appended to each partition subsumed under n and m of A&S.
Denoting h_n by (n') for brevity, to 8th order in t,
g(t) = t * (0')
+ t^2 * [ (0') (1') ]
+ t^3 * [ (0')^2 (2') + (0') (1')^2 ]
+ t^4 * [ (0')^3 (3') + 3 (0')^2 (1') (2') + (0') (1')^3 ]
+ t^5 * [ (0')^4 (4') + 4 (0')^3 (1') (3') + 2 (0')^3 (2')^2 + 6 (0')^2 (1')^2 (2') + (0') (1')^4 ]
+ t^6 * [ (0')^5 (5') + 5 (0')^4 (1') (4') + 5 (0')^4 (2') (3') + 10 (0')^3 (1')^2 (3') + 10 (0')^3 (1') (2')^2 + 10 (0')^2 (1')^3 (2') + (0') (1')^5 ]
+ t^7 * [ (0')^6 (6') + 6 (0')^5 (1') (5') + 6 (0')^5 (2') (4') + 3 (0')^5 (3')^2 + 15 (0')^4 (1')^2 (4') + 30 (0')^4 (1') (2') (3') + 5 (0')^4 (2')^3 + 20 (0')^3 (1')^3 (3') + 30 (0')^3 (1')^2 (2')^2 + 15 (0')^2 (1')^4 (2') + (0') (1')^6]
+ t^8 * [ (0')^7 (7') + 7 (0')^6 (1') (6') + 7 (0')^6 (2') (5') + 7 (0')^6 (3') (4') + 21 (0')^5 (1')^2* (5') + 42 (0')^5 (1') (2') (4') + 21 (0')^5 (1') (3')^2 + 21 (0')^5 (2')^2 (3') + 35 (0')^4 (1')^3 (4') + 105 (0)^4 (1')^2 (2') (3') + 35 (0')^4 (1') (2')^3 + 35 (0')^3 (1')^4 (3') + 70 (0')^3 (1')^3 (2')^2 + 21 (0')^2 (1')^5 (2') + (0') (1')^7 ]
+ ..., where from the formula section, for example, T(8,1',2',...,7') = 7! / ((8 - (1'+ 2' + ... + 7'))! * 1'! * 2'! * ... * 7'!) are the coefficients of the integer partitions (1')^1' (2')^2' ... (7')^7' in the t^8 term.
A125181 is an extended, reordered version of the above sequence, omitting the leading 1, with alternate interpretations.
If the coefficients of partitions with the same exponent for h_0 are summed within rows, A001263 is obtained, omitting the leading 1. From identification of the elements of the inversion with those on page 25 of the Ardila et al. link, the coefficients of the irregular table enumerate non-crossing partitions on [n]. - Tom Copeland, Oct 13 2014 Operating with d/d(1') = d/d(h_1) on the n-th partition polynomial Prt(n;h_0,h_1,..,h_n) in square brackets above associated with t^(n+1) generates n * Prt(n-1;h_0,h_1,..,h_(n-1)); therefore, the polynomials are an Appell sequence of polynomials in the indeterminate h_1 when h_0=1 (a special type of Sheffer sequence).
Consequently, umbrally, [Prt(.;1,x,h_2,..) + y]^n = Prt(n;1,x+y,h_2,..); that is, Sum_{k=0..n} binomial(n,k) * Prt(k;1,x,h_2,..) * y^(n-k) = Prt(n;1,x+y,h_2,..).
Or, e^(x*z) * exp[Prt(.;1,0,h_2,..) * z] = exp[Prt(.;1,x,h_2,..) * z]. Then with x = h_1 = -(1/2) * d^2[f(t)]/dt^2 evaluated at t=0, the formal Laplace transform from z to 1/t of this expression generates g(t), the comp. inverse of f(t), when h_0 = 1 = df(t)/dt eval. at t=0.
I.e., t / (1 - t*(x + Prt(.;1,0,h_2,..))) = t / (1 - t*Prt(.;1,x,h_2,..)) = g(t), interpreted umbrally, when h_0 = 1.
(End)
Connections to and between arrays associated to the Catalan ( A000108 and A007317), Riordan ( A005043), Fibonacci ( A000045), and Fine ( A000957) numbers and to lattice paths, e.g., the Motzkin, Dyck, and Łukasiewicz, can be made explicit by considering the inverse in x of the o.g.f. of A104597(x,-t), i.e., f(x) = P(Cinv(x),t-1) = Cinv(x) / (1 + (t-1)*Cinv(x)) = x*(1-x) / (1 + (t-1)*x*(1-x)) = (x-x^2) / (1 + (t-1)*(x-x^2)), where Cinv(x) = x*(1-x) is the inverse of C(x) = (1 - sqrt(1-4*x)) / 2, a shifted o.g.f. for the Catalan numbers, and P(x,t) = x / (1+t*x) with inverse Pinv(x,t) = -P(-x,t) = x / (1-t*x). Then h(x,t) = x / f(x,t) = x * (1+(t-1)Cinv(x)) / Cinv(x) = 1 + t*x + x^2 + x^3 + ..., i.e., h_1=t and all other coefficients are 1, so the inverse of f(x,t) in x, which is explicitly in closed form finv(x,t) = C(Pinv(x,t-1)), is given by A091867, whose coefficients are sums of the refined Narayana numbers above obtained by setting h_1=(1')=t in the partition polynomials and all other coefficients to one. The group generators C(x) and P(x,t) and their inverses allow associations to be easily made between these classic number arrays. - Tom Copeland, Nov 03 2014 Inverting in x with t a parameter, let F(x;t,n) = x - t*x^(n+1). Then h(x) = x / F(x;t,n) = 1 / (1-t*x^n) = 1 + t*x^n + t^2*x^(2n) + t^3*x^(3n) + ..., so h_k vanishes unless k = m*n with m an integer in which case h_k = t^m.
Finv(x;t,n) = Sum_{j>=0} {binomial((n+1)*j,j) / (n*j + 1)} * t^j * x^(n*j + 1), which gives the Catalan numbers for n=1, and the Fuss-Catalan sequences for n>1 (see A001764, n=2). [Added braces to disambiguate the formula. - N. J. A. Sloane, Oct 20 2015] This relation reveals properties of the partitions and sums of the coefficients of the array. For n=1, h_k = t^k for all k, implying that the row sums are the Catalan numbers. For n = 2, h_k for k odd vanishes, implying that there are no blocks with only even-indexed h_k on the even-numbered rows and that only the blocks containing only even-sized bins contribute to the odd-row sums giving the Fuss-Catalan numbers for n=2. And so on, for n > 2.
These relations are reflected in any combinatorial structures enumerated by this array and the partitions, such as the noncrossing partitions depicted for a five-element set (a pentagon) in Wikipedia.
(End)
An Appell sequence possesses an umbral inverse sequence (cf. A249548). The partition polynomials here, Prt(n;1,h_1,...), are an Appell sequence in the indeterminate h_1=u, so have an e.g.f. exp[Prt(.;1,u,h_2...)*t] = e^(u*t) * exp[Prt(.;1,0,h2,...)*t] with umbral inverses with an e.g.f e^(-u*t) / exp[Prt(.;1,0,h2,...)*t]. This makes contact with the formalism of A133314 (cf. also A049019 and A019538) and the signed, refined face partition polynomials of the permutahedra (or their duals), which determine the reciprocal of exp[Prt(.,0,u,h2...)*t] (cf. A249548) or exp[Prt(.;1,u,h2,...)*t], forming connections among the combinatorics of permutahedra and the noncrossing partitions, Dyck paths and trees (cf. A125181), and many other important structures isomorphic to the partitions of this entry, as well as to formal cumulants through A127671 and algebraic structures of Lie algebras. (Cf. relationship of permutahedra with the Eulerians A008292.) (End)
The n-th row multiplied by n gives the number of terms in the homogeneous symmetric monomials generated by [x(1) + x(2) + ... + x(n+1)]^n under the umbral mapping x(m)^j = h_j, for any m. E.g., [a + b + c]^2 = [a^2 + b^2 + c^2] + 2 * [a*b + a*c + b*c] is mapped to [3 * h_2] + 2 * [3 * h_1^2], and 3 * A134264(3) = 3 *(1,1)= (3,3) the number of summands in the two homogeneous polynomials in the square brackets. For n=3, [a + b + c + d]^3 = [a^3 + b^3 + ...] + 3 [a*b^2 + a*c^2 + ...] + 6 [a*b*c + a*c*d + ...] maps to [4 * h_3] + 3 [12 * h_1 * h_2] + 6 [4 * (h_1)^3], and the number of terms in the brackets is given by 4 * A134264(4) = 4 * (1,3,1) = (4,12,4). The further reduced expression is 4 h_3 + 36 h_1 h_2 + 24 (h_1)^3 = A248120(4) with h_0 = 1. The general relation is n * A134264(n) = A248120(n) / A036038(n-1) where the arithmetic is performed on the coefficients of matching partitions in each row n. Abramowitz and Stegun give combinatorial interpretations of A036038 and relations to other number arrays. This can also be related to repeated umbral composition of Appell sequences and topology with the Bernoulli numbers playing a special role. See the Todd class link.
(End)
These partition polynomials are dubbed the Voiculescu polynomials on page 11 of the He and Jejjala link. - Tom Copeland, Jan 16 2015 See page 5 of the Josuat-Verges et al. reference for a refinement of these partition polynomials into a noncommutative version composed of nondecreasing parking functions. - Tom Copeland, Oct 05 2016 (Per Copeland's Oct 13 2014 comment.) The number of non-crossing set partitions whose block sizes are the parts of the n-th integer partition, where the ordering of integer partitions is first by total, then by length, then lexicographically by the reversed sequence of parts. - Gus Wiseman, Feb 15 2019 With h_0 = 1 and the other h_n replaced by suitably signed partition polynomials of A263633, the refined face partition polynomials for the associahedra of normalized A133437 with a shift in indices are obtained (cf. In the Realm of Shadows). - Tom Copeland, Sep 09 2019 Number of primitive parking functions associated to each partition of n. See Lemma 3.8 on p. 28 of Rattan. - Tom Copeland, Sep 10 2019 With h_n = n + 1, the d_k ( A006013) of Table 2, p. 18, of Jong et al. are obtained, counting the n-point correlation functions in a quantum field theory. - Tom Copeland, Dec 25 2019 By inspection of the diagrams on Robert Dickau's website, one can see the relationship between the monomials of this entry and the connectivity of the line segments of the noncrossing partitions. - Tom Copeland, Dec 25 2019 Speicher has examples of the first four inversion partition polynomials on pp. 22 and 23 with his k_n equivalent to h_n = (n') here with h_0 = 1. Identifying z = t, C(z) = t/f(t) = h(t), and M(z) = f^(-1)(t)/t, then statement (3), on p. 43, of Theorem 3.26, C(z M(z)) = M(z), is equivalent to substituting f^(-1)(t) for t in t/f(t), and statement (4), M(z/C(z)) = C(z), to substituting f(t) for t in f^(-1)(t)/t. - Tom Copeland, Dec 08 2021 Given a Laurent series of the form f(z) = 1/z + h_1 + h_2 z + h_3 z^2 + ..., the compositional inverse is f^(-1)(z) = 1/z + Prt(1;1,h_1)/z^2 + Prt(2;1,h_1,h_2)/z^3 + ... = 1/z + h_1/z^2 + (h_1^2 + h_2)/z^3 + (h_1^3 + 3 h_1 h_2 + h_3)/z^4 + (h_1^4 + 6 h_1^2 h_2 + 4 h_1 h_3 + 2 h_2^2 + h_4)/z^5 + ... for which the polynomials in the numerators are the partition polynomials of this entry. For example, this formula applied to the q-expansion of Klein's j-invariant / function with coefficients A000521, related to monstrous moonshine, gives the compositional inverse with the coefficients A091406 (see He and Jejjala). - Tom Copeland, Dec 18 2021 The partition polynomials of A350499 'invert' the polynomials of this entry giving the indeterminates h_n. A multinomial formula for the coefficients of the partition polynomials of this entry, equivalent to the multinomial formula presented in the first four sentences of the formula section below, is presented in the MathOverflow question referenced in A350499. - Tom Copeland, Feb 19 2022
REFERENCES
A. Nica and R. Speicher (editors), Lectures on the Combinatorics of Free Probability, London Mathematical Society Lecture Note Series: 335, Cambridge University Press, 2006 (see in particular, Eqn. 9.14 on p. 141, enumerating noncrossing partitions).
LINKS
M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy]. T. Banica, S. Belinschi, M. Capitaine, and B. Collins, Free Bessel laws, arXiv preprint arXiv:0710.5931 [math.PR], 2008.
FORMULA
For j>1, there are P(j,m;a...) = j! / [ (j-m)! (a_1)! (a_2)! ... (a_(j-1))! ] permutations of h_0 through h_(j-1) in which h_0 is repeated (j-m) times; h_1, repeated a_1 times; and so on with a_1 + a_2 + ... + a_(j-1) = m.
If, in addition, a_1 + 2 * a_2 + ... + (j-1) * a_(j-1) = j-1, then each distinct combination of these arrangements is correlated with a partition of j-1.
T(j,k) is [ P(j,m;a...) / j ] for the k-th partition of j-1 as described in the comments.
For example from g(t) above, T(5,4) = (5! / ((5-3)! * 2!)) / 5 = 6 for the 4th partition under n=5-1=4 with m=3 parts in A&S.
Let W(x) = 1/(df(x)/dx)= 1/{d[x/h(x)]/dx}
= [(h_0)-1+:1/(1-h.*x):]^2 / {(h_0)-:[h.x/(1-h.x)]^2:}
= [(h_0)+(h_1)x+(h_2)x^2+...]^2 / [(h_0)-(h_2)x^2-2(h_3)x^3-3(h_4)x^4-...], where :" ": denotes umbral evaluation of the expression within the colons and h. is an umbral coefficient.
Then for the partition polynomials of A134264, Poly[n;h_0,...,h_(n-1)]=(1/n!)(W(x)*d/dx)^n x, evaluated at x=0, and the compositional inverse of f(t) is g(t) = exp(t*W(x)*d/dx) x, evaluated at x=0. Also, dg(t)/dt = W(g(t)), and g(t) gives A001263 with (h_0)=u and (h_n)=1 for n>0 and A000108 with u=1. (End)
With exp(x* PS(.,t)) = exp(t*g(x)) = exp(x*W(y)d/dy) exp(t*y) eval. at y=0, the raising (creation) and lowering (annihilation) operators defined by R PS(n,t) = PS(n+1,t) and L PS(n,t) = n*PS(n-1,t) are
R = t*W(d/dt) = t*((h_0) + (h_1)d/dt + (h_2)(d/dt)^2 + ...)^2 / ((h_0) - (h_2)(d/dt)^2 - 2(h_3)(d/dt)^3 - 3(h_4)(d/dt)^4 + ...), and
L = (d/dt)/h(d/dt) = (d/dt) 1/((h_0) + (h_1)*d/dt + (h_2)*(d/dt)^2 + ...)
Then P(n,t) = (t^n/n!) dPS(n,z)/dz eval. at z=0 are the row polynomials of A134264. (Cf. A139605, A145271, and link therein to Mathemagical Forests for relation to planted trees on p. 13.) (End)
Using the formalism of A263634, the raising operator for the partition polynomials of this array with h_0 = 1 begins as R = h_1 + h_2 D + h_3 D^2/2! + (h_4 - h_2^2) D^3/3! + (h_5 - 5 h_2 h_3) D^4/4! + (h_6 + 5 h_2^3 - 7 h_3^2 - 9 h_2 h_4) D^5/5! + (h_7 - 14 h_2 h_5 + 56 h_2^2 h_3) D^6/6! + ... with D = d/d(h_1). - Tom Copeland, Sep 09 2016 Let h(x) = x/f^{-1}(x) = 1/[1-(c_2*x+c_3*x^2+...)], with c_n all greater than zero. Then h_n are all greater than zero and h_0 = 1. Determine P_n(t) from exp[t*f^{-1}(x)] = exp[x*P.(t)] with f^{-1}(x) = x/h(x) expressed in terms of the h_n (cf. A133314 and A263633). Then P_n(b.) = 0 gives a recursion relation for the inversion polynomials of this entry a_n = b_n/n! in terms of the lower order inversion polynomials and P_j(b.)P_k(b.) = P_j(t)P_k(t)|_{t^n = b_n} = d_{j,k} >= 0 is the coefficient of x^j/j!*y^k/k! in the Taylor series expansion of the formal group law FGL(x,y) = f[f^{-1}(x)+f^{-1}(y)]. - Tom Copeland, Feb 09 2018 A raising operator for the partition polynomials with h_0 = 1 regarded as a Sheffer Appell sequence in h_1 is described in A249548. - Tom Copeland, Jul 03 2018
EXAMPLE
1) With f(t) = t / (t-1), then h(t) = -(1-t), giving h_0 = -1, h_1 = 1 and h_n = 0 for n>1. Then g(t) = -t - t^2 - t^3 - ... = t / (t-1).
2) With f(t) = t*(1-t), then h(t) = 1 / (1-t), giving h_n = 1 for all n. The compositional inverse of this f(t) is g(t) = t*A(t) where A(t) is the o.g.f. for the Catalan numbers; therefore the sum over k of T(j,k), i.e., the row sum, is the Catalan number A000108(j-1). 3) With f(t) = (e^(-a*t)-1) / (-a), h(t) = Sum_{n>=0} Bernoulli(n) * (-a*t)^n / n! and g(t) = log(1-a*t) / (-a) = Sum_{n>=1} a^(n-1) * t^n / n. Therefore with h_n = Bernoulli(n) * (-a)^n / n!, Sum_{permutations s with s(1)+s(2)+...+s(j)=j-1} h_s(1) * h_s(2) * ... * h_s(j) = j * Sum_{k=1..(# of partitions for j-1)} T(j,k) * H(j-1,k ; h_0,h_1,...) = a^(j-1). Note, in turn, Sum_{a=1..m} a^(j-1) = (Bernoulli(j,m+1) - Bernoulli(j)) / j for the Bernoulli polynomials and numbers, for j>1.
4) With f(t,x) = t / (x-1+1/(1-t)), then h(t,x) = x-1+1/(1-t), giving (h_0)=x and (h_n)=1 for n>1. Then g(t,x) = (1-(1-x)*t-sqrt(1-2*(1+x)*t+((x-1)*t)^2)) / 2, a shifted o.g.f. in t for the Narayana polynomials in x of A001263. 5) With h(t)= o.g.f. of A075834, but with A075834(1)=2 rather than 1, which is the o.g.f. for the number of connected positroids on [n] (cf. Ardila et al., p. 25), g(t) is the o.g.f. for A000522, which is the o.g.f. for the number of positroids on [n]. (Added Oct 13 2014 by author.) 6) With f(t,x) = x / ((1-t*x)*(1-(1+t)*x)), an o.g.f. for A074909, the reverse face polynomials of the simplices, h(t,x) = (1-t*x) * (1-(1+t)*x) with h_0=1, h_1=-(1+2*t), and h_2=t*(1+t), giving as the inverse in x about 0 the o.g.f. (1+(1+2*t)*x-sqrt(1+(1+2*t)*2*x+x^2)) / (2*t*(1+t)*x) for signed A033282, the reverse face polynomials of the Stasheff polytopes, or associahedra. Cf. A248727. (Added Jan 21 2015 by author.) 7) With f(x,t) = x / ((1+x)*(1+t*x)), an o.g.f. for the polynomials (-1)^n * (1 + t + ... + t^n), h(t,x) = (1+x) * (1+t*x) with h_0=1, h_1=(1+t), and h_2=t, giving as the inverse in x about 0 the o.g.f. (1-(1+t)*x-sqrt(1-2*(1+t)*x+((t-1)*x)^2)) / (2*x*t) for the Narayana polynomials A001263. Cf. A046802. (Added Jan 24 2015 by author.) Triangle begins:
1
1
1 1
1 3 1
1 4 2 6 1
1 5 5 10 10 10 1
1 6 6 3 15 30 5 20 30 15 1
1 7 7 7 21 42 21 21 35 105 35 35 70 21 1
Row 5 counts the following non-crossing set partitions:
{{1234}} {{1}{234}} {{12}{34}} {{1}{2}{34}} {{1}{2}{3}{4}}
{{123}{4}} {{14}{23}} {{1}{23}{4}}
{{124}{3}} {{12}{3}{4}}
{{134}{2}} {{1}{24}{3}}
{{13}{2}{4}}
{{14}{2}{3}}
(End)
MATHEMATICA
Table[Binomial[Total[y], Length[y]-1]*(Length[y]-1)!/Product[Count[y, i]!, {i, Max@@y}], {n, 7}, {y, Sort[Sort/@IntegerPartitions[n]]}] (* Gus Wiseman, Feb 15 2019 *)
PROG
(PARI)
C(v)={my(n=vecsum(v), S=Set(v)); n!/((n-#v+1)!*prod(i=1, #S, my(x=S[i]); (#select(y->y==x, v))!))}
row(n)=[C(Vec(p)) | p<-partitions(n-1)]
CROSSREFS
( A001263, A119900) = (reduced array, associated g(x)). See A145271 for meaning and other examples of reduced and associated. Cf. A119900 (e.g.f. for reduced W(x) with (h_0)=t and (h_n)=1 for n>0). Cf. A248927 and A248120, "scaled" versions of this Lagrange inversion. Cf. A000045, A000108, A000957, A001764, A000522, A005043, A007317, A033282, A036038, A046802, A074909, A075834, A104597, A145271, A248727. Cf. A249548 for use of Appell properties to generate the polynomials.
EXTENSIONS
Added explicit t^6, t^7, and t^8 polynomials and extended initial table to include the coefficients of t^8. - Tom Copeland, Sep 14 2016
Search completed in 0.075 seconds
|