cp's OEIS Frontend

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

Showing 1-8 of 8 results.

A001263 Triangle of Narayana numbers T(n,k) = C(n-1,k-1)*C(n,k-1)/k with 1 <= k <= n, read by rows. Also called the Catalan triangle.

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 6, 6, 1, 1, 10, 20, 10, 1, 1, 15, 50, 50, 15, 1, 1, 21, 105, 175, 105, 21, 1, 1, 28, 196, 490, 490, 196, 28, 1, 1, 36, 336, 1176, 1764, 1176, 336, 36, 1, 1, 45, 540, 2520, 5292, 5292, 2520, 540, 45, 1, 1, 55, 825, 4950, 13860, 19404, 13860, 4950, 825
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

Number of antichains (or order ideals) in the poset 2*(k-1)*(n-k) or plane partitions with rows <= k-1, columns <= n-k and entries <= 2. - Mitch Harris, Jul 15 2000
T(n,k) is the number of Dyck n-paths with exactly k peaks. a(n,k) = number of pairs (P,Q) of lattice paths from (0,0) to (k,n+1-k), each consisting of unit steps East or North, such that P lies strictly above Q except at the endpoints. - David Callan, Mar 23 2004
Number of permutations of [n] which avoid-132 and have k-1 descents. - Mike Zabrocki, Aug 26 2004
T(n,k) is the number of paths through n panes of glass, entering and leaving from one side, of length 2n with k reflections (where traversing one pane of glass is the unit length). - Mitch Harris, Jul 06 2006
Antidiagonal sums given by A004148 (without first term).
T(n,k) is the number of full binary trees with n internal nodes and k-1 jumps. In the preorder traversal of a full binary tree, any transition from a node at a deeper level to a node on a strictly higher level is called a jump. - Emeric Deutsch, Jan 18 2007
From Gary W. Adamson, Oct 22 2007: (Start)
The n-th row can be generated by the following operation using an ascending row of (n-1) triangular terms, (A) and a descending row, (B); e.g., row 6:
A: 1....3....6....10....15
B: 15...10....6.....3.....1
C: 1...15...50....50....15....1 = row 6.
Leftmost column of A,B -> first two terms of C; then followed by the operation B*C/A of current column = next term of row C, (e.g., 10*15/3 = 50). Continuing with the operation, we get row 6: (1, 15, 50, 50, 15, 1). (End)
The previous comment can be upgraded to: The ConvOffsStoT transform of the triangular series; and by rows, row 6 is the ConvOffs transform of (1, 3, 6, 10, 15). Refer to triangle A117401 as another example of the ConvOffsStoT transform, and OEIS under Maple Transforms. - Gary W. Adamson, Jul 09 2012
For a connection to Lagrange inversion, see A134264. - Tom Copeland, Aug 15 2008
T(n,k) is also the number of order-decreasing and order-preserving mappings (of an n-element set) of height k (height of a mapping is the cardinal of its image set). - Abdullahi Umar, Aug 21 2008
Row n of this triangle is the h-vector of the simplicial complex dual to an associahedron of type A_n [Fomin & Reading, p.60]. See A033282 for the corresponding array of f-vectors for associahedra of type A_n. See A008459 and A145903 for the h-vectors for associahedra of type B and type D respectively. The Hilbert transform of this triangle (see A145905 for the definition of this transform) is A145904. - Peter Bala, Oct 27 2008
T(n,k) is also the number of noncrossing set partitions of [n] into k blocks. Given a partition P of the set {1,2,...,n}, a crossing in P are four integers [a, b, c, d] with 1 <= a < b < c < d <= n for which a, c are together in a block, and b, d are together in a different block. A noncrossing partition is a partition with no crossings. - Peter Luschny, Apr 29 2011
Noncrossing set partitions are also called genus 0 partitions. In terms of genus-dependent Stirling numbers of the second kind S2(n,k,g) that count partitions of genus g of an n-set into k nonempty subsets, one has T(n,k) = S2(n,k,0). - Robert Coquereaux, Feb 15 2024
Diagonals of A089732 are rows of A001263. - Tom Copeland, May 14 2012
From Peter Bala, Aug 07 2013: (Start)
Let E(y) = Sum_{n >= 0} y^n/(n!*(n+1)!) = 1/sqrt(y)*BesselI(1,2*sqrt(y)). Then this triangle is the generalized Riordan array (E(y), y) with respect to the sequence n!*(n+1)! as defined in Wang and Wang.
Generating function E(y)*E(x*y) = 1 + (1 + x)*y/(1!*2!) + (1 + 3*x + x^2)*y^2/(2!*3!) + (1 + 6*x + 6*x^2 + x^3)*y^3/(3!*4!) + .... Cf. A105278 with a generating function exp(y)*E(x*y).
The n-th power of this array has a generating function E(y)^n*E(x*y). In particular, the matrix inverse A103364 has a generating function E(x*y)/E(y). (End)
T(n,k) is the number of nonintersecting n arches above the x axis, starting and ending on vertices 1 to 2n, with k being the number of arches starting on an odd vertice and ending on a higher even vertice. Example: T(3,2)=3 [16,25,34] [14,23,56] [12,36,45]. - Roger Ford, Jun 14 2014
Fomin and Reading on p. 31 state that the rows of the Narayana matrix are the h-vectors of the associahedra as well as its dual. - Tom Copeland, Jun 27 2017
The row polynomials P(n, x) = Sum_{k=1..n} T(n, k)*x^(k-1), together with P(0, x) = 1, multiplied by (n+1) are the numerator polynomials of the o.g.f.s of the diagonal sequences of the triangle A103371: G(n, x) = (n+1)*P(n, x)/(1 - x)^{2*n+1}, for n >= 0. This is proved with Lagrange's theorem applied to the Riordan triangle A135278 = (1/(1 - x)^2, x/(1 - x)). See an example below. - Wolfdieter Lang, Jul 31 2017
T(n,k) is the number of Dyck paths of semilength n with k-1 uu-blocks (pairs of consecutive up-steps). - Alexander Burstein, Jun 22 2020
In case you were searching for Narayama numbers, the correct spelling is Narayana. - N. J. A. Sloane, Nov 11 2020
Named after the Canadian mathematician Tadepalli Venkata Narayana (1930-1987). They were also called "Runyon numbers" after John P. Runyon (1922-2013) of Bell Telephone Laboratories, who used them in a study of a telephone traffic system. - Amiram Eldar, Apr 15 2021 The Narayana numbers were first studied by Percy Alexander MacMahon (see reference, Article 495) as pointed out by Bóna and Sagan (see link). - Peter Luschny, Apr 28 2022
From Andrea Arlette España, Nov 14 2022: (Start)
T(n,k) is the degree distribution of the paths towards synchronization in the transition diagram associated with the Laplacian system over the complete graph K_n, corresponding to ordered initial conditions x_1 < x_2 < ... < x_n.
T(n,k) for n=2N+1 and k=N+1 is the number of states in the transition diagram associated with the Laplacian system over the complete bipartite graph K_{N,N}, corresponding to ordered (x_1 < x_2 < ... < x_N and x_{N+1} < x_{N+2} < ... < x_{2N}) and balanced (Sum_{i=1..N} x_i/N = Sum_{i=N+1..2N} x_i/N) initial conditions. (End)
From Gus Wiseman, Jan 23 2023: (Start)
Also the number of unlabeled ordered rooted trees with n nodes and k leaves. See the link by Marko Riedel. For example, row n = 5 counts the following trees:
((((o)))) (((o))o) ((o)oo) (oooo)
(((o)o)) ((oo)o)
(((oo))) ((ooo))
((o)(o)) (o(o)o)
((o(o))) (o(oo))
(o((o))) (oo(o))
The unordered version is A055277. Leaves in standard ordered trees are counted by A358371. (End)

Examples

			The initial rows of the triangle are:
  [1] 1
  [2] 1,  1
  [3] 1,  3,   1
  [4] 1,  6,   6,    1
  [5] 1, 10,  20,   10,    1
  [6] 1, 15,  50,   50,   15,    1
  [7] 1, 21, 105,  175,  105,   21,   1
  [8] 1, 28, 196,  490,  490,  196,  28,  1
  [9] 1, 36, 336, 1176, 1764, 1176, 336, 36, 1;
  ...
For all n, 12...n (1 block) and 1|2|3|...|n (n blocks) are noncrossing set partitions.
Example of umbral representation:
  A007318(5,k)=[1,5/1,5*4/(2*1),...,1]=(1,5,10,10,5,1),
  so A001263(5,k)={1,b(5)/b(1),b(5)*b(4)/[b(2)*b(1)],...,1}
  = [1,30/2,30*20/(6*2),...,1]=(1,15,50,50,15,1).
  First = last term = b.(5!)/[b.(0!)*b.(5!)]= 1. - _Tom Copeland_, Sep 21 2011
