On the number of distinct multinomial coefficients (Q2493049): Difference between revisions

For a natural number \(n\), let \(M(n)\) denote the number of distinct values of multinomial coefficients \(\binom{n}{i_1,\ldots,i_n}=n!/(i_1!i_2!\ldots i_n!)\), where \(i_1,\ldots,i_n\) runs over non-negative integers with \(i_1+\cdots+i_n=n\). This paper is devoted to the study of \(M(n)\) and related topics. When \(S\subset{\mathbb N}\), write \(p_S(n)\) for the number of partitions of \(n\) into parts belonging to \(S\), and put \(p(n)=p_{\mathbb N}(n)\). Also, let \({\mathbb P}\) be the set of all primes. Then it is easy to see that \(p_{\mathbb P}(n)\leq M(n)\leq p(n)\). In this paper, it is proved amongst others that \(\lim_{n\rightarrow\infty}M(n)/p(n)=0\) and \(\lim_{n\rightarrow\infty}p_{\mathbb P}(n)/M(n)=0\). The authors encode partitions and multinomial coefficients as monomials in a natural way, and the arguments are mostly based on some methods in commutative algebra. The authors call a pair of partitions of \(n\) an \textit{irreducible pair}, when the pair have no common parts, but the corresponding multinomial coefficients take the same values. So, for example, \((4,1,1,1)\) and \((3,2,2)\) form an irreducible pair, because \(7!/(4!1!1!1!)=7!/(3!2!2!)\). On writing \(i(n)\) for the number of irreducible pairs of partitions of \(n\), it is proved here that \(i(n)>n/56-1\). Finally, the authors come up with several conjectures on \(M(n)\), being based on their computations. In particular, they conjecture that \(p_{S_1}(n)\leq M(n)\leq p_{S_2}(n)\), where \(S_1=3{\mathbb N}\cup\{1,2,4,5\}\) and \(S_2=S_1\cup\{7\}\), and also that \(\lim_{n\rightarrow\infty}n^{-1/2}\log M(n)=\pi\sqrt2/3\).