# A Problem on Combinatorics

For non negative integers $x,y,z$ define the following operation

$$(x,y,z) \to (x-1,y-1,z) \to (x-2,y-1,z-1) \to (x-2,y-2,z-2) \to (x-3,y-3,z-2) \to \cdots.$$

Continue the above process when at least two cells become zero. Also please don't consider the coordinate which already becomes zero.

For example $(2,2,1) \to (1,1,1) \to (0,1,0)$.

$$(3,1,2) \to (2,0,2) \to (1,0,1) \to (0,0,0).$$

Now function $f(x,y,z)$ is the number of such operation. So $f(2,2,1)=2$, $f(3,1,2)=3$.

I want to find $\sum_{x,y,z=0}^a f(x,y,z)$ as a function of $a$. I also try to generalize the above operation for $n$ coordinates and find $\sum_{x_1,x_2,\ldots, x_n=0}^a f(x_1,x_2,\ldots, x_n)$.

The following algorithm would better explain my problem. Let $x,y,z$ are variables.

t=0

for a=0 to m

for b=0 to m

for c=0 to m

s=$x^ay^bz^c$

s_0=0

while(s $\neq$ s_0){ s_0=s

        if xy divides s{

s=s/xy

t=t+1}

if xz divides s{

s=s/xz

t=t+1        }

if yz divides s{

s=s/yz

t=t+1  }

}


I want to find t.

-
I don't see how that defines an operation; it's ambiguous what to do when you apply $\rightarrow$ for 3 arbitrary natural numbers. Maybe define it as a triplet of operations, which don't need their own symbol. Just subtract $(1,1,0)$, then $(1,0,1)$, etc. –  Eric Tressler Aug 6 '13 at 1:37
Yes, each time subtract (1,1,0), (1,0,1) and (0,1,1) sequentially, skip if any one of the corresponding cell is already 0, stop if two cells are zero. –  user46185 Aug 6 '13 at 1:45
@user46185 Then put this explanation in the body of the question! –  Matemáticos Chibchas Aug 6 '13 at 3:15
I changed a bunch of instances of $(2,2,1)->(1,1,1)$ to $(2,2,1)\to(1,1,1)$. That is standard usage. –  Michael Hardy Aug 6 '13 at 4:58
@user46185 That explains why my answer isnt exactly what you want. I was using the full cycle substracting $(1,1,0), (1,0,1),(0,1,1),(1,1,0)$ and so on, using a given vector even if it was used on only one coordinate. –  Jean-Sébastien Aug 6 '13 at 18:25

Given $v=(x_1,x_2,x_3)\in\mathbb N^3$, we define $r=r_v=\min\{x_1,x_2,x_3\}$ and $i=i_v=\min\{j: x_j=r\}$. The maximum number of times that you can apply the three "processes" $(1,1,0),(1,0,1), (0,1,1)$ together on $v$ (that is, without skipping) is the greatest $k=k_v$ such that

$$\min\bigl\{x_1-2(k-1),x_2-2(k-1),x_3-2(k-1)\bigr\}\geq2$$

(reason: the triple $\bigl(x_1-2(k-1),x_2-2(k-1),x_3-2(k-1)\bigr)$ corresponds to the penultimate possible application of all the three processes), that is $r-2(k-1)\geq2$, and so $k$ is the greatest integer such that $k\leq r/2$. Therefore $k=\lfloor r/2\rfloor$.

Let $w=v-2k\cdot(1,1,1)$. If $r$ is even, then $w$ has its $i$-th entry equal to $0$. Therefore exactly two of the three processes $(1,1,0),(1,0,1),(0,1,1)$ cannot be used anymore, and the remaining process can be applied exactly $\min\{x_j-2k:j\ne i\}$ times until obtaining another entry equal to $0$ (reason: this remaining process, when applied, subtracts $1$ from each entry different from the $i$-th entry). This shows that

$$f(v)=3k+\min\{x_j-2k: j\ne i\}=k+\min\{x_j: j\ne i\},\ \text{if}\ r\ \text{is even}\,.$$

If $r$ is odd, then $x_j-2k=1$ whenever $x_j=r$ and $x_j-2k>1$ otherwise. We consider the following cases (recall the definition of $i$):

$\boldsymbol{i=1:}$

In this case we can apply the process $(1,1,0)$ to $w=(1,x_2-2k,x_3-2k)$, obtaining the triple $(0,x_2-2k-1,x_3-2k)$. From now on the only available process is $(0,1,1)$, which can be applied precisely $\min\{x_2-2k-1,x_3-2k\}$ times until obtaining another entry equal to $0$. Summarizing, we get