Row polynomials and diagonal sequences of A103371: n = 4,  P(4, x) = 1 + 6*x + 6*x^2 + x^3, and the o.g.f. of fifth diagonal is G(4, x) = 5* P(4, x)/(1 - x)^9, namely [5, 75, 525, ...]. See a comment above. - _Wolfdieter Lang_, Jul 31 2017

References

  • Berman and Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), pp. 103-124.
  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 196.
  • P. A. MacMahon, Combinatory Analysis, Vols. 1 and 2, Cambridge University Press, 1915, 1916; reprinted by Chelsea, 1960, Sect. 495.
  • T. V. Narayana, Lattice Path Combinatorics with Statistical Applications. Univ. Toronto Press, 1979, pp. 100-101.
  • A. Nkwanta, Lattice paths and RNA secondary structures, in African Americans in Mathematics, ed. N. Dean, Amer. Math. Soc., 1997, pp. 137-147.
  • T. K. Petersen, Eulerian Numbers, Birkhäuser, 2015, Chapter 2.
  • J. Riordan, Combinatorial Identities, Wiley, 1968, p. 17.
  • R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 6.36(a) and (b).

Links

Crossrefs

Other versions are in A090181 and A131198. - Philippe Deléham, Nov 18 2007
Cf. variants: A181143, A181144. - Paul D. Hanna, Oct 13 2010
Row sums give A000108 (Catalan numbers), n>0.
Columns give A000217, A002415, A006542, A006857, A108679. A084938.
Cf. A000372, A002083, A056932, A056939, A056940, A056941, A065329, A073345.
A145596, A145597, A145598, A145599. - Peter Bala, Oct 22 2008
A008459 (h-vectors type B associahedra), A033282 (f-vectors type A associahedra), A145903 (h-vectors type D associahedra), A145904 (Hilbert transform). - Peter Bala, Oct 27 2008
Cf. A016098 and A189232 for numbers of crossing set partitions.
Cf. A243752.
Cf. A089231, A103371, A135278.
Cf. A002378, A007318, A010790, A089732, A105278, A119900, A132710, A134264.
Triangles of generalized binomial coefficients (n,k)_m (or generalized Pascal triangles) for m = 1,...,12: A007318 (Pascal), A001263, A056939, A056940, A056941, A142465, A142467, A142468, A174109, A342889, A342890, A342891.
Cf. A000081, A005043, A032027, A055277, A358371.

Programs

  • GAP
    Flat(List([1..11],n->List([1..n],k->Binomial(n-1,k-1)*Binomial(n,k-1)/k))); # Muniru A Asiru, Jul 12 2018
  • Haskell
    a001263 n k = a001263_tabl !! (n-1) !! (k-1)
a001263_row n = a001263_tabl !! (n-1)
a001263_tabl = zipWith dt a007318_tabl (tail a007318_tabl) where
   dt us vs = zipWith (-) (zipWith (*) us (tail vs))
                          (zipWith (*) (tail us ++ [0]) (init vs))
-- Reinhard Zumkeller, Oct 10 2013
  • Magma
    /* triangle */ [[Binomial(n-1,k-1)*Binomial(n,k-1)/k : k in [1..n]]: n in [1.. 15]]; // Vincenzo Librandi, Oct 19 2014
  • Maple
    A001263 := (n,k)->binomial(n-1,k-1)*binomial(n,k-1)/k;
a:=proc(n,k) option remember; local i; if k=1 or k=n then 1 else add(binomial(n+i-1, 2*k-2)*a(k-1,i),i=1..k-1); fi; end:
# Alternatively, as a (0,0)-based triangle:
R := n -> simplify(hypergeom([-n, -n-1], [2], x)): Trow := n -> seq(coeff(R(n,x),x,j), j=0..n): seq(Trow(n), n=0..9); # Peter Luschny, Mar 19 2018
  • Mathematica
    T[n_, k_] := If[k==0, 0, Binomial[n-1, k-1] Binomial[n, k-1] / k];
