login
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.
1
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
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.
Sequence in context: A112906 A137375 A376788 * A307657 A269939 A239731
KEYWORD
nonn,tabl
AUTHOR
David Galvin, Oct 23 2021
STATUS
approved