A112495 -id:A112495 - cp's OEIS frontend

A124324 Triangle read by rows: T(n,k) is the number of partitions of an n-set having k blocks of size > 1 (0<=k<=floor(n/2)).

1, 1, 1, 1, 1, 4, 1, 11, 3, 1, 26, 25, 1, 57, 130, 15, 1, 120, 546, 210, 1, 247, 2037, 1750, 105, 1, 502, 7071, 11368, 2205, 1, 1013, 23436, 63805, 26775, 945, 1, 2036, 75328, 325930, 247555, 27720, 1, 4083, 237127, 1561516, 1939630, 460845, 10395, 1, 8178

Offset: 0

Emeric Deutsch, Oct 28 2006

Row sums are the Bell numbers (A000110).
It appears that the triangles in this sequence and A112493 have identical columns, except for shifts. - Jörgen Backelin, Jun 20 2022
Equivalent to Jörgen Backelin's observation, the rows of A112493 may be read off as the diagonals of this entry. - Tom Copeland, Sep 24 2022

			T(4,2) = 3 because we have 12|34, 13|24 and 14|23 (if we take {1,2,3,4} as our 4-set).
Triangle starts:
  1;
  1;
  1,    1;
  1,    4;
  1,   11,     3;
  1,   26,    25;
  1,   57,   130,    15;
  1,  120,   546,   210;
  1,  247,  2037,  1750,   105;
  1,  502,  7071, 11368,  2205;
  1, 1013, 23436, 63805, 26775, 945;
  ...

Alois P. Heinz, Rows n = 0..200, flattened
Per Alexandersson and Olivia Nabawanda, Peaks are preserved under run-sorting, arXiv:2104.04220 [math.CO], 2021.
Fufa Beyene and Roberto Mantaci, Merging-Free Partitions and Run-Sorted Permutations, arXiv:2101.07081 [math.CO], 2021.
Tom Copeland, Appell-Bell polynomials: Linking the associated Bell polynomials and the associated reduced inverse refined Eulerian polynomials, 2022.
Tom Copeland, The reduced inverse refined Eulerian polynomials and associated arrays, 2022.
Robin Houston, Adam P. Goucher, and Nathaniel Johnston, A New Formula for the Determinant and Bounds on Its Tensor and Waring Ranks, arXiv:2301.06586 [math.CO], 2023.
O. Nabawanda, F. Rakotondrajao, and A. S. Bamunoba, Run Distribution Over Flattened Partitions, arXiv:2007.03821 [math.CO], 2020.

Columns k=0-10 give: A000012, A000295, A112495, A112496, A112497, A290034, A290035, A290036, A290037, A290038, A290039.

Cf. A000110, A001147, A048993, A124323, A124325, A136394, A112493.

G:=exp(t*exp(z)-t+(1-t)*z): Gser:=simplify(series(G,z=0,36)): for n from 0 to 33 do P[n]:=sort(n!*coeff(Gser,z,n)) od: for n from 0 to 13 do seq(coeff(P[n],t,k),k=0..floor(n/2)) od; # yields sequence in triangular form
# second Maple program:
b:= proc(n) option remember; expand(`if`(n=0, 1, add(
      `if`(i>1, x, 1)*binomial(n-1, i-1)*b(n-i), i=1..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n)):
seq(T(n), n=0..15);  # Alois P. Heinz, Mar 08 2015, Jul 15 2017

multinomial[n_, k_List] := n!/Times @@ (k!); b[n_, i_] :=  b[n, i] = Expand[If[n == 0, 1, If[i<1, 0, Sum[multinomial[n, Join[{n-i*j}, Array[i&, j]]]/j!*b[n-i*j, i-1]*If[i>1, x^j, 1], {j, 0, n/i}]]]]; T[n_] := Function[{p}, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, n]]; Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, May 22 2015, after Alois P. Heinz *)

E.g.f.: G(t,z) = exp(t*exp(z) - t + (1-t)*z).
T(n,1) = A000295(n) (the Eulerian numbers).
Sum_{k=0..floor(n/2)} k*T(n,k) = A124325(n).
T(2n,n) = A001147(n). - Alois P. Heinz, Apr 06 2018

