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.

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

Author

Ron L.J. van den Burg, Nov 29 2021

Keywords

• nonn
• tabl

Comments

List means an ordered subset.

Examples

			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;
  ...
		

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.
• Wikipedia, The twentyfold way

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.

Programs

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 *)

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

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