A349776 - OEIS

%I #56 Jan 27 2023 09:05:23

%S 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 3720,4020,4050,4051,0,5040,20160,32760,36960,37590,37632,37633,0,

%U 40320,181440,322560,381360,393120,394296,394352,394353

%N 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 List means an ordered subset.

%D Kenneth P. Bogart, Combinatorics Through Guided Discovery, Kenneth P. Bogart, 2004, 57-58.

%H 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 Wikipedia, <a href="https://en.wikipedia.org/wiki/Twelvefold_way#The_twentyfold_way">The twentyfold way</a>

%F T(n, k) = Sum_{j=0..k} A271703(n, j) for n >= 0.

%F T(n, n) = A000262(n).

%F T(n, k) = Sum_{j=0..k} binomial(n-1, n-j)*n!/j!.

%F 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 |Sum_{k=0..n} (-1)^k * T(n,k)| = A096965(n). - _Alois P. Heinz_, Dec 01 2021

%e 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 If you add the set of 3 lists {(1), (2), (3)}, you get T(3, 3) = 13 = A000262(3).

%e Triangle begins:

%e   1;

%e   0,   1;

%e   0,   2,    3;

%e   0,   6,   12,   13;

%e   0,  24,   60,   72,   73;

%e   0, 120,  360,  480,  500,  501;

%e   0, 720, 2520, 3720, 4020, 4050, 4051;

%e   ...

%p T:= proc(n, k) option remember; `if`(k<0, 0,

%p       binomial(n-1, k-1)*n!/k! +T(n, k-1))

%p     end:

%p seq(seq(T(n, k), k=0..n), n=0..10);  # _Alois P. Heinz_, Dec 01 2021

%t T[n_, k_] := Sum[Binomial[n-1, n-j] n!/j!, {j, 0, k}];

%t Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Jan 27 2023 *)

%o (PARI) Lah(n, k) = if (n==0, 1, binomial(n-1, k-1)*n!/k!); \\ A271703

%o T(n, k) = sum(j=0, k, Lah(n, j)); \\ _Michel Marcus_, Nov 30 2021

%o (SageMath)

%o def T(n, k):

%o     return sum(binomial(n, i)*falling_factorial(n-1, n-i) for i in (0..k))

%o print([[T(n, k) for k in (0..n)] for n in (0..9)])  # _Peter Luschny_, Dec 01 2021

%Y Columns k=0-2 give (for n>=k): A000007, A000142, A001710.

%Y Partial sums of A271703 per row.

%Y Main diagonal is A000262.

%Y Row sums give A062147(n-1) for n>=1.

%Y Cf. A096965.

%K nonn,tabl

%O 0,5

%A _Ron L.J. van den Burg_, Nov 29 2021