A344115 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 one-to-one functions.

1, 2, 14, 5, 58, 506, 12, 244, 4072, 65512, 27, 1004, 32708, 1048456, 33554312, 58, 4066, 262024, 16776856, 1073741104, 68719476016, 121, 16342, 2096942, 268434616, 34359735848, 4398046506064, 562949953416272, 248, 65480, 16776880, 4294965616, 1099511621056

Offset: 1

Author

Mohammad K. Azarian, Jun 06 2021

Keywords

• easy
• nonn
• tabl

Comments

If n=k, then T(n,k) = 2^(n^2) - n!, which is A344114, and if kA344110.

Examples

			For T(2,2): the number of relations is 2^4 and the number of one-to-one functions is 2, so 2^4 - 2 = 14 and thus T(2,2) = 14.
Triangle T(n,k) begins:
   1;
   2,   14;
   5,   58,   506;
  12,  244,  4072,   65512;
  27, 1004, 32708, 1048456, 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, A068424, A101030, A199656, A344110, A344112, A344113, A344114.

Programs

Mathematica

Table[2^(n*k) - k!/(k - n)!, {k, 10}, {n, k}] // Flatten

Formula

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