login
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.
3
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
KEYWORD
easy,nonn,tabl
AUTHOR
Mohammad K. Azarian, Jun 06 2021
STATUS
approved