Identities that represent powers of positive integers using multinomial coefficients

Shoichi Kamada · 2026

Read Identities that represent powers of positive integers using multinomial coefficients by Shoichi Kamada (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-17332.txt.

Introduction

Kamada proves new identities that express powers of positive integers through multinomial coefficients. Such coefficients generalize the binomial ones to splits into several parts. The identities here do not come from the two standard sources for such formulas. They arise neither from the multinomial theorem nor from the multinomial Vandermonde convolution. The paper presents the identities and proves them. The proofs are short and use counting steps that any reader can check.

Catalog record

CREATORShoichi Kamada
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18889
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.17332

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Identities that represent powers of positive integers using multinomial coefficients Shoichi Kamada Abstract In this paper, we show combinatorial identities that represent powers of positive integers using multinomial coefficients, which do not come from the multinomial theorem and the multinomial Vandermonde’s convolution. 1 Introduction 1.1 Background The multinomial theorem states that for a positive integer m and variables x_{1},\ldots,x_{s} , it holds that (x_{1}+\cdots+x_{s})^{m}=\sum_{r_{1},\ldots,r_{s}}\binom{m}{r_{1},\ldots,r_{s}}x_{1}^{r_{1}}\cdots x_{s}^{r_{s}}, (1.1) where r_{1},\ldots,r_{s} in the sum are taken over all nonnegative integers, and a multinomial coefficient \binom{m}{r_{1},\ldots,r_{s}} is defined by \binom{m}{r_{1},\ldots,r_{s}}:=\begin{cases}\frac{m!}{r_{1}!\cdots r_{s}!}&\text{if $r_{1}+\cdots+r_{s}=m$,}\\ 0&\text{otherwise.}\end{cases} Substituting x_{1}=\cdots=x_{s}=1 in ( 1.1 ), we have s^{m}=\sum_{r_{1},\ldots,r_{s}}\binom{m}{r_{1},\ldots,r_{s}}. (1.2) Taking a look at the coefficient of x^{r_{1}}\cdots x^{r_{s}} in (x_{1}+\cdots+x_{s})^{m_{1}+m_{2}}=(x_{1}+\cdots+x_{s})^{m_{1}}(x_{1}+\cdots+x_{s})^{m_{2}}, the multinomial Vandermonde’s convolution holds, i.e. \binom{m_{1}+m_{2}}{r_{1},\ldots,r_{s}}=\sum_{k_{1},\ldots,k_{s}}\binom{m_{1}}{k_{1},\ldots,k_{s}}\binom{m_{2}}{r_{1}-k_{1},\ldots,r_{s}-k_{s}}. Taking a summation on r_{1},\ldots,r_{s} , it follows from the multinomial theorem and ( 1.2 ) that s^{m}=\sum_{r_{1},\ldots,r_{s},k_{1},\ldots,k_{s}}\binom{m_{1}}{k_{1},\ldots,k_{s}}\binom{m_{2}}{r_{1}-k_{1},\ldots,r_{s}-k_{s}}. (1.3) From identities ( 1.2 ) and ( 1.3 ), we found that a power of a positive integer s^{m} can be represented as a sum of multinomial coefficients or a sum of products of two multinomial coefficients. Some literatures on the classical and multinomial Vandermonde’s convolution can be found in [ 3 , 1 , 5 ] . Another type identity that represents a multinomial coefficient using multinomial coefficients can be found in [ 4 ] . Generalizations of classical and multinomial Vandermonde’s convolution can be found in [ 2 ] and [ 6 ] , respectively. 1.2 Contribution Our contribution is to give identities that represent s^{m} as sums using multinomial coefficients, which do not come from the multinomial theorem. Let K denote a nonempty set. For positive integers m and n , let {\mathcal{M}}_{m,n}(K) denote the set of m -by- n matrices whose components are in K . For a positive integer s , let V denote a subset of K^{n} such that |V|=s , and let {\mathcal{X}}\subseteq{\mathcal{M}}_{m,n}(K) denote the set \{{}^{t}({}^{t}{\bm{r}}_{1},\ldots,{}^{t}{\bm{r}}_{m})\in{\mathcal{M}}_{m,n}(K)\colon{\bm{r}}_{i}\in V\}. Then we have the trivial identity s^{m}=|{\mathcal{X}}|. (1.4) We will define some equivalence relations \sim and sets {\mathcal{X}}\big/{\sim} of equivalence classes [A] . Then it is clear that the following identity holds. s^{m}=\sum_{[A]\in{\mathcal{X}}\big/\sim}|[A]|. (1.5) Since we may take K=\{1,\ldots,s\} and V=\{(i,\ldots,i)\colon i\in K\}\subseteq K^{n} , the arbitrariness of positive integers s and m is guaranteed in ( 1.5 ). Our contribution is to give concrete definitions of equivalence relations \sim and write the cardinality |[A]| using one (or two) multinomial coefficient(s), where our identities require a set V to be symmetrical in a group theoretical sense. Notation and terminology: For a multiset S , let \supp(S) denote the support of S , i.e. \supp(S) is the set consisting of elements in S . For an element a , let \mult_{S}(a) denote the multiplicity of a in S . Let \Mult(S) denote the multiset \{\mult_{S}(a)\colon a\in\supp(S)\} of cardinality |\supp(S)| . For a positive integer m and nonnegative integers r_{1},\ldots,r_{q} , let S=\{r_{1}\ldots,r_{q}\} be a multiset of cardinality q . Then a multinomial coefficient is defined as \binom{m}{S}:=\begin{cases}\frac{m!}{r_{1}!\cdots r_{q}!}&\text{if $r_{1}+\cdots+r_{q}=m$,}\\ 0&\text{otherwise.}\end{cases} For a positive integer n , let {\mathcal{S}}_{n} denote the symmetric group on \{1,\ldots,n\} . A finite set V\subseteq K^{n} is {\mathcal{S}}_{n} -invariant if {\mathcal{S}}_{n}V=V , where {\mathcal{S}}_{n}V is defined as a set \{(r_{\sigma(1)},\ldots,r_{\sigma(n)})\in K^{n}\colon(r_{1},\ldots,r_{n})\in V,\,\sigma\in{\mathcal{S}}_{n}\} . 2 Identities using sums of multinomial coefficients For a matrix A=({\bm{c}}_{1},\ldots,{\bm{c}}_{n}) , let \col(A) denote the multiset \{{\bm{c}}_{1},\ldots,{\bm{c}}_{n}\} . For m -by- n matrices A,B\in{\mathcal{X}} , a relation A\overset{\mathrm{c}}{\sim}B holds if \col(A)=\col(B) . Let {\mathcal{X}}/{\overset{\mathrm{c}}{\sim}} denote the set of equivalence classes in {\mathcal{X}} with respect to the equivalence relation \overset{\mathrm{c}}{\sim} , and [A]_{\mathrm{c}} denote an equivalence class in {\mathcal{X}}/{\overset{\mathrm{c}}{\sim}} for a matrix A\in{\mathcal{X}} . Theorem 2.1 . For any positive integers m and s and any nonempty set K , there are a positive integer n and an {\mathcal{S}}_{n} -invariant subset V\subseteq K^{n} with |V|=s such that s^{m}=\sum_{[A]_{\mathrm{c}}\in{\mathcal{X}}/{\overset{\mathrm{c}}{\sim}}}\binom{n}{\Mult(\col(A))}. Proof of Theorem 2.1 . For a matrix A=(A_{i,j})\in{\mathcal{X}} , it holds that \left|[A]_{\mathrm{c}}\right|=|\{(A_{i,\sigma(j)})\colon\sigma\in{\mathcal{S}}_{n}\}|=\binom{n}{\Mult(\col(A))} for each A\in{\mathcal{X}} , where the argument of the cardinality |\cdot| in the second expression above is a set. Since we can consider this for any [A]_{\mathrm{c}}\in{\mathcal{X}}/{\overset{\mathrm{c}}{\sim}} , we complete the proof. ∎ For a vector {\bm{r}}=(r_{1},\ldots,r_{n}) , let f({\bm{r}}) denote a multiset \{r_{1},\ldots,r_{n}\} of cardinality n , i.e. f({\bm{r}})=\{r_{1},\ldots,r_{n}\} . For a matrix A={}^{t}({}^{t}{\bm{r}}_{1},\ldots,{}^{t}{\bm{r}}_{m}) , let \row_{f}(A) denote the multiset \{f({\bm{r}}_{1}),\ldots,f({\bm{r}}_{m})\} . For m -by- n matrices A,B\in{\mathcal{X}} , a relation A\overset{\mathrm{r}}{\sim}B holds if \row_{f}(A)=\row_{f}(B) . Let {\mathcal{X}}/{\overset{\mathrm{r}}{\sim}} denote the set of equivalence classes in {\mathcal{X}} with respect to the equivalence relation \overset{\mathrm{r}}{\sim} , and [A]_{\mathrm{r}} denote an equivalence class in {\mathcal{X}}/{\overset{\mathrm{r}}{\sim}} for a matrix A\in{\mathcal{X}} . Theorem 2.2 . For any positive integers m and s and any nonempty set K , there are a positive integer n and an {\mathcal{S}}_{n} -invariant subset V\subseteq K^{n} with |V|=s such that s^{m}=\sum_{[A]_{\mathrm{r}}\in{\mathcal{X}}/{\overset{\mathrm{r}}{\sim}}}\binom{m}{\Mult(\row_{f}(A))}. Proof of Theorem 2.2 . Let A={}^{t}({}^{t}{\bm{r}}_{1},\ldots,{}^{t}{\bm{r}}_{m})\in{\mathcal{X}} . Put \{S_{1},\ldots,S_{l}\}=\supp(\{f({\bm{r}}_{1}),\ldots,f({\bm{r}}_{m})\}). We consider a permutation \sigma\in{\mathcal{S}}_{m} that satisfies the following condition. If for any S\in\{S_{1},\ldots,S_{l}\} , all rows {\bm{r}}_{i_{1}},\ldots,{\bm{r}}_{i_{m^{\prime}}} with i_{1}<\cdots<i_{m^{\prime}} satisfy f({\bm{r}}_{i_{j}})=S for all j=1,\ldots,m^{\prime} , then \sigma(i_{1})<\cdots<\sigma(i_{m^{\prime}}) , i.e. the order of {\bm{r}}_{i_{1}},\ldots,{\bm{r}}_{i_{m^{\prime}}} does not change in a matrix {}^{t}({}^{t}{\bm{r}}_{\sigma(1)},\ldots,{}^{t}{\bm{r}}_{\sigma(m)}) . Since the cardinality |[A]_{\mathrm{r}}| coincides with the number of such permutations \sigma\in{\mathcal{S}}_{m} , which is equal to the number of rearrangements in a tuple (f({\bm{r}}_{1}),\ldots,f({\bm{r}}_{m})) , we have |[A]_{\mathrm{r}}|=\binom{m}{\Mult(\row_{f}(A))}. Hence, we complete the proof. ∎ 3 An identity using a sum of products of two multinomial coefficients For m -by- n matrices A,B\in{\mathcal{X}} , a relation A\overset{\mathrm{r,c}}{\sim}B holds if A\overset{\mathrm{r}}{\sim}B and A\overset{\mathrm{c}}{\sim}B . Let {\mathcal{X}}/{\overset{\mathrm{r,c}}{\sim}} denote the set of equivalence classes in {\mathcal{X}} with respect to the equivalence relation \overset{\mathrm{r,c}}{\sim} , and [A]_{\mathrm{r,c}} denote an equivalence class in {\mathcal{X}}/{\overset{\mathrm{r,c}}{\sim}} for a matrix A\in{\mathcal{X}} . Theorem 3.1 . For any positive integers m and s and any nonempty set K , there are a positive integer n and an {\mathcal{S}}_{n} -invariant subset V\subseteq K^{n} with |V|=s such that s^{m}=\sum_{[A]_{\mathrm{r,c}}\in{\mathcal{X}}/{\overset{\mathrm{r,c}}{\sim}}}\binom{m}{\Mult(\row_{f}(A))}\binom{n}{\Mult(\col(A))}. Lemma 3.2 . Let A,B\in{\mathcal{X}} . Then A\overset{\mathrm{c}}{\sim}B implies A\overset{\mathrm{r,c}}{\sim}B . Proof of Lemma 3.2 . Let A=(A_{i,j})={}^{t}({}^{t}{\bm{r}}_{1},\ldots,{}^{t}{\bm{r}}_{m})\in{\mathcal{X}} and B=(B_{i,j})={}^{t}({}^{t}{\bm{s}}_{1},\ldots,{}^{t}{\bm{s}}_{m})\in{\mathcal{X}} . Then a relation A\overset{\mathrm{c}}{\sim}B holds if and only if (f({\bm{r}}_{1}),\ldots,f({\bm{r}}_{m}))=(f({\bm{s}}_{1}),\ldots,f({\bm{s}}_{m})) (3.1) and (A_{i,j})=(B_{i,\tau(j)}) for some \tau\in{\mathcal{S}}_{n} . Moreover, ( 3.1 ) implies \row_{f}(A)=\row_{f}(B) . Hence, we complete the proof of the lemma. ∎ Proof of Theorem 3.1 . Let A=(A_{i,j})={}^{t}({}^{t}{\bm{r}}_{1},\ldots,{}^{t}{\bm{r}}_{m})\in{\mathcal{X}} . Basically, we need to determine whether (A_{\sigma(i),\tau(j)})\in[A]_{\mathrm{r,c}} (3.2) or not for all \sigma\in{\mathcal{S}}_{m} and all \tau\in{\mathcal{S}}_{n} . The cardinality |[A]_{\mathrm{r,c}}| is the number of matrices (A_{\sigma(i),\tau(j)}) without repetition such that each pair (\sigma,\tau)\in{\mathcal{S}}_{m}\times{\mathcal{S}}_{n} satisfies ( 3.2 ). We show the validity of the definition of the equivalence relation \overset{\mathrm{r,c}}{\sim} and |[A]_{\mathrm{r,c}}|=\binom{m}{\Mult(\row_{f}(A))}\binom{n}{\Mult(\col(A))}. (3.3) Put \{S_{1},\ldots,S_{l}\}=\supp(\{f({\bm{r}}_{1}),\ldots,f({\bm{r}}_{m})\}). For each l^{\prime}=1,\ldots,l , we define I_{l^{\prime}}:=\{i\colon f({\bm{r}}_{i})=S_{l^{\prime}}\} and let \sigma_{I_{l^{\prime}}} be a permutation on I_{l^{\prime}} . Then we define a permutation \sigma\in{\mathcal{S}}_{m} as \sigma(i)=\begin{cases}\sigma_{I_{l^{\prime}}}(i)&\text{if $i\in I_{l^{\prime}}$},\\ i&\text{otherwise}.\end{cases} (3.4) For a permutation \sigma\in{\mathcal{S}}_{m} defined by ( 3.4 ), a mapping [(A_{i,j})]_{\mathrm{c}}\mapsto[(A_{\sigma(i),j})]_{\mathrm{c}} defines a permutation on the set {\mathcal{X}}/{\overset{\mathrm{c}}{\sim}} . This statement also holds for any permutation \sigma which is a composition of permutations defined in ( 3.4 ) for several l^{\prime} . From Lemma 3.2 , if two classes [(A_{i,j})]_{\mathrm{c}} and [(A_{\sigma(i),j})]_{\mathrm{c}} are different, then so are two classes [(A_{i,j})]_{\mathrm{r,c}} and [(A_{\sigma(i),j})]_{\mathrm{r,c}} . Notice that the choice of a matrix A\in{\mathcal{X}} is arbitrary. To count all permutations \sigma\in{\mathcal{S}}_{m} up to [(A_{i,j})]_{\mathrm{r,c}}=[(A_{\sigma(i),j})]_{\mathrm{r,c}} , we may consider all permutations \sigma\in{\mathcal{S}}_{m} such that for any S\in\{S_{1},\ldots,S_{l}\}

Read the complete text