Tell me more ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
up vote 1 down vote favorite

EDITED Let $d > 0$ be a fixed integer. Let $m_i = \binom{d}{i}$ so that $\sum_{i=0}^d m_i = m = 2^{d}$

How fast does $S_d = \prod_{i=0}^d m_i!$ grow in relation to $m!$ ? is $S_d = O(m!)?$ How about $o(m!)?$ or is it actually lower bounded by $m!$?

Also, more generally, the answer to the question stated by Zev below, and the equivalent when 'max' is replaced by 'min' would also be of interest.

share|improve this question
It's not clear what you mean by this question. Do you mean to ask, how fast does $$\max_{\substack{m_1,\ldots,m_n\geq 0\\ \sum_i m_i=m}}\left\{\prod_i m_i!\right\}$$ grow as a function of $m$? – Zev Chonoles Mar 1 at 5:12
Are your $m_i$ partitions or compositions? If $m=6$, do we count $4,2$ separately from $2,4$? It makes quite a difference. – Ross Millikan Mar 1 at 5:58
Sorry, editing the question now for clarity. – rhl Mar 1 at 6:32
$S_d$ is $O(m!)$; in fact it's less than $m!$: It has as many factors as $m!$ (namely $m$), but some of them are smaller. That also answers your question whether it's lower bounded by $m!$ in the negative. The only non-trivial question here is whether it's $o(m!)$; you might want to focus the post on that. – joriki Mar 1 at 7:48
Well, just because it is O(m!) doesn't mean that it is not $\Omega(m!)$ as well.. I suspect that it still is, because some $m_i \geq m/d$ so you must have at least $(m/d)!$ – rhl Mar 1 at 9:06
show 1 more comment

1 Answer

up vote 1 down vote accepted

Decreasing all but the largest $m_i$ to $1$ while correspondingly increasing the largest $m_i$ replaces smaller factors by larger factors, and thus increases the product. The result is $(m-d)!$, which is $o(m!)$, so $S_d$ is $o(m!)$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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