Part I: Randomly generating and drawing self-avoiding paths [35 marks] 1. [10 marks] Explain in detail how the function enumerate_paths and the related code defined above works. More specifically:...

Part I: Randomly generating and drawing self-avoiding paths [35 marks]

1. [10 marks]Explain in detail how the functionenumerate_pathsand the related code defined above works. More specifically:

• Explain the purpose of the variableedges.


• Explain the purpose of the functionmake_step.


• Explain how the functionenumerate_pathsworks. In particular:
  
  
  • Describe the input parameters and the output of this function, in particular the meaning ofPath=[[0, 0]].
  
  
  • Explain the purpose of the variablenext_points.
  
  
  • Explain the purpose of the variableallowed_points.
  
  
  • Most importantly, explain the meaning ofcount=sum([enumerate_paths(n-1, Path+[point]) for point in allowed_points]).
  
  
  
  


• Run the command[enumerate_paths(n, [[0, 0], [1, 0]]) for n in range(10)]and explain the output.

Your explanation(s) should make it clear how the functionenumerate_pathsactually does its job, i.e. enumerating all self-avoiding lattice paths with a given number of steps. For example, it is not enough to say "the variableedgesis a list with four elements". That is obvious. You should instead explain what those four elements represent in the context of the problem, and how they are used in the functionenumerate_paths.

