A008826 - OEIS

A008826

Triangle of coefficients from fractional iteration of e^x - 1.

1, 1, 3, 1, 13, 18, 1, 50, 205, 180, 1, 201, 1865, 4245, 2700, 1, 875, 16674, 74165, 114345, 56700, 1, 4138, 155477, 1208830, 3394790, 3919860, 1587600, 1, 21145, 1542699, 19800165, 90265560, 182184030, 167310360, 57153600, 1, 115973, 16385857, 335976195, 2338275240, 7342024200, 11471572350, 8719666200, 2571912000

(list; table; graph; refs; listen; history; text; internal format)

OFFSET

2,3

COMMENTS

The triangle reflects the Jordan-decomposition of the matrix of Stirling numbers of the second kind. A display of the matrix formula can be found at the Helms link which also explains the generation rule for the A()-numbers in a different way. - Gottfried Helms Apr 19 2014

From Gus Wiseman, Jan 02 2020: (Start)

Also the number of balanced reduced multisystems with atoms {1..n} and depth k. A balanced reduced multisystem is either a finite multiset, or a multiset partition with at least two parts, not all of which are singletons, of a balanced reduced multisystem. For example, row n = 4 counts the following multisystems:

{1,2,3,4} {{1},{2,3,4}} {{{1}},{{2},{3,4}}}

{{1,2},{3,4}} {{{1},{2}},{{3,4}}}

{{1,2,3},{4}} {{{1},{2,3}},{{4}}}

{{1,2,4},{3}} {{{1,2}},{{3},{4}}}

{{1,3},{2,4}} {{{1,2},{3}},{{4}}}

{{1,3,4},{2}} {{{1},{2,4}},{{3}}}

{{1,4},{2,3}} {{{1,2},{4}},{{3}}}

{{1},{2},{3,4}} {{{1}},{{3},{2,4}}}

{{1},{2,3},{4}} {{{1},{3}},{{2,4}}}

{{1,2},{3},{4}} {{{1,3}},{{2},{4}}}

{{1},{2,4},{3}} {{{1,3},{2}},{{4}}}

{{1,3},{2},{4}} {{{1},{3,4}},{{2}}}

{{1,4},{2},{3}} {{{1,3},{4}},{{2}}}

{{{1}},{{4},{2,3}}}

{{{1},{4}},{{2,3}}}

{{{1,4}},{{2},{3}}}

{{{1,4},{2}},{{3}}}

{{{1,4},{3}},{{2}}}

(End)

From Harry Richman, Mar 30 2023: (Start)

Equivalently, T(n,k) is the number of length-k chains from minimum to maximum in the lattice of set partitions of {1..n} ordered by refinement. For example, row n = 4 counts the following chains, leaving out the minimum {1|2|3|4} and maximum {1234}:

(empty) {12|3|4} {12|3|4} < {123|4}

{13|2|4} {12|3|4} < {124|3}

{14|2|3} {12|3|4} < {12|34}

{1|23|4} {13|2|4} < {123|4}

{1|24|3} {13|2|4} < {134|2}

{1|2|34} {13|2|4} < {13|24}

{123|4} {14|2|3} < {124|3}

{124|3} {14|2|3} < {134|2}

{134|2} {14|2|3} < {14|23}

{1|234} {1|23|4} < {123|4}

{12|34} {1|23|4} < {1|234}

{13|24} {1|23|4} < {14|23}

{14|23} {1|24|3} < {124|3}

{1|24|3} < {1|234}

{1|24|3} < {13|24}

{1|2|34} < {134|2}

{1|2|34} < {1|234}

{1|2|34} < {12|34}

(End)

Also the number of cells of dimension k in the fine subdivision of the Bergman complex of the complete graph on n vertices. - Harry Richman, Mar 30 2023

REFERENCES

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 148.

LINKS

Alois P. Heinz, Rows n = 2..150, flattened (first 19 rows from Vincenzo Librandi)

Gottfried Helms, How this expression leads to the given sequence, MathOverflow.

Federico Ardila and Caroline J. Klivans, The Bergman complex of a matroid and phylogenetic trees, J. Combin. Theory Ser. B, 96 (2006), 38-49.

FORMULA

G.f. A(n;x) for n-th row satisfies A(n;x) = Sum_{k=0..n-1} Stirling2(n, k)*A(k;x)*x, A(1;x) = 1. - Vladeta Jovovic, Jan 02 2004

Sum_{k=1..n-1} (-1)^k*T(n,k) = (-1)^(n-1)*(n-1)! = A133942(n-1). - Geoffrey Critzer, Sep 06 2020

EXAMPLE

Triangle starts:

1, 3;

1, 13, 18;

1, 50, 205, 180;

1, 201, 1865, 4245, 2700;

1, 875, 16674, 74165, 114345, 56700;

1, 4138, 155477, 1208830, 3394790, 3919860, 1587600;

...

The f-vector of (the fine subdivision of) the Bergman complex of the complete graph K_3 is (1, 3). The f-vector of the Bergman complex of K_4 is (1, 13, 18). - Harry Richman, Mar 30 2023

MAPLE

b:= proc(n) option remember; expand(`if`(n=1, 1,

add(Stirling2(n, j)*b(j)*x, j=0..n-1)))

end:

T:= (n, k)-> coeff(b(n), x, k):

seq(seq(T(n, k), k=1..n-1), n=2..10); # Alois P. Heinz, Mar 31 2023

MATHEMATICA

a[n_, x_] := Sum[ StirlingS2[n, k]*a[k, x]*x, {k, 0, n-1}]; a[1, _] = 1; Table[ CoefficientList[ a[n, x], x] // Rest, {n, 2, 10}] // Flatten (* Jean-François Alcover, Dec 11 2012, after Vladeta Jovovic *)

sps[{}]:={{}}; sps[set:{i_, ___}]:=Join@@Function[s, Prepend[#, s]&/@sps[Complement[set, s]]]/@Cases[Subsets[set], {i, ___}];

tots[m_]:=Prepend[Join@@Table[tots[p], {p, Select[sps[m], 1<Length[#]<Length[m]&]}], m];

Table[Length[Select[tots[Range[n]], Depth[#]==k&]], {n, 2, 6}, {k, 2, n}] (* Gus Wiseman, Jan 02 2020 *)

CROSSREFS

Row sums are A005121.

Alternating row sums are signed factorials A133942(n-1).

Column k = 2 is A008827.

Diagonal k = n - 1 is A006472.

Diagonal k = n - 2 is A059355.

Row n equals row 2^n of A330727.