A231915 Number T(n,k) of endofunctions on [n] such that at most k elements with nonempty preimage have equal preimage cardinality and non-equinumerous preimages have cardinalities that differ by at least k; triangle T(n,k), n>=0, 0<=k<=n, read by rows.

1, 0, 1, 0, 2, 4, 0, 21, 3, 9, 0, 52, 88, 40, 64, 0, 305, 705, 105, 5, 125, 0, 7836, 2736, 4086, 2286, 2106, 2826, 0, 24703, 20293, 34993, 4711, 301, 7, 5047, 0, 155688, 557488, 107472, 283872, 188224, 178816, 178368, 218688

Offset: 0

Author

Alois P. Heinz, Nov 15 2013

Keywords

• nonn
• tabl
• look

Comments

T(n,k) is defined for n,k >= 0. The triangle contains terms with k <= n. T(n,k) = T(n,n) = A231812(n) for k >= n.

T(p,p) = p! + p = A005095(p) for p prime.

T(p,p-1) = p for prime p.

Examples

			Triangle T(n,k) begins:
  1;
  0,     1;
  0,     2,     4;
  0,    21,     3,     9;
  0,    52,    88,    40,   64;
  0,   305,   705,   105,    5,  125;
  0,  7836,  2736,  4086, 2286, 2106, 2826;
  0, 24703, 20293, 34993, 4711,  301,    7, 5047;
  ...
		

Links

• Alois P. Heinz, Rows n = 0..140, flattened

Crossrefs

Columns k=0-1 give: A000007, A231807,

Main diagonal gives: A231812.

T(n,n)-T(n,n-1) gives: A000142.

Cf. A005095.

Programs

Maple

with(combinat):
b:= proc(t, i, u, k) option remember; `if`(t=0, 1,
      `if`(i<1, 0, b(t, i-1, u, k) +add(multinomial(t, t-i*j, i$j)
      *b(t-i*j, i-k, u-j, k)*u!/(u-j)!/j!, j=1.. min(k, t/i) )))
    end:
T:= (n, k)-> b(n$3, k):
seq(seq(T(n, k), k=0..n), n=0..11);

Mathematica

multinomial[n_, k_List] := n!/Times@@(k!); b[t_, i_, u_, k_] := b[t, i, u, k] = If[t == 0, 1, If[i < 1, 0, b[t, i-1, u, k] + Sum[multinomial[t, Join[{t-i*j}, Array[i&, j]]]*b[t-i*j, i-k, u-j, k]*u!/(u-j)!/j!, {j, 1, Min[k, t/i]}]]]; T[n_, k_] := b[n, n, n, k]; Table[Table[T[n, k], {k, 0, n}], {n, 0, 11}] // Flatten (* Jean-François Alcover, Dec 27 2013, translated from Maple *)