Solving recurrence relation with minimum and factorial

I need to solve the following recurrece:

$$T(n,m)=\begin{cases} 1, & n=1\text{ or }m\leq 2(n-1)!\\ \min\limits_{a,b,c\geq 1\\a\leq c!\\b\leq(n-c)!\\c\leq n-1}{T(c,a)+T(n-c,b)+T(n,m-ab)}, & \text{else} \end{cases}$$

Note: This question is highly related to my previous question here, since $$ab\leq\max\limits_{1\leq c\leq n-1}{c!(n-c)!}=(n-1)!$$

I guess that the closed form expression for $$T(n,m)$$ here is similar to the one that I found for my previous question.

Also, I guess that the minimum is obtained at $$c=\lceil n/2\rceil,a=c!,b=(n-c)!$$, but I don't know how to prove it.

I made a little change in the definition of $$T$$ to make it a bit simpler but without affecting the rest of the values of $$T$$.

The first 10 values of the first n's are:

$$T(1,*)=1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\dots\\ T(2,*)=1, 1, 3, 5, 7, 9, 11, 13, 15, 17,\dots\\ T(3,*)=1, 1, 1, 1, 3, 3, 5, 5, 7, 7,\dots\\ T(4,*)=1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\dots$$

Experiments show that

$$T(n,m)=\begin{cases}1 & n=1 \text{ or }f(n,m)\leq 0,\\ 3+2\Big\lfloor\frac {f(n,m)-1}{g(n)}\Big\rfloor & \text{otherwise},\end{cases}$$

for $$f(n,m)=m-2(n-1)!$$, and for some $$g$$ whose first values are: 1, 1, 2, 4, 12, 48, 240. I guess that $$g(n)=\begin{cases}1 & \text{if }n<3,\\ 2(n-2)! & \text{otherwise.}\end{cases}$$

This question has an open bounty worth +150 reputation from Dudi Frid ending in 2 days.

This question has not received enough attention.

Link to a similar question that I did manage to solve appears at the body of the question. Any help would be highly appreciated

• Can you explain where all these questions are coming from? Are we solving some exercise sheet? Writing your thesis? – Yuval Filmus Jun 9 at 8:23
• It's neither an exercise sheet, nor my thesis: I am working on a rather complicated article in combinatorics for a while, since I don't have co-authors in my article I post here some stuff to get some help and to assure that my conclusions are correct – Dudi Frid Jun 9 at 8:30
• After getting all this help, you will be having co-authors, namely people who helped you write the article. – Yuval Filmus Jun 9 at 9:24
• Assume that $T(n,m)$ is defined on $\Bbb Z_{\ge1}\times\Bbb Z_{\ge1}$ as before. What is the value of $T(1,3)$? Since $3\not\le2(1-1)!$, we cannot apply the first rule. Since there is no $c$ such that $c\ge1$ and $c<1-1$, so $T(1,3)$ is the min of an empty set to be infinity. Is $T(1,3)$ infinity? – Apass.Jack Jun 12 at 8:55
• It looks like $T(1,m)$ for $m\ge 3$ can be set to infinity or any value that is no less than 1 without affecting other values. – Apass.Jack Jun 12 at 10:52

Summary

It is not true that the minimum can always be obtained at $$c=\lceil n/2\rceil,a=c!,b=(n-c)!$$. Here is an counterexample. $$T(5,49) = T(1,1) + T(4,1) + T(5,48) = 3 \not=5=T(3,6)+T(2,2)+T(5,12).$$ Instead, the minimum can always be obtained at $$c=1$$, $$a=1$$, $$b=2(n-2)!.$$

The following neat formulas given in the question is correct. $$T(n,m)=\begin{cases}1 & n=1 \text{ or }f(n,m)\leq 0,\\ 3+2\Big\lfloor\frac {f(n,m)-1}{g(n)}\Big\rfloor & \text{otherwise},\end{cases}$$ where $$f(n,m)=m-2(n-1)!$$ and $$g(n)=\begin{cases}1 & \text{if }n<3,\\ 2(n-2)! & \text{otherwise.}\end{cases}$$

Observations

1. $$T(n,m)=1,$$ if $$n=1$$ or $$m\le 2(n-1)!$$.
2. $$T(n,m)$$ is nondecreasing with respect to $$m$$.
3. $$T(n,m)\ge3$$ if $$m\gt 2(n-1)!$$.
4. $$T(2,m)=\begin{cases} 5 & m\le2,\\ 2m-3 & \text{otherwise}.\end{cases}$$
5. If $$n=3,4,5$$, then $$T(n,m)=\begin{cases} 1 & m\le 2(n-1)!,\\ 3+2\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor & \text{otherwise}. \end{cases}$$

6. Let $$p(n,j)$$ be the following proposition: $$\text{If n\ge3 and j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor for some j\ge0 and m, then T(n,m)=3+2j.}$$ $$p(n,j)$$ is true for all $$n\ge3, j\gt0$$.

Items 1, 4 and 6 confirm the formula given in the question.

All above items except item 6 can be proved easily, although item 5 might take a while to sort out case by case.

