# Counting number of paths on a triangular lattice

I am trying to find an effective way to approach this problem. Consider a triangular lattice. I am interested in counting the number of directed red paths starting at a given point ($0$ in the figure). At each step, the red path can move left or right. Additionally however, it can branch into two coloured paths (both of the same color), one moving left and one right. There are $n$ colour for the branches all distinct from the red one of the single path. The coloured branch can evolve independently (each moving left/right at each step). However, if they meet at the same point they annihilate. Then, either a red path starts from this point, or another branch with an arbitrary colour, among the $n$ available.

Note that only the red path can branch, so that at any time slice there are at most two paths.

There is no constraint about the configuration on the final step.

I would like to have the asymptotic behaviour of the number of these configurations $N(t)$ for large $t$, i.e. the lattice height. We start from $N(0) = 1$. We have $N(1) = n+2$ (the red path can go left/right or branch in $n$ coloured paths). For the case $n=3$, I get the sequence: $\{1, 5, 22, 95, 406, 1724, 7288, 30707, 129046, \ldots \}$.

My question is about the value of $\alpha$ where $$N(t) \simeq \alpha^t \qquad t \to \infty \;.$$

I think one can write recursive equations, but I would be more interested in an approach which assumes directly $t$ large and aims at computing $\alpha$.

Do you have any suggestions?

• If you branch, you can have 2 ways (in same level) with 2 differents colours ? A branched way can branche again recursively ? I mean, can you have for one possibility after "t" steps, "t" branches ? I only want to clarify this. – Daniel Pol Dec 13 '17 at 10:46
• no only the red path can branch; once it branches, it takes one of the n other colours (all different from red) and they do not branch again. Nevertheless, they can annihilate in a red path again and re-branch in another color. – abenassen Dec 13 '17 at 11:09
• I not finished to found a full answer, but i have some suggestions : First found for classes of ways : 1) red (can go left or right), 2) branche in one colour of n (one double way), 3) same colour (can go left or right), 4) branch come together in order to continue with 1) (red) (this have only a double unique way). Now my suggestion is to make A) englobe 1). and B) englobe 2)3)4). A) is a red way. B) is a coloured way. Now we have a seccession or red-colour-red-colour-... with differents lengths. colour-way have at least length 2, and red-way have at least length 1. May be this can help. ... – Daniel Pol Dec 13 '17 at 12:10
• yes, but you have to take into account the number of ways in which each situation is realised. There are many branched configuration but you can go back to the single one only when the two branches are close one another. – abenassen Dec 13 '17 at 12:27
• so the coloured branches can go left or right independently until meet together ? So, sometimes this 2 branches can have more as distane 1 ? – Daniel Pol Dec 13 '17 at 13:46

