0.25
0.5
0.75
1.25
1.5
1.75
2
Computer algebra for lattice path combinatorics
Published on Jul 19, 2019183 Views
Classifying lattice walks in restricted lattices is an important problem in enumerative combinatorics. Recently, computer algebra has been used to explore and to solve a number of difficult questions
Related categories
Chapter list
Computer Algebra for Lattice Path Combinatorics00:00
Computer Algebra for Enumerative Combinatorics00:25
An (innocent looking) combinatorial question01:03
Teasers03:37
Why care about counting walks?04:28
Counting walks is an old topic: the ballot problem - 105:03
Counting walks is an old topic: the ballot problem - 206:39
Counting walks is an old topic: the ballot problem - 308:06
. . . but it is still a very hot topic - 108:34
. . . but it is still a very hot topic - 209:02
Our approach: Experimental Mathematics using Computer Algebra - 109:44
Our approach: Experimental Mathematics using Computer Algebra - 210:19
Lattice walks with small steps in the quarter plane - 110:29
Lattice walks with small steps in the quarter plane - 212:16
Entire books dedicated to small step walks in the quarter plane!12:49
Small-step models of interest13:21
The 79 small steps models of interest15:10
Task: classify their generating functions!15:45
Classification criterion: properties of generating functions - 116:01
Classification criterion: properties of generating functions - 219:07
Classification criterion: properties of generating functions - 319:29
Algebraic reformulation of main task: solving a functional equation - 120:12
Algebraic reformulation of main task: solving a functional equation - 222:41
“Special” models of walks in the quarter plane22:48
Gessel walks (2000) - 123:29
Gessel walks (2000) - 224:11
Gessel walks (2000) - 324:27
Gessel walks (2000) - 425:31
Guess-and-Prove26:10
Guess-and-Prove: a toy example - 126:59
Guess-and-Prove: a toy example - 228:49
Guess-and-Prove: a toy example - 329:01
Guess-and-Prove for Gessel walks29:33
A typical Guess-and-Prove algorithmic proof31:22
Algorithmic classification of models - 136:38
Algorithmic classification of models - 237:34
Algorithmic classification of models - 337:51
Algorithmic classification of models - 438:07
Models 1–19: proofs, explicit expressions and transcendence38:33
Kernel method - 140:21
Kernel method - 241:07
Kernel method - 341:29
Kernel method - 441:50
Kernel method - 542:03
Kernel method - 642:26
Kernel method - 743:18
Kernel method - 843:28
Kernel method - 943:42
Kernel method - 1044:07
Kernel method - 1144:27
Kernel method - 1244:41
Creative Telescoping - 144:51
Creative Telescoping - 246:18
Creative Telescoping - 346:33
Creative Telescoping - 448:11
Creative Telescoping - 548:32
4G Creative Telescoping48:48
A toy transcendence proof50:23
Summary - 150:34
Summary - 251:56
Conclusion52:24