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
Examples
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;
...
Links
- D. Galvin, G. Wesley and B. Zacovic, Enumerating threshold graphs and some related graph classes, arXiv:2110.08953 [math.CO], 2021.
Programs
-
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}] -
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
Formula
T(n,k) = Sum_{j=1..n-1} (n-j)*A173018(n-1, j-1)*binomial(j-1, n-k-1).
Comments