I have a new result and is pretty much more complicated. Result is : $$N_t = 2^t + \sum_{i=1}^{\lfloor t/2 \rfloor} { a_i^t n^i}$$ , in which $$a_i \approx 3.94-1.03 {2i \over t} - 1.904 {{4i^2} \over {t^2}}$$ A graph for "a" is :
but need to divide x-values by 500. Experimental values for $\alpha$ are for differents n : $$\begin{array}{|c|c} \hline n & \alpha \\ \hline 2 & 4\\ \hline 3 & 4.12431\\ \hline 4 & 4.31272\\ \hline 5 & 4.59366\\ \hline 6 & 4.68728\\ \hline 7 & 4.86206\\ \hline 8 & 5.02835\\ \hline 9 & 5.18693\\ \hline 10 & 5.33858\\ \hline 20 & 6.59619\\ \hline 30 & 7.58097\\ \hline 100 & 12.0721\\ \hline \end{array}$$ For higher values of $n$, $N_{\infty} \approx (2+\sqrt{n})^t$. For example for n=400 we have $\lim_{t \to \infty} {(N_t)^{1/t}} \approx 22.0781 \approx 2+\sqrt{400}$
Here $N_t$ is a total number of ways beginning with a red colour (distance is 0).
My demo is also pretty long. I will try to explain to you :
Imagine that you go down and paint all bifurcations. Now only consider a horizontal distance between this 2 branches. Let us call this distance D. If D=0, this mean we are painting a red colour, and we not branch.
If D=0, at next we have n+2 possibilities : 1) next one is also D=0, a red one, going to left. 2) next one is D=0, going to right 3) brach colour 1 4) colour 2 , ... n+2) branch colour n.
If we are already in a branched state with distance D , we need to continue with this colour. Then we have at next this possibilities : 1) come together to a distance D-1, 2) go paral.lel to left 3) go paralel to right, 4) come to distance D+1.
At this point of explanation, i will give a notation : $$D_c$$ A number D indicating a state of distance, and $c$ is colour. Examples are $1_1, 1_2, 3_1, ...$. A $0$ mean red colour so, it no need a subindex indicating a colour. I will indicate with a "L" that we come to this state going to left, and with a "R" going to right. If now we begin to enumerate all ways, putting at begin everything to 0 (all red colour) : $$0 L\to 0L \to 0L \to ... \to 0L \to 0L \\ 0 L\to 0L \to 0L \to ... \to 0L \to 0R \\ 0 L\to 0L \to 0L \to ... \to 0L \to 1_1 \\ 0 L\to 0L \to 0L \to ... \to 0L \to 1_2 \\ ... \\ 0 L\to 0L \to 0L \to ... \to 0L \to 1_n \\ ...$$ Then we will discover a few formulas. At first let us define
$A_{i,L}=$ All ways beginning with distance $i$ at level L.
L is a number of vertical columns we consider at right of last table, and asymptotical with similar meaning to $t$. Formulas are : $$A_{i,1}=1 \\ N_1 = 1 \\ A_{0,L} = N_L \\ A_{i,L} = A_{i-1,L-1} + 2A_{i,L-1} + A_{i+1,L-1} (i>0)\\ N_L = 2N_{L-1} + n A_{1,L-1}$$ After having this formulas 1)2)3)4)5), let us make a table of values for $A_{i,L}$ : $$\begin{array}{|c|c|c|c|c|c|c|c} \hline i | L& 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline 0 & 1 & N_2 & N_3 & N_4 & N_5 & N_6 & N_7\\ \hline 1 & 1 & 4 & N_2+12 & N_3+2N_2+40 & N_4+2N_3+5N_2+140 & N_5+2N_4+5N_3+14N_2+504 & N_6 + 2N_5+5N_4+14N_3+42N_2+1848\\ \hline 2 & 1 & 4 & 16 & N_2+60 & N_3+4N_2+224 & N_4+4N_3+14N_2+840 & N_5+4N_4+14N_3+48N_2+3168\\ \hline 3 & 1 & 4 & 16 & 64 & N_2+252 & N_3+6N_2+984 & N_4+6N_3+27N_2+3828\\ \hline 4 & 1 & 4 & 16 & 64 & 256 & N_2+1020 & N_3+8N_2+4048\\ \hline 5 & 1 & 4 & 16 & 64 & 256 & 1024 & N_2+4096\\ \hline. \end{array}$$ If we put now everything in terms of $n$'s : $$\begin{array}{|c|c|c|c|c|c|c|c} \hline i | L& 1 & 2 & 3 & 4 & 5 & 6 & 7\\ \hline 0 & 1 & 2+n & 4+6n & 8+26n+n^2 & 16+100n+10n^2 & 32+366n+63n^2+n^3 & 64+1316n+322n^2+14n^3\\ \hline 1 & 1 & 4 & 14+n & 48+8n & 166+43n+n^2 & 584+196n+12n^2 & 2092+822n+88n^2+n^3\\ \hline 2 & 1 & 4 & 16 & 62+n & 236+10n & 892+64n+n^2 & 3368+336n+14n^2\\ \hline 3 & 1 & 4 & 16 & 64 & 254+n & 1000+12n & 3914+89n+n^2\\ \hline 4 & 1 & 4 & 16 & 64 & 256 & 1022+n & 4068+14n\\ \hline 5 & 1 & 4 & 16 & 64 & 256 & 1024 & 4094+n\\ \hline 6 & 1 & 4 & 16 & 64 & 256 & 1024 & 4096 \\ \hline. \end{array}$$ At i=0, we see all $N_i$ values. Every value now is exactly same as you results for n=3. $N_i$ values until 7 are then : $$N_1 = 1 \\ N_2 = 2+n \\ N_3 = 4+6n \\ N_4 = 8+26n+n^2 \\ N_5 = 16+100n+10n^2 \\ N_6 = 32+366n+63n^2 + n^3 \\ N_7 = 64+1316n+322n^2+14n^3$$ If now we only write down this coefficients, like for for $N_4$ we have : $$N_4 = [8,26,1]$$ Then, what happen for bigger values of $t$ ? Then for example : $$N_{20} = [524288,38752453180,19351322910,7927318360,2374077045,461818586,52529635,3135220,84415,770,1]$$ Now we can observe that at middle, his order is very similar. If now we meek a n-rooth of every member we have : $$"Roots"N_{20} = [2,3.6081,3.47861,3.319,3.11492,2.85775,2.54881,2.1974,1.81671,1.4188,1]$$ We see that only first member is =2, and later we have in general descending values. What will happen if t is even bigger ? This line is even more smoother : $$"Roots"N_{100} = [2,3.88627,3.85915,3.83138,3.80291,3.7737,3.74369,3.71285,3.68111,3.64842,3.6147,3.5799,3.54394,3.50675,3.46824,3.42834,3.38696,3.34403,3.29946,3.25319,3.20514,3.15527,3.10352,3.04986,2.99428,2.93676,2.87731,2.81597,2.75275,2.68771,2.6209,2.5524,2.48228,2.41062,2.33751,2.26305,2.18731,2.1104,2.03241,1.95341,1.87348,1.79268,1.71105,1.6286,1.54529,1.46103,1.37558,1.28853,1.19903,1.10513,1]$$ $$"Roots"N_{999} = [2,3.9839,3.98114,3.97837,3.97559,3.9728,3.97001,3.96722,3.96441,3.9616,3.95879,3.95596,..., ...,1.06843,1.05726,1.04576,1.03383,1.02127,1.00764]$$ If now we paint this values in a graph we obtain this graph : This form is same for each high values for $t$. So, we obtain a more universal values $a(x)$ if x is from 0 to 1, so we can divide in 500 using this data. Now, i used regression in order to aproximate this curve, for a polinomy of grade 2 i have : $$a(x)=-1.904x^2-1.03x+3.96$$ For a polinomy of grade 4 : $$a(x)=3.985-1.394x-0.310x^2-2.479x^3+1.237x^4$$ May be somebody have a better regression program ? This values we put in our formula : $$N_i = 2^t+\sum_{i=1}^{t/2} a(2i/t) n^i$$ If we substitute now in this formula a regression of grade 2 we obtain : $$N_i = 2^t+\sum_{i=1}^{t/2} {(-1.904*4i^2/t^2-1.03*2i/t+3.96)^t n^i}$$ Now, a way to have a final result is to integrate this values, instead of sum. But it is not a easy integration. For example : $$\int{(x/t)^t n^x dx} = ((x/t)^t (-x log(n))^(-t) Γ(t + 1, -x log(n)))/(log(n)) + constant$$ Appendix
Diagram of $A_{2,L}$ (example for $i>0$) :
(At right of $1_c$,$2_c L$, $2_c R$ and $3_c$ there is not only one way, there are all combination of ways descending from level L-1.) $$... 2_c \to 1_c \to ... \to ... \to ... \to ... \\ ... 2_c \to 2_c L \to ... \to ... \to ... \to ... \\ ... 2_c \to 2_c R \to ... \to ... \to ... \to ... \\ ... 2_c \to 3_c \to ... \to ... \to ... \to ...$$ Diagram of $A_{0,L}$ : $$... 0 \to 0 L \to ... \to ... \to ... \to ... \\ ... 0 \to 0 R \to ... \to ... \to ... \to ... \\ ... 0 \to 1_1 \to ... \to ... \to ... \to ... \\ ... 0 \to 1_2 \to ... \to ... \to ... \to ... \\ ... \\ ... 0 \to 1_n \to ... \to ... \to ... \to ... \\$$

