|
EXAMPLE
|
Triangle begins:
2 | 1;
3 | 1, 8;
4 | 1, 16, 78;
5 | 1, 32, 234, 944;
6 | 1, 64, 710, 3776, 13800;
...
In the following examples, the notation 1->{2,3} is shorthand for the set of arcs {(1,2), (1,3)}.
T(5,2) = 32 is attained with the digraph described by: 1->{2,3}, 2->{1,3}, 3->{1,2}, 4->{1,2}, 5->{1,2}. Regardless of the endofunction chosen, it will contain exactly one cycle and will therefore be connected, so T(5,2) = 2^5 = 32. One such endofunction is 1->2, 2->1, 3->1, 4->1, 5->1 which has the cycle between nodes 1 and 2.
T(5,3) = 234 is attained with the digraph constructed from the complete graph on 4 vertices plus a 5th vertex described by 5->{1,2,3}. The number of endofunctions which are spanning subgraphs is A000435(4)*3 = 78 * 3, since any of the 3 choices for the 5th vertex will not create a new cycle.
T(6,3) = 710 is attained with the digraph described by 1->{2,3,4}, 2->{1,3,4}, 3->{1,2,5}, 4->{3,5,6}, 5->{1,2,6}, 6->{1,2,3}. Up to isomorphism this is the only graph. Just 19 of the possible 3^6 = 729 endofunctions that are subgraphs of this digraph are disconnected. They have cycles described by one of the following permutations written in cycle notation: (13)(2456), (1456)(23), (135)(246), (146)(235), (12)(356), (13)(245), (13)(246), (145)(23), (146)(23). The last 5 of these omit one vertex which does not appear in a cycle.
|