2
$\begingroup$

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}$$

$\endgroup$

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

  • $\begingroup$ Can you explain where all these questions are coming from? Are we solving some exercise sheet? Writing your thesis? $\endgroup$ – Yuval Filmus Jun 9 at 8:23
  • $\begingroup$ 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 $\endgroup$ – Dudi Frid Jun 9 at 8:30
  • 4
    $\begingroup$ After getting all this help, you will be having co-authors, namely people who helped you write the article. $\endgroup$ – Yuval Filmus Jun 9 at 9:24
  • $\begingroup$ 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? $\endgroup$ – Apass.Jack Jun 12 at 8:55
  • $\begingroup$ 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. $\endgroup$ – Apass.Jack Jun 12 at 10:52
2
$\begingroup$

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)<y\le (x-2)!(T(x,y)+2x-3).$$

    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<n$, we have $a<(c-2)!(A+2c-3)$.
  • Since $n-c<n$, 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<j$, 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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.