login
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.
3
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
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
KEYWORD
nonn,tabl,look
AUTHOR
Alois P. Heinz, Nov 15 2013
STATUS
approved