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,5

Comments

List means an ordered subset.

References

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

Links

Table of n, a(n) for n=0..44.

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

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

Adjacent sequences: A349773 A349774 A349775 * A349777 A349778 A349779

Keyword

nonn,tabl

Author

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

Status

approved