Flatten[Table[Binomial[n-1,k-1] Binomial[n,k-1]/k,{n,15},{k,n}]] (* Harvey P. Dale, Feb 29 2012 *)
TRow[n_] := CoefficientList[Hypergeometric2F1[1 - n, -n, 2, x], x];
Table[TRow[n], {n, 1, 11}] // Flatten (* Peter Luschny, Mar 19 2018 *)
aot[n_]:=If[n==1,{{}},Join@@Table[Tuples[aot/@c],{c,Join@@Permutations/@IntegerPartitions[n-1]}]];
Table[Length[Select[aot[n],Length[Position[#,{}]]==k&]],{n,2,9},{k,1,n-1}] (* Gus Wiseman, Jan 23 2023 *)
T[1, 1] := 1; T[n_, k_]/;1<=k<=n := T[n, k] = (2n/k-1) T[n-1,k-1] + T[n-1, k]; T[n_, k_] := 0; Flatten@Table[T[n, k], {n, 1, 11}, {k, 1, n}] (* Oliver Seipel, Dec 31 2024 *)
  • PARI
    {a(n, k) = if(k==0, 0, binomial(n-1, k-1) * binomial(n, k-1) / k)};
  • PARI
    {T(n,k)=polcoeff(polcoeff(exp(sum(m=1,n,sum(j=0,m,binomial(m,j)^2*y^j)*x^m/m) +O(x^(n+1))),n,x),k,y)} \\ Paul D. Hanna, Oct 13 2010
  • Sage
    @CachedFunction
def T(n, k):
    if k == n or k == 1: return 1
    if k <= 0 or k > n: return 0
    return binomial(n, 2) * (T(n-1, k)/((n-k)*(n-k+1)) + T(n-1, k-1)/(k*(k-1)))
for n in (1..9): print([T(n, k) for k in (1..n)])  # Peter Luschny, Oct 28 2014

Formula

a(n, k) = C(n-1, k-1)*C(n, k-1)/k for k!=0; a(n, 0)=0.
Triangle equals [0, 1, 0, 1, 0, 1, ...] DELTA [1, 0, 1, 0, 1, 0, 1, 0, ...] where DELTA is Deléham's operator defined in A084938.
0Mike Zabrocki, Aug 26 2004
T(n, k) = C(n, k)*C(n-1, k-1) - C(n, k-1)*C(n-1, k) (determinant of a 2 X 2 subarray of Pascal's triangle A007318). - Gerald McGarvey, Feb 24 2005
T(n, k) = binomial(n-1, k-1)^2 - binomial(n-1, k)*binomial(n-1, k-2). - David Callan, Nov 02 2005
a(n,k) = C(n,2) (a(n-1,k)/((n-k)*(n-k+1)) + a(n-1,k-1)/(k*(k-1))) a(n,k) = C(n,k)*C(n,k-1)/n. - Mitch Harris, Jul 06 2006
Central column = A000891, (2n)!*(2n+1)! / (n!*(n+1)!)^2. - Zerinvary Lajos, Oct 29 2006
G.f.: (1-x*(1+y)-sqrt((1-x*(1+y))^2-4*y*x^2))/(2*x) = Sum_{n>0, k>0} a(n, k)*x^n*y^k.
From Peter Bala, Oct 22 2008: (Start)
Relation with Jacobi polynomials of parameter (1,1):
Row n+1 generating polynomial equals 1/(n+1)*x*(1-x)^n*Jacobi_P(n,1,1,(1+x)/(1-x)). It follows that the zeros of the Narayana polynomials are all real and nonpositive, as noted above. O.g.f for column k+2: 1/(k+1) * y^(k+2)/(1-y)^(k+3) * Jacobi_P(k,1,1,(1+y)/(1-y)). Cf. A008459.
T(n+1,k) is the number of walks of n unit steps on the square lattice (i.e., each step in the direction either up (U), down (D), right (R) or left (L)) starting from the origin and finishing at lattice points on the x axis and which remain in the upper half-plane y >= 0 [Guy]. For example, T(4,3) = 6 counts the six walks RRL, LRR, RLR, UDL, URD and RUD, from the origin to the lattice point (1,0), each of 3 steps. Compare with tables A145596 - A145599.
Define a functional I on formal power series of the form f(x) = 1 + ax + bx^2 + ... by the following iterative process. Define inductively f^(1)(x) = f(x) and f^(n+1)(x) = f(x*f^(n)(x)) for n >= 1. Then set I(f(x)) = lim_{n -> infinity} f^(n)(x) in the x-adic topology on the ring of formal power series; the operator I may also be defined by I(f(x)) := 1/x*series reversion of x/f(x).
The o.g.f. for this array is I(1 + t*x + t*x^2 + t*x^3 + ...) = 1 + t*x + (t + t^2)*x^2 + (t + 3*t^2 + t^3)*x^3 + ... = 1/(1 - x*t/(1 - x/(1 - x*t/(1 - x/(1 - ...))))) (as a continued fraction). Cf. A108767, A132081 and A141618. (End)
G.f.: 1/(1-x-xy-x^2y/(1-x-xy-x^2y/(1-... (continued fraction). - Paul Barry, Sep 28 2010
E.g.f.: exp((1+y)x)*Bessel_I(1,2*sqrt(y)x)/(sqrt(y)*x). - Paul Barry, Sep 28 2010
G.f.: A(x,y) = exp( Sum_{n>=1} [Sum_{k=0..n} C(n,k)^2*y^k] * x^n/n ). - Paul D. Hanna, Oct 13 2010
With F(x,t) = (1-(1+t)*x-sqrt(1-2*(1+t)*x+((t-1)*x)^2))/(2*x) an o.g.f. in x for the Narayana polynomials in t, G(x,t) = x/(t+(1+t)*x+x^2) is the compositional inverse in x. Consequently, with H(x,t) = 1/ (dG(x,t)/dx) = (t+(1+t)*x+x^2)^2 / (t-x^2), the n-th Narayana polynomial in t is given by (1/n!)*((H(x,t)*D_x)^n)x evaluated at x=0, i.e., F(x,t) = exp(x*H(u,t)*D_u)u, evaluated at u = 0. Also, dF(x,t)/dx = H(F(x,t),t). - Tom Copeland, Sep 04 2011
With offset 0, A001263 = Sum_{j>=0} A132710^j / A010790(j), a normalized Bessel fct. May be represented as the Pascal matrix A007318, n!/[(n-k)!*k!], umbralized with b(n)=A002378(n) for n>0 and b(0)=1: A001263(n,k)= b.(n!)/{b.[(n-k)!]*b.(k!)} where b.(n!) = b(n)*b(n-1)...*b(0), a generalized factorial (see example). - Tom Copeland, Sep 21 2011
With F(x,t) = {1-(1-t)*x-sqrt[1-2*(1+t)*x+[(t-1)*x]^2]}/2 a shifted o.g.f. in x for the Narayana polynomials in t, G(x,t)= x/[t-1+1/(1-x)] is the compositional inverse in x. Therefore, with H(x,t)=1/(dG(x,t)/dx)=[t-1+1/(1-x)]^2/{t-[x/(1-x)]^2}, (see A119900), the (n-1)-th Narayana polynomial in t is given by (1/n!)*((H(x,t)*d/dx)^n)x evaluated at x=0, i.e., F(x,t) = exp(x*H(u,t)*d/du) u, evaluated at u = 0. Also, dF(x,t)/dx = H(F(x,t),t). - Tom Copeland, Sep 30 2011
T(n,k) = binomial(n-1,k-1)*binomial(n+1,k)-binomial(n,k-1)*binomial(n,k). - Philippe Deléham, Nov 05 2011
A166360(n-k) = T(n,k) mod 2. - Reinhard Zumkeller, Oct 10 2013
Damped sum of a column, in leading order: lim_{d->0} d^(2k-1) Sum_{N>=k} T(N,k)(1-d)^N=Catalan(n). - Joachim Wuttke, Sep 11 2014
Multiplying the n-th column by n! generates the revert of the unsigned Lah numbers, A089231. - Tom Copeland, Jan 07 2016
Row polynomials: (x - 1)^(n+1)*(P(n+1,(1 + x)/(x - 1)) - P(n-1,(1 + x)/(x - 1)))/((4*n + 2)), n = 1,2,... and where P(n,x) denotes the n-th Legendre polynomial. - Peter Bala, Mar 03 2017
The coefficients of the row polynomials R(n, x) = hypergeom([-n,-n-1], [2], x) generate the triangle based in (0,0). - Peter Luschny, Mar 19 2018
Multiplying the n-th diagonal by n!, with the main diagonal n=1, generates the Lah matrix A105278. With G equal to the infinitesimal generator of A132710, the Narayana triangle equals Sum_{n >= 0} G^n/((n+1)!*n!) = (sqrt(G))^(-1) * I_1(2*sqrt(G)), where G^0 is the identity matrix and I_1(x) is the modified Bessel function of the first kind of order 1. (cf. Sep 21 2011 formula also.) - Tom Copeland, Sep 23 2020
T(n,k) = T(n,k-1)*C(n-k+2,2)/C(k,2). - Yuchun Ji, Dec 21 2020
From Sergii Voloshyn, Nov 25 2024: (Start)
G.f.: F(x,y) = (1-x*(1+y)-sqrt((1-x*(1+y))^2-4*y*x^2))/(2*x) is the solution of the differential equation x^3 * d^2(x*F(x,y))/dx^2 = y * d^2(x*F(x,y))/dy^2.
Let E be the operator x*D*D, where D denotes the derivative operator d/dx. Then (1/(n! (1 + n)!)) * E^n(x/(1 - x)) = (row n generating polynomial)/(1 - x)^(2*n+1) = Sum_{k >= 0} C(n-1, k-1)*C(n, k-1)/k*x^k. For example, when n = 4 we have (1/4!/5!)*E^3(x/(1 - x)) = x (1 + 6 x + 6 x^2 + x^3)/(1 - x)^9. (End)

Extensions

Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

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

Original entry on oeis.org

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

Views

Author

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

Keywords

Comments

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

Examples

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

References

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

Links

Crossrefs

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

Programs

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

Formula

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

A028246 Triangular array a(n,k) = (1/k)*Sum_{i=0..k} (-1)^(k-i)*binomial(k,i)*i^n; n >= 1, 1 <= k <= n, read by rows.

Original entry on oeis.org

1, 1, 1, 1, 3, 2, 1, 7, 12, 6, 1, 15, 50, 60, 24, 1, 31, 180, 390, 360, 120, 1, 63, 602, 2100, 3360, 2520, 720, 1, 127, 1932, 10206, 25200, 31920, 20160, 5040, 1, 255, 6050, 46620, 166824, 317520, 332640, 181440, 40320, 1, 511, 18660, 204630, 1020600, 2739240, 4233600, 3780000, 1814400, 362880
Offset: 1

Views

Author

N. J. A. Sloane, Doug McKenzie (mckfam4(AT)aol.com)

Keywords

Comments

Let M = n X n matrix with (i,j)-th entry a(n+1-j, n+1-i), e.g., if n = 3, M = [1 1 1; 3 1 0; 2 0 0]. Given a sequence s = [s(0)..s(n-1)], let b = [b(0)..b(n-1)] be its inverse binomial transform and let c = [c(0)..c(n-1)] = M^(-1)*transpose(b). Then s(k) = Sum_{i=0..n-1} b(i)*binomial(k,i) = Sum_{i=0..n-1} c(i)*k^i, k=0..n-1. - Gary W. Adamson, Nov 11 2001
From Gary W. Adamson, Aug 09 2008: (Start)
Julius Worpitzky's 1883 algorithm generates Bernoulli numbers.
By way of example [Wikipedia]:
B0 = 1;
B1 = 1/1 - 1/2;
B2 = 1/1 - 3/2 + 2/3;
B3 = 1/1 - 7/2 + 12/3 - 6/4;
B4 = 1/1 - 15/2 + 50/3 - 60/4 + 24/5;
B5 = 1/1 - 31/2 + 180/3 - 390/4 + 360/5 - 120/6;
B6 = 1/1 - 63/2 + 602/3 - 2100/4 + 3360/5 - 2520/6 + 720/7;
...
Note that in this algorithm, odd n's for the Bernoulli numbers sum to 0, not 1, and the sum for B1 = 1/2 = (1/1 - 1/2). B3 = 0 = (1 - 7/2 + 13/3 - 6/4) = 0. The summation for B4 = -1/30. (End)
Pursuant to Worpitzky's algorithm and given M = A028246 as an infinite lower triangular matrix, M * [1/1, -1/2, 1/3, ...] (i.e., the Harmonic series with alternate signs) = the Bernoulli numbers starting [1/1, 1/2, 1/6, ...]. - Gary W. Adamson, Mar 22 2012
From Tom Copeland, Oct 23 2008: (Start)
G(x,t) = 1/(1 + (1-exp(x*t))/t) = 1 + 1 x + (2 + t)*x^2/2! + (6 + 6t + t^2)*x^3/3! + ... gives row polynomials for A090582, the f-polynomials for the permutohedra (see A019538).
G(x,t-1) = 1 + 1*x + (1 + t)*x^2 / 2! + (1 + 4t + t^2)*x^3 / 3! + ... gives row polynomials for A008292, the h-polynomials for permutohedra.
G[(t+1)x,-1/(t+1)] = 1 + (1+ t) x + (1 + 3t + 2 t^2) x^2 / 2! + ... gives row polynomials for the present triangle. (End)
The Worpitzky triangle seems to be an apt name for this triangle. - Johannes W. Meijer, Jun 18 2009
If Pascal's triangle is written as a lower triangular matrix and multiplied by A028246 written as an upper triangular matrix, the product is a matrix where the (i,j)-th term is (i+1)^j. For example,
1,0,0,0 1,1,1, 1 1,1, 1, 1
1,1,0,0 * 0,1,3, 7 = 1,2, 4, 8
1,2,1,0 0,0,2,12 1,3, 9,27
1,3,3,1 0,0,0, 6 1,4,16,64
So, numbering all three matrices' rows and columns starting at 0, the (i,j) term of the product is (i+1)^j. - Jack A. Cohen (ProfCohen(AT)comcast.net), Aug 03 2010
The Fi1 and Fi2 triangle sums are both given by sequence A000670. For the definition of these triangle sums see A180662. The mirror image of the Worpitzky triangle is A130850. - Johannes W. Meijer, Apr 20 2011
Let S_n(m) = 1^m + 2^m + ... + n^m. Then, for n >= 0, we have the following representation of S_n(m) as a linear combination of the binomial coefficients:
S_n(m) = Sum_{i=1..n+1} a(i+n*(n+1)/2)*C(m,i). E.g., S_2(m) = a(4)*C(m,1) + a(5)*C(m,2) + a(6)*C(m,3) = C(m,1) + 3*C(m,2) + 2*C(m,3). - Vladimir Shevelev, Dec 21 2011
Given the set X = [1..n] and 1 <= k <= n, then a(n,k) is the number of sets T of size k of subset S of X such that S is either empty or else contains 1 and another element of X and such that any two elemements of T are either comparable or disjoint. - Michael Somos, Apr 20 2013
Working with the row and column indexing starting at -1, a(n,k) gives the number of k-dimensional faces in the first barycentric subdivision of the standard n-dimensional simplex (apply Brenti and Welker, Lemma 2.1). For example, the barycentric subdivision of the 2-simplex (a triangle) has 1 empty face, 7 vertices, 12 edges and 6 triangular faces giving row 4 of this triangle as (1,7,12,6). Cf. A053440. - Peter Bala, Jul 14 2014
See A074909 and above g.f.s for associations among this array and the Bernoulli polynomials and their umbral compositional inverses. - Tom Copeland, Nov 14 2014
An e.g.f. G(x,t) = exp[P(.,t)x] = 1/t - 1/[t+(1-t)(1-e^(-xt^2))] = (1-t) * x + (-2t + 3t^2 - t^3) * x^2/2! + (6t^2 - 12t^3 + 7t^4 - t^5) * x^3/3! + ... for the shifted, reverse, signed polynomials with the first element nulled, is generated by the infinitesimal generator g(u,t)d/du = [(1-u*t)(1-(1+u)t)]d/du, i.e., exp[x * g(u,t)d/du] u eval. at u=0 generates the polynomials. See A019538 and the G. Rzadkowski link below for connections to the Bernoulli and Eulerian numbers, a Ricatti differential equation, and a soliton solution to the KdV equation. The inverse in x of this e.g.f. is Ginv(x,t) = (-1/t^2)*log{[1-t(1+x)]/[(1-t)(1-tx)]} = [1/(1-t)]x + [(2t-t^2)/(1-t)^2]x^2/2 + [(3t^2-3t^3+t^4)/(1-t)^3]x^3/3 + [(4t^3-6t^4+4t^5-t^6)/(1-t)^4]x^4/4 + ... . The numerators are signed, shifted A135278 (reversed A074909), and the rational functions are the columns of A074909. Also, dG(x,t)/dx = g(G(x,t),t) (cf. A145271). (Analytic G(x,t) added, and Ginv corrected and expanded on Dec 28 2015.) - Tom Copeland, Nov 21 2014
The operator R = x + (1 + t) + t e^{-D} / [1 + t(1-e^(-D))] = x + (1+t) + t - (t+t^2) D + (t+3t^2+2t^3) D^2/2! - ... contains an e.g.f. of the reverse row polynomials of the present triangle, i.e., A123125 * A007318 (with row and column offset 1 and 1). Umbrally, R^n 1 = q_n(x;t) = (q.(0;t)+x)^n, with q_m(0;t) = (t+1)^(m+1) - t^(m+1), the row polynomials of A074909, and D = d/dx. In other words, R generates the Appell polynomials associated with the base sequence A074909. For example, R 1 = q_1(x;t) = (q.(0;t)+x) = q_1(0;t) + q__0(0;t)x = (1+2t) + x, and R^2 1 = q_2(x;t) = (q.(0;t)+x)^2 = q_2(0:t) + 2q_1(0;t)x + q_0(0;t)x^2 = 1+3t+3t^2 + 2(1+2t)x + x^2. Evaluating the polynomials at x=0 regenerates the base sequence. With a simple sign change in R, R generates the Appell polynomials associated with A248727. - Tom Copeland, Jan 23 2015
For a natural refinement of this array, see A263634. - Tom Copeland, Nov 06 2015
From Wolfdieter Lang, Mar 13 2017: (Start)
The e.g.f. E(n, x) for {S(n, m)}{m>=0} with S(n, m) = Sum{k=1..m} k^n, n >= 0, (with undefined sum put to 0) is exp(x)*R(n+1, x) with the exponential row polynomials R(n, x) = Sum_{k=1..n} a(n, k)*x^k/k!. E.g., e.g.f. for n = 2, A000330: exp(x)*(1*x/1!+3*x^2/2!+2*x^3/3!).
The o.g.f. G(n, x) for {S(n, m)}{m >=0} is then found by Laplace transform to be G(n, 1/p) = p*Sum{k=1..n} a(n+1, k)/(p-1)^(2+k).
Hence G(n, x) = x/(1 - x)^(n+2)*Sum_{k=1..n} A008292(n,k)*x^(k-1).
E.g., n=2: G(2, 1/p) = p*(1/(p-1)^2 + 3/(p-1)^3 + 2/(p-1)^4) = p^2*(1+p)/(p-1)^4; hence G(2, x) = x*(1+x)/(1-x)^4.
This works also backwards: from the o.g.f. to the e.g.f. of {S(n, m)}_{m>=0}. (End)
a(n,k) is the number of k-tuples of pairwise disjoint and nonempty subsets of a set of size n. - Dorian Guyot, May 21 2019
From Rajesh Kumar Mohapatra, Mar 16 2020: (Start)
a(n-1,k) is the number of chains of length k in a partially ordered set formed from subsets of an n-element set ordered by inclusion such that the first term of the chains is either the empty set or an n-element set.
Also, a(n-1,k) is the number of distinct k-level rooted fuzzy subsets of an n-set ordered by set inclusion. (End)
The relations on p. 34 of Hasan (also p. 17 of Franco and Hasan) agree with the relation between A019538 and this entry given in the formula section. - Tom Copeland, May 14 2020
T(n,k) is the size of the Green's L-classes in the D-classes of rank (k-1) in the semigroup of partial transformations on an (n-1)-set. - Geoffrey Critzer, Jan 09 2023
T(n,k) is the number of strongly connected binary relations on [n] that have period k (A367948) and index 1. See Theorem 5.4.25(6) in Ki Hang Kim reference. - Geoffrey Critzer, Dec 07 2023

Examples

			The triangle a(n, k) starts:
n\k 1   2    3     4      5      6      7      8     9
1:  1
2:  1   1
3:  1   3    2
4:  1   7   12     6
5:  1  15   50    60     24
6:  1  31  180   390    360    120
7:  1  63  602  2100   3360   2520    720
8:  1 127 1932 10206  25200  31920  20160   5040
9:  1 255 6050 46620 166824 317520 332640 181440 40320
... [Reformatted by _Wolfdieter Lang_, Mar 26 2015]
-----------------------------------------------------
Row 5 of triangle is {1,15,50,60,24}, which is {1,15,25,10,1} times {0!,1!,2!,3!,4!}.
From _Vladimir Shevelev_, Dec 22 2011: (Start)
Also, for power sums, we have
S_0(n) = C(n,1);
S_1(n) = C(n,1) +    C(n,2);
S_2(n) = C(n,1) +  3*C(n,2) +  2*C(n,3);
S_3(n) = C(n,1) +  7*C(n,2) + 12*C(n,3) +  6*C(n,4);
S_4(n) = C(n,1) + 15*C(n,2) + 50*C(n,3) + 60*C(n,4) + 24*C(n,5); etc.
(End)
For X = [1,2,3], the sets T are {{}}, {{},{1,2}}, {{},{1,3}}, {{},{1,2,3}}, {{},{1,2},{1,2,3}}, {{},{1,3},{1,2,3}} and so a(3,1)=1, a(3,2)=3, a(3,3)=2. - _Michael Somos_, Apr 20 2013

References

  • Ki Hang Kim, Boolean Matrix Theory and Applications, Marcel Dekker, New York and Basel (1982).

Links

Crossrefs

Dropping the column of 1's gives A053440.
Without the k in the denominator (in the definition), we get A019538. See also the Stirling number triangle A008277.
Cf. A087127, A087107, A087108, A087109, A087110, A087111, A084938 A075263.
Row sums give A000629(n-1) for n >= 1.
Cf. A027642, A002445. - Gary W. Adamson, Aug 09 2008
Appears in A161739 (RSEG2 triangle), A161742 and A161743. - Johannes W. Meijer, Jun 18 2009
Binomial transform is A038719. Cf. A131689.
Cf. A007318, A008292, A046802, A074909, A090582, A123125, A130850, A135278, A141618, A145271, A163626, A248727, A263634.
Cf. A119879.
From Rajesh Kumar Mohapatra, Mar 29 2020: (Start)
A000007(n-1) (column k=1), A000225(n-1) (column k=2), A028243(n-1) (column k=3), A028244(n-1) (column k=4), A028245(n-1) (column k=5), for n > 0.
Diagonal gives A000142(n-1), for n >=1.
Next-to-last diagonal gives A001710,
Third, fourth, fifth, sixth, seventh external diagonal respectively give A005460, A005461, A005462, A005463, A005464. (End)

Programs

  • GAP
    Flat(List([1..10], n-> List([1..n], k-> Stirling2(n,k)* Factorial(k-1) ))); # G. C. Greubel, May 30 2019
  • Magma
    [[StirlingSecond(n,k)*Factorial(k-1): k in [1..n]]: n in [1..10]]; // G. C. Greubel, May 30 2019
  • Maple
    a := (n,k) -> add((-1)^(k-i)*binomial(k,i)*i^n, i=0..k)/k;
seq(print(seq(a(n,k),k=1..n)),n=1..10);
T := (n,k) -> add(eulerian1(n,j)*binomial(n-j,n-k), j=0..n):
seq(print(seq(T(n,k),k=0..n)),n=0..9); # Peter Luschny, Jul 12 2013
  • Mathematica
    a[n_, k_] = Sum[(-1)^(k-i) Binomial[k,i]*i^n, {i,0,k}]/k; Flatten[Table[a[n, k], {n, 10}, {k, n}]] (* Jean-François Alcover, May 02 2011 *)
  • PARI
    {T(n, k) = if( k<0 || k>n, 0, n! * polcoeff( (x / log(1 + x + x^2 * O(x^n) ))^(n+1), n-k))}; /* Michael Somos, Oct 02 2002 */
  • PARI
    {T(n,k) = stirling(n,k,2)*(k-1)!}; \\ G. C. Greubel, May 31 2019
  • Python
    # Assuming offset (n, k) = (0, 0).
def T(n, k):
    if k >  n: return 0
    if k == 0: return 1
    return k*T(n - 1, k - 1) + (k + 1)*T(n - 1, k)
for n in range(9):
    print([T(n, k) for k in range(n + 1)])  # Peter Luschny, Apr 26 2022
  • Sage
    def A163626_row(n) :
    x = polygen(ZZ,'x')
    A = []
    for m in range(0, n, 1) :
        A.append((-x)^m)
        for j in range(m, 0, -1):
            A[j - 1] = j * (A[j - 1] - A[j])
    return list(A[0])
for i in (1..7) : print(A163626_row(i))  # Peter Luschny, Jan 25 2012
  • Sage
    [[stirling_number2(n,k)*factorial(k-1) for k in (1..n)] for n in (1..10)] # G. C. Greubel, May 30 2019

Formula

E.g.f.: -log(1-y*(exp(x)-1)). - Vladeta Jovovic, Sep 28 2003
a(n, k) = S2(n, k)*(k-1)! where S2(n, k) is a Stirling number of the second kind (cf. A008277). Also a(n,k) = T(n,k)/k, where T(n, k) = A019538.
Essentially same triangle as triangle [1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, 7, ...] DELTA [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...] where DELTA is Deléham's operator defined in A084938, but the notation is different.
Sum of terms in n-th row = A000629(n) - Gary W. Adamson, May 30 2005
The row generating polynomials P(n, t) are given by P(1, t)=t, P(n+1, t) = t(t+1)(d/dt)P(n, t) for n >= 1 (see the Riskin and Beckwith reference). - Emeric Deutsch, Aug 09 2005
From Gottfried Helms, Jul 12 2006: (Start)
Delta-matrix as can be read from H. Hasse's proof of a connection between the zeta-function and Bernoulli numbers (see link below).
Let P = lower triangular matrix with entries P[row,col] = binomial(row,col).
Let J = unit matrix with alternating signs J[r,r]=(-1)^r.
Let N(m) = column matrix with N(m)(r) = (r+1)^m, N(1)--> natural numbers.
Let V = Vandermonde matrix with V[r,c] = (r+1)^c.
V is then also N(0)||N(1)||N(2)||N(3)... (indices r,c always beginning at 0).
Then Delta = P*J * V and B' = N(-1)' * Delta, where B is the column matrix of Bernoulli numbers and ' means transpose, or for the single k-th Bernoulli number B_k with the appropriate column of Delta,
B_k = N(-1)' * Delta[ *,k ] = N(-1)' * P*J * N(k).
Using a single column instead of V and assuming infinite dimension, H. Hasse showed that in x = N(-1) * P*J * N(s), where s can be any complex number and s*zeta(1-s) = x.
His theorem reads: s*zeta(1-s) = Sum_{n>=0..inf} (n+1)^-1*delta(n,s), where delta(n,s) = Sum_{j=0..n} (-1)^j * binomial(n,j) * (j+1)^s.
(End)
a(n,k) = k*a(n-1,k) + (k-1)*a(n-1,k-1) with a(n,1) = 1 and a(n,n) = (n-1)!. - Johannes W. Meijer, Jun 18 2009
Rephrasing the Meijer recurrence above: Let M be the (n+1)X(n+1) bidiagonal matrix with M(r,r) = M(r,r+1) = r, r >= 1, in the two diagonals and the rest zeros. The row a(n+1,.) of the triangle is row 1 of M^n. - Gary W. Adamson, Jun 24 2011
From Tom Copeland, Oct 11 2011: (Start)
With e.g.f.. A(x,t) = G[(t+1)x,-1/(t+1)]-1 (from 2008 comment) = -1 + 1/[1-(1+t)(1-e^(-x))] = (1+t)x + (1+3t+2t^2)x^2/2! + ..., the comp. inverse in x is
B(x,t)= -log(t/(1+t)+1/((1+t)(1+x))) = (1/(1+t))x - ((1+2t)/(1+t)^2)x^2/2 + ((1+3t+3t^2)/(1+t)^3)x^3/3 + .... The numerators are the row polynomials of A074909, and the rational functions are (omitting the initial constants) signed columns of the re-indexed Pascal triangle A007318.
Let h(x,t)= 1/(dB/dx) = (1+x)(1+t(1+x)), then the row polynomial P(n,t) = (1/n!)(h(x,t)*d/dx)^n x, evaluated 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(1,t)=1+t. (Series added Dec 29 2015.)(End)
Let denote the Eulerian numbers A173018(n,k), then T(n,k) = Sum_{j=0..n} *binomial(n-j,n-k). - Peter Luschny, Jul 12 2013
Matrix product A007318 * A131689. The n-th row polynomial R(n,x) = Sum_{k >= 1} k^(n-1)*(x/(1 + x))^k, valid for x in the open interval (-1/2, inf). Cf A038719. R(n,-1/2) = (-1)^(n-1)*(2^n - 1)*Bernoulli(n)/n. - Peter Bala, Jul 14 2014
a(n,k) = A141618(n,k) / C(n,k-1). - Tom Copeland, Oct 25 2014
For the row polynomials, A028246(n,x) = A019538(n-1,x) * (1+x). - Tom Copeland, Dec 28 2015
A248727 = A007318*(reversed A028246) = A007318*A130850 = A007318*A123125*A007318 = A046802*A007318. - Tom Copeland, Nov 14 2016
n-th row polynomial R(n,x) = (1+x) o (1+x) o ... o (1+x) (n factors), where o denotes the black diamond multiplication operator of Dukes and White. See example E11 in the Bala link. - Peter Bala, Jan 12 2018
From Dorian Guyot, May 21 2019: (Start)
Sum_{i=0..k} binomial(k,i) * a(n,i) = (k+1)^n.
Sum_{k=0..n} a(n,k) = 2*A000670(n).
(End)
With all offsets 0, let A_n(x;y) = (y + E.(x))^n, an Appell sequence in y where E.(x)^k = E_k(x) are the Eulerian polynomials of A123125. Then the row polynomials of this entry, A028246, are given by x^n * A_n(1 + 1/x;0). Other specializations of A_n(x;y) give A046802, A090582, A119879, A130850, and A248727. - Tom Copeland, Jan 24 2020
The row generating polynomials R(n,x) = Sum_{i=1..n} a(n,i) * x^i satisfy the recurrence equation R(n+1,x) = R(n,x) + Sum_{k=0..n-1} binomial(n-1,k) * R(k+1,x) * R(n-k,x) for n >= 1 with initial value R(1,x) = x. - Werner Schulte, Jun 17 2021

Extensions

Definition corrected by Li Guo, Dec 16 2006
Typo in link corrected by Johannes W. Meijer, Oct 17 2009
Error in title corrected by Johannes W. Meijer, Sep 24 2010
Edited by M. F. Hasler, Oct 29 2014

A055302 Triangle of number of labeled rooted trees with n nodes and k leaves, n >= 1, 1 <= k <= n.

Original entry on oeis.org

1, 2, 0, 6, 3, 0, 24, 36, 4, 0, 120, 360, 140, 5, 0, 720, 3600, 3000, 450, 6, 0, 5040, 37800, 54600, 18900, 1302, 7, 0, 40320, 423360, 940800, 588000, 101136, 3528, 8, 0, 362880, 5080320, 16087680, 15876000, 5143824, 486864, 9144, 9, 0, 3628800
Offset: 1

Views

Author

Christian G. Bower, May 11 2000

Keywords

Comments

Beginning with the second row, dividing each row by n gives the mirror of row n-1 of A141618. Under the exponential transform, the mirror of A141618 is generated, relating the number of connected graphs here to the number of disconnected graphs associated with A141618 (cf. A127671 and A036040). - Tom Copeland, Oct 25 2014

Examples

			Triangle begins
     1,
     2,     0;
     6,     3,     0;
    24,    36,     4,     0;
   120,   360,   140,     5,    0;
   720,  3600,  3000,   450,    6, 0;
  5040, 37800, 54600, 18900, 1302, 7, 0;

References

  • Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 313.

Links

Crossrefs

Row sums give A000169. Columns 1 through 12: A000142, A055303-A055313. Cf. A055314.
Cf. A248120 for a natural refinement.

Programs

  • Maple
    T:= (n, k)-> (n!/k!)*Stirling2(n-1, n-k):
seq(seq(T(n, k), k=1..n), n=1..10);  # Alois P. Heinz, Nov 13 2013
  • Mathematica
    Table[Table[n!/k! StirlingS2[n-1,n-k], {k,1,n}], {n,0,10}]//Grid  (* Geoffrey Critzer, Dec 01 2012 *)
  • PARI
    A055302(n,k)=n!/k!*stirling(n-1, n-k,2);
for(n=1,10,for(k=1,n,print1(A055302(n,k),", "));print());
\\ Joerg Arndt, Oct 27 2014

Formula

E.g.f. (relative to x) satisfies: A(x,y) = xy + x*exp(A(x,y)) - x. Divides by n and shifts up under exponential transform.
T(n,k) = (n!/k!)*Stirling2(n-1, n-k). - Vladeta Jovovic, Jan 28 2004
T(n,k) = A055314(n,k)*(n-k) + A055314(n,k+1)*(k+1). The first term is the number of such trees with root degree > 1 while the second term is the number of such trees with root degree = 1. This simplifies to the above formula by Vladeta Jovovic. - Geoffrey Critzer, Dec 01 2012
E.g.f.: G(x,t) = log[1 + t * N(x*t,1/t)], where N(x,t) is the e.g.f. of A141618. Also, G(x*t,1/t)= log[1 + N(x,t)/t] is the comp. inverse in x of x / [1 + t * (e^x - 1)]. - Tom Copeland, Oct 26 2014

A090582 T(n, k) = Sum_{j=0..n-k} (-1)^j*binomial(n - k + 1, j)*(n - k + 1 - j)^n. Triangle read by rows, T(n, k) for 1 <= k <= n.

Original entry on oeis.org

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

Views

Author

Hugo Pfoertner, Jan 11 2004

Keywords

Comments

Let Q(m, n) = Sum_(k=0..n-1) (-1)^k * binomial(n, k) * (n-k)^m. Then Q(m,n) is the numerator of the probability P(m,n) = Q(m,n)/n^m of seeing each card at least once if m >= n cards are drawn with replacement from a deck of n cards, written in a two-dimensional array read by antidiagonals with Q(m,m) as first row and Q(m,1) as first column.
The sequence is given as a matrix with the first row containing the cases #draws = size_of_deck. The second row contains #draws = 1 + size_of_deck. If "mn" indicates m cards drawn from a deck with n cards then the locations in the matrix are:
11 22 33 44 55 66 77 ...
21 32 43 54 65 76 87 ...
31 42 53 64 75 86 97 ...
41 52 63 74 85 .. .. ...
read by antidiagonals ->:
11, 22, 21, 33, 32, 31, 44, 43, 42, 41, 55, 54, 53, 52, ....
The probabilities are given by Q(m,n)/n^m:
.(m,n):.....11..22..21..33..32..31..44..43..42..41...55...54..53..52..51
.....Q:......1...2...1...6...6...1..24..36..14...1..120..240.150..30...1
...n^m:......1...4...1..27...8...1.256..81..16...1.3125.1024.243..32...1
%.Success:.100..50.100..22..75.100...9..44..88.100....4...23..62..94.100
P(n,n) = n!/n^n which can be approximated by sqrt(Pi*(2n+1/3))/e^n (Gosper's approximation to n!).
Let P[n] be the set of all n-permutations. Build a superset Q[n] of P[n] composed of n-permutations in which some (possibly all or none) ascents have been designated. An ascent in a permutation s[1]s[2]...s[n] is a pair of consecutive elements s[i],s[i+1] such that s[i] < s[i+1]. As a triangular array read by rows T(n,k) is the number of elements in Q[n] that have exactly k distinguished ascents, n >= 1, 0 <= k <= n-1. Row sums are A000670. E.g.f. is y/(1+y-exp(y*x)). For example, T(3,1)=6 because there are four 3-permutations with one ascent, with these we would also count 1->2 3, and 1 2->3 where exactly one ascent is designated by "->". (After Flajolet and Sedgewick.) - Geoffrey Critzer, Nov 13 2012
Sum_(k=1..n) Q(n, k)*binomial(x, k) = x^n such that Sum_{k=1..n} Q(n, i)*binomial(x+1,i+1) = Sum_{k=1..x} k^n. - David A. Corneth, Feb 17 2014
A141618(n,n-k+1) = a(n,k) * C(n,k-1) / k. - Tom Copeland, Oct 25 2014
See A074909 and above g.f.s below for associations among this array and the Bernoulli polynomials and their umbral compositional inverses. - Tom Copeland, Nov 14 2014
For connections to toric varieties and Eulerian polynomials (in addition to those noted below), see the Dolgachev and Lunts and the Stembridge links in A019538. - 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
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

Examples

			For m = 4, n = 2, we draw 4 times from a deck of two cards. Call the cards "a" and "b" - of the 16 possible combinations of draws (each of which is equally likely to occur), only two do not contain both a and b: a, a, a, a and b, b, b, b. So the probability of seeing both a and b is 14/16. Therefore Q(m, n) = 14.
Table starts:
  [1] 1;
  [2] 2,      1;
  [3] 6,      6,       1;
  [4] 24,     36,      14,      1;
  [5] 120,    240,     150,     30,      1;
  [6] 720,    1800,    1560,    540,     62,     1;
  [7] 5040,   15120,   16800,   8400,    1806,   126,    1;
  [8] 40320,  141120,  191520,  126000,  40824,  5796,   254,   1;
  [9] 362880, 1451520, 2328480, 1905120, 834120, 186480, 18150, 510, 1.

Links

Crossrefs

Cf. A073593 first m >= n giving at least 50% probability, A085813 ditto for 95%, A055775 n^n/n!, A090583 Gosper's approximation to n!.
Reflected version of A019538.
Cf. A233734 (central terms).
Cf. A074909, A008292, A028246.
Cf. A046802, A119879, A123125, A130850, and A248727.

Programs

  • Haskell
    a090582 n k = a090582_tabl !! (n-1) !! (k-1)
a090582_row n = a090582_tabl !! (n-1)
a090582_tabl = map reverse a019538_tabl
-- Reinhard Zumkeller, Dec 15 2013
  • Maple
    T := (n, k) -> add((-1)^j*binomial(n - k + 1, j)*(n - k + 1 - j)^n, j = 0..n-k):
# Or:
T := (n, k) -> (n - k + 1)!*Stirling2(n, n - k + 1):
for n from 1 to 9 do seq( T(n, k), k = 1..n) od; # Peter Luschny, May 21 2021
  • Mathematica
    In[1]:= Table[Table[k! StirlingS2[n, k], {k, n, 1, -1}], {n, 1, 6}] (* Victor Adamchik, Oct 05 2005 *)
nn=6; a=y/(1+y-Exp[y x]); Range[0,nn]! CoefficientList[Series[a, {x,0,nn}], {x,y}]//Grid (* Geoffrey Critzer, Nov 10 2012 *)
  • PARI
    a(n)={m=ceil((-1+sqrt(1+8*n))/2);k=m+1+binomial(m,2)-n;k*sum(i=1,k,(-1)^(i+k)*i^(m-1)*binomial(k-1,i-1))} \\ David A. Corneth, Feb 17 2014

Formula

T(n, k) = (n - k + 1)!*Stirling2(n, n - k + 1), generated by Stirling numbers of the second kind multiplied by a factorial. - Victor Adamchik, Oct 05 2005
Triangle T(n,k), 1 <= k <= n, read by rows given by [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...] DELTA [0, 1, 0, 2, 0, 3, 0, 4, 0, 5, 0, 6, 0, ...] where DELTA is the operator defined in A084938. - Philippe Deléham, Nov 10 2006
From Tom Copeland, Oct 07 2008: (Start)
G(x,t) = 1/ (1 + (1-exp(x*t))/t) = 1 + 1*x + (2 + t)*x^2/2! + (6 + 6*t + t^2)*x^3/3! + ... gives row polynomials of A090582, the f-polynomials for the permutohedra (see A019538).
G(x,t-1) = 1 + 1*x + (1 + t)*x^2/2! + (1 + 4*t + t^2)*x^3/3! + ... gives row polynomials for A008292, the h-polynomials of permutohedra.
G[(t+1)x,-1/(t+1)] = 1 + (1 + t)*x + (1 + 3*t + 2*t^2)*x^2/2! + ... gives row polynomials of A028246. (End)
From Tom Copeland, Oct 11 2011: (Start)
With e.g.f. A(x,t) = G(x,t) - 1, the compositional inverse in x is
B(x,t) = log((t+1)-t/(1+x))/t. Let h(x,t) = 1/(dB/dx) = (1+x)*(1+(1+t)x), then the row polynomial P(n,t) is given by (1/n!)*(h(x,t)*d/dx)^n x, evaluated at x=0, A=exp(x*h(y,t)*d/dy) y, eval. at y=0, and dA/dx = h(A(x,t),t). (End)
k <= 0 or k > n yields Q(n, k) = 0; Q(1,1) = 1; Q(n, k) = k * (Q(n-1, k) + Q(n-1, k-1)). - David A. Corneth, Feb 17 2014
T = A008292*A007318. - Tom Copeland, Nov 13 2016
With all offsets 0 for this entry, let A_n(x;y) = (y + E.(x))^n, an Appell sequence in y where E.(x)^k = E_k(x) are the Eulerian polynomials of A123125 with offsets -1 so that the array becomes A008292; i.e., we ignore the first row and first column of A123125. Then the row polynomials of this entry, A090582, are given by A_n(1 + x;0). Other specializations of A_n(x;y) give A028246, A046802, A119879, A130850, and A248727. - Tom Copeland, Jan 24 2020

A108767 Triangle read by rows: T(n,k) is number of paths from (0,0) to (3n,0) that stay in the first quadrant (but may touch the horizontal axis), consisting of steps u=(1,1), d=(1,-2) and have k peaks (i.e., ud's).

Original entry on oeis.org

1, 1, 2, 1, 6, 5, 1, 12, 28, 14, 1, 20, 90, 120, 42, 1, 30, 220, 550, 495, 132, 1, 42, 455, 1820, 3003, 2002, 429, 1, 56, 840, 4900, 12740, 15288, 8008, 1430, 1, 72, 1428, 11424, 42840, 79968, 74256, 31824, 4862, 1, 90, 2280, 23940, 122094, 325584, 465120
Offset: 1

Views

Author

Emeric Deutsch, Jun 24 2005

Keywords

Comments

Row sums yield A001764.
From Peter Bala, Sep 16 2012: (Start)
The number of 2-Dyck paths of order n with k peaks (Cigler). A 2-Dyck path of order n is a lattice path from (0,0) to (2*n,n) with steps (0,1) (North) and (1,0) (East) that never goes below the diagonal {2*i,i} 0 <= i <= n. A peak is a consecutive North East pair.
Row reverse of A120986. Described in A173020 as generalized Runyon numbers R_{n,k}^(2).
(End)
From Alexander Burstein, Jun 15 2020: (Start)
T(n,k) is the number of paths from (0,0) to (3n,0) that stay on or above the horizontal axis, with unit steps u=(1,1) and d=(1,-2), that have n+1-k peaks at even height.
T(n,k) is also the number of paths from (0,0) to (3n,0) that stay on or above the horizontal axis, with unit steps u=(1,1) and d=(1,-2), that have n-k peaks at odd height. (End)
An apparent refinement is A338135. - Tom Copeland, Oct 12 2020

Examples

			T(3,2)=6 because we have uuduuuudd, uuuduuudd, uuuuduudd, uuuudduud, uuuuududd and uuuuuddud.
Triangle starts:
  1;
  1,  2;
  1,  6,   5;
  1, 12,  28,   14;
  1, 20,  90,  120,   42;
  1, 30, 220,  550,  495,  132;
  1, 42, 455, 1820, 3003, 2002, 429;
  ...

Links

Crossrefs

Cf. A000108, A001764, A025174, A120986.
Runyon numbers R_{n,k}^(m): A010054 (m=0), A001263 (m=1), this sequence (m=2), A173020 (m=3).

Programs

  • Magma
    A108767:= func< n,k,m | Binomial(n,k)*Binomial(m*n,k-1)/n >;
[A108767(n,k,2): k in [1..n], n in [1..12]]; // G. C. Greubel, Feb 20 2021
  • Maple
    T:=(n,k)->binomial(n,k)*binomial(2*n,k-1)/n: for n from 1 to 10 do seq(T(n,k),k=1..n) od; # yields sequence in triangular form
  • Mathematica
    T[n_, k_] := Binomial[n, k]*Binomial[2*n, k - 1]/n;
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 11 2017, from Maple *)
  • PARI
    T(n,k) = binomial(n, k)*binomial(2*n, k-1)/n; \\ Andrew Howroyd, Nov 06 2017
  • Python
    from sympy import binomial
def T(n, k): return binomial(n, k)*binomial(2*n, k - 1)//n
for n in range(1, 21): print([T(n, k) for k in range(1, n + 1)]) # Indranil Ghosh, Nov 07 2017
  • R
    T <- function(n, k) {
  choose(n, k)*choose(2*n, k - 1)/n
} # Indranil Ghosh, Nov 07 2017
  • Sage
    def A108767(n,k,m): return binomial(n,k)*binomial(m*n,k-1)/n
flatten([[A108767(n,k,2) for k in (1..n)] for n in (1..12)]) # G. C. Greubel, Feb 20 2021

Formula

T(n, k) = binomial(n, k)*binomial(2*n, k-1)/n.
T(n, n) = A000108(n) (the Catalan numbers).
Sum_{k=1..n} k*T(n,k) = A025174(n).
G.f.: T-1, where T = T(t, z) satisfies T = 1 + z*T^2*(T - 1 + t).
From Peter Bala, Oct 22 2008: (Start)
Define a functional I on formal power series of the form f(x) = 1 + ax + bx^2 + ... by the following iterative process. Define inductively f^(1)(x) = f(x) and f^(n+1)(x) = f(x*f^(n)(x)) for n >= 1. Then set I(f(x)) = Limit_{n -> oo} f^(n)(x) in the x-adic topology on the ring of formal power series; the operator I may also be defined by I(f(x)) := 1/x*series reversion of x/f(x).
The o.g.f. for the array of Narayana numbers A001263 is I(1 + t*x + t*x^2 + t*x^3 + ...) = 1 + t*x + (t + t^2)*x^2 + (t + 3*t^2 + t^3)*x^3 + ... . The o.g.f. for the current array is IoI(1 + t*x + t*x^2 + t*x^3 + ...) = 1 + t*x + (t + 2*t^2)*x^2 + (t + 6*t^2 + 5*t^3)*x^3 + ... . Cf. A132081 and A141618. Alternatively, the o.g.f. of this array can be obtained from a single application of I, namely, form I(1 + t*x^2 + t*x^4 + t*x^6 + ...) = 1 + t*x^2 + (t + 2*t^2)*x^4 + (t + 6*t^2 + 5*t^3)*x^6 + ... and then replace x by sqrt(x). This is a particular case of the general result that forming the n-fold composition I^(n)(f(x)) and then replacing x with x^n produces the same result as I(f(x^n)). (End)
O.g.f. is series reversion with respect to x of x/((1+x)*(1+x*u)^2). Cf. A173020. - Peter Bala, Sep 12 2012
n-th row polynomial = x * hypergeom([1 - n, -2*n], [2], x). - Peter Bala, Aug 30 2023

A198204 Series reversion of (1 - t*x)*log(1 + x) with respect to x.

Original entry on oeis.org

1, 1, 2, 1, 9, 12, 1, 28, 120, 120, 1, 75, 750, 2100, 1680, 1, 186, 3780, 21840, 45360, 30240, 1, 441, 16856, 176400, 705600, 1164240, 665280, 1, 1016, 69552, 1224720, 8316000, 25280640, 34594560, 17297280, 1, 2295, 272250, 7692300, 82577880, 408648240, 998917920, 1167566400, 518918400
Offset: 1

Views

Author

Peter Bala, Jul 31 2012

Keywords

Comments

This triangle is A133399 read by diagonals.

Examples

			Triangle begins
.n\k.|..0....1.....2......3......4......5
= = = = = = = = = = = = = = = = = = = = =
..1..|..1
..2..|..1....2
..3..|..1....9....12
..4..|..1...28...120....120
..5..|..1...75...750...2100...1680
..6..|..1..186..3780..21840..45360..30240
...

Crossrefs

Cf. A001813, A002691, A052892, A058877, A133386, A133399, A141618.

Programs

  • Mathematica
    Flatten[CoefficientList[CoefficientList[InverseSeries[Series[Log[1 + x]*(1 - t*x),{x,0,9}]], x]*Table[n!, {n,0,9}], t]] (* Peter Luschny, Oct 25 2015 *)

Formula

T(n,k) = k!*binomial(n + k - 1,k)*Stirling2(n,k + 1) (n >= 1, k >=0).
E.g.f.: A(x,t) = series reversion of (1 - t*x)*log(1 + x) w.r.t. x = x + (1 + 2*t)*x^2/2! + (1 + 9*t + 12*t^2)*x^3/3! + ....
Main diagonal A001813, first subdiagonal A002691.
Column 1 A058877, column 2 A133386. Row sums A052892.
1 - t*A(x,t) = x/series reversion of x*(1 - t(exp(x) - 1)) with respect to x. Cf. A141618. - Peter Bala, Oct 22 2015

A248927 Triangle read by rows: T(n,k) are the coefficients of the Lagrange (compositional) inversion of a function in terms of the Taylor series expansion of its reciprocal, n >= 1, k = 1..A000041(n-1).

Original entry on oeis.org

1, 1, 2, 1, 6, 9, 1, 24, 72, 12, 16, 1, 120, 600, 300, 200, 50, 25, 1, 720, 5400, 5400, 2400, 450, 1800, 450, 60, 90, 36, 1, 5040, 52920, 88200, 29400, 22050, 44100, 7350, 4410, 2940, 4410, 882, 245, 147, 49, 1, 40320, 564480, 1411200, 376320, 705600, 940800
Offset: 1

Views

Author

Tom Copeland, Oct 16 2014

Keywords

Comments

Coefficients are listed in reverse graded colexicographic order (A228100). This is the reverse of Abramowitz and Stegun order (A036036).
Coefficients for Lagrange (compositional) inversion of a function in terms of the Taylor series expansion of its shifted reciprocal. Complementary to A134264 for formal power series. A refinement of A141618 with row sums A000272.
Given an invertible function f(t) analytic about t=0 with f(0)=0 and df(0)/dt not 0, form h(t) = t / f(t) and denote h_n = (n') as the coefficient of t^n/n! in h(t). Then the compositional inverse of f(t), g(t), as a formal Taylor series, or e.g.f., is given up to the first few orders by
g(t)/t = [ 1 (0') ]
+ [ 1 (0') (1') ] * t
+ [ 2 (0') (1')^2 + 1 (0')^2 (2') ] * t^2/2!
+ [ 6 (0') (1')^3 + 9 (0')^2 (1') (2') + 1 (0')^3 (3') ] * t^3/3!
+ [24 (0') (1')^4 + 72 (0')^2 (1')^2 (2') + (0')^3 [12 (2')^2
+ 16 (1') (3')] + (0')^4 (4')] * t^4/4!
+ [120 (0')(1')^5 + 600 (0')^2 (1')^3(2') + (0')^3 [300 (1')(2')^2 + 200 ( 1')^2(3')] + (0')^4 [50 (2')(3') + 25 (1')(4')] + (0')^5 (5')] * t^5/5! + [720 (0')(1')^6 + (0')^2 (1')^4(2')+(0')^3 [5400 (1')^2(2')^2 + 2400 (1')^3(3')] + (0')^4 [450 (2')^3+ 1800 (1')(2')(3') + 450( 1')^2(4')]+ (0')^5 [60 (3')^2 + 90 (2')(4') + 36 (1')(5')] + (0')^6 (6')] * t^6/6! + ...
..........
From Tom Copeland, Oct 28 2014: (Start)
Expressing g(t) as a Taylor series or formal e.g.f. in the indeterminates h_n generates a refinement of A055302, which enumerates the number of labeled root trees with n nodes and k leaves, with row sum A000169.
Operating with (1/n^2) d/d(1') = (1/n^2) d/d(h_1) on the n-th partition polynomial in square brackets above associated with t^n/n! generates the (n-1)-th partition polynomial.
Multiplying the n-th partition polynomial here by (n + 1) gives the (n + 1)-th partition polynomial of A248120. (End)
These are also the coefficients in the expansion of a series related to the Lagrange reversion theorem presented in Wikipedia of which the Lagrange inversion formula about the origin is a special case. Cf. Copeland link. - Tom Copeland, Nov 01 2016

Examples

			Triangle T(n,k) begins:
    1;
    1;
    2,    1;
    6,    9,    1;
   24,   72,   12,   16,   1;
  120,  600,  300,  200,  50,   25,   1;
  720, 5400, 5400, 2400, 450, 1800, 450, 60, 90, 36, 1;
  ...
For f(t) = e^t-1, h(t) = t/f(t) = t/(e^t-1), the e.g.f. for the Bernoulli numbers, and plugging the Bernoulli numbers into the Lagrange inversion formula gives g(t) = t - t^2/2 + t^3/3 + ... = log(1+t).

Links

Crossrefs

Cf. A145271
Cf. A134264 and A248120, "scaled" versions of this Lagrange inversion.
Cf. A036038.

Programs

  • PARI
    C(v)={my(n=vecsum(v), S=Set(v)); n!^2/((n-#v+1)!*prod(i=1, #S, my(x=S[i], c=#select(y->y==x, v)); x!^c*c!))}
row(n)=[C(Vec(p)) | p<-Vecrev(partitions(n-1))]
{ for(n=1, 7, print(row(n))) } \\ Andrew Howroyd, Feb 02 2022

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 [(j-1)!/j]* P(j,m;a...) / [(2!)^a_2 (3!)^a_3 ... ((j-1)!)^a_(j-1) ] for the k-th partition of j-1. The partitions are in reverse order--from bottom to top--from the order in Abramowitz and Stegun (page 831).
For example, from g(t) above, T(6,3) = [5!/6][6!/(3!*2!)]/(2!)^2 = 300 for the 3rd partition from the bottom under n=6-1=5 with m=3 parts, and T(6,5) = [5!/6][6!/4!]/(2!*3!) = 50.
If the initial factorial and final denominator are removed and the partitions reversed in order, A134264 is obtained, a refinement of the Narayana numbers.
For f(t) = t*e^(-t), g(t) = T(t), the Tree function, which is the e.g.f. of A000169, and h(t) = t/f(t) = e^t, so h_n = 1 for all n in this case; therefore, the row sums of A248927 are A000169(n)/n = n^(n-2) = A000272(n).
Let W(x) = 1/(df(x)/dx)= 1/{d[x/h(x)]/dx}=1/{d[x/[h_0+h_1*x+ ...]]/dx}. Then the partition polynomials above are given by (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)). See A145271.
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) and L =(d/dt)/h(d/dt)=(d/dt) 1/[(h_0)+(h_1)*d/dt+(h_2)*(d/dt)^2/2!+...], which will give a lowering operator associated to the refined f-vectors of permutohedra (cf. A133314 and A049019).
Then [dPS(n,z)/dz]/n eval. at z=0 are the row partition polynomials of this entry. (Cf. A139605, A145271, and link therein to Mathemagical Forests for relation to planted trees on p. 13.)
As noted in A248120 and A134264, this entry is given by the Hadamard product by partition of A134264 and A036038. For example, (1,4,2,6,1)*(1,4,6,12,24) = (1,16,12,72,24). - Tom Copeland, Nov 25 2016
T(n,k) = ((n-1)!)^2/((n-j)!*Product_{i>=1} s_i!*(i!)^s_i), where (1*s_1 + 2*s_2 + ... = n-1) is the k-th partition of n-1 and j = s_1 + s_2 ... is the number of parts. - Andrew Howroyd, Feb 02 2022

Extensions

Name edited and terms a(31) and beyond from Andrew Howroyd, Feb 02 2022
Showing 1-8 of 8 results.

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

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