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

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.

Formula

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

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

Example

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

Mathematica

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

Prog

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

Crossrefs

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

Sequence in context: A090786 A127818 A320261 * A187772 A291796 A155886

Adjacent sequences: A344113 A344114 A344115 * A344117 A344118 A344119

Keyword

easy,nonn,tabl

Author

Mohammad K. Azarian, Jun 07 2021

Status

approved