{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# MTH5001: Introduction to Computer Programming 2019/20\n", "\n", "## Final Report Project: \"Lattice Paths\"" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You must write your answers in this Jupyter Notebook, using either Python code or Markdown, as appropriate. (We have left blank code and/or Markdown cells for you, but you may also create additional cells if you feel you need to.)\n", "\n", "Your code must be **well documented**. As a rough guide, you should aim to include one line of comments for each line of code. \n", "\n", "You should also use **sensible variable names**, so that your code is as clear as possible. If your code works but is difficult to read, then you may lose marks.\n", "\n", "### Marking:\n", "\n", "The project is worth 70% of your final mark for this module.\n", "\n", "The total number of marks available for the project is 100. Attempt all parts of all questions.\n", "\n", "When writing up your project, good writing style is even more important than in written exams.\n", "\n", "> To get full marks in any assessed work (tests or exams) you must normally not only give the right answers but also explain your working clearly and give reasons for your answers by writing legible and grammatically correct English sentences. Mathematics is about logic and reasoned arguments and the only way to present a reasoned and logical argument is by writing about it clearly. Your writing may include numbers and other mathematical symbols, but they are not enough on their own. You should copy the writing style used in good mathematical textbooks, such as those recommended for your modules. **You can expect to lose marks for poor writing (incorrect grammar and spelling) as well as for poor mathematics (incorrect or unclear logic).**\n", "\n", "### Plagiarism warning:\n", "\n", "Your work will be tested for plagiarism, which is an assessment offence. In particular, while only academic staff will make a judgement on whether plagiarism has occurred in a piece of work, we will use the software \"Turnitin\" to help us assess how much of your work matches other sources. You will have the opportunity to upload your work, see the Turnitin result, and edit your work accordingly before finalising your submission.\n", "\n", "If necessary, you may summarise relevant parts of books, online notes or other resources.\n", "However, you must use your own words as far as possible, and you **must** reference any sources that you use. If you decide to work with other students on parts of the project, then you **must** write up your work individually. \n", "\n", "You should also note that some of the questions are personalised in the sense that you will need to import and manipulate data that will be unique to you (i.e. no other student will have the same data)." ] }, { "attachments": { "image.png": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAWoAAAD4CAYAAADFAawfAAAVfUlEQVR4Ae2dX6hmVRmHf2JG/sWwJCU/RyEyGyQ8gRUlEhQiQiTVVdFFMbeCCJqGo3Qh0o1RiBcRFY3eBBZNOUKDgTBNchxH00zxfwOW3YoQRifWuPe49tnf2fu8a+1vnXeveTYc9t93r7We913P2Wefb+ZILBCAAAQgAAEIQAACEIAABCAAAQhAAAIQgAAEIAABCEAAAhCAAAQgAAEIQAACEDhO4LzzzttYW1vjCwbUADVADWyzBiT9u+i3kCBpFghAAAIQ2D4BSeuIevu8uBICEIBAcQKIujhyGoQABCBgI4Cobby4GgIQgEBxAoi6OHIahAAEIGAjgKhtvLgaAhCAQHECiLo4chqEAAQgYCOAqG28uBoCEIBAcQKIujhyGoQABCBgIzCFqF+V9FdJR7dzs5r+wctDR45tfO7ugxu7btl/fB32WSAAAQhMTWA7bh37BzFB1B8au6g9X4uog5Qv+/7DGxffsv/EV9hH1lOXKPeDAAQQdWINhCfpWNLtdjjOAgEIQGBKAlOI+hVJRyQ9IWlP++S8aR2Oh3+rvr5YLKbs/47dK7zuaOUcr8NxFghAAAJTEphC1Bc2Uj5f0lOSrt4k6c5uLa8+eKKesgy5FwQgMERgClHHIr5T0s3xgc3btYiad9RDZcU5CEBgSgK5oj5T0tmNjMP2IUnXbpZzvF+LqEMSgqw/dtsfjr8CCU/Y/CJxytLkXhCAQEsgV9SXNq87wiuPZyXdHkt52XZNog4Qv3H/oeNfLVDWEIAABKYmkCvqZS4ePIaop04h94MABGongKgzM8wTdSZAwiEAgVECiHoU0fAFiHqYD2chAIF8Aog6kyGizgRIOAQgMEoAUY8iGr4AUQ/z4SwEIJBPAFFnMkTUmQAJhwAERgkg6lFEwxcg6mE+nIUABPIJIOpMhog6EyDhEIDAKAFEPYpo+AJEPcyHsxCAQD4BRJ3JEFFnAiQcAhAYJYCoRxENX4Coh/lwFgIQyCeAqDMZIupMgIRDAAKjBBD1KKLhCxD1MB/OQgAC+QQQdSZDRJ0JkHAIQGCUAKIeRTR8AaIe5sNZCEAgnwCizmSIqDMBEg4BCIwSQNSjiIYvQNTDfDgLAQjkE0DUmQwRdSZAwiEAgVECiHoU0fAFiHqYD2chAIF8Aog6kyGizgRIOAQgMEoAUY8iGr4AUQ/z4SwEIJBPAFFnMkTUmQAJhwAERgkg6lFEwxcg6mE+nIUABPIJIOpMhog6EyDhEIDAKAFEPYpo+AJEPcyHsxCAQD4BRJ3JEFFnAiQcAhAYJYCoRxENX4Coh/lwFgIQyCeAqDMZIupMgIRDAAKjBBD1KKLhCxD1MB/OQgAC+QQQdSZDRJ0JkHAIQGCUwFSiPlXSk5L2a2RZW1sb7dScLkDUc8oWfYXAPAlMJeqbJD2AqOdZBPQaAhDwTWAKUX9U0kFJX0TUvpNN7yAAgXkSmELUv5a0JukaRD3PIqDX7xLYd/i1jfZVFutD22YRuLGslkCuqK+XdF/zWnpI1HuahtYXi8VqR1T47u2ELtwsza2AQMjl7r0Hti2oNvcn87rltYJ0cMuIQK6o75Z0TNKrkv4p6W1Jvxr6fSK/TIzos+mKQCtcV51y3hmYlUlQrqhjJw89UZ+4DlGXSSyt2AkgHZjZCZSJQNSZnJncmQAdhZNLezJgZmeWEjGlqE88NQ9t8ESdkiZiShBAOnbKMLMzS4lA1CnUohgKNYIx801yaU8gzOzMUiIQdQq1KIZCjWDMfJNc2hMIMzuzlAhEnUItiqFQIxgz3ySX9gTCzM4sJQJRp1CLYijUCMbMN8mlPYEwszNLiUDUKdSiGAo1gjHzTXJpTyDM7MxSIhB1CrUohkKNYMx8k1zaEwgzO7OUCESdQi2KoVAjGDPfJJf2BMLMziwlAlGnUItiKNQIxsw3yaU9gTCzM0uJQNQp1KIYCjWCMfNNcmlPIMzszFIiEHUKtSiGQo1gzHyTXNoTCDM7s5QIRJ1CLYqhUCMYM98kl/YEwszOLCUCUadQi2Io1AjGzDfJpT2BMLMzS4lA1CnUohgKNYIx801yaU8gzOzMUiIQdQq1KIZCjWDMfJNc2hMIMzuzlAhEnUItiqFQIxgz3ySX9gTCzM4sJQJRp1CLYijUCMbMN8mlPYEwszNLiUDUKdSiGAo1gjHzTXJpTyDM7MxSIhB1CrUohkKNYMx8k1zaEwgzO7OUCESdQi2KoVAjGDPfJJf2BMLMziwlAlGnUItiKNQIxsw3yaU9gTCzM0uJQNQp1KIYCjWCMfNNcmlPIMzszFIiEHUKtSiGQo1gzHyTXNoTCDM7s5QIRJ1CLYqhUCMYM98kl/YEwszOLCUCUadQi2Io1AjGzDfJpT2BMLMzS4lA1CnUohgKNYIx801yaU8gzOzMUiIQdQq1KIZCjWDMfJNc2hMIMzuzlAhEnUItiqFQIxgz3ySX9gTCzM4sJQJRp1CLYijUCMbMN8mlPYEwszNLiUDUKdSiGAo1gjHzTXJpTyDM7MxSIhB1CrUohkKNYMx8k1zaEwgzO7OUiFxRf0DS45KekvSspLs0sqytraX0020Mheo2NeaOkUszsg2Y2ZmlROSK+hRJZzVuPk3SXyR9ZsjViDolTcSUIIB07JRhZmeWEpEr6tjJZ0g6Iumq+ODm7RpFvXvvgRNPFm3hsj40OyZtHlMm0skaE+q85eat5vcdfq2atEwh6lMlHZX0lqR7Nou52d/TNLS+WCyqgRcGEorBW4HSn/RvEjVN7hITzWv9t988SjAo0cYUom7dfK6kRyXtbg8sW9f2RF0iSbQBAQjYCLQPK7Yov1dPKerg5b2Sbl4m6PYYovZbDPQMArUQQNStcd9df1hSeJIOy+mSHpN0fbO/dIWoa5kKjAMCfgkg6q5+r5D0pKSnJT0j6Y7u6f4eovZb3PQMArUQQNR995qOIOpapgLjgIBfAojapOX+xYjab3HTMwjUQgBR991rOoKoa5kKjAMCfgkgapOW+xcjar/FTc8gUAsBRN13r+kIoq5lKjAOCPglgKhNWu5fjKj9Fjc9g0AtBBB1372mI4i6lqnAOCDglwCiNmm5fzGi9lvc9AwCtRBA1H33mo4g6lqmAuOAgF8CiNqk5f7FiNpvcdMzCNRCAFH33Ws6gqhrmQqMAwJ+CSBqk5b7FyNqv8VNzyBQCwFE3Xev6QiirmUqMA4I+CWAqE1a7l+MqP0WNz2DQC0EEHXfvaYjiLqWqcA4IOCXAKI2abl/MaL2W9z0DAK1EEDUffeajiDqWqYC44CAXwKI2qTl/sWI2m9x0zMI1EIAUffdazqCqGuZCowDAn4JIGqTlvsXI2q/xU3PIFALAUTdd6/pCKKuZSowDgj4JYCoTVruX4yo/RY3PYNALQQQdd+9piOIupapwDgg4JcAojZpuX8xovZb3PQMArUQQNR995qOIOpapgLjgIBfAojapOX+xYjab3HTMwjUQgBR991rOoKoa5kKjAMCfgkgapOW+xcjar/FTc8gUAsBRN13r+kIoq5lKjAOCPglgKhNWu5fjKj9Fjc9g0AtBBB1170XSXpU0nOSnpV0Y/d0fw9R1zIVGAcE/BJA1F33XiDpyubQ2ZJekHR595LuHqL2W9z0DAK1EEDUXe9u3vutpC9tPhjvI+papgLjgIBfAog6tm53e5ek1yWd0z18fG+PpPXwtVgs/GaXnkEAAlUQQNRLLCzpLElPSLph+en3jvJEXcU8YBAQcE0AUb/n3HbrNEmPSLqpPTC0RtSu65vOQaAKAoi6a+FTJP1S0r3dw1vvIeoq5gGDgIBrAoi66+DPS9qQ9LSko83Xdd1LunuI2nV90zkIVEEAUXe9a95D1FXMAwYBAdcEELVZzd0ARO26vukcBKoggKi73jXvIeoq5gGDgIBrAojarOZuAKJ2Xd90DgJVEEDUXe+a9xB1FfOAQUDANQFEbVZzNwBRu65vOgeBKggg6q53zXuIuop5wCAg4JoAojaruRuAqF3XN52DQBUEEHXXu+Y9RF3FPGAQEHBNAFGb1dwNQNSu65vOQaAKAoi6613zHqKuYh4wCAi4JoCozWruBiBq1/VN5yBQBQFE3fWueQ9RVzEPGAQEXBNA1GY1dwMQtev6pnMQqIIAou5617yHqKuYBwwCAq4JIGqzmrsBiNp1fdM5CFRBAFF3vWveQ9RVzAMGAQHXBBC1Wc3dAETtur7pHASqIICou9417yHqKuYBg4CAawKI2qzmbgCidl3fdA4CVRBA1F3vmvcQdRXzgEFAwDUBRG1WczcAUbuubzoHgSoIIOqud817iLqKecAgIOCaAKI2q7kbgKhd1zedg0AVBBB117vmPURdxTxgEBBwTQBRm9XcDUDUruubzkGgCgKIuutd8x6irmIeMAgIuCaAqM1q7gYgatf1TecgUAUBRN31rnkPUVcxDxgEBFwTQNRmNXcDELXr+qZzEKiCAKLuevdnkt6U9Ez38NZ7iLqKecAgIOCaAKLuOvhqSVciatc1S+cgcNIRQNRdUYe9XYj6pJsHDBgCrgkgakTtukDbzu07/NpGW6ysD22bReDGsn0CXuts994Dx3O+/ZH4vlLSel+9tiPbeaLe0zS0vlgsfBOppHdBzm2xIurtibrlVUkJFBmG5zqr6ZtuKVGfUD+/TCwyf048QZZprY5W2m9odYymzChgVoYzoi7DuXgrTCA7cpjBzE6gTESuqB+U9IakdyQdk/SdE4/OW2zwRF0msUjHzhlmMLMTKBORK+otdLz1YURdJrFIx84ZZjCzEygTgajLcC7eCtKxI4cZzOwEykQg6jKci7eCdOzIYQYzO4EyEYi6DOfirSAdO3KYwcxOoEwEoi7DuXgrSMeOHGYwsxMoE4Goy3Au3grSsSOHGczsBMpEIOoynIu3gnTsyGEGMzuBMhGIugzn4q0gHTtymMHMTqBMBKIuw7l4K0jHjhxmMLMTKBOBqMtwLt4K0rEjhxnM7ATKRCDqMpyLt4J07MhhBjM7gTIRiLoM5+KtIB07cpjBzE6gTASiLsO5eCtIx44cZjCzEygTgajLcC7eCtKxI4cZzOwEykQg6jKci7eCdOzIYQYzO4EyEYi6DOfirSAdO3KYwcxOoEwEoi7DuXgrSMeOHGYwsxMoE4Goy3Au3grSsSOHGczsBMpEIOoynIu3gnTsyGEGMzuBMhGIugzn4q0gHTtymMHMTqBMBKIuw7l4K0jHjhxmMLMTKBOBqMtwLt4K0rEjhxnM7ATKRCDqMpyLt4J07MhhBjM7gTIRiLoM5+KtIB07cpjBzE6gTASiLsO5eCtIx44cZjCzEygTgajLcC7eCtKxI4cZzOwEykQg6jKci7eCdOzIYQYzO4EyEYi6DOfirSAdO3KYwcxOoEwEoi7DuXgrSMeOHGYwsxMoE4Goy3Au3grSsSOHGczsBMpEIOoynIu3gnTsyGEGMzuBMhFTiPpaSc9LelHSrRpZ1tbWyozsJG7loSPHNj522x82Lr5l/8bn7j64EfZZxgkg6nFGm6+A2WYiq9nPFfWpkl6SdKmk90t6StLlQ65G1KtJZHvXIOXLvv/wcUkHUYevsI+sW0Jbr5HO1my2OgOzrchMezxX1J+V9Egk5u9JCl9bLoh62gRuvlt4gm4FHa/DcZZhAkE6u/ce2Gjlw/rQKIuW1zBZzuYSyBX11yT9NLLytyT9JNpvN/c0Da0vFovcPhM/QGBX8xQdSzpsh+MswwT2HX5tVEzIuy/vwI1ltQRyRf31JaL+cWvnZWueqFebUJ6oV8uXu0NgJwjkippXHzuRtYE2eUc9AIdTEJgpgVxRv0/Sy5IuiX6Z+MllT9LtMZ6oV18pQdbhyTq87ghrfpG4eua0AIFVEsgVdfDvdZJeaD79cXsr5K3WiHqV6eTeEIBAjQSmEPVWTl56HFHXWEaMCQIQWCUBRL1KutwbAhCAwAQEEPUEELkFBCAAgVUSQNSrpMu9IQABCExAAFFPAJFbQAACEFglAUS9SrrcGwIQgMAEBBD1BBC5BQQgAIFVEkDUq6TLvSEAAQhMQKC4qCX9u2l0PWH9akJMSjvWGPolwczOwMLMa42FMXjtm9d+pTAL3pzNEgbocaFf9qzAzMbMK68wCq9989ovz8xsVbnF1V7B068tEjZwGGYDcJac8sordNVr37z2yzOzJaVnP+QVPP0il3YCtgivNRZG4bVvXvvlmZmtKre4OvwBAo8L/bJnBWY2Zl55hVF47ZvXfnlmZqtKroYABCAAAQhAAAIQgAAEIAABCEAAAicfgR9K+rukpyU9JOlcRwjC3498VtL/JH3aQb+ulfS8pBcl3eqgP20XfibpTUnPtAecrC+S9Kik55o83uikXx+Q9Likp5p+3eWkX203TpX0pKT97QEn6/AZ6r9KOursl53BWb9uPBZqLfw5w+qWL0sKf/4rLPc0X83ujq8+Ienjkv7kQNRh8rwk6dLoT6RdvuOE3u3A1ZKudCjqC5p+hV6e3fzVIg/MTpF0VpO70yT9RdJnnOQydOMmSQ84FfWHHHFqu/ILSd9tdt7v7GGz7eOk669K2jfpHae5mQdRm//o8DRD3/ZddjkU9ebO/1bSlzYf3OH9MyQdkXTVDvejbf6jkg5K+iKibpEMrs+R9Iqk8M33pFl+J+mbDkfrQdRfk/TTiM23JP0k2t/pTe+iDv17XVKYWB6W8BNS+BH+LWc/RYYf4dckXeNQ1EGI4ZvaE44+Pvip5jXWz5vXRWGOnumhwFL68MfmaSu8w4y/vhLdLPwR3fCOuvR3pu30zYOow/vyzaL+ccRvpzc9izq8ZgiT+4adhrSk/fB+M7xH373kXOlD10u6r2nUo6gvbPp2fvN+P7xy2+kl/O7qv9FPRD+S9IOd7tSq2v+2pD9LCj8Gelw8iJpXH2mVEd4BP9K8d027w+qj9kq6efXNjLZwt6RjzX/I9E9Jb0v61WjUzlxwpxNmH2l4tRS+IOn37U5N6/BJhr9J+rDjQXkQdfiF68uSLol+mfhJR8w8PlGHn85+KeleR5xCV0Ktt59uOl3SY5LC06ynxdsTdXidEH4hHJawfUhScIeHJeQvfOggLOEbSPgkW3VL+KjZP5r3deGd3f2ORhh+uRmeMP4j6V/Nk9lOdu+65pML4dMf4VWRl+VBSW9Ieqfh9R0nHfu8pI3mo5+htsJXYLjTyxXN+8zwkdTwKvCOne7Qkva9iTp82il8nLH9SKOn+g/vqcP/QRLy+RtJH1zCk0MQgAAEIAABCEAAAhCAAAQgAAEIQAACEIAABCAAAQhAAAIQgAAEIAABCEAAAhCAAAQgAAEIQAACEIAABCAwQOD/Kpn6FrPa89wAAAAASUVORK5CYII=" } }, "cell_type": "markdown", "metadata": {}, "source": [ "## Background information\n", "\n", "In this project you will learn about a field of mathematics called [lattice paths](https://en.wikipedia.org/wiki/Lattice_path). \n", "(You should read the linked article for an introduction.)\n", "\n", "An important class of lattice paths are **simple random walks** on the square lattice $\\mathbb Z^2$: starting at the origin $(0,0)$, these paths are generated by taking steps of length $1$ in randomly chosen directions (east, north, west, or south). For example, taking a north step, then an east step, then a south step gives the path $(0,0)$, $(0,1)$, $(1,1)$, $(1,0)$. As there are four possibilities for each step, there are precisely $4^n$ different simple random walks with $n$ steps.\n", "\n", "In this project we will also consider lattice paths with **self-avoidance**, i.e. lattice paths that are not allowed to step onto themselves. For example, the self-avoiding path in the picture below starts at the origin, has $20$ steps, and ends at position $(-1,5)$.\n", "\n", "\n", "\n", "In general, there are fewer self-avoiding lattice paths than there are simple random walks, because requiring that a path not step onto itself limits the choice of direction at each step. For example, there are $4^3 = 64$ simple random walks with $n=3$ steps (on $\\mathbb Z^2$, starting at the origin), but only $4\\cdot3\\cdot3=36$ self-avoiding lattice paths with $n=3$ steps (you might like to draw them all on a piece of paper to convince yourself). As mentioned above, the number of $n$-step simple random walks is precisely $4^n$; one of your first tasks will be to investigate how the number of $n$-step self-avoiding paths grows as a function of $n$.\n", "\n", "We will also consider the effect of random **defects** of the lattice, where certain points of the lattice are randomly removed and therefore cannot be visited by a lattice path. As with self-avoidance, it should be clear that such defects reduce the overall number of allowed paths compared to simple random walks." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Some code to get you started\n", "It is very easy to find code for enumerating (i.e. counting all possible) self-avoiding lattice paths on the internet, so we'll spare you the effort and provide some code. The function `enumerate_paths` given below enumerates all $n$-step self-avoiding lattice paths on the square lattice $\\mathbb Z^2$ (starting at the origin). The code is adapted from https://oeis.org/A001411." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# You may wish to use this cell to import some useful packages; two suggestions have been included for you\n", "import numpy as np\n", "import matplotlib.pyplot as plt" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "# Code for counting n-step self-avoiding lattice paths on the square lattice\n", "# Code from Robert FERREOL, Nov 30 2018, rewritten by Thomas PRELLBERG, Feb 26 2020\n", "# Source: https://oeis.org/A001411, accessed Feb 20 2020\n", "\n", "edges = [[1, 0], [0, 1], [-1, 0], [0, -1]]\n", "\n", "make_step = lambda point, edge: [x+y for x,y in zip(point, edge)]\n", "\n", "def enumerate_paths(n, Path=[[0, 0]]):\n", " if n==0: \n", " count=1\n", " else:\n", " next_points = [make_step(Path[-1], edge) for edge in edges]\n", " allowed_points = [point for point in next_points if point not in Path]\n", " count = sum([enumerate_paths(n-1, Path+[point]) for point in allowed_points])\n", " return count" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Notice that the above code is uncommented. This is because one of your tasks is to clearly explain what each line of this code does (see Question 1 below).\n", "\n", "First let's use the function `enumerate_paths` to count the number of $n$-step self-avoiding lattice paths for $n=1,2,\\dots,10$:" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44100]" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "[enumerate_paths(n) for n in range(11)]" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "We see that the number of $n$-step self-avoiding lattice paths on the square lattice is given by the sequence\n", "\n", "$$1, 4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44100, \\ldots\\;.$$\n", "\n", "That is, there is exactly one such path for $n=0$, four paths for $n=1$, $12$