A112493 Triangle read by rows, T(n, k) = Sum_{j=0..n} C(n-j, n-k)*E2(n, j), where E2 are the second-order Eulerian numbers A201637, for n >= 0 and 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 4, 3, 1, 11, 25, 15, 1, 26, 130, 210, 105, 1, 57, 546, 1750, 2205, 945, 1, 120, 2037, 11368, 26775, 27720, 10395, 1, 247, 7071, 63805, 247555, 460845, 405405, 135135, 1, 502, 23436, 325930, 1939630, 5735730, 8828820, 6756750, 2027025, 1

Offset: 0

Wolfdieter Lang, Oct 14 2005

Previous name was: Coefficient triangle of polynomials used for e.g.f.s of Stirling2 diagonals.
For the o.g.f. of diagonal k of the Stirling2 triangle one has a similar result. See A008517 (second-order Eulerian triangle).
A(m,x), the o.g.f. for column m, satisfies the recurrence A(m,x) = x*(x*(d/dx)A(m-1,x) + m*A(m-1,x))/(1-(m+1)*x), for m >= 1 and A(0,x) = 1/(1-x).
The e.g.f. for the sequence in column k+1, k >= 0, of A008278, i.e., for the diagonal k >= 0 of the Stirling2 triangle A048993, is exp(x)*Sum_{m=0..k} a(k,m)*(x^(m+k))/(m+k)!.
It appears that the triangles in this sequence and A124324 have identical columns, except for shifts. - Jörgen Backelin, Jun 20 2022
A refined version of this triangle is given in A356145, which contains a link providing the precise relationship between A124324 and this entry, confirming Jörgen Backelin's observation above. - Tom Copeland, Sep 24 2022

			Triangle starts:
  [1]
  [1, 1]
  [1, 4,  3]
  [1, 11, 25,  15]
  [1, 26, 130, 210,  105]
  [1, 57, 546, 1750, 2205, 945]
  ...
The e.g.f. of [0,0,1,7,25,65,...], the k=3 column of A008278, but with offset n=0, is exp(x)*(1*(x^2)/2! + 4*(x^3)/3! + 3*(x^4)/4!).
Third row [1,4,3]: There are three plane increasing trees on 3 vertices. The number of colors are shown to the right of a vertex.
...................................................
....1o.(1+t)...........1o.t*(1+t).....1o.t*(1+t)...
....|................. /.\............/.\..........
....|................ /...\........../...\.........
....2o.(1+t)........2o.....3o......3o....2o........
....|..............................................
....|..............................................
....3o.............................................
...................................................
The total number of trees is (1+t)^2 + t*(1+t) + t*(1+t) = 1+4*t+3*t^2 = R(2,t).

F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA], 2005.
Wolfdieter Lang, First ten rows.
MathOverflow, Recursion for row polynomials of A112493, (2025).
Andrew Elvey Price and Alan D. Sokal, Phylogenetic trees, augmented perfect matchings, and a Thron-type continued fraction (T-fraction) for the Ward polynomials, arXiv:2001.01468 [math.CO], 2020.

Row sums give A006351(k+1), k>=0.
The column sequences start with A000012 (powers of 1), A000295 (Eulerian numbers), A112495, A112496, A112497.
Cf. A008278, A008517, A048993, A054589, A075856, A134991, A201637, A124324.
Antidiagonal sums give A000110.
Cf. A356145.

T := (n, k) -> add(combinat:-eulerian2(n, j)*binomial(n-j, n-k), j=0..n):
seq(seq(T(n, k), k=0..n), n=0..9); # Peter Luschny, Apr 11 2016

max = 11; f[x_, t_] := -1 - (1 + t)/t*ProductLog[-t/(1 + t)*Exp[(x - t)/(1 + t)]]; coes = CoefficientList[ Series[f[x, t], {x, 0, max}, {t, 0, max}], {x, t}]* Range[0, max]!; Table[coes[[n, k]], {n, 0, max}, {k, 1, n - 1}] // Flatten (* Jean-François Alcover, Nov 22 2012, from e.g.f. *)

