#Math 454 (Combinatorics) Fall 2020 Project 3
#Database of sequences enumerating lattice walks in 3-dimensional space

#Team Leader: William Wang
#Team Members: Daniel Yang

#Needed for each sequence to publish in OEIS:
#Description
#Formula: ex. f(n+2) = f(n+1) + f(n), f(1) = 1, f(1) = 1 (Linear Recurrence Formula for Fibonacci numbers)
#Generating function: Would be great if we could find a generating function for each list of atomic steps examined.
#Simple Maple procedure
#Growth rates
#Critical exponents
#Asymptotics: a(i+1)/a(i), for i large



----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Database:



#1.
Atomic steps: {[1,0,0],[0,1,0],[0,0,1],[2,0,0],[0,2,0],[0,0,2],[1,1,1],[2,2,2]}

Sequence: [7, 248, 9741, 426719, 19725956, 945573793, 46496604627, 2330130198628, 118494430525573, 6096421370592533, 316645280669755956, 16576490090960754263, 873571148975832074915, 46298964043875792395392, 2465912665088397543706509, 131900710343673817734601975, 7082026383236714350731260152, 381526151282177147429713579019, 20615427152924581647222068540319, 1116940488173516027160256057162574]
Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[1,0,0],[0,1,0],[0,0,1],[2,0,0],[0,2,0],[0,0,2],[1,1,1],[2,2,2]}.
#Not in the OEIS

Good Sequence (stays in x>=y>=z): [2, 20, 328, 7480, 203176, 6211182, 206714074, 7336899407, 273892391945, 10649307342741, 428172896101165, 17705872314493431, 749878571241157489, 32418826689694348416, 1426841638137112004717, 63793830459393076747667, 2892158020340582449887009, 132754664924043492708227013, 6161798967035543718962532610, 288883222283520707614746820731]
Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[1,0,0],[0,1,0],[0,0,1],[2,0,0],[0,2,0],[0,0,2],[1,1,1],[2,2,2]} such that the first coordinate is always greater than or equal to the second coordinate, and the second coordinate is always greater than or equal to the third coordinate, i.e. x>=y>=z
#Not in the OEIS



#2.
Atomic steps: {[1,0,0],[0,1,0],[0,0,1],[1,1,1],[2,2,2]}

Sequence: [7, 116, 2397, 54845, 1329644, 33464881, 864627351, 22776683200, 609024723535, 16478750543705, 450190397799036, 12397538372467109, 343712858468053319, 9584085091610235280, 268571959802603851989, 7558772037473679862681, 213548821612723752662596, 6053567963855857530305675, 172122223664458866543268605, 4907277770241720608057395514]
Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[1,0,0],[0,1,0],[0,0,1],[1,1,1],[2,2,2]}.
#Not in the OEIS

Good Sequence (stays in x>=y>=z): [2, 11, 94, 1102, 15555, 248239, 4324125, 80451430, 1575855961, 32170583918, 679454086275, 14764207771916, 328660778213440, 7469735592973418, 172863516984646383, 4064255876703426163, 96904549652068261697, 2339531574588039426453, 57118224184387094924409, 1408652232800360284464616]
Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[1,0,0],[0,1,0],[0,0,1],[1,1,1],[2,2,2]} such that the first coordinate is always greater than or equal to the second coordinate, and the second coordinate is always greater than or equal to the third coordinate, i.e. x>=y>=z
#Not in the OEIS



#3.
Atomic steps: {[2,1,0],[1,2,0],[0,2,1],[0,1,2],[1,0,2],[2,0,1]} (kind of like a knight in 3d)

Sequence: [0, 6, 12, 90, 360, 2040, 10080, 54810, 290640, 1588356, 8676360, 47977776, 266378112, 1488801600, 8355739392, 47104393050, 266482019232, 1512589408044, 8610448069080, 49144928795820]
Description: Number of paths from (0,0,0) to (i,i,i) by only using the permutations of the numbers 0,1,2 as atomic steps, i.e. the atomic steps {[2,1,0],[1,2,0],[0,2,1],[0,1,2],[1,0,2],[2,0,1]}
#In the OEIS, but our description of this sequence is not mentioned in the comments

Good Sequence: [0, 1, 0, 4, 4, 31, 76, 376, 1332, 5994, 24828, 112016, 500044, 2313815, 10787288, 51270984, 246265136, 1198208064, 5887369312, 29212675530]
Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[2,1,0],[1,2,0],[0,2,1],[0,1,2],[1,0,2],[2,0,1]} such that the first coordinate is always greater than or equal to the second coordinate, and the second coordinate is always greater than or equal to the third coordinate, i.e. x>=y>=z
#Not in the OEIS



#4.
Atomic steps: {[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]}

