A344116 Triangle read by rows: T(n,k) is the number of relations from an n-element set to a k-element set that are not onto functions.

1, 3, 14, 7, 58, 506, 15, 242, 4060, 65512, 31, 994, 32618, 1048336, 33554312, 63, 4034, 261604, 16775656, 1073740024, 68719476016, 127, 16258, 2095346, 268427056, 34359721568, 4398046495984, 562949953416272, 255, 65282, 16771420, 4294926472, 1099511501776, 281474976519136, 72057594037786816, 18446744073709511296

Offset: 1

Author

Mohammad K. Azarian, Jun 07 2021

Keywords

• easy
• nonn
• tabl

Examples

			For T(2,2), the number of relations is 2^4 and the number of onto functions is 2, so 2^4 - 2 = 14.
Triangle T(n,k) begins:
   1
   3     14
   7     58      506
  15    242     4060      65512
  31    994    32618    1048336    33554312
		

Links

• Michael De Vlieger, Table of n, a(n) for n = 1..1275 (rows n = 1..50, flattened)
• Mohammad K. Azarian, Remarks and Conjectures Regarding Combinatorics of Discrete Partial Functions, Int'l Math. Forum (2022) Vol. 17, No. 3, 129-141.

Crossrefs

Cf. A000312, A002416, A036679, A101030, A131689, A199656, A344110, A344112, A344113, A344115.

Programs

Mathematica

TableForm[Table[2^(n*k) - Sum[Binomial[k, k - i] (k - i)^n*(-1)^i, {i, 0, k}], {n, 5}, {k, n}]]

PARI

T(n,k) = 2^(n*k) - k!*stirling(n, k, 2); \\ Michel Marcus, Jun 26 2021

Formula

T(n,k) = 2^(n*k) - k!*Stirling2(n,k).

T(n,k) = A344110(n,k) - A131689(n,k).