A344112 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 functions.

1, 3, 12, 7, 56, 485, 15, 240, 4015, 65280, 31, 992, 32525, 1047552, 33551307, 63, 4032, 261415, 16773120, 1073726199, 68719430080, 127, 16256, 2094965, 268419072, 34359660243, 4398046231168, 562949952597769, 255, 65280, 16770655, 4294901760, 1099511237151

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^n, n,k >= 1.

Example

T(2,2) = (number of relations) - (number of functions) = 2^4 - 4 = 12.
Triangle T(n,k) begins:
   1;
   3,  12;
   7,  56,   485;
  15, 240,  4015,   65280;
  31, 992, 32525, 1047552, 33551307;

Mathematica

Column[Table[2^(n*k) - k^n, {n, 10}, {k, n}], Center]

Crossrefs

Cf. A101030, A199656, A036679, A344110.

Sequence in context: A175046 A093855 A355338 * A337203 A013188 A234947

Adjacent sequences: A344109 A344110 A344111 * A344113 A344114 A344115

Keyword

easy,nonn,tabl

Author

Mohammad K. Azarian, May 10 2021

Status

approved