Solving recurrence relation with minimum and factorial
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 the smallest 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 formula conjectured in the question is correct.
$$T(n,m)=\begin{cases}
1 &amp; n=1 \text{ or }f(n,m)\leq 0,\\
3+2\Big\lfloor\dfrac {f(n,m)-1}{g(n)}\Big\rfloor &amp;\text{otherwise},
\end{cases}$$
where $f(n,m)=m-2(n-1)!$ and $g(n)=\begin{cases}1 &amp;\text{if }n&lt;3,\\ 2(n-2)! &amp;\text{otherwise.}\end{cases}$



Observations




$T(n,m)=1,$ if $n=1$ or $m\le 2(n-1)!$.
$T(n,m)$ is nondecreasing with respect to $m$.
$T(n,m)\ge3$ if $m\gt 2(n-1)!$.
$T(2,m)=\begin{cases}
1 &amp; m\le2,\\ 
2m-3 &amp; \text{otherwise}.\end{cases}$
If $n=3,4,5$, then the conjectured formula is correct. 
The following proposition $p(n,j)$ is true for all $n\ge3$ and $j\ge0$.
$$\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.$}$$




The conjectured formula is the same as the combination of observations 1, 4, and 6.

All observations above except observation 6 can be proved easily, although observation 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).$ The reason why we can replace the condition $c\le n-1$ by $c\le \frac n2$ is that $(n,m,a,b,c)=(n,m,b, a, n-c)$.

Proof of observation 6 by well-founded induction

Here are the steps. Steps 1 and 2 are the induction bases while step 3 is the induction step.


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$.
Observation 5 says that $p(n,j)$ is true for $n=3,4,5$.
Let $n\ge6$ and $j\ge1$. As induction hypothesis, suppose $p(x,y)$ is true for all $x\le n$ or $x=n$ and $y\lt j$, i.e.,
$T(x,y)=3+2\lfloor\frac{f(x,y)-1}{2(x-2)!}\rfloor$, which implies, by the definition of $\lfloor\cdot\rfloor$, $$(x-2)!(T(x,y)+2x-5)&lt;y\le (x-2)!(T(x,y)+2x-3).$$

We will prove that $p(n,j)$ is true, i.e., $T(n,j)\le 3+2j$.


Let $j=\lfloor\frac{f(n,m)-1}{2(n-1)!}\rfloor$ for some $m$.

Proof for $T(n,m)\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.$$

Proof for $T(n,m)\ge 3+2j$

Because $T(n,m)$ is nondecreasing with respect to $m$ (observation 2), we will 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.$

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

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&lt;n$, we have $a\le(c-2)!(A+2c-3)$.
Since $n-c&lt;n$, we have $b\le(n-c-2)!(B+2n-2c-3)$.
Since $ab\ge1$, we have $\lfloor\frac{f(n,m-ab)-1}{2(n-2)!}\rfloor&lt;j$, so we can apply induction hypothesis to yield the first equality below. 


Since $T(n,m)$ is nondecreasing w.r.t $m$, 
$$\begin{aligned}
&amp;S(n,m,a,b,c)\\
&amp;\ge A+B+T(n,m-(c-2)!(A+2c-3)\,(n-c-2)!(B+2n-2c-3))\\
&amp;= 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\\
&amp;= 3+2j+ A+B +2\lfloor\frac{-(c-2)!(A+2c-3)(n-c-2)!(B+2n-2c-3))}{2(n-2)!}\rfloor\\
&amp;\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)}.$$
Since $n-c&lt;n$, induction hypothesis yields the second equality below.
$$\begin{aligned}
B&amp;=T(n-c,b)\le T(n-c, (n-c)!)\\
&amp;=3+2(\frac{(n-c)(n-c-1)}2-(n-c-1)-1)\\
&amp;=(n-c)(n-c-3)+3.
\end{aligned}$$
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)
&amp;\ge\frac{(A+B-2)(n-2)(n-3)(n-4)}{(A+2c-3)(B+2n-2c-3)}\\
&amp;\ge\frac{(n-3)(n-4)}{B+2n-2c-3}\frac{(n-2)(A+B-2)}{A+2c-3}\\
&amp;\ge\frac{(n-3)(n-4)}{(n-c)(n-c-1)}\frac{(n-2)(A+B-2)}{A+2c-3}\\
&amp;\gt1
\end{aligned}$$

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

The proof is complete. By the way, the proof for $T(n,j)\le 3+2j$ 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. (Observation 5) Prove the formula for $T(3,m)$, $T(4,m)$, and $T(5,m)$. Hint, the proof of observation 6 above might be helpful.

Exercise 3. Let $T_1$ be defined over $\Bbb N_{+}\times\Bbb N_{+}$.
$$T_1(n,m)=\begin{cases}
1, &amp; n=1\text{ or }m\leq (n-1)!\\
\min\limits_{a,b,c\geq 1,\ c\le n-1\\a\leq c!,\ b\leq(n-c)!}T_1(c,a)+T_1(n-c,b)+T_1(n,m-ab), &amp; \text{else}
\end{cases}$$
Show that $$T_1(n,m)=\begin{cases}
1 &amp; n=1 \text{ or }m\le (n-1)!,\\ 
3+2\Big\lfloor\dfrac {m-(n-1)!-1}{(n-2)!}\Big\rfloor &amp; \text{otherwise}.\end{cases}$$