a(k, m) = 0 if k < m, a(k, -1):=0, a(0, 0)=1, a(k, m)=(m+1)*a(k-1, m) + (k+m-1)*a(k-1, m-1) else.
From Peter Bala, Sep 30 2011: (Start)
E.g.f.: A(x,t) = -1-((1+t)/t)*LambertW(-(t/(1+t))*exp((x-t)/(1+t))) = x + (1+t)*x^2/2! + (1+4*t+3*t^2)*x^3/3! + .... A(x,t) is the inverse function of (1+t)*log(1+x)-t*x.
A(x,t) satisfies the partial differential equation (1-x*t)*dA/dx = 1 + A + t*(1+t)*dA/dt. It follows that the row generating polynomials R(n,t) satisfy the recurrence R(n+1,t) =(n*t+1)*R(n,t) + t*(1+t)*dR(n,t)/dt. Cf. A054589 and A075856. The polynomials t/(1+t)*R(n,t) are the row polynomials of A134991.
The generating function A(x,t) satisfies the autonomous differential equation dA/dx = (1+A)/(1-t*A). Applying [Bergeron et al., Theorem 1] gives a combinatorial interpretation for the row generating polynomials R(n,t): R(n,t) counts plane increasing trees on n+1 vertices where the non-leaf vertices of outdegree k come in t^(k-1)*(1+t) colors. An example is given below. Cf. A006351, which corresponds to the case t = 1. Applying [Dominici, Theorem 4.1] gives the following method for calculating the row polynomials R(n,t): Let f(x) = (1+x)/(1-x*t). Then R(n,t) = (f(x)*d/dx)^n(f(x)) evaluated at x = 0. (End)
Sum_{j=0..n} T(n-j,j) = A000110(n). - Alois P. Heinz, Jun 20 2022
From Mikhail Kurkov, Apr 01 2025: (Start)
E.g.f.: B(y) = -w/(x*(1+w)) where w = LambertW(-x/(1+x)*exp((y-x)/(1+x))) satisfies the first-order ordinary differential equation (1+x)*B'(y) = B(y)*(1+x*B(y))^2, hence row polynomials are P(n,x) = P(n-1,x) + x*Sum_{j=0..n-1} binomial(n, j)*P(j,x)*P(n-j-1,x) for n > 0 with P(0,x) = 1 (see MathOverflow link).
Conjecture: row polynomials are P(n,x) = Sum_{i=0..n} Sum_{j=0..i} Sum_{k=0..j} (n+i)!*Stirling1(n+j-k,j-k)*x^k*(x+1)^(j-k)*(-1)^(j+k)/((n+j-k)!*(i-j)!*k!). (End)
Conjecture: g.f. satisfies 1/(1 - x - x*y/(1 - 2*x - 2*x*y/(1 - 3*x - 3*x*y/(1 - 4*x - 4*x*y/(1 - 5*x - 5*x*y/(1 - ...)))))) (see A383019 for conjectures about combinatorial interpretation and algorithm for efficient computing). - Mikhail Kurkov, Apr 21 2025

New name from Peter Luschny, Apr 11 2016

A112496 Fourth column of triangle A112493 used for e.g.f.s of Stirling2 diagonals.

Original entry on oeis.org

15, 210, 1750, 11368, 63805, 325930, 1561516, 7150000, 31682651, 137031986, 582035714, 2438479592, 10109790809, 41579014154, 169946747160, 691299506640, 2801567046135, 11320801495410, 45642930545070, 183698923750440

Offset: 0

Wolfdieter Lang, Oct 14 2005

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (20, -175, 882, -2835, 6072, -8777, 8458, -5204, 1848, -288).

Cf. A112495 (third column).

Column k=3 of A124324 (shifted).

CoefficientList[Series[(15 - 90*x + 175*x^2 - 112*x^3)/((1 - x)^4*(1 - 2*x)^3*(1 - 3*x)^2*(1 - 4*x)), {x, 0, 50}], x] (* G. C. Greubel, Nov 13 2017 *)
Table[2^(2*n+11)/3- 3^(n+5)*(n+9)/2 + 2^(n+3)*(n^2 + 15*n + 58) - n^3/6 - 3*n^2 - 55*n/3 - 229/6, {n,0,25}] (* Vaclav Kotesovec, Jul 23 2021 *)

x='x+O('x^50); Vec((15-90*x+175*x^2-112*x^3)/((1-x)^4*(1-2*x)^3*(1-3*x)^2*(1-4*x))) \\ G. C. Greubel, Nov 13 2017

G.f.: (15-90*x+175*x^2-112*x^3)/((1-x)^4*(1-2*x)^3*(1-3*x)^2*(1-4*x)).
a(n) = 4*a(n-1) + (n+5)*A112495(n).
a(n) = 2^(2*n+11)/3- 3^(n+5)*(n+9)/2 + 2^(n+3)*(n^2 + 15*n + 58) - n^3/6 - 3*n^2 - 55*n/3 - 229/6. - Vaclav Kotesovec, Jul 23 2021

