cp's OEIS Frontend

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.

%I A231915 #25 Dec 16 2021 16:50:28
%S A231915 1,0,1,0,2,4,0,21,3,9,0,52,88,40,64,0,305,705,105,5,125,0,7836,2736,
%T A231915 4086,2286,2106,2826,0,24703,20293,34993,4711,301,7,5047,0,155688,
%U A231915 557488,107472,283872,188224,178816,178368,218688
%N 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.
%C A231915 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.
%C A231915 T(p,p) = p! + p = A005095(p) for p prime.
%C A231915 T(p,p-1) = p for prime p.
%H A231915 Alois P. Heinz, <a href="/A231915/b231915.txt">Rows n = 0..140, flattened</a>
%e A231915 Triangle T(n,k) begins:
%e A231915   1;
%e A231915   0,     1;
%e A231915   0,     2,     4;
%e A231915   0,    21,     3,     9;
%e A231915   0,    52,    88,    40,   64;
%e A231915   0,   305,   705,   105,    5,  125;
%e A231915   0,  7836,  2736,  4086, 2286, 2106, 2826;
%e A231915   0, 24703, 20293, 34993, 4711,  301,    7, 5047;
%e A231915   ...
%p A231915 with(combinat):
%p A231915 b:= proc(t, i, u, k) option remember; `if`(t=0, 1,
%p A231915       `if`(i<1, 0, b(t, i-1, u, k) +add(multinomial(t, t-i*j, i$j)
%p A231915       *b(t-i*j, i-k, u-j, k)*u!/(u-j)!/j!, j=1.. min(k, t/i) )))
%p A231915     end:
%p A231915 T:= (n, k)-> b(n$3, k):
%p A231915 seq(seq(T(n, k), k=0..n), n=0..11);
%t A231915 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 *)
%Y A231915 Columns k=0-1 give: A000007, A231807,
%Y A231915 Main diagonal gives: A231812.
%Y A231915 T(n,n)-T(n,n-1) gives: A000142.
%Y A231915 Cf. A005095.
%K A231915 nonn,tabl,look
%O A231915 0,5
%A A231915 _Alois P. Heinz_, Nov 15 2013