A344116 - OEIS

%I #25 Aug 24 2022 14:38:21

%S 1,3,14,7,58,506,15,242,4060,65512,31,994,32618,1048336,33554312,63,

%T 4034,261604,16775656,1073740024,68719476016,127,16258,2095346,

%U 268427056,34359721568,4398046495984,562949953416272,255,65282,16771420,4294926472,1099511501776,281474976519136,72057594037786816,18446744073709511296

%N 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.

%H Michael De Vlieger, <a href="/A344116/b344116.txt">Table of n, a(n) for n = 1..1275</a> (rows n = 1..50, flattened)

%H Mohammad K. Azarian, <a href="https://doi.org/10.12988/imf.2022.912321">Remarks and Conjectures Regarding Combinatorics of Discrete Partial Functions</a>, Int'l Math. Forum (2022) Vol. 17, No. 3, 129-141.

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

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

%e For T(2,2), the number of relations is 2^4 and the number of onto functions is 2, so 2^4 - 2 = 14.

%e Triangle T(n,k) begins:

%e    1

%e    3     14

%e    7     58      506

%e   15    242     4060      65512

%e   31    994    32618    1048336    33554312

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

%o (PARI) T(n,k) = 2^(n*k) - k!*stirling(n, k, 2); \\ _Michel Marcus_, Jun 26 2021

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

%K easy,nonn,tabl

%O 1,2

%A _Mohammad K. Azarian_, Jun 07 2021