# Results from the counting program

For explaination of the results presented here, please read the page about counting Hamilton cycles in product graphs first. Below, a table is given with solutions to problems found with the count.c program for some given graphs. The properties I tried are:
• Domino tilings (DT). Also known as matchings or 1-Factors
• 2-Factors (2F)
• Hamilton paths (HP)
• Hamilton cycles (HC)
• Spanning trees (ST)
• Spanning trees with degrees 1 and 3 (ST13)
• Path from one corner to other corner (PFT)
Solutions marked with known were known from literature. The marking zero indicate that all values are zero. When solutions were published in the paper mentioned above, they are marked with published. If I omitted a solution from the paper because of its size then it is marked with omitted. All solutions marked with new are new solutions not published before in literature to my knowledge. Some of these results were found with a newer version of the program in combination with Maple linear algebra package. These are marked with Maple. Solutions marked with others were found by others, but were not known to me at the moment I found my results. The abbreviation EIS indicates that the sequence can also be found the Encyclopedia of Integer Sequences. (see here for a list of these sequence by sequence number.)

 DT 2F HC HP ST ST13 PFT K2 known, EIS known, EIS known known, EIS known, EIS zero P3 known, EIS known known published, EIS published, EIS published known, EIS K3 published, EIS published, EIS published, EIS published, EIS published, EIS published, EIS P4 known, EIS published, EIS known, EIS published, EIS published, EIS zero new, EIS C4 published, EIS published, EIS published, EIS published, EIS published, EIS zero S4 published, EIS zero zero published, EIS published, EIS published, EIS D4 published, EIS published, EIS published, EIS published, EIS published, EIS published, EIS W4 published, EIS published, EIS published, EIS published, EIS published, EIS published, EIS K4 published, EIS published, EIS published, EIS published, EIS published, EIS published, EIS P5 known, EIS published, EIS known, EIS new, EIS Maple, EIS published, EIS new, EIS C5 published, EIS published, EIS published, EIS published, EIS published, EIS published, EIS W5 published, EIS published, EIS published, EIS published, EIS omitted, EIS omitted, EIS O5 published, EIS published, EIS published, EIS new, EIS new, EIS new, EIS K5 published, EIS published, EIS published, EIS published, EIS published, EIS published, EIS P6 known, EIS published, EIS published, EIS omitted, EIS EIS Maple, EIS C6 others, EIS others, EIS O6 published, EIS published, EIS published, EIS omitted, EIS new, EIS K6 published, EIS published, EIS published, EIS published, EIS omitted, EIS new, EIS P7 published, EIS published, EIS published, EIS C7 others, EIS others, EIS P8 published, EIS Maple, EIS Maple, EIS zero C8 others, EIS others, EIS P9 others, EIS others, EIS C9 others, EIS others, EIS P10 others, EIS others, EIS C10 others, EIS others, EIS P11 others, EIS others, EIS C11 others, EIS others, EIS P12 others, EIS C12 others, EIS others, EIS C13 others, EIS C14 others, EIS C15 others, EIS C16 others, EIS

The graphs:

• Kn: The complete graph on n vertices.
• Pn: The path graph on n vertices.
• Cn: The cycle graph on n vertices.
• S4: The graph on 4 vertices with the edges {1,2}, {1,3} and {1,4}.
• D4: The graph on 4 vertices with the edges {1,2}, {1,3}, {2,3} and {1,4}.
• W4: The graph on 4 vertices with the edges {1,2}, {1,3}, {2,3}, {2,4} and {3,4}.
• W5: The graph on 5 vertices with the edges {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,5}, {3,4} and {4,5}.
• O5: The K5 graph with one edge removed.
• O6: The octaeder graph.
 Remark: Appearently, MSIE incorrectly considers all mark-up as word delimitters. As a result it can sometimes happen that there is a single "C" at the end of a line, which should have been joint with, for example, a "(1)".

## Results for K2

For CHC it is known that C(1) = 0, C(2) = 1, and C(n) = C(n-1).

For CHP it is known that C(1) = 1, C(2) = 4, C(3) = 8, C(4) = 14, and C(n) = 3C(n-1) - 3C(n-2) + C(n-3). This is the EIS sequence A003682.

For CST it is known that C(1) = 1, C(2) = 4, and C(n) = 4C(n-1) - C(n-2). This is the EIS sequence A001353.

For CST13 it is known that C(n) = 0.

## Results for P3

For CDT it is known that C(1) = 0, C(2) = 3, C(3) = 0, C(4) = 11, and C(n) = 4C(n-2) - C(n-4). This is related to the EIS sequence A001835. See also Opera Omnia by L. Euler, Teubner, Leipzig, 1911, Series (1), Vol. 1, p. 375, Side-and-diagonal numbers by F. V. Waugh and M. W. Maxfield, Math. Mag., 40 (1967), 74-83, and Concrete Mathematics by R. L. Graham, D. E. Knuth and O. Patashnik, Addison-Wesley, Reading, MA, 1990, p. 329.

For C2F it is known that C(1) = 0, C(2) = 1, and C(n) = 3C(n-2).

For CHC it is known that C(1) = 0, C(2) = 1, and C(n) = 2C(n-2).

For CST we found C(1) = 1, C(2) = 15, C(3) = 192, C(4) = 2415, and C(n) = 15C(n-1) - 32C(n-2) + 15C(n-3) - C(n-4). This the EIS sequence A006238. See also Complexite et circuits Euleriens dans la sommes tensorielles de graphes by G. Kreweras, in J. Combin. Theory, B 24 (1978), 202-212.

