For u(a,b,c) is a function of a,b,c $\in Z $,
We have the recursive relationships: $$u(a,b,c)=1/6[u(a-1,b+1,c)+u(a-1,b,c+1)+u(a,b-1,c+1)+u(a+1,b-1,c)+u(a,b+1,c-1)+u(a+1,b,c-1)]+1$$
and constraints: 1)$u(1,1,1)=1$;2)$u(a,b,c)=0$ if any of a or b or c =0; 3) for $(x,y,z)$ is a re-permutation of $(a,b,c)$, we have $u(x,y,z)=u(a,b,c)$
Can anyone give me some hints on how to derive the close-form expression of u(a,b,c)?
Approach only, not closed form.
For now, we restrict the discussion to $a,b,c \ge 0$ (i.e. $\in \mathbb{N} = \{0, 1, 2, ...\}$).
In the recurrence, all the $u(x,y,z)$ terms have the same sum $S = x+y+z$. Therefore, the $\mathbb{N}^3$ grid is actually sliced into layers of the same sum, and one layer does not affect another layer at all. (Geometrically, the layers are $\perp$ the "normal" vector $(1,1,1)$.) Within each layer, the boundaries are zeros but the internal numbers are defined recursively. Also, each layer is an equilateral triangle.
The $S=0$ layer consists of only $u(0,0,0) = 0$.
The $S=1$ layer consists of $u(0,0,1) = u(0,1,0) = u(1,0,0) = 0$.
The $S=2$ layer consists of $6$ points, all valued $0$.
The $S=3$ layer consists of $10$ points, and finally a non-zero value appears:
We have $u(1,1,1) = p = 1 + {1\over 6}\cdot (0 + 0 + 0 + 0 + 0 + 0) = 1$. Note that the $6$ terms in the RHS of the recurrence correspond to the $6$ surrounding points in the hexagonal grid.
The $S=4$ layer consists of $15$ points:
We have $q = u(1,2,1) = u(2,1,1) = u(1,1,2) = 1+ {1\over 6}\cdot 2q \implies q = {3 \over 2}$.
The $S=5$ layer consists of $21$ points and is the first layer with $2$ different non-zero values.
We have $r = u(3,1,1) = u(1,3,1) = u(1,1,3) = 1+ {1\over 6} (2s)$ and $s = u(2,2,1) = u(2,1,2) = u(1,2,2) = 1+ {1\over 6}(2s + 2r)$. Solving these simultaneous equations give $s = {12\over 5}, r = {9 \over 5}.$
So basically in each layer, there will be $n$ equations in $n$ unknowns. I have no proof that the system is even solvable, but my gut feel says yes. As for closed-form, I don't see any right now. Also BTW, I think $n \approx 2S/3$ for large $S$, so we are talking about a large number of unknowns.
[Update: Actually I just realized that $u(a,b,c)$ can be interpreted as the expected no. of steps to hit the boundaries, starting from $(a,b,c)$, in an unbiased random walk on the hexagonal grid. So I am pretty sure the system of $n$ equations is solvable, and in fact, I wonder if there might be a closed form based on reasoning about the random walk a different way. ]
The OP says $a,b,c \in \mathbb{Z}$. IMHO this is ill-defined, or to be precise: "75%" ill-defined! The layering concept still holds, except now each layer is infinite. However, consider e.g. the $S=4$ layer again. Including the negative coordinates, it looks like this:
There are clearly $3$ infinite lines of zeros, and the triangle they enclose can be solved, but are the outside values well-defined? In the sense that, there exists a unique infinite sequence (pattern) of values fitting the recurrence? For now, I don't see any proof.
[Update: Again, if we interpret $u(a,b,c)$ as expected time to hit the boundaries, then they are indeed unique, even outside the triangle, although I wonder if the values might be infinite (my guess is not: this is still just a 2-D walk, albeit on a hex grid). ]
Having said that, the recurrence seems inspired by some kind of diffusion model, so maybe we can define the values that way. I.e. start with all zeros, and just keep updating all values in parallel. I don't see any proof this process will converge either, but maybe it will?
Anyway, if we accept that values outside the triangle are undefined, then how much is undefined? Well, $\mathbb{Z}^3$ is naturally divided into $8$ octants, of which the $\mathbb{N}^3$ octant is well-defined, and by symmetry so is the $(-\mathbb{N})^3$ octant (where $a,b,c \le 0$). The other $6$ octants are outside the triangles. Hence: "75%" ill-defined. :)