\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \usepackage{enumerate} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \begin{center} \vskip 1cm{\LARGE\bf Fermat Numbers in Multinomial Coefficients } \vskip 1cm \large Shane Chern \\ Department of Mathematics\\ Zhejiang University\\ Hangzhou, 310027\\ China\\ \href{mailto:chenxiaohang92@gmail.com}{\tt chenxiaohang92@gmail.com}\\ \end{center} \vskip .2 in \begin{abstract} In 2001 Luca proved that no Fermat number can be a nontrivial binomial coefficient. We extend this result to multinomial coefficients. \end{abstract} \section{Introduction}\label{Intro} Let $F_m=2^{2^m}+1$ be the $m^{th}$ Fermat number for any nonnegative integer $m$. Several authors studied the Diophantine equation \begin{equation}\label{eq:1.1} \binom{n}{k}=2^{2^m}+1=F_m, \end{equation} where $n\geq 2k\geq 2$, and $m\geq 0$. We refer to the articles \cite{Hewgill,Krishna,Luca2,Luca,Radovici} for further details. In 2001, Luca \cite{Luca} completely solved Eq.~\eqref{eq:1.1} and proved that it has only the trivial solutions $k=1, n-1$ and $n=F_m$. The proof is mainly based on a congruence given by Lucas \cite{Lucas}. For more about Fermat numbers, see \cite{Krizek}. For a positive integer $t$, let $n,k_1,\ldots,k_t$ be nonnegative integers, and define the $t$-order multinomial coefficient as follows: $$\binom{n}{k_1,\ldots,k_t}=\frac{n(n-1)\cdots(n-k_1-\cdots-k_t+1)}{k_1!\cdots k_t!},$$ with $\sum_{i=1}^t k_i< n+1$. In particular, $\binom{n}{0,\ldots,0}=1$. Note that for $t\geq 2$, if $\sum_{i=1}^t k_i= n$, then the $t$-order multinomial coefficient equals a $(t-1)$-order multinomial coefficient $$\binom{n}{k_1,\ldots,k_t}=\binom{n}{k_1,\ldots,k_{t-1}}.$$ There are many papers concerning the Diophantine equations related to multinomial coefficients. For example, Yang and Cai \cite{Yang} proved that the Diophantine equation $$\binom{n}{k_1,\ldots,k_t}=x^l$$ has no positive integer solutions for $n,t\geq 3$, $l\geq 2$, and $\sum_{i=1}^t k_i= n$. In this paper, we consider the Diophantine equation \begin{equation}\label{eq:1.2} \binom{n}{k_1,\ldots,k_t}=2^{2^m}+1=F_m,\quad\text{for $t\geq 2$, and $\sum_{i=1}^t k_i< n$}, \end{equation} and prove the following theorem. \begin{theorem}\label{th:1.1} The Diophantine equation~\eqref{eq:1.2} has no integer solutions $(m,n,k_1,\ldots,k_t)$ for nonnegative $m$ and positive $n,k_1,\ldots,k_t$. \end{theorem} \section{Two Lemmas}\label{Lemmas} To prove Theorem \ref{th:1.1}, we need the following two lemmas. \begin{lemma}[Euler \cite{Euler}]\label{lm:2.1} Any prime factor $p$ of the Fermat number $F_m$ satisfies $$p\equiv 1 \pmod{2^{m+1}}.$$ \end{lemma} \begin{lemma}[Luca \cite{Luca}]\label{lm:2.2} If $F_m=s\binom{n}{k}$, with $m\geq 5$, $s\geq 1$, and $1\leq k \leq \frac{n}{2}$, we have the following two properties. \begin{enumerate}[(i)] \item Let $n=n'd$, where $$A=\left\{ p:\text{\rm{prime }}p\mid n,\text{\rm{ and }}p\equiv 1 \text{\rm{ (mod $2^{m+1}$)}}\right\},$$ and $$n'=\prod_{p\in A}p^{\alpha_p}.$$ Then $k=d< 2^m$. \item $k-i\mid n-i$ for any $i=0,\ldots,k-1$. \end{enumerate} \end{lemma} \begin{remark} Lemma \ref{lm:2.2} is summarized from Luca's proof \cite{Luca} of Diophantine equation (\ref{eq:1.1}). Although Luca only proved the case $s=1$, he indicated that the result also holds for all positive integers $s$. \end{remark} \section{Proof of Theorem \ref{th:1.1}}\label{Proof} The first five Fermat numbers are primes, which cannot be a multinomial coefficient in Eq.~\eqref{eq:1.2}. Therefore, we only need to consider $m\geq5$. Moreover, for any multinomial coefficient $\binom{n}{k_1,\ldots,k_t}$ with $t>0$, $k_1, \ldots, k_t\geq 1$, and $\sum_{i=1}^t k_i< n$, there exists a multinomial coefficient $$\binom{n}{k'_1,\ldots,k'_t}=\binom{n}{k_1,\ldots,k_t},$$ such that $1\leq k'_1,\ldots,k'_t\leq \frac{n}{2}$. Hence, Eq.~\eqref{eq:1.2} becomes \begin{equation}\label{eq:2.1} F_m=\binom{n}{k_1,\ldots,k_t},\quad\text{for $m\ge 5$, $1\leq k_i\leq\frac{n}{2}$, and $\sum_{i=1}^t k_i< n$.} \end{equation} Let $n=n'd$, where $$A=\left\{ p:\text{prime }p\mid n,\text{ and }p\equiv 1 \text{ (mod $2^{m+1}$)}\right\},$$ and $$n'=\prod_{p\in A}p^{\alpha_p}.$$ For any $i=1,\ldots,t$, we have \begin{equation}\label{ki} F_m=\binom{n}{k_1,\ldots,k_t}=\binom{n}{k_i}\binom{n-k_i}{k_1,\ldots,k_{i-1},k_{i+1},\ldots,k_t}, \end{equation} where $\binom{n-k_i}{k_1,\ldots,k_{i-1},k_{i+1},\ldots,k_t}$ is a positive integer. By Lemma \ref{lm:2.2} (i), we have $k_i=d<2^m$ for $i=1,\ldots,t$. Then Eq.~\eqref{eq:2.1} becomes \begin{align} F_m&=\binom{n}{\underbrace{d,\ldots,d}_{t}},\quad \text{$n>td$, and $t\geq 2$} \label{eq:2.2}\\ &=\binom{n}{d}\binom{n-d}{d}\binom{n-2d}{\underbrace{d,\ldots,d}_{t-2}}. \label{eq:2.3} \end{align} Note that $d\geq 1$. We study Eq.~\eqref{eq:2.3} in the following three cases. \bigskip Case 1: $d>2$. Since $n>2d$ and $d\mid n$, we have $n\geq 3d$. Then, $$d\leq \frac{n-d}{2}<\frac{n}{2}.$$ In Eq.~\eqref{eq:2.3}, applying Lemma \ref{lm:2.2} (ii) to $\binom{n}{d}$ and $\binom{n-d}{d}$ respectively, and setting $i=1$, we have $$d-1\mid n-1$$ and $$d-1\mid n-d-1.$$ Thus, $d-1\mid d$, which is impossible. \bigskip Case 2: $d=2$. Let $n=2n'$. Then Eq.~\eqref{eq:2.2} becomes $$F_m=\binom{2n'}{\underbrace{2,\ldots,2}_{t}}=n'(2n'-1)(n'-1)(2n'-3)\binom{2n'-4}{\underbrace{2,\ldots,2}_{t-2}}.$$ Then $n'$ and $n'-1$ are both $F_m$'s factors. According to Lemma \ref{lm:2.1}, we obtain $n'\equiv n'-1\equiv 1$ (mod $2^{m+1}$), which is impossible. \bigskip Case 3: $d=1$. Eq.~\eqref{eq:2.2} becomes $$F_m=\binom{n}{\underbrace{1,\ldots,1}_{t}}=n(n-1)\binom{n-2}{\underbrace{1,\ldots,1}_{t-2}}.$$ Then $n$ and $n-1$ are both $F_m$'s factors. According to Lemma \ref{lm:2.1}, we obtain $n\equiv n-1\equiv 1$ (mod $2^{m+1}$), which is also impossible. \bigskip This completes the proof of Theorem \ref{th:1.1}. \begin{remark} One can even find that the multinomial coefficient in Eq.~\eqref{eq:1.2} could not divide a Fermat number. Otherwise, assume that there exists a positive integer $s$ such that $$F_m=s\binom{n}{k_1,\ldots,k_t}.$$ Note that in Eq.~\eqref{ki} we still have $$\binom{n}{k_i} \mid F_m,$$ and in Eqs.~\eqref{eq:2.2} and \eqref{eq:2.3} similar results hold. Hence, we can get the proof in the same way. \end{remark} \section{Acknowledgments}\label{Ack} I am indebted to Mr. Yong Zhang for providing relevant references and examining the whole proof, and to Mr. Jiaxing Cui for giving detailed comments. I am also indebted to the referee for his careful reading and helpful suggestions. \begin{thebibliography}{9} \bibitem{Euler} L. Euler, Observationes de theoremate quodam Fermatiano aliisque ad numeros primos spectantibus, {\it Acad. Sci. Petropol.} \textbf{6} (1738), 103--107. Available at \url{http://eulerarchive.maa.org/pages/E026.html}. \bibitem{Hewgill} D. Hewgill, A relationship between Pascal's triangle and Fermat's numbers, {\it Fibonacci Quart.} \textbf{15} (1977), 183--184. \bibitem{Krishna} H. V. Krishna, On Mersenne and Fermat numbers, {\it Math. Student} \textbf{39} (1971), 51--52. \bibitem{Krizek} M. K\v{r}\'i\v{z}ek, F. Luca, and L. Somer, \emph{17 Lectures on Fermat Numbers: From Number Theory to Geometry}, Springer, 2001. \bibitem{Luca2} F. Luca, Pascal's triangle and constructible polygons, {\it Util. Math.} \textbf{58} (2000), 209--214. \bibitem{Luca} F. Luca, Fermat numbers in the Pascal triangle, {\it Divulg. Mat.} \textbf{9} (2001), 191--195. \bibitem{Lucas} \'E. Lucas, Th\'eorie des fonctions num\'eriques simplement p\'eriodiques, {\it Amer. J. Math.} \textbf{1} (1878), 184--196, 197--240, 289--321. \bibitem{Radovici} P. Radovici-M\u{a}rculescu, Diophantine equations without solutions (Romanian), {\it Gaz. Mat. Mat. Inform.} \textbf{1} (1980), 115--117. \bibitem{Yang} P. Yang and T. Cai, On the Diophantine equation $\binom{n}{k_1,\ldots,k_s}=x^l$, {\it Acta Arith.} \textbf{151} (2012), 7--9. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\it Mathematics Subject Classification}: Primary 11D61; Secondary 11D72, 05A10. \noindent \emph{Keywords: } Fermat number, multinomial coefficient. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A000215}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received January 19 2014; revised version received February 11 2014. Published in {\it Journal of Integer Sequences}, February 15 2014. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document} .