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,5

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.

Links

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

Example

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;
  ...

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 *)

Crossrefs

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

Main diagonal gives: A231812.

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

Cf. A005095.

Sequence in context: A321956 A173315 A205975 * A009170 A009625 A308024

Adjacent sequences: A231912 A231913 A231914 * A231916 A231917 A231918

Keyword

nonn,tabl,look

Author

Alois P. Heinz, Nov 15 2013

Status

approved