Bound inférieur pour fusionner les tableaux triés $ m $ (les feuilles de décision comptent - Permutations)

Question

J'ai besoin d'aide à comprendre comment calculer la limite inférieure sur la complexité temporelle de la fusion $ m $ des tableaux triés de longueur $ n $.

La limite doit être $ nm lg (m) $. Je dois prouver cela en utilisant un arbre de décision.

J'ai essayé de compter le nombre de permutations possibles (ce qui serait le nombre de feuilles dans l'arbre) mais je suis resté coincé. J'ai essayé ce qui suit:

Lors de la fusion du 2ème tableau avec le premier, nous avons $ binom {2n} {n} $ possibilités de placer les éléments. Lors de la fusion du 3ème, nous avons $ binom {3n} {n} $ Et ainsi de suite, le nombre total de permutations est:

$$ binom {2n} {n} binom {3n} {n} Dots binom {mn} {n} $$

La hauteur de l'arbre est indiquée $ h $.

$$ h> lg { binom {2n} {n} binom {3n} {n} dots binom {mn} {n}} $$

Et d'ici, je ne sais pas comment prouver la complexité.

Ma question est - ai-je compté correctement les permutations? Y a-t-il une limite plus simple? Comment continuer à partir d'ici?

De plus, ce problème est peut-être équivalent au problème du tri $ m $- Tableau de taille $ nm $? Parce que dans ce problème, il est facile de prouver que la limite est $ nm lg (m) $.