For CST13 we found C(1) = 0, C(2) = 1, C(3) = 0, C(4) = 0, C(5) = 0, and C(n) = 4C(n-4).

For CPFT it is known that C(1) = 1, C(2) = 4, C(3) = 12, C(4) = 38, and C(n) = 4C(n-1) - 3C(n-2) + 2C(n-3) + C(n-4). This is the EIS sequence A006192. See also A lattice path problem by H. L. Abbott and D. Hanson, in Ars Combin., 6 (1978), 163-178. And the netnews group rec.puzzles, Frequently Asked Questions (FAQ) file (Science Section).

## Results for P4

For CDT it is known that C(1) = 1, C(2) = 5, C(3) = 11, C(4) = 36, and C(n) = C(n-1) + 5C(n-2) + C(n-3) - C(n-4). This is the EIS sequence A005178. See also page 292 of Enumerative Combinatorics I by Stanley.

For CHC it is known that C(1) = 0, C(2) = 1, C(3) = 2, C(4) = 6, and C(n) = 2C(n-1) + 2C(n-2) - 2C(n-3) + C(n-4). This is the EIS sequence A006864. See also On the number of Hamilton cycles of P4 x Pn by R. Tosic et al., Indian J. of Pure and Applied Math. 21 (1990), 403-409, and Enumeration of Hamiltonian cycles in P4 x Pn and P5 x Pn by Y.H.H. Kwong in Ars Combin. 33 (1992), 87-96.

For CST13 we found C(n) = 0.

For CPFT we found C(1) = 1, C(2) = 8, C(3) = 38, C(4) = 184, C(5) = 976, C(6) = 5382, C(7) = 29739, C(8) = 163496, C(9) = 896476, C(10) = 4913258, C(11) = 26932712, C(12) = 147657866, and C(n) = 12C(n-1) - 54C(n-2) + 124C(n-3) - 133C(n-4) - 16C(n-5) + 175C(n-6) - 94C(n-7) - 69C(n-8) + 40C(n-9) + 12C(n-10) - 4C(n-11) - C(n-12). This the EIS sequence A007786. See alse netnews group rec.puzzles, Frequently Asked Questions (FAQ) file (Science Section).

## Results for C4

For CST13 we found C(n) = 0.

## Results for S4

For C2F it is known that C(n) = 0.

For CHC it is known that C(n) = 0.

## Results for K4

For CST we found C(1) = 16, C(2) = 3456, C(3) = 686000, C(4) = 135834624, C(5) = 26894628304, and C(n) = 205C(n-1) - 1394C(n-2) + 1394C(n-3) - 205C(n-4) + C(n-5). This the EIS sequence A003773. Paul Raff found C(n) = 204C(n-1) - 1190C(n-2) + 204C(n-3) - C(n-4).

## Results for P5

For CDT it is known that C(1) = 0, C(2) = 8, C(3) = 0, C(4) = 95, C(5) = 0, C(6) = 1183, C(7) = 0, C(8) = 14824, and C(n) = 15C(n-2) - 32C(n-4) + 15C(n-6) - C(n-8). This is the EIS sequence A003775. See also page 292 of Enumerative Combinatorics I by Stanley.

For CHC it is known that C(1) = 0, C(2) = 1, C(3) = 0, C(4) = 14, C(5) = 0, C(6) = 154, and C(n) = 11C(n-2) + 2C(n-6). This is the EIS sequence A006865. See also Enumeration of Hamiltonian cycles in P4 x Pn and P5 x Pn by Y.H.H. Kwong in Ars Combin. 33 (1992), 87-96, and A Matrix Method for Counting Hamiltonian Cycles on Grid Graphs by Y.H.H. Kwong in European J. of Combinatorics 15 (1994), 277-283.

## Results for P6

For CDT it is known that C(1) = 1, C(2) = 13, C(3) = 41, C(4) = 281, C(5) = 1183, C(6) = 6728, C(7) = 31529, C(8) = 167089, C(9) = 817991, C(10) = 4213133, C(11) = 21001799, C(12) = 106912793, C(13) = 536948224, C(14) = 2720246633, and C(n) = 40C(n-2) - 416C(n-4) + 1224C(n-6) - 1224C(n-8) + 416C(n-10) - 40C(n-12) + C(n-14). This the EIS sequence A028468. See also page 292 of Enumerative Combinatorics I by Stanley, and Computation of matching polynomials and the number of 1-factors in polygraphs by P.H. Lundow, Research report, No 12, 1996, Department of Math., Umea University, Sweden.

## Results for P7

For CDT we found C(1) = 0, C(2) = 21, C(3) = 0, C(4) = 781, C(5) = 0, C(6) = 31529, C(7) = 0, C(8) = 1292697, C(9) = 0, C(10) = 53175517, C(11) = 0, C(12) = 2188978117, C(13) = 0, C(14) = 90124167441, C(15) = 0, C(16) = 3710708201969, and C(n) = 56C(n-2) - 672C(n-4) + 2632C(n-6) - 4094C(n-8) + 2632C(n-10) - 672C(n-12) + 56C(n-14) - C(n-16). This the EIS sequence A028469. See also Computation of matching polynomials and the number of 1-factors in polygraphs by P.H. Lundow, Research report, No 12, 1996, Department of Math., Umea University, Sweden.

## Results for P8

For CST13 we found C(n) = 0.

Home and email address | Counting Hamilton Cycles | Integer Sequences