• Hi Daniel, thanks for all the work. I agree with your equation for $A_{i,L}$ in terms of previous $A_{j, L-1}$, but I don't agree with $A_{0,L} = N_{L-1}$. Inside $N_{L-1}$ there are many configurations which end with $i>1$, which cannot reduce to $i=0$ in one step. – abenassen Dec 14 '17 at 10:48
• I added a appendix. May be i not was clear about what i mean with $A_{i,L}$. $i_c$ is not at right of this last bloc with $L$ steps, $i_c$ is at begin (left) of this. Now we agree ? Daniel – Daniel Pol Dec 14 '17 at 13:57
• Hi. I make a redefinition of $N_L$. Also i found some mistakes in calculations of table and now al values i found (n=3) are exactly same with you results. I also found that it not is $\alpha$=4. There is also a strong component of $n$. I will try to finish it and then i will correct my answer. Greatings. Daniel – Daniel Pol Dec 14 '17 at 22:46
• I already have edit my answer. What you think ? – Daniel Pol Dec 15 '17 at 14:06
• I have calculated a value for $\alpha$ if $n$ is big. We can then aproximate $\alpha$ by $\alpha \approx 2+\sqrt{n}$. For lower values of $n$ i give you a table in my answer. – Daniel Pol Dec 15 '17 at 22:40