|
%I #32 Jan 03 2022 16:29:31
%S 0,1,0,1,3,0,1,10,12,0,1,25,80,60,0,1,56,360,660,360,0,1,119,1372,
%T 4620,5880,2520,0,1,246,4788,26376,58800,57120,20160,0,1,501,15864,
%U 134316,466704,771120,604800,181440,0,1,1012,50880,637020,3238200,8094240,10584000,6955200,1814400,0
%N 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.
%C Ordered partitions are also referred to as weak orders.
%H D. Galvin, G. Wesley and B. Zacovic, <a href="https://arxiv.org/abs/2110.08953">Enumerating threshold graphs and some related graph classes</a>, arXiv:2110.08953 [math.CO], 2021.
%F T(n,k) = Sum_{j=1..n-1} (n-j)*A173018(n-1, j-1)*binomial(j-1, n-k-1).
%e 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.
%e Triangle begins:
%e 0;
%e 1, 0;
%e 1, 3, 0;
%e 1, 10, 12, 0;
%e 1, 25, 80, 60, 0;
%e 1, 56, 360, 660, 360, 0;
%e 1, 119, 1372. 4620, 5880, 2520, 0;
%e 1, 246, 4788, 26376, 58800, 57120, 20160, 0;
%e 1, 501, 15864, 134316, 466704, 771120, 604800, 181440, 0;
%e 1, 1012, 50880, 637020, 3238200, 8094240, 10584000, 6955200, 1814400, 0;
%e ...
%p b:= proc(n, t) option remember; expand(`if`(n=0, 1,
%p add(x*b(n-j, 1)*binomial(n, j), j=t..n)))
%p end:
%p T:= n-> (p-> seq(coeff(p, x, i), i=1..n))(b(n, 2)):
%p seq(T(n), n=1..10); # _Alois P. Heinz_, Oct 24 2021
%t eulerian[n_,m_] := eulerian[n,m] =
%t 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 *);
%t op2[n_,k_] := op2[n,k] =
%t 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}]
%o (PARI) TE(n, k) = sum(j=0, k, (-1)^j * (k-j)^n * binomial( n+1, j)); \\ A008292
%o 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
%Y Row sums are A053525.
%Y Cf. A173018, A000247, A001710, A131689.
%K nonn,tabl
%O 1,5
%A _David Galvin_, Oct 23 2021
|
