--> Use Turbowarp for faster results: turbowarp.org/1323944773 ___ This project calculates the number of unrooted trees with degree constraint four with n nodes, or simply the number of structural isomers of alkane with n carbon atoms. ... The method used is an algorithmic translation of the Cayley-Pólya-Henze-Blair recursive formulas. It is a bottom-up (tabulation) dynamic programming algorithm. Do not enter large n to avoid freezing your computer. (Note that ‘large’ n is subjective ;D ) 1874 - Arthur Cayley realized that organic molecules like alkanes could be drawn and treated as mathematical graphs called 'trees'. He attempted to count them, but doing it manually for large molecules was nearly impossible because of how easily branches flip and create duplicate structures. 1931 - Chemists Henry R. Henze and Charles M. Blair made a massive breakthrough. They created the first recursive mathematical formulas to count isomers. They realized you can find the count of a large molecule by multiplying the combinations of its smaller branches. The bicentroidal and centroidal part in my code comes straight from this. 1937 - Mathematician George Pólya published the Pólya Enumeration Theorem, a legendary mathematical formula used to count objects that have geometric symmetries (like a spinning 3D molecule). Pólya used complex calculus-like generating functions, cycle indices to account for these rotations. I used deterministic triplet and quartet conditions inspired from this.
--> A “brief” outline of my algorithm: Step 1) Given a target alkane size n, calculate max_k = floor of n divided by 2. Create a reference table with rows from 0 to max_k and three columns: R, A, and B. Fill row 0 and row 1 with these exact numbers: Row 0: R = 1, A = 1, B = 1 Row 1: R = 1, A = 1, B = 1 ___ Step 2) For every row k starting from 2 up to max_k, run this exact calculation: a. Set the remaining sum S = k - 1. b. Find all combinations of (a,b,c) where a+b+c = S and a is greater than or equal to b, b is greater than or equal to c, and c is greater than or equal to 0 c. Check the values of a, b, and c against these four strict conditions to find a score for the triplet: - If a > b and b > c: score = R_a x R_b x R_c - If a = b and b > c: score = A_a x R_c - If a > b and b = c: score = R_a x A_b - If a = b and b = c: score = B_a d. Add up the scores of all valid triplets found for that k. This total sum is your R_k value. e. Use R_k to calculate and fill in the rest of row k before moving to the next row: A_k = (R_k x (R_k + 1))/2 B_k = (R_k x (R_k + 1) x (R_k + 2))/6 ___ Step 3) Look at your target alkane size n: - If n is odd, Bicentered = 0 - If n is even, look at row n divided by 2 in your table. Bicentered = the value in column A of that row. ___ Step 4) Set the remaining sum S = n - 1. Run this exact calculation: a. Loop a from floor of S divided by 2 down to ceiling of S divided by 4. b. For each a, loop b from min(a, S - a) down to ceiling of (S - a) divided by 3. c. For each a and b, loop c from min(b, S - a - b) down to ceiling of (S - a - b) divided by 2. d. For each a, b, and c, calculate d = S - a - b - c. e. Check the values of a, b, c, and d against these conditions to find a score for the quartet: - If a > b and b > c and c > d: score = R_a x R_b x R_c x R_d - If a = b and b > c and c > d: score = A_a x R_c x R_d - If a > b and b = c and c > d: score = R_a x A_b x R_d - If a > b and b > c and c = d: score = R_a x R_b x A_c - If a = b and c = d and a > c: score = A_a x A_c - If a = b and b = c and c > d: score = B_a x R_d - If a > b and b = c and c = d: score = R_a x B_b - If a = b and b = c and c = d: score = (R_a x (R_a + 1) x (R_a + 2) x (R_a + 3)) divided by 24 f. Add up the scores of all valid quartets found. This total sum is your Unicentered value. ___ Step 5) Total Isomers = Bicentered + Unicentered ___ --> Useful links: - oeis.org/A000602 - cs.uwaterloo.ca/journals/JIS/cayley.html - wikipedia.org/wiki/Polya_enumeration_theorem - oeis.org/A000598/a000598_2.pdf