$$f(v)=3k+1+\min\{x_2-1,x_3\}-2k=k+1+\min\{x_2-1,x_3\},\ \text{if}\ x_1\leq x_2,x_3\,.$$

$\boldsymbol{i=2:}$

We have $x_2<x_1$ and $x_2\leq x_3$, and $w=(x_1-2k,1,x_3-2k)$. We can apply process $(1,1,0)$, obtaining $(x_1-2k-1,0,x_3-2k)$. Now the only available process is $(1,0,1)$, which can be applied $\min\{x_1-2k-1,x_3-2k\}$ times until obtaining another entry equal to $0$. Therefore we have

$$f(v)=3k+1+\min\{x_1-1,x_3\}-2k=k+1+\min\{x_1-1,x_3\},\ \text{if}\ x_2<x_1\ \text{and}\ x_2\leq x_3\,.$$

$\boldsymbol{i=3:}$

In this case $x_3<x_1,x_2$ and $w=(x_1-2k,x_2-2k,1)$, so it is possible to apply both processes $(1,1,0)$ and $(1,0,1)$, obtaining the triple $(x_1-2k-2,x_2-2k-1,0)$, and now we apply process $(1,1,0)$ exactly $\min\{x_1-2k-2,x_2-2k-1\}$ times until obtaining another entry equal to $0$. Therefore

$$f(v)=3k+2+\min\{x_1-1,x_2\}-2k-1=k+1+\min\{x_1-1,x_2\},\ \text{if}\ x_3<x_1,x_2\,.$$

Given $a\in\mathbb N$, it remains to split the set $T=\{(x_1,x_2,x_3)\in\mathbb N^3: x_1,x_2,x_3\leq a\}$ into disjoint sets corresponding to the four cases considered above (and some subcases). Since we want to evaluate $S=\sum_{v\in T}f(v)$, we will successively add the values according to the emerging cases.

• If we want $r=r_v$ to be even, then first we choose $t$ such that $0\leq2t\leq a/2$ and define $r_v=2t$, and so $k=\lfloor r/2\rfloor=t$. Now we consider several options:

• If we want the minimum attained exactly once, then we have $3$ choices for the value of $i$ such that $r=x_i$, and necessarily we must have $r=2t<a$, which is equivalent to $t\leq\lfloor(a-1)/2\rfloor$. The other two entries can be equal, say, to $m\in\{2t+1,\dots,a\}$, so in this case we have $f(v)=k+\min\{x_j:j\ne i\}=t+m$. Consequently these cases contribute

$$3\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{m=2t+1}^a(t+m)\tag{I}$$

to the value of $S$. On the other hand, if we want the other two entries to be different, then we must have $2t<a-1$ in advance, that is $t\leq\lfloor(a-2)/2\rfloor=\lfloor a/2\rfloor-1$. Also, we have $2$ choices for the coordinate attaining that "intermediate" minimum, with value $m\in\{2t+1,\dots,a-1\}$, and finally we choose the remaining entry in the set $\{m+1,\dots,a\}$. These cases contribute

$$3\cdot2\sum_{t=0}^{\lfloor\frac a2\rfloor-1}\sum_{m=2t+1}^{a-1}\sum_{j=m+1}^a(t+m)=6\sum_{t=0}^{\lfloor\frac a2\rfloor-1}\sum_{m=2t+1}^{a-1}(a-m)(t+m)\tag{II}$$ to the value of $S$.

• Now, if we want the minimum to be attained exactly twice, then first we choose the corresponding two coordinates, which can be made into $\binom32=3$ ways, and we choose the value of the remaining entry in the set $\{2t+1,\dots,a\}$ (again, we must have $r=2t<a$ from the beginning, that is $t\leq\lfloor(a-1)/2\rfloor$). Note that in this case $\min\{x_j:j\ne i\}$ is equal to $\boldsymbol{2t}$. These cases contribute

$$3\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{m=2t+1}^{a-1}\sum_{j=m+1}^a(t+2t)=9\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}t\sum_{m=2t+1}^{a-1}(a-m)\tag{III}$$

to the value of $S$.

• Finally, the case of all entries equal contributes (in this case we have $2t\leq a$, that is $t\leq\lfloor a/2\rfloor$)

$$\sum_{t=0}^{\lfloor\frac a2\rfloor}(t+2t)=\frac32\,\biggl\lfloor\frac a2\biggr\rfloor\,\Biggl(\,\biggl\lfloor\frac a2\biggr\rfloor+1\Biggr)\tag{IV}$$ to the value of $S.\\[1cm]$

