A101030 Triangle read by rows: T(n,k) = number of functions from an n-element set into but not onto a k-element set.

0, 0, 2, 0, 2, 21, 0, 2, 45, 232, 0, 2, 93, 784, 3005, 0, 2, 189, 2536, 13825, 45936, 0, 2, 381, 7984, 61325, 264816, 818503, 0, 2, 765, 24712, 264625, 1488096, 5623681, 16736896, 0, 2, 1533, 75664, 1119005, 8172576, 38025127, 132766208, 387057609, 0

Offset: 1

Author

Clark Kimberling, Nov 26 2004

Keywords

• nonn
• tabl
• easy

Examples

			T(3,3) = #(functions into) - #(functions onto) = 3^3 - 6 = 21
Triangle T(n,k) begins:
  0,
  0, 2;
  0, 2,   21;
  0, 2,   45,   232;
  0, 2,   93,   784,    3005;
  0, 2,  189,  2536,   13825,   45936;
  0, 2,  381,  7984,   61325,  264816,   818503;
  0, 2,  765, 24712,  264625, 1488096,  5623681,  16736896;
  0, 2, 1533, 75664, 1119005, 8172576, 38025127, 132766208, 387057609;
		

Links

• Mohammad K. Azarian, Remarks and Conjectures Regarding Combinatorics of Discrete Partial Functions, Int'l Math. Forum (2022) Vol. 17, No. 3, 129-141. See Theorem 2.2(v).
• D. P. Walsh, A note on non-surjective functions from [n] to [k].

Crossrefs

Cf. A199656, A036679 (diagonal).

Programs

Maple

T:=(n, k)->sum((-1)^(j-1)*binomial(k, j)*(k-j)^n, j=1..k);
seq(seq(T(n, k), k=1..n), n=1..15); # Dennis P. Walsh, Apr 13 2016

Formula

T(n,k) = A089072(n,k) - A019538(n,k).

T(n,k) = Sum_{j=1..k} (-1)^(j-1)*C(k,j)*(k-j)^n. - Dennis P. Walsh, Apr 13 2016

T(n,k) = k^n - k!*Stirling2(n,k). - Dennis P. Walsh, Apr 13 2016

Extensions

Offset corrected from 0 to 1 by Dennis P. Walsh, Apr 13 2016