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

Comments

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

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!/(k-n)!, k >= n.

Example

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;

Mathematica

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

Crossrefs

Cf. A000312, A002416, A036679, A068424, A101030, A199656, A344110, A344112, A344113, A344114.

Sequence in context: A103979 A183420 A084677 * A191995 A168207 A082609

Adjacent sequences: A344112 A344113 A344114 * A344116 A344117 A344118

Keyword

easy,nonn,tabl

Author

Mohammad K. Azarian, Jun 06 2021

Status

approved