• Now we consider the case $r$ odd. Then $r$ must be of the form $r=2t+1$, with $t\in\mathbb N$ such that $2t+1\leq a$, that is $t\leq\lfloor(a-1)/2\rfloor$. In this case $k=\lfloor r/2\rfloor=t$. Pay attention to the splitting of the innermost sums because of the minimum function that appears in their summands.

• If $i=1$, then both $x_2$ and $x_3$ must be chosen in the set $\{2t+1,\dots,a\}$. The contribution for the value of $S$ is then equal to

\begin{align*} &\,\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{x_3=2t+1}^a\sum_{x_2=2t+1}^a\bigl(t+1+\min \{x_2-1,x_3\}\bigr)\\ =&\,\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{x_3=2t+1}^a\Biggl[\,\sum_{x_2=2t+1}^{x_3}(t+1+x_2-1)\ \ +\,\sum_{x_2=x_3+1}^a(t+1+x_3)\,\Biggr]\,.\tag{V} \end{align*}

• If $i=2$, then $x_1\in\{2t+2,\dots,a\}$ and $x_3\in\{2t+1,\dots,a\}$. The contribution for the value of $S$ is then equal to

\begin{align*} &\,\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{x_3=2t+1}^a\sum_{x_1=2t+2}^a\bigl(t+1+\min \{x_1-1,x_3\}\bigr)\\ =&\,\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{x_3=2t+1}^a\Biggl[\,\sum_{x_1=2t+2}^{x_3}(t+1+x_1-1)\ \ +\,\sum_{x_1=x_3+1}^a(t+1+x_3)\,\Biggr]\,.\tag{VI} \end{align*}

• If $i=3$, then both $x_1$ and $x_2$ must be chosen in the set $\{2t+2,\dots,a\}$. The contribution for the value of $S$ is then equal to

\begin{align*} &\,\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{x_2=2t+2}^a\sum_{x_1=2t+2}^a\bigl(t+1+\min\{x_1-1,x_2\}\bigr)\\ =&\,\sum_{t=0}^{\lfloor\frac{a-1}2\rfloor}\sum_{x_2=2t+2}^a\Biggl[\,\sum_{x_1=2t+2}^{x_2}(t+1+x_1-1)\ \ +\,\sum_{x_1=x_2+1}^a(t+1+x_2)\,\Biggr]\,.\tag{VII} \end{align*}

I used Mathematica to evaluate $S=(I)+\cdots+(VII)$. It is very convenient to separate the cases $a$ even and $a$ odd; otherwise the resulting formulas are very nasty because of the integer part, and not illuminating at all.

For $a=2b$ we obtain

$$S=5b+4b^2+\frac{19}2\,b^3+\frac{23}2\,b^4$$

and for $a=2b+1$ ($b\geq0$) we obtain

$$S=4+\frac{37}2\,b+\frac{71}2\,b^2+\frac{65}2\,b^3+\frac{23}2\,b^4\,.$$

In both cases above we have $b=\lfloor a/2\rfloor$, so modulo integer part, your desired sum is a polynomial in $a$ of degree $4$ with leader coefficient $\dfrac{23}{32}$ (and modulo mistakes, of course!!!).

-
Thank you so much. –  user46185 Aug 30 '13 at 4:02

Edit: It seems that OP doesn't want to use a vector, say $(1,1,0)$ if it can't substract from two coordinate. This answer is based on the use of the cyclic $(1,1,0)\to(1,0,1)\to(0,1,1)\to(1,1,0)\to \cdots$ and doesn't skip a particular vector if it can't substract from two coordinates, but rather just ignore the already zero position and substract from the other.

This ain't going to be pretty, plus I was pretty tired while doing it so there may be some errors. Assuming that by $\sum_{x,y,z=0}^a$ you mean that $x=0..n, y=0..n, z=0..n$ then I believe we have as follow.

Note that to get $f(x,y,z)$, it is sufficient to know when the middle value goes to zero. You should be able to see that if $x=n$ then it gets to zero at step $$F_1:=\frac{3}{2}\,n-\frac{3}{4}-\frac{1}{4}\, \left( -1 \right) ^{n}.$$ This is a fancy way to express the $n$th number that is not divisible by $3$. It comes from the fact that for every step divisible by $3$ we do not remove a unit at $x$. Similarly, we define $$F_2:=\frac{3}{2}\,n-\frac{1}{4}+\frac{1}{4}\, \left( -1 \right) ^{n}, \\ F_3:=\frac{3}{2}\,n+\frac{1}{4}-\frac{1}{4}\, \left( -1 \right) ^{n},$$ which are respectively the $n$th number that isn't $2\mod 3$ and $1\mod 3$. Now we distinguish multiple cases.

Case $1$ is when $x=y=z$. In this case there are

