login
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.
2
1, 0, 1, 0, 2, 3, 0, 6, 12, 13, 0, 24, 60, 72, 73, 0, 120, 360, 480, 500, 501, 0, 720, 2520, 3720, 4020, 4050, 4051, 0, 5040, 20160, 32760, 36960, 37590, 37632, 37633, 0, 40320, 181440, 322560, 381360, 393120, 394296, 394352, 394353
OFFSET
0,5
COMMENTS
List means an ordered subset.
REFERENCES
Kenneth P. Bogart, Combinatorics Through Guided Discovery, Kenneth P. Bogart, 2004, 57-58.
LINKS
David Callan, Sets, Lists and Noncrossing Partitions, arXiv:0711.4841 [math.CO], 2007-2008. Also Sets, Lists and Noncrossing Partitions, Journal of Integer Sequences, Vol. 11 (2008), Article 08.1.3.
FORMULA
T(n, k) = Sum_{j=0..k} A271703(n, j) for n >= 0.
T(n, n) = A000262(n).
T(n, k) = Sum_{j=0..k} binomial(n-1, n-j)*n!/j!.
T(n, k) = A000262(n) - A271703(n, k + 1) * hypergeom([1, k - n + 1], [k + 1, k + 2], -1). - Peter Luschny, Nov 30 2021
|Sum_{k=0..n} (-1)^k * T(n,k)| = A096965(n). - Alois P. Heinz, Dec 01 2021
EXAMPLE
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)}.
If you add the set of 3 lists {(1), (2), (3)}, you get T(3, 3) = 13 = A000262(3).
Triangle begins:
1;
0, 1;
0, 2, 3;
0, 6, 12, 13;
0, 24, 60, 72, 73;
0, 120, 360, 480, 500, 501;
0, 720, 2520, 3720, 4020, 4050, 4051;
...
MAPLE
T:= proc(n, k) option remember; `if`(k<0, 0,
binomial(n-1, k-1)*n!/k! +T(n, k-1))
end:
seq(seq(T(n, k), k=0..n), n=0..10); # Alois P. Heinz, Dec 01 2021
MATHEMATICA
T[n_, k_] := Sum[Binomial[n-1, n-j] n!/j!, {j, 0, k}];
Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jan 27 2023 *)
PROG
(PARI) Lah(n, k) = if (n==0, 1, binomial(n-1, k-1)*n!/k!); \\ A271703
T(n, k) = sum(j=0, k, Lah(n, j)); \\ Michel Marcus, Nov 30 2021
(SageMath)
def T(n, k):
return sum(binomial(n, i)*falling_factorial(n-1, n-i) for i in (0..k))
print([[T(n, k) for k in (0..n)] for n in (0..9)]) # Peter Luschny, Dec 01 2021
CROSSREFS
Columns k=0-2 give (for n>=k): A000007, A000142, A001710.
Partial sums of A271703 per row.
Main diagonal is A000262.
Row sums give A062147(n-1) for n>=1.
Cf. A096965.
Sequence in context: A233672 A233670 A089134 * A305622 A269940 A350463
KEYWORD
nonn,tabl
AUTHOR
STATUS
approved