On the number of words of N = 3 M N=3\,M letters with a three-letter alphabet
Pablo Serra · 2025
Read On the number of words of N = 3 M N=3\,M letters with a three-letter alphabet by Pablo Serra (2025) 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-2512-22362.txt.
Introduction
Pablo Serra counts words over a three-letter alphabet, sorting them by modular arithmetic. The classic problem asks how many words of a given length exist with prescribed counts of each letter. Serra classifies words by the residues modulo three of both the total length and each letter's multiplicity, covering every combination of cases systematically.
That classification yields explicit formulas for all cases. As a consequence, several identities involving sums of trinomial coefficients fall out, the trinomial coefficients being the natural counting numbers for three-symbol words. The note offers a tidy, complete treatment of a staple combinatorics question.
Catalog record
| CREATOR | Pablo Serra |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 17 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-22362
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the number of words of N = 3 M N=3\,M letters with a three-letter alphabet Pablo Serra Abstract In this paper we address the well-known problem of counting the number of 3 M 3M -letter words that can be formed from a three-letter alphabet by decomposing it into four possible cases based on its remainder when divided by three. The solution to the problem also gives us some sums of trinomial coefficients. I problem statement The number of N -letter words that can be formed with a m-letter alphabet is standard in combinatorics stanley2012 . For a configuration where each letter a_{i} appears n_{i}\geqslant 0\;;\;i=1,\ldots,m times, the number of possible words is given by c(m;\{n_{i}\})\,=\,\binom{N}{n_{1},\,\ldots,n_{m}}\;;\;\mbox{ where }N=\sum_{i=1}^{m}n_{i}\,, (1) and the total number of N -letter words is given by C(m;N)\,=\,\sum_{n_{1}+\ldots+n_{m}=N}c(m;\{n_{i}\})\,=\,\sum_{n_{1}+\ldots+n_{m}=N}\binom{N}{n_{1},\,\ldots,n_{m}}\,=\,m^{N}\,. (2) In this work, we study the case of a three-letter alphabet, a_{1},\,a_{2},\,a_{3} , and words of N=n_{1}+n_{2}+n_{3}=3\,M letters. With this constraint, the possibles cases are as follows, \displaystyle\mbox{A.- }n_{i} \displaystyle= \displaystyle 3 \displaystyle\,k_{i};\;k_{i}\in\mathbb{N}\quad;\;i=1,\,2,\,3, (3a) \displaystyle\mbox{B.- }n_{i} \displaystyle= \displaystyle 3 \displaystyle\,k_{i}+1;\;k_{i}\in\mathbb{N}_{0}\quad;i=1,\,2,\,3\,, (3b) \displaystyle\mbox{C.- }n_{i} \displaystyle= \displaystyle 3 \displaystyle\,k_{i}+2;\;k_{i}\in\mathbb{N}_{0}\quad;i=1,\,2,\,3, (3c) \displaystyle\mbox{D.- }n_{1} \displaystyle= \displaystyle 3 \displaystyle\,k_{1},\;n_{2}=3\,k_{2}+1,\;n_{3}=3\,k_{3}+2\mbox{ and permutations};\;k_{i}\in\mathbb{N}_{0}\hskip 142.26378pt (3d) Because m=3 is fixed, instead of the notation of the eq. ( 2 ), we will call C_{A}(k) the number of words of 3\,k letters in the case A , C_{B}(k) the number of words of 3\,(k+1) letters in the case B , C_{C}(k) the number of words of 3\,(k+2) letters in the case C , and C_{D}(k) the number of words of 3\,(k+1) letters in the case D , which are defined as \displaystyle\mbox{A.- }C_{A}(k)=\sum_{k_{1}+k_{2}+k_{3}=k}\binom{3\,(k_{1}+k_{2}+k_{3})}{3\,k_{1},\,3\,k_{2},\,3\,k_{3}} \displaystyle;\; \displaystyle k\in\mathbb{N}\,, (4a) \displaystyle\mbox{B.- }C_{B}(k)=\sum_{k_{1}+k_{2}+k_{3}=k}\binom{3\,(k_{1}+k_{2}+k_{3}+1)}{3\,k_{1}+1,\,3\,k_{2}+1,\,3\,k_{3}+1} \displaystyle\quad;\; \displaystyle k\in\,\mathbb{N}_{0}\,, (4b) \displaystyle\mbox{C.- }C_{C}(k)=\sum_{k_{1}+k_{2}+k_{3}=k}\binom{3\,(k_{1}+k_{2}+k_{3}+2)}{3\,k_{1}+2,\,3\,k_{2}+2,\,3\,k_{3}+2} \displaystyle\,\quad;\; \displaystyle k\in\,\mathbb{N}_{0}\,, (4c) \displaystyle\mbox{D.- }C_{D}(k)=6\,\sum_{k_{1}+k_{2}+k_{3}=k}\binom{3\,(k_{1}+k_{2}+k_{3}+1)}{3\,k_{1},\,3\,k_{2}+1,\,3\,k_{3}+2} \displaystyle\quad;\; \displaystyle k\in\mathbb{N}_{0}\,. (4d) Our main result is the following Theorem \displaystyle\mbox{A.- }C_{A}(k)=3^{3\,k-2}\,+\,\left(1+(-1)^{k}\right)i^{k}\,3^{3\,k/2-1}\quad;\quad k\in\mathbb{N}\,. (5a) \displaystyle\mbox{B.- }C_{B}(k)\,=\,3^{3k+1}+\left(\frac{\left(1+(-1)^{k}\right)}{2}i^{k}+\frac{\left(1-(-1)^{k}\right)}{2\sqrt{3}}\,i^{k-1}\right)3^{3k/2+1}\quad;\quad k\in\mathbb{N}_{0}\,. (5b) \displaystyle\mbox{C.- }C_{C}(k)\,=\,3^{3k+4}+\frac{(1-(-1)^{k})}{2}\,i^{k-1}3^{(3k+5)/2}\,+\,\frac{(1+(-1)^{k})}{2}\,i^{k}\,3^{(3k/2+2)};\quad k\in\mathbb{N}_{0}\,. (5c) \displaystyle\mbox{D.- }C_{D}(k)\,=\,2\,\cdot\,3^{3\,k+2}\quad;\quad k\in\mathbb{N}_{0}\,. (5d) The sequences eqs. ( 5a ), ( 5b ), and ( 5c ) were added in the OEIS, A391468 A391468 , A391469 A391469 , and A391470 A391470 respectively. We note that the eqs. ( 4 ) and ( 5 ) give new results for sums of trinomial coefficients. From eq. ( 2 ), the eqs. ( 5 ) must satisfy C_{A}(k+2)+C_{B}(k+1)+C_{C}(k)+C_{D}(k+1)=3^{3(k+2)} , which is directly verifiable. All the corresponding generating functions are geometric series, and straightforwardly, we obtain the following Corollary \displaystyle\mbox{A.- }g_{A}(x)=\sum_{k=1}^{\infty}C_{A}(k)\,x^{k}\,=\,\frac{3\,x(1-6\,x+189\,x^{2})}{(1-27\,x)\,(1+27\,x^{2})}\,. (6a) \displaystyle\mbox{B.- }g_{B}(x)\,=\,\sum_{k=0}^{\infty}\,C_{B}(k)\,x^{k}\,=\,\frac{6\,(1-12\,x-27\,x^{2})}{(1-27\,x)\,(1+27\,x^{2})}\,. (6b) \displaystyle\mbox{C.- }g_{C}(x)\,=\,\sum_{k=0}^{\infty}C_{C}(k)\,x^{k}\,=\,\frac{18\,(5-9\,x)}{(1-27\,x)\,(1+27\,x^{2})}\,. (6c) \displaystyle\mbox{D.- }g_{D}(x)\,=\,\sum_{k=0}^{\infty}C_{D}(k)\,x^{k}\,=\,\frac{18}{1-27\,x}\,. (6d) In order to demonstrate the theorem, we will look for recurrence relations (RR) for C_{\alpha};\;\alpha=A,\,B,\,C,\,D , and then we will prove them by mathematical induction. II The recurrence relations To found out RR, we will use a well-known RR for multinomial coefficients ha1971 , that, in the case of trinomial coefficients, take the form \binom{P}{p_{1},\,p_{2},\,p_{3}}\,=\,\sum_{j=1}^{3}\,\binom{P-1}{p_{1}-\delta_{1,j},\,p_{2}-\delta_{2,j},\,p_{3}-\delta_{3,j}}\quad;\quad P=p_{1}+p_{2}+p_{3}\,. (7) In our case, 3|P ; therefore we need to apply the eq. ( 7 ) three times in order to obtain RR. Beginning with C_{A}(M=k) we have \displaystyle C_{A}(k) \displaystyle= \displaystyle\sum_{k_{1}+k_{2}+k_{3}=k}\binom{3\,(k_{1}+k_{2}+k_{3})}{3\,k_{1},\,3\,k_{2},\,3\,k_{3}} (8) \displaystyle= \displaystyle\sum_{k_{1}+k_{2}+k_{3}=k}\;\sum_{j_{1},j_{2},j_{3}=1}^{3}\binom{3\,(k_{1}+k_{2}+k_{3}-1)}{3\,k_{1}-\delta_{j1,1}-\delta_{j2,1}-\delta_{j3,1},\,3\,k_{2}-\delta_{j1,2}-\delta_{j2,2}-\delta_{j3,2},\,3\,k_{3}-\delta_{j1,3}-\delta_{j2,3}-\delta_{j3,3}}\;, and, because of the permutation symmetry of the trinomial coefficients, we obtain C_{A}(k)=\sum_{k_{1}+k_{2}+k_{3}=k}\,3\,\binom{3\,(k_{1}+k_{2}+k_{3}-1)}{3\,(k_{1}-1),\,3\,k_{2},\,3\,k_{3}}+18\,\binom{3\,(k_{1}+k_{2}+k_{3}-1)}{3\,k_{1},\,3\,k_{2}-1,\,3\,k_{3}-2}+6\,\binom{3\,(k_{1}+k_{2}+k_{3}-1)}{3\,k_{1}-1,\,3\,k_{2}-1,\,3\,k_{3}-1}\;, (9) bearing in mind that if any of the numbers involved is negative, the trinomial coefficient is zero, and using the definitions of C_{\alpha} , we get C_{A}(k+1)\,=\,3\,C_{A}(k)\,+\,6\,C_{C}(k-2)\,+\,3\,C_{D}(k-1)\;. (10) By repeating calculations of the same type, we obtain the following RR for C_{B} C_{B}(k+1)\,=\,3\,C_{B}(k)\,+\,6\,C_{A}(k+1)\,+\,3\,C_{D}(k)\;, (11) for C_{C} C_{C}(k+1)\,=\,3\,C_{C}(k)\,+\,6\,C_{B}(k+1)\,+\,3\,C_{D}(k+1)\;, (12) and for C_{D} C_{D}(k+1)\,=\,18\left(C_{D}(k)\,+\,C_{A}(k+1)\,+\,C_{B}(k)\,+\,C_{C}(k-1)\right)\;. (13) The next step is to decouple the RR, eqs. ( 10 )-( 13 ). III Decoupling the recurrence equations The eq. ( 11 ) is rewriten as C_{D}(k)\,=\,\frac{1}{3}\left(C_{B}(k+1)-3\,C_{B}(k)-6\,C_{A}(k+1)\right)\,, (14) this equation in eq. ( 13 ) C_{C}(k)\,=\,\frac{1}{18}\left(-2\,C_{A}(k+3)+18\,C_{A}(k+2)+\frac{1}{3}C_{B}(k+3)-7\,C_{B}(k+2)\right)\,, (15) and from the eq. ( 12 ) 6\,C_{A}(k+2)-\,C_{B}(k+2)-3\,C_{B}(k+1)+C_{C}(k+1)-3C_{C}(k)\,=\,0\,, (16) now, using eq. ( 15 ), we get an equation involving C_{A} and C_{B} , C_{A}(k+3)-12\,C_{A}(k+2)-27\,C_{A}(k+1)-\frac{1}{6}C_{B}(k+3)+4\,C_{B}(k+2)-\frac{3}{2}C_{B}(k+1)+27\,C_{B}(k)\,=\,0\,. (17) On the other hand, from eq. ( 14 ) in eq. ( 10 ) C_{A}(k+1)+3\,C_{A}(k)-C_{B}(k)+3\,C_{B}(k-1)-6\,C_{C}(k-2)\,=\,0\,. (18) and again we can eliminate C_{C} from the later equation, 15\,C_{A}(k+1)-27\,C_{A}(k)-C_{B}(k+1)+12\,C_{B}(k)+27\,C_{B}(k-1)\,=\,0\,. (19) Once we have the two coupled RR for C_{A} and C_{B} , as given in eqs. ( 17 ) and ( 19 ), which can be decoupled, the resulting formal RR for both is the same , but with different initial terms, C_{A}(k+3)\,=\,27\left(C_{A}(k+2)-C_{A}(k+1)+27\,C_{A}(k)\right)\quad;\quad C_{A}(1)=3,\;C_{A}(2)=63,\;C_{A}(3)=2187\,, (20) C_{B}(k+3)\,=\,27\left(C_{B}(k+2)-C_{B}(k+1)+27\,C_{B}(k)\right)\quad;\quad C_{B}(0)=6,\;C_{B}(1)=90,\;C_{B}(2)=58806\,, (21) where the initial values were calculated from the definitions of C_{A} , eq. ( 4a ), and C_{B} , eq. ( 4b ). Now, we proceed to obtain RR for C_{C} and C_{D} . Subtracting eq. ( 13 ) from eq. ( 12 ) we get C_{D}(k+2)-C_{C}(k+2)\,=\,C_{A}(k+2)+6\left(3\,C_{B}(k+1)-C_{B}(k+2)\right)+\,3\left(6\,C_{C}(k)-C_{C}(k+1)\right)+3\left(6\,C_{D}(k+1)\,-\,C_{D}(k+2)\right)\,, (22) and now, using eq. ( 11 ), we can eliminate C_{B} , 18\,C_{A}(k+2)-C_{C}(k+2)+3\,C_{C}(k+1)-18\,C_{C}(k)+4\,C_{D}(k+2)\,=\,0\,. (23) And this equation allows us to eliminate C_{A} from eq. ( 10 ), C_{C}(k+2)-6\,C_{C}(k+1)+27\,C_{C}(k)-162\,C_{C}(k-1)-4\,C_{D}[k+2]+12\,C_{D}(k+1)-54\,C_{D}(k]\,=\,0\,, (24) we can also use eq. ( 12 ) in order to eliminate C_{B} from ( 11 ), 18\,C_{A}(k+2)-\frac{1}{2}C_{C}(k+2)+3\,C_{C}(k+1)-\frac{9}{2}\,C_{C}(k)+\frac{3}{2}\,C_{D}(k+2)+\frac{9}{2}\,C_{D}(k+1)\,=\,0\,, (25) from the eqs. ( 23 ) and ( 25 ) we get C_{C}(k+2)+27\,C_{C}(k)-5\,C_{D}(k+2)+9\,C_{D}(k+1)\,=\,0\,. (26) Now we rewrite the eq. ( 24 ) as C_{C}(k+2)+27\,C_{C}(k)-6\,(C_{C}(k+1)+27\,C_{C}(k-1))-4\,C_{D}(k+2)+12\,C_{D}(k+1)-54\,C_{D}(k)\,=\,0\,, (27) and use eq. ( 26 ) to obtain a RR for C_{D} , C_{D}(k+1)\,=\,27\,C_{D}(k)\quad;\quad C_{D}(0)=18\,, (28) where C_{D}(0) was calculated from the definition, eq. ( 4d ). Finally, we decouple C_{C} using ( 24 ), ( 26 ), and ( 28 ) (that we will prove in the next section), \displaystyle C_{C}(k+4) \displaystyle= \displaystyle\frac{1}{5}\left(137\,C_{C}(k+3)-189\,C_{C}(k+2)+3699\,C_{C}(k+1)-1458\,C_{C}(k)\right)\quad; (29) \displaystyle C_{C}(0) \displaystyle= \displaystyle 90,\;C_{C}(1)=2268,\;C_{C}(2)=58806,\;C_{C}(3)=1592136\,, (30) where the first values for k=0,\ldots,3 were calculated using the definition eq. ( 4c ) The characteristic polynomial of the RR eq ( 29 ) for C_{C} is P_{C}(x)\,=\,5\,x^{4}-137\,x^{3}+189\,x^{2}-3699\,x+1458\,=\,(5\,x-2)\,\left(x^{3}-27(x^{2}-x+27)\right)\,, (31) then, we note that first polynomial gives the RR C_{C}(k+1)=5\,C_{C}(k)/2 , that does not meet the initial values. The second polynomial, x^{3}-27(x^{2}-x+27) , is the characteristic polynomial of C_{A} and C_{B} , therefore we conclude that the RR for C_{C} is the same RR that for C_{A} and C_{B} with different initial values, C_{C}(k+3)\,=\,27\left(C_{C}(k+2)-C_{C}(k+1)+27\,C_{C}(k)\right)\quad;\quad C_{C}(0)=90,\;C_{C}(1)=2268,\;C_{C}(2)=58806\,. (32) We can understand this result by the symmetry properties of the C_{\alpha} , if we have a given configuration of 3\,k letters and we add three new letters, we obtain if • the three letters are same: A\rightarrow A;\;B\rightarrow B;\;C\rightarrow C;\;D\rightarrow D\,. • the three letters are different: A\rightarrow B;\;B\rightarrow C;\;C\rightarrow A;\;D\rightarrow D\,. • one letter is absent: A\rightarrow D;\;B\rightarrow D;\;C\rightarrow D;\;D\rightarrow A\mbox{ or }B\mbox{ or }C\mbox{ or }D\,. highlighting the symmetry between the configurations A,\,B and C , that differ just in the initial values. We can use the characteristic polynomial to rewrite the proposed solutions of the RR, eqs. ( 5a )-( 5d ). The RR for C_{A},\,C_{B} and C_{C} have the same characteristic polynomial x^{3}-27(x^{2}-x+27) , whose roots are x_{1}=27=3^{3}\quad;\quad x_{2}=3^{3/2}\,i\quad;\quad x_{3}=-3^{3/2}\,i\,, (33) therefore, using the three first values of each succession, we can write down the proposed solutions in terms of these roots, \displaystyle C_{A}(k)=3^{3\,k-2}\,+\,\left(1+(-1)^{k}\right)i^{k}\,3^{3\,k/2-1}=\frac{1}{9}\,x_{1}^{k}-\frac{1}{3}\,x_{2}^{k}+\frac{1}{3}\,x_{3}^{k}\,. (34a) \displaystyle C_{B}(k)\,=\,3^{3k+1}+\left(\frac{\left(1+(-1)^{k}\right)}{2}i^{k}+\frac{\left(1-(-1)^{k}\right)}{2\sqrt{3}}\,i^{k-1}\right)3^{3k/2+1}=3\,x_{1}^{k}+\frac{3-i\,\sqrt{3}}{2}x_{2}^{k}+\frac{3+i\,\sqrt{3}}{2}x_{3}^{k}\,. (34b) \displaystyle C_{C}(k)\,=\,3^{3k+4}+\frac{(1-(-1)^{k})}{2}\,i^{k-1}3^{(3k+5)/2}\,+\,\frac{(1+(-1)^{k})}{2}\,i^{k}\,3^{(3k/2+2)}=3^{4}\,x_{1}^{k}+\frac{9\,(1-i\,\sqrt{3})}{2}x_{2}^{k}+\frac{9\,(1+i\,\sqrt{3})}{2}x_{3}^{k}\,. (34c) The characteristic polynomial for the RR of C_{D} is x-3^{3} , then it has only one root, x_{1}=3^{3} , which gives C_{D}(k)\,=\,2\,\cdot\,3^{3\,k+2}=18\,x_{1}^{k}\,. (35) In the next section we, demonstrate the expressions for C_{\alpha},\;\alpha=A,\,B,\,C,\,D , eqs. ( 5a )-( 5d ) by mathematical induction. IV Proof of the proposed solutions for the decoupled recurrence relations In this section, we complete the proof of the theorem using mathematical induction for each expression of the