cp's OEIS Frontend

A349776 Triangle read by rows: T(n,k) is the number of partitions of set [n] into a set of at most k lists, with 0 <= k <= n. Also called broken permutations.

%I A349776 #56 Jan 27 2023 09:05:23
%S A349776 1,0,1,0,2,3,0,6,12,13,0,24,60,72,73,0,120,360,480,500,501,0,720,2520,
%T A349776 3720,4020,4050,4051,0,5040,20160,32760,36960,37590,37632,37633,0,
%U A349776 40320,181440,322560,381360,393120,394296,394352,394353
%N A349776 Triangle read by rows: T(n,k) is the number of partitions of set [n] into a set of at most k lists, with 0 <= k <= n. Also called broken permutations.
%C A349776 List means an ordered subset.
%D A349776 Kenneth P. Bogart, Combinatorics Through Guided Discovery, Kenneth P. Bogart, 2004, 57-58.
%H A349776 David Callan, <a href="http://arxiv.org/abs/0711.4841">Sets, Lists and Noncrossing Partitions</a>, arXiv:0711.4841 [math.CO], 2007-2008. Also <a href="https://cs.uwaterloo.ca/journals/JIS/VOL11/Callan/callan412.html">Sets, Lists and Noncrossing Partitions</a>, Journal of Integer Sequences, Vol. 11 (2008), Article 08.1.3.
%H A349776 Wikipedia, <a href="https://en.wikipedia.org/wiki/Twelvefold_way#The_twentyfold_way">The twentyfold way</a>
%F A349776 T(n, k) = Sum_{j=0..k} A271703(n, j) for n >= 0.
%F A349776 T(n, n) = A000262(n).
%F A349776 T(n, k) = Sum_{j=0..k} binomial(n-1, n-j)*n!/j!.
%F A349776 T(n, k) = A000262(n) - A271703(n, k + 1) * hypergeom([1, k - n + 1], [k + 1, k + 2], -1). - _Peter Luschny_, Nov 30 2021
%F A349776 |Sum_{k=0..n} (-1)^k * T(n,k)| = A096965(n). - _Alois P. Heinz_, Dec 01 2021
%e A349776 For n=3 the T(3, 2)=12 broken permutations are {(1, 2, 3)}, {(1, 3, 2)}, {(2, 1, 3)}, {(2, 3, 1)}, {(3, 1, 2)}, {(3, 2, 1)}, {(1, 2), (3)}, {(2, 1), (3)}, {(1, 3), (2)}, {(3, 1), (2)}, {(2, 3), (1)}, {(3, 2), (1)}.
%e A349776 If you add the set of 3 lists {(1), (2), (3)}, you get T(3, 3) = 13 = A000262(3).
%e A349776 Triangle begins:
%e A349776   1;
%e A349776   0,   1;
%e A349776   0,   2,    3;
%e A349776   0,   6,   12,   13;
%e A349776   0,  24,   60,   72,   73;
%e A349776   0, 120,  360,  480,  500,  501;
%e A349776   0, 720, 2520, 3720, 4020, 4050, 4051;
%e A349776   ...
%p A349776 T:= proc(n, k) option remember; `if`(k<0, 0,
%p A349776       binomial(n-1, k-1)*n!/k! +T(n, k-1))
%p A349776     end:
%p A349776 seq(seq(T(n, k), k=0..n), n=0..10);  # _Alois P. Heinz_, Dec 01 2021
%t A349776 T[n_, k_] := Sum[Binomial[n-1, n-j] n!/j!, {j, 0, k}];
%t A349776 Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Jan 27 2023 *)
%o A349776 (PARI) Lah(n, k) = if (n==0, 1, binomial(n-1, k-1)*n!/k!); \\ A271703
%o A349776 T(n, k) = sum(j=0, k, Lah(n, j)); \\ _Michel Marcus_, Nov 30 2021
%o A349776 (SageMath)
%o A349776 def T(n, k):
%o A349776     return sum(binomial(n, i)*falling_factorial(n-1, n-i) for i in (0..k))
%o A349776 print([[T(n, k) for k in (0..n)] for n in (0..9)])  # _Peter Luschny_, Dec 01 2021
%Y A349776 Columns k=0-2 give (for n>=k): A000007, A000142, A001710.
%Y A349776 Partial sums of A271703 per row.
%Y A349776 Main diagonal is A000262.
%Y A349776 Row sums give A062147(n-1) for n>=1.
%Y A349776 Cf. A096965.
%K A349776 nonn,tabl
%O A349776 0,5
%A A349776 _Ron L.J. van den Burg_, Nov 29 2021