A348576 Triangle read by rows: T(n,k) is the number of ordered partitions of [n] into k nonempty subsets, in which the first subset has size at least 2, n >= 1 and 1 <= k <= n.

0, 1, 0, 1, 3, 0, 1, 10, 12, 0, 1, 25, 80, 60, 0, 1, 56, 360, 660, 360, 0, 1, 119, 1372, 4620, 5880, 2520, 0, 1, 246, 4788, 26376, 58800, 57120, 20160, 0, 1, 501, 15864, 134316, 466704, 771120, 604800, 181440, 0, 1, 1012, 50880, 637020, 3238200, 8094240, 10584000, 6955200, 1814400, 0

Offset

1,5

Comments

Ordered partitions are also referred to as weak orders.

Links

Table of n, a(n) for n=1..55.

D. Galvin, G. Wesley and B. Zacovic, Enumerating threshold graphs and some related graph classes, arXiv:2110.08953 [math.CO], 2021.

Formula

T(n,k) = Sum_{j=1..n-1} (n-j)*A173018(n-1, j-1)*binomial(j-1, n-k-1).

Example

For n=3, the ordered partitions of {1,2,3} in which the first block has size at least 2 are 123, 12/3, 13/2 and 23/1, so T(3,1)=1, T(3,2)=3 and T(3,3)=0.
Triangle begins:
  0;
  1,     0;
  1,     3,     0;
  1,    10,    12,       0;
  1,    25,    80,      60,       0;
  1,    56,   360,     660,     360,       0;
  1,   119,  1372.    4620,    5880,    2520,        0;
  1,   246,  4788,   26376,   58800,   57120,    20160,        0;
  1,   501, 15864,  134316,  466704,  771120,   604800,   181440,       0;
  1,  1012, 50880,  637020, 3238200, 8094240, 10584000,  6955200, 1814400, 0;
  ...

Maple

b:= proc(n, t) option remember; expand(`if`(n=0, 1,
      add(x*b(n-j, 1)*binomial(n, j), j=t..n)))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 2)):
seq(T(n), n=1..10);  # Alois P. Heinz, Oct 24 2021

Mathematica

eulerian[n_, m_] := eulerian[n, m] =
  Sum[((-1)^k)*Binomial[n+1, k]*((m+1-k)^n), {k, 0, m+1}] (* eulerian[n, m] is an Eulerian number, counting the permutations of [n] with m descents *);
op2[n_, k_] := op2[n, k] =
   Sum[(n-j)*eulerian[n-1, j-1]*Binomial[j-1, n-k-1], {j, 1, n-1}] (* op2[n, k] counts ordered partitions on [n] with k parts, with first part having size at least 2 *); Table[op2[n, k], {n, 1, 12}, {k, 1, n}]

Prog

(PARI) TE(n, k) = sum(j=0, k, (-1)^j * (k-j)^n * binomial( n+1, j)); \\ A008292
T(n, k) = sum(j=1, n-1, (n-j)*TE(n-1, j)*binomial(j-1, n-k-1)); \\ Michel Marcus, Oct 24 2021

Crossrefs

Row sums are A053525.

Cf. A173018, A000247, A001710, A131689.

Sequence in context: A353010 A112906 A137375 * A307657 A269939 A239731

Adjacent sequences: A348573 A348574 A348575 * A348577 A348578 A348579

Keyword

nonn,tabl

Author

David Galvin, Oct 23 2021

Status

approved