$$1/4\,\sum _{n=1}^{a}F_2=1/4\,\sum _{n=1}^{a}6\,n-1+ \left( -1 \right) ^{n}=\frac{1}{8}\, \left( -1 \right) ^{a}-\frac{1}{8}+\frac{1}{2}\,a+\frac{3}{4}\,{a}^{2}.$$ This is due to the fact that we must eliminate $2$ of them, and the second one will always come from the $y$ position.

Case $2$ is when $x=y,x\neq z$. In this case, we have $$\frac{1}{4}\,\sum _{y=1}^{a} \left( \sum _{n=1}^{y-1}6\,n-1+ \left( -1 \right) ^{n}+\sum _{n=y+1}^{a}6\,n-3- \left( -1 \right) ^{n} \right) +\frac{1}{4}\,\sum _{y=1}^{a}6\,y-3- \left( -1 \right) ^{y}=\frac{3}{4}a^3+\frac{1}{4}a^2+\frac{1}{8}(-1)^{a+1}a-\frac{3}{8}a+\frac{1}{8}+\frac{1}{8}(-1)^{a+1}.$$ The first outer sum deals with the cases $(x,x, z>0)$ and the second one with $(x,x,0)$. Under the first sign, we split into two sums depending on $x<y$ (first inner sum) or $x>y$. In a similar fashion, we get for $(x,y,x),(y,x,x)$ the fonctions $$\frac{1}{8}{\frac {a \left( 18{a}^{2} \left( -1 \right) ^{2a}+13 \left( -1 \right) ^{2a+1}- \left( -1 \right) ^{3a}+55 \left( -1 \right) ^{a+1}+108 \left( -1 \right) ^{a+1}{a}^{4}+172 \left( -1 \right) ^{a}{a}^{2}+8 \left( -1 \right) ^{a}a-75+40a+410{a}^{2} -48{a}^{3}-564{a}^{4}+216{a}^{6} \right) }{ \left( 5+ \left( -1 \right) ^{a}-6{a}^{2}+4a \right) \left( 5+ \left( -1 \right) ^{a }-6{a}^{2} \right) }}$$ (This is the only one Maple couldn't simplify neatly... it may have a mistake, I'll double check tomorrow) and $$\frac{3}{4}\,{a}^{3}+\frac{3}{4}{a}^{2}+\frac{1}{8}\, \left( -1 \right) ^{a}a-\frac{1}{8}\,a+\frac{1}{8}\, \left( -1 \right) ^{a}-\frac{1}{8}.$$ Finally, for $(x,y,z)$ where none are the same, we split again in $6$ cases... I'll put the case $x<y<z$ here and then the sum of all those $6$ subcases. So for $x<y<z$ we get $$\sum _{x=0}^{a-2} \left( \sum _{n=x+1}^{a-1} \left( \sum _{z=n+1}^{a}{ \it F_2} \right) \right)=\frac{1}{48}\left( 6\,{a}^{3}-2\,{a}^{2}-6\,a-1+3\, \left( -1 \right) ^{a+1 } \right) a$$ The outer sum sums over the possible value for $x$, the middle sum deals with the second minimum, in this case $y$, and the inner sums counts how many time we need to have $F_2$. For example with $a=3$, we want to have for $x<y<z$ the combinations $(0,1,2),(0,1,3),(0,2,3),(1,2,3)$. Note that when $y=1$ we count $F_2(n) a-n= 3-1=2 times, which is done by the inner sum. I'll leave as an exercice the job of adding all those to get your desired value. - Thank you so much. I observe that Case 1 matches perfectly. For example when a=3, value would be 8. But for x =y and x \neq z, theoretical value will be 22 although actual value is 20. – user46185 Aug 6 '13 at 16:24 @user46185 I get 22 by brute force counting. Forgetting the one that starts with 2 zeroes already, we have$(1,1,2),(1,1,3),(2,2,3),(1,1,0)(2,2,0),(3,3,0),(2,2,1),(3,3,1),(3,3,2),$which fade respectively in$1,1,3,1,2,4,2,4,4$for a total of$22\$. –  Jean-Sébastien Aug 6 '13 at 17:05
Please note that f(3,3,0) should be 3 not 4. As (3,3,0) -> (2,2,0) -> (1,1,0) ->(0,0,0). –  user46185 Aug 6 '13 at 17:49
Will you kindly give me some idea for the exact problem? It seems function may be of the form ra^3 + ... For me, finding r is sufficient. –  user46185 Aug 6 '13 at 19:07
@user46185 I haven't given thought on how your skip condition would affect the function. Where did you encouter this problem? Perhaps some context would help –  Jean-Sébastien Aug 6 '13 at 19:24