cp's OEIS Frontend

A359686 Triangle read by rows: T(n,k) is the minimum number of connected endofunctions that are spanning subgraphs of a semi-regular loopless digraph on n vertices each with out-degree k.

%I A359686 #16 Jan 04 2024 14:31:09
%S A359686 1,1,8,0,14,78,0,22,213,944,0,0,529,3400,13800,0,0
%N A359686 Triangle read by rows: T(n,k) is the minimum number of connected endofunctions that are spanning subgraphs of a semi-regular loopless digraph on n vertices each with out-degree k.
%C A359686 An endofunction represented as a digraph is one in which every vertex has out-degree 1. Loopless means that there are no fixed points in the function. The digraph of a connected endofunction is unicyclic (contains exactly one cycle).
%C A359686 In the case k = 1, the graphs considered have vertices with out-degree 1 and the entire graph is the only spanning subgraph that is an endofunction. Hence T(n,1) = 0. (n > 3 because when n = 2, 3 it still will be unicyclic.)
%C A359686 In the case k = n-1, the graphs considered are the complete digraphs and every connected endofunction on the vertex set is a subgraph. Hence T(n, n-1) = A000435(n), which gives the total number of connected endofunctions without fixed points.
%F A359686 T(n,1) = 0 for n > 3, otherwise 1.
%F A359686 T(n,n-1) = A000435(n).
%F A359686 T(n,k) = 0 for 2*k + 2 < n.
%e A359686 Triangle begins:
%e A359686   2 | 1;
%e A359686   3 | 1,  8;
%e A359686   4 | 0, 14,  78;
%e A359686   5 | 0, 22, 213,  944;
%e A359686   6 | 0,  0, 529, 3400, 13800;
%e A359686   ...
%e A359686 In the following examples, the notation 1->{2,3} is shorthand for the set of arcs {(1,2), (1,3)}.
%e A359686 T(5,2) = 22 is attained with the digraph described by: 1->{4,5}, 2->{3,5}, 3->{2,4}, 4->{1,3}, 5->{1,2}.
%Y A359686 Cf. A000435, A359628.
%K A359686 nonn,tabl,more
%O A359686 2,3
%A A359686 _Yali Harrary_, Jan 11 2023