Sequence: [0, 0, 0, 6, 0, 12, 0, 90, 0, 360, 0, 2040, 0, 10080, 0, 54810, 0, 290640, 0, 1588356]
Description: Number of paths from (0,0,0) to (i,i,i) by only using permutations of the numbers 1,2,3 as atomic steps, i.e. the atomic steps {[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]}
#Not in the OEIS

Good Sequence: [0, 0, 0, 1, 0, 0, 0, 4, 0, 4, 0, 31, 0, 76, 0, 376, 0, 1332, 0, 5994]
Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]} such that the first coordinate is always greater than or equal to the second coordinate, and the second coordinate is always greater than or equal to the third coordinate, i.e. x>=y>=z
#Not in the OEIS



#5.
Atomic steps: {[1,0,0],[0,1,0],[0,0,1],[2,0,0],[0,2,0],[0,0,2],[3,0,0],[0,3,0],[0,0,3],[1,1,1],[2,2,2],[3,3,3]}

Sequence: [7, 248, 11380, 560089, 29125351, 1569958128, 86788339340, 4888825879881, 279426677977031, 16157131667825848, 943111939336618632, 55484322315357923295, 3285892503171164775331, 195702284602101274293904, 11712934523286758880149936, 704033995863342702374989573, 42477455605755398896927508851, 2571440107359622413265590226942, 156132324067001479278797740575360, 9505535222065315340412164983124315]
Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[1,0,0],[0,1,0],[0,0,1],[2,0,0],[0,2,0],[0,0,2],[3,0,0],[0,3,0],[0,0,3],[1,1,1],[2,2,2],[3,3,3]}.
#Not in the OEIS

Good Sequence (stays in x>=y>=z): [2, 20, 392, 10076, 308794, 10635713, 398441947, 15910609458, 668028916680, 29206855477312, 1320278973721984, 61376155938006849, 2921956330642160652, 141988546015907480399, 7023987411657638359608, 352956796641795342983912, 17983988432058939859228520, 927734228865395980435400669, 48392903645851368612470472981, 2549699038949640998393766990510]
#Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[1,0,0],[0,1,0],[0,0,1],[2,0,0],[0,2,0],[0,0,2],[3,0,0],[0,3,0],[0,0,3],[1,1,1],[2,2,2],[3,3,3]} such that the first coordinate is always greater than or equal to the second coordinate, and the second coordinate is always greater than or equal to the third coordinate, i.e. x>=y>=z
#Not in the OEIS



#6.
Atomic steps: {[1,1,0],[1,0,1],[0,1,1]}

Sequence: [0, 6, 0, 90, 0, 1680, 0, 34650, 0, 756756, 0, 17153136, 0, 399072960, 0, 9465511770, 0, 227873431500, 0, 5550996791340]
Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[1,1,0],[1,0,1],[0,1,1]}.
#Not in the OEIS, but if searched, brings up A245086, which is similar (but not exactly the same)

Good Sequence (stays in x>=y>=z): [0, 1, 0, 5, 0, 42, 0, 462, 0, 6006, 0, 87516, 0, 1385670, 0, 23371634, 0, 414315330, 0, 7646001090]
Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[1,1,0],[1,0,1],[0,1,1]} such that the first coordinate is always greater than or equal to the second coordinate, and the second coordinate is always greater than or equal to the third coordinate, i.e. x>=y>=z
#Not in the OEIS

#7.
Atomic steps: {[1,1,0],[1,0,1],[0,1,1],[1,1,1]}

Sequence: [1, 7, 25, 151, 751, 4411, 24697, 146455, 862351, 5195257, 31392967, 191815339, 1177508515, 7276161907, 45154764025, 281492498455, 1761076827895, 11055132835705, 69600761349175, 439370198255401]
Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[1,1,0],[1,0,1],[0,1,1],[1,1,1]}.
#In the OEIS (A208425), but our description of this sequence is not mentioned in the comments

Good Sequence (stays in x>=y>=z): [1, 2, 5, 16, 56, 218, 897, 3907, 17677, 82864, 399191, 1970684, 9928426, 50931050, 265381781, 1402206785, 7500986535, 40574241582, 221679865651, 1222204655828]
Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[1,1,0],[1,0,1],[0,1,1],[1,1,1]} such that the first coordinate is always greater than or equal to the second coordinate, and the second coordinate is always greater than or equal to the third coordinate, i.e. x>=y>=z
#Not in the OEIS



#8.
Atomic steps: {[1,1,0],[1,0,1],[0,1,1],[2,2,0],[2,0,2],[0,2,2]}

Sequence: [0, 6, 0, 222, 0, 8280, 0, 347850, 0, 15381828, 0, 705379416, 0, 33176670912, 0, 1590179139450, 0, 77338582832940, 0, 3805317108650772]
Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[1,1,0],[1,0,1],[0,1,1],[2,2,0],[2,0,2],[0,2,2]}.
#Not in the OEIS