Let $$S(n,m,a,b,c)=T(c,a)+T(n-c,b)+T(n, m-ab)$$. Then for $$m\gt 2(n-1)!$$, $$T(n,m)= \min\limits_{a,b,c\geq 1,\ c\le\frac n2\\a\leq c!,\ b\leq(n-c)!}S(n,m,a,b,c),$$ where $$c$$ is required to be at most $$\frac n2$$ since otherwise we can replace $$(n,m,a,b,c)$$ by $$(n,m,b, a, n-c)$$.

Proof of item 6 by Well-Founded Induction

Here are the steps.

• Suppose $$j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor=0$$, i.e., $$2(n-1)!\lt m\le2(n-1)!+2(n-2)!$$. Since $$m\gt 2(n-1)$$, $$T(n,m)\ge3.$$ On the other hand, $$T(n,m)\le S(n,m,1,2(n-2)!,1)=1+1+1=3.$$ So $$T(n,m)=3$$, i.e., $$p(n,j)$$ is true when $$j=0$$.

• Item 5 says that $$p(n,j)$$ is true for $$n=3,4,5$$.

• As induction hypothesis, suppose $$p(x,y)$$ is true for all $$x\le n$$ or $$x=n$$ and $$y\lt j$$, where $$n\ge 6$$ and $$j\ge1$$. So for $$x\le n$$ or $$x=n$$ and $$y\lt j$$, we have $$T(x,y)=3+2\lfloor\frac{f(x,y)-1}{2(x-2)!}\rfloor,$$ i.e., $$(x-2)!(T(x,y)+2x-5)

We will prove that for $$p(n,j)$$ is true. Let $$j=\lfloor\frac{f(n,m)-1}{2(n-1)!}\rfloor$$ for some $$m$$.

Part one, $$T(n,j)\le 3+2j$$

By induction hypothesis, we know that $$T(n, m-2(n-2)!)=3+2(j-1)$$. Hence, $$T(n,m)\le S(n,m,1,2(n-2)!,1)=1 + 1 + T(n, m-2(n-2)!)=3+2j.$$

Part two, $$T(n,j)\ge 3+2j$$

We will prove that $$S(n,m,a,b,c)\ge 3+2j$$ for all valid choices of $$(a,b,c)$$. The case when $$c=1$$ or $$c=2$$ is relatively easy. From now on assume $$3\le c\le \frac n2$$. Because of item 2, we can assume $$m=2(n-1)!+2(n-2)!j+1$$, the smallest value possible such that $$j=\lfloor\frac{f(n,m)-1}{2(n-2)!}\rfloor$$.

Let $$A=T(c,a)$$ and $$B=T(n-c,b)$$. The case when $$A=1$$ or $$B=1$$ is much easier to prove. Now assume $$A,B\ge2$$.

• Since $$c, we have $$a<(c-2)!(A+2c-3)$$.
• Since $$n-c, we have $$b<(n-c-2)!(B+2n-2c-3)$$.
• Since $$ab\ge1$$, we have $$\lfloor\frac{f(n,m-ab)-1}{2(n-2)!}\rfloor, so we can apply induction hypothesis to yield the second inequality below.

Since $$T(n,m)$$ is nondecreasing w.r.t $$m$$, \begin{aligned} S(&n,m,a,b,c)=\\ &\ge A+B+T(n,m-(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3))\\ &\ge A+B+3+ 2\lfloor\frac{f(n,m-(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3))-1}{2(n-2)!}\rfloor\\ &\ge 3+2j+ A+B +2\lfloor\frac{-(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3))}{2(n-2)!}\rfloor\\ &\gt 3+2j+ \frac{(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3)}{(n-2)!}(h(c,A,B)-1) \\ \end{aligned}

where $$h(n,A,B,c)=\frac{(A+B-2)(n-2)!} {(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3)}$$ By induction hypothesis, $$A=T(c,a)\le T(c,c!)=3+2\left(\frac{c(c-1)}2-(c-1)-1\right)=c^2-3c+3.$$ Similarly, $$B=T(n-c,b)\le =(n-c)^2-3(n-c)+3.$$ Since $$n\ge6$$ and $$c\ge3$$, $$(n-2)!\ge (n-2)(n-3)(n-4)(c-2)!(n-c-2)!.$$
Since $$n\ge6$$, $$c\le \frac n2$$ and $$A,B\ge2$$, $$(n-2)(A+B-2)\gt A+2c-3.$$

\begin{aligned}h(n,A,B,c)= &\ge\frac{(A+B-2)(n-2)(n-3)(n-4)}{(A+2c-3)(B+2n-2c-3)}\\ &\ge\frac{(n-3)(n-4)}{B+2n-2c-3}\frac{(n-2)(A+B-2)}{A+2c-3}\\ &\ge\frac{(n-3)(n-4)}{(n-c)(n-c-1)}\frac{(n-2)(A+B-2)}{A+2c-3}\\ &\gt1 \end{aligned}

So $$S(n,m, a,b,c) \gt 3+2j.$$

The proof is complete. By the way, part one of the proof shows that the minimum can always be obtained at $$c=1,$$ $$a=1,$$ $$b=2(n-2)!.$$

Exercises

Exercise 1. Prove the formula for $$T(2,m)$$.

Exercise 2. (Item 5) Prove the formula for $$T(3,m)$$, $$T(4,m)$$, $$T(5,m)$$ and $$T(6,m)$$. Hint, you may use or adapt the proof of item 6 above.