A381646 a(n) = 4^n - 23^(n-1)(n+3) + 2^(n-2)(n^2+3n+4).

Original entry on oeis.org

0, 0, 0, 0, 6, 80, 650, 4172, 23310, 119016, 571122, 2621828, 11651222, 50536928, 215219706, 903799548, 3754755102, 15469272536, 63320624642, 257886717812, 1046169235110, 4230947198160, 17069749295370, 68738191563500, 276393979740206

Offset: 0

Enrique Navarrete, Mar 03 2025

a(n) is the number of words of length n defined on 4 letters where two of the letters are used at least twice.

			For n=5 the 80 words that use 0 and 1 at least twice are 00111 (10 of this type), 00011 (10 of this type), 00112 (30 of this type), 00113 (30 of this type).

Index entries for linear recurrences with constant coefficients, signature (16,-105,362,-692,696,-288).

Cf. A112495, A380024, A380249.

LinearRecurrence[{16,-105,362,-692,696,-288},{0,0,0,0,6,80},25] (* Stefano Spezia, Mar 03 2025 *)

def A381646(n): return ((1<2 else 0 # Chai Wah Wu, Mar 15 2025

a(n) = 4^n - 2*3^(n-1)*(n+3) + 2^(n-2)*(n^2+3*n+4).
E.g.f. exp(2*x)*(exp(x)-x-1)^2.
G.f.: 2*x^4*(3 - 8*x)/((1 - 3*x)^2*(1 - 2*x)^3*(1 - 4*x)). - Stefano Spezia, Mar 03 2025

A385329 a(n) = 5^n - 24^(n-1)(n+4) + 3^(n-2)(n^2+5n+9).

Original entry on oeis.org

0, 0, 0, 0, 6, 110, 1220, 10612, 79786, 544434, 3468792, 21012200, 122500334, 693324502, 3833742796, 20809676604, 111288341970, 588046458074, 3076991784512, 15972440574064, 82370489136214, 422506631928510, 2157589903432020, 10977781519321220, 55686118748465786

Offset: 0

Enrique Navarrete, Jun 25 2025

a(n) is the number of words of length n defined on 5 letters where two chosen letters, say a and b, are used at least twice.

			a(4) = 6 since the words are the 6 permutations of aabb.
a(5) = 110 since the words are (number of permutations in parentheses): aaabb (10), aabbb (10), aabbc (30), aabbd (30), aabbe (30).

Vincenzo Librandi, Table of n, a(n) for n = 0..500
Index entries for linear recurrences with constant coefficients, signature (22,-200,962,-2583,3672,-2160).

Cf. A112495, A381646.

m:=50; R:=PowerSeriesRing(Integers(), m); [0,0,0,0] cat Coefficients(R!((2*x^4*(3 - 11*x)/((1 - 4*x)^2*(1 - 3*x)^3*(1 - 5*x))))); // Vincenzo Librandi, Jul 05 2025

LinearRecurrence[{22, -200, 962, -2583, 3672, -2160}, {0, 0, 0, 0, 6, 110, 1220}, 25] (* Amiram Eldar, Jun 28 2025 *)

E.g.f.: exp(3*x)*(exp(x) - x - 1)^2.

G.f.: 2*x^4*(3 - 11*x)/((1 - 4*x)^2*(1 - 3*x)^3*(1 - 5*x)). - Jinyuan Wang, Jun 26 2025

cp's OEIS Frontend

A124324 Triangle read by rows: T(n,k) is the number of partitions of an n-set having k blocks of size > 1 (0<=k<=floor(n/2)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A112493 Triangle read by rows, T(n, k) = Sum_{j=0..n} C(n-j, n-k)*E2(n, j), where E2 are the second-order Eulerian numbers A201637, for n >= 0 and 0 <= k <= n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A112496 Fourth column of triangle A112493 used for e.g.f.s of Stirling2 diagonals.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A381646 a(n) = 4^n - 2*3^(n-1)*(n+3) + 2^(n-2)*(n^2+3*n+4).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

A385329 a(n) = 5^n - 2*4^(n-1)*(n+4) + 3^(n-2)*(n^2+5*n+9).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A381646 a(n) = 4^n - 23^(n-1)(n+3) + 2^(n-2)(n^2+3n+4).

A385329 a(n) = 5^n - 24^(n-1)(n+4) + 3^(n-2)(n^2+5n+9).