Good Sequence (stays in x>=y>=z: [0, 1, 0, 14, 0, 227, 0, 5095, 0, 133766, 0, 3939013, 0, 125968801, 0, 4290568003, 0, 153574639342, 0, 5721989787415]
Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[1,1,0],[1,0,1],[0,1,1],[2,2,0],[2,0,2],[0,2,2]} such that the first coordinate is always greater than or equal to the second coordinate, and the second coordinate is always greater than or equal to the third coordinate, i.e. x>=y>=z
#Not in the OEIS



#9.
Atomic steps: {[3,1,0],[1,3,0],[0,3,1],[0,1,3],[1,0,3],[3,0,1]} (long knight in 3d)

Sequence: [0, 0, 0, 12, 0, 0, 0, 900, 0, 0, 0, 124320, 0, 0, 0, 20404692, 0, 0, 0, 3565834272]
Description: Number of paths from (0,0,0) to (i,i,i) by moving through the 3D lattice like a long chess knight (3 steps in one direction, 1 in perpendicular direction), i.e. using the atomic steps {[3,1,0],[1,3,0],[0,3,1],[0,1,3],[1,0,3],[3,0,1]}
#Not in the OEIS

Good Sequence (stays in x>=y>=z): [0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 368, 0, 0, 0, 30305, 0, 0, 0, 2914078]
#Description: Number of paths from (0,0,0) to (i,i,i) by only using the atomic steps {[3,1,0],[1,3,0],[0,3,1],[0,1,3],[1,0,3],[3,0,1]} such that the first coordinate is always greater than or equal to the second coordinate, and the second coordinate is always greater than or equal to the third coordinate, i.e. x>=y>=z
#Not in the OEIS

----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

An interesting pattern:

#Same as atomic steps in #3
SeqW({[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]}, 20);
  [0, 6, 12, 90, 360, 2040, 10080, 54810, 290640, 1588356, 8676360, 47977776, 266378112, 1488801600, 8355739392, 47104393050, 266482019232, 1512589408044, 8610448069080, 49144928795820]

#Same as atomic steps in #4
SeqW({[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]}, 20);
  [0, 0, 0, 6, 0, 12, 0, 90, 0, 360, 0, 2040, 0, 10080, 0, 54810, 0, 290640, 0, 1588356]

SeqW({[2, 3, 4], [2, 4, 3], [3, 2, 4], [3, 4, 2], [4, 2, 3], [4, 3, 2]}, 20);
  [0, 0, 0, 0, 0, 6, 0, 0, 12, 0, 0, 90, 0, 0, 360, 0, 0, 2040, 0, 0]

SeqW({[3, 4, 5], [3, 5, 4], [4, 3, 5], [4, 5, 3], [5, 3, 4], [5, 4, 3]}, 20);
  [0, 0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 12, 0, 0, 0, 90, 0, 0, 0, 360]


SeqGW({[0, 1, 2], [0, 2, 1], [1, 0, 2], [1, 2, 0], [2, 0, 1], [2, 1, 0]}, 20);
  [0, 1, 0, 4, 4, 31, 76, 376, 1332, 5994, 24828, 112016, 500044, 2313815, 10787288, 51270984, 246265136, 1198208064, 5887369312, 29212675530]

SeqGW({[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]}, 20);
  [0, 0, 0, 1, 0, 0, 0, 4, 0, 4, 0, 31, 0, 76, 0, 376, 0, 1332, 0, 5994]

SeqGW({[2, 3, 4], [2, 4, 3], [3, 2, 4], [3, 4, 2], [4, 2, 3], [4, 3, 2]}, 20);
  [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 4, 0, 0, 4, 0, 0, 31, 0, 0]

SeqGW({[3, 4, 5], [3, 5, 4], [4, 3, 5], [4, 5, 3], [5, 3, 4], [5, 4, 3]}, 20);
  [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 4]

Conjecture: By increasing the values of each atomic step by 1 in every list of atomic steps, a 0 is added before the original integer sequence and between every value of the original integer sequence.
i.e. If x1,x2,x3,x4,x5,x6,... is some integer sequence corresponding to some list of atomic steps {[i],[j],[k]}, then the integer sequence corresponding to the list of atomic steps {[i~],[j~],[k~]}, where i~ is equal to i with 1 added to every value in i

Does this work for all lists of atomic steps? Let's test:
ex. #9
SeqW({[0, 1, 3], [0, 3, 1], [1, 0, 3], [1, 3, 0], [3, 0, 1], [3, 1, 0]}, 20);
  [0, 0, 0, 12, 0, 0, 0, 900, 0, 0, 0, 124320, 0, 0, 0, 20404692, 0, 0, 0, 3565834272]

SeqW({[1, 2, 4], [1, 4, 2], [2, 1, 4], [2, 4, 1], [4, 1, 2], [4, 2, 1]}, 20);
[0, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 900, 0, 0, 0, 0, 0, 0]

This seems to work!