Abstract
The three theorems, Kummer’s theorem, Lucas’s theorem and the Multinomial Coefficient theorem, help determine the parity of a term from the expansion (x+y+z) n. To identify the parity of a term, using one or more of these theorems, requires heavy computation for calculating the parity of a multinomial term. This paper tries to answer the question: Is there a method to identify the parity of a multinomial term that potentially does not require heavy computation? Additionally, the paper also explores the question, is it possible to determine the parity of a multinomial coefficient without requiring base 2 conversions or factorials? The approach was to use representative data as a starting point to observe and identify potential patterns. The prepared data set was made of the expanded terms from the expansion (x+y+z) n; the exponents of x, y, z were represented by the variables i, j and k, respectively. A pattern was found between the distribution and parity of i, j, k and the parity of the corresponding coefficient. These rules were stated and then proved through the Kummer’s theorem and the Multinomial Coefficient theorem (except for one conjecture). The rules, defined as an algorithm, were benchmarked against the Multinomial Coefficient theorem. The set of rules is not to be considered as a replacement for the theorems mentioned and must instead be looked at as a way to predict the parity of multinomial coefficients without requiring heavy computation.
Keywords: Multinomial term parity; Kummer’s theorem; Lucas’s theorem; Multinomial Coefficient theorem; Computation for parity determination; Parity of coefficients through patterns rules.
Introduction
The method used to find the parity of a term for the expansion (x+y+z) n is the multinomial coefficient method1, which not only gives the parity of the term, but also the value of the coefficient of the term. The multinomial coefficient2,3 uses the following formula (The formula present here is only applicable to the expansion (x+y+z) n):
![\[ \frac{n!}{i! j! k!}\]](https://nhsjs.com/wp-content/ql-cache/quicklatex.com-4d5063a4136d5d50160afedea263ac30_l3.png "Rendered by QuickLaTeX.com")
The resulting value is then divided by 2. Depending on whether the quotient is a whole number or not, the outcome would be decided as an odd or an even coefficient. The challenge of using the said method is, for large values of n and i, j, & k the computation becomes a long process and would potentially require a computer to get the right results4,5. In order to find a method which can yield the same results as the Multinomial Coefficient theorem, but with lesser computation, I needed to find patterns to understand why a certain expanded term has a parity of odd or even. The number of terms in the expansion (x+y+z) n is bijectively equal to the number of non-negative solutions to the equation i+j+k=n where each solution is indexed as xiyjzk6. There’s another theorem that explains the parity of a binomial coefficient. This theorem is called Kummer’s theorem. It was published in 1852 by Kummer and it’s considered a major milestone in the evolution of the number theory concepts. It states that if there’s a binomial coefficient in the form of:
![\[\begin{pmatrix} n \\ k \end{pmatrix}\]](https://nhsjs.com/wp-content/ql-cache/quicklatex.com-5f8451c466948aade1ad6901467a3a64_l3.png "Rendered by QuickLaTeX.com")
Then the highest power of p that divides the result of this, n choose k is equal to number of carries when k is added to n-k in the base of p7,8,9. There’s another variation to this theorem; this variation states that the number of borrows that are performed in n-k in p base10 is the highest power of p that divides n choose k. In order to prove many of the rules and patterns that were found while examining the expanded terms from the expansion (x+y+z) n8, these two theorems were applied. There’s another theorem which is called Lucas theorem. This is a theorem that states the following: If p is a prime, and m=m1m2m3m4.mk in base p, n=n1n2n3n4…nk in base p, then the result of it is11:
![\[\begin{pmatrix} n \\ m \end{pmatrix} \equiv \begin{pmatrix} n^0 \\ m^0 \end{pmatrix} \begin{pmatrix} n^1 \\ m^1 \end{pmatrix} ... \begin{pmatrix} n_k \\ m_k \end{pmatrix}\ mod\ p\]](https://nhsjs.com/wp-content/ql-cache/quicklatex.com-fd5497d0af15e55b35c924e3fa78cad5_l3.png "Rendered by QuickLaTeX.com")
This theorem reduces the computational load of computing an expression such as n choose m modulo p by breaking them into smaller multinomial expressions, which reduces the computational load required to compute the final result12,13. Determining the parity of coefficients in multinomial expansions is governed by nontrivial number-theoretic results, particularly those arising from modular arithmetic and p-adic valuation, such as Kummer’s theorem and Lucas’ theorem, reflecting the depth and extensive development of this area14. This is due to the aspect of this structure which allows the number of terms in an expansion to increase combinatorically as the value of n in an expression increases15,16.
. There have been studies that have tried to find algorithms and recursive programming methods that could lessen the direct computational load of calculating the coefficient of each expanded term15. One of the papers found that it’s possible to split a multinomial expression into binomial expressions and by leveraging binomial identities and symmetries, it’s possible to reduce the load of computation on a computer significantly15.
Literature Review
In this section, the relevant work that has already been published by previous authors will be discussed and how the work of this article will be positioned in it. In order to reduce the time required to determine if a multinomial coefficient result is going to be even or odd, there has been a theorem which was introduced in 1852 by Kummer to solve this problem. Theorems such as the Kummer theorem and the Lucas theorem does reduce the time required to find the parity of a binomial coefficient. There has been significant literature that has been published on the idea that these two theorems can be extended into the space of multinomial coefficients7.
There has been no study so far that has provided an approach to solve or find the parity of a multinomial coefficient theorem without the use of code or a computer. This is what the study in this article is going to attempt to cover. This study will attempt to solve this problem by providing a method that can determine the parity of an expanded term from a multinomial expression without requiring heavy computations. In order to achieve this, a rule-based approach was used. And to make sure that this approach works, these rules were proved (except for one) by using existing theorems such as Kummer’s theorem. This approach has been proven to be able to work for a majority of cases but it may fall short in certain cases as the total possible arrangements that can be possible for a multinomial expression increases combinatorically.
So, this method is not considered a replacement of the multinomial coefficient theorem or the Kummer theorem, but instead should be considered a method for predicting and finding the parity of expanded terms. There has been no rule-based approach such as this that can determine the parity of a multinomial term and this paper’s study has addressed this research gap.
Method
In order to find patterns that could explain the parity of an expanded term, a sample data set was gathered. In the data set, a record of the expanded term, the values of the coefficient of each expanded term and finally the values of i, j and k for this specific term, were recorded. To start off, an expansion for the expression (x+y+z) for different values of n was conducted, and then these values were recorded in form of tables. An observation and analysis of the resultant tables was done to identify underlying pattern that could explain the parity of each expanded term. Each pattern was then proved using the standard form of the Multinomial Coefficient17 theorem and Kummer’s theorem8. In order to test if, these rules do in fact reduce the time required to solve multinomial problems, a benchmark test was set up. In this benchmark test, a sample of 22 terms from the expansions: (x+y+z)8 and (x+y+z)9 was used. The number of steps and the amount of time spent were tested and compared between the two methods. A step is defined as one operation that has been performed such as: greater than or equal to, multiplication, division, factorial, lesser than or equal to, and so on. The number of seconds required was measured via a stopwatch app.
Sample Set Analysis
In this section, let’s discuss how the problem was approached. The first step was to take cases of the problem and gather data about the coefficients and the corresponding exponents of the variables in each term.
Here are examples that showcases the sampled gathered data.
Example 1
(x+y+z)2 = x2+2xy+2xz+y2+2yz+z2
| Term | Coefficient | Value of exponents i, j, k, for x, y, z, respectively |
| X2 | 1 | 2,0,0 |
| Y2 | 1 | 0,2,0 |
| Z2 | 1 | 0,0,2 |
| 2x1y1 | 2 | 1,1,0 |
| 2y1z1 | 2 | 0,1,1 |
| 2z1x1 | 2 | 1,0,1 |
Example 2
(x+y+z)3 = x3+y3+z3+3x2y+3x2z+3y2x+3y2z+3z2x+3z2y+6xyz
| Term | Coefficient | Value of exponents i, j, k, for x, y, z, respectively |
| 6x1y1z1 | 6 | 1,1,1 |
| 3z2y1 | 3 | 0,1,2 |
| 3z2x1 | 3 | 1,0,2 |
| 3y2z1 | 3 | 0,2,1 |
| 3y2x1 | 3 | 1,2,0 |
| 3x2z1 | 3 | 2,0,1 |
| 3x2y1 | 3 | 2,1,0 |
| Z3 | 1 | 0,0,3 |
| Y3 | 1 | 0,3,0 |
| X3 | 1 | 3,0,0 |
Example 3
(x+y+z)4 = x4 + y4 + z4+ 4x3y1 + 4x3z1 + 4y3x1 + 4y3z1 + 4z3x1 + 4z3y1 + 6x2y2 + 6x2z2 + 6y2z2 + 12x2y1z1 + 12y2x1z1 + 12z2x1y1
| Term | Coefficient | Value of exponents i, j, k, for x, y, z, respectively |
| x4 | 1 | 4,0,0 |
| y4 | 1 | 0,4,0 |
| z4 | 1 | 0,0,4 |
| 4x3y1 | 4 | 3,1,0 |
| 4y3x1 | 4 | 1,3,0 |
| 4z3x1 | 4 | 1,0,3 |
| 4z3y1 | 4 | 0,1,3 |
| 6x2y2 | 6 | 2,2,0 |
| 6x2z2 | 6 | 2,0,2 |
| 6y2z2 | 6 | 0,2,2 |
| 12x2y1z1 | 12 | 2,1,1 |
| 12y2x1z1 | 12 | 1,2,1 |
| 12z2x1y1 | 12 | 1,1,2 |
Example 4
(x+y+z)5 = x5 + y5 + z5 + 5x4y1 + 5x4z1 + 5y4x1 + 5y4z1 + 5z4x1 + 5z4y1 + 10x3y2 + 10x3z2 + 10y3x2 + 10y3z2 + 10z3x2 + 10z3y2 + 20x3y1z1 + 20y3x1z1 + 20z3x1y1 + 30x2y2z1 + 30x2z2y1 + 30y2z2x1
| Term | Coefficient | Value of exponents i, j, k, for x, y, z, respectively |
| x5 | 1 | 5,0,0 |
| y5 | 1 | 0,5,0 |
| z5 | 1 | 0,0,5 |
| 5x4y1 | 5 | 4,1,0 |
| 5x4z1 | 5 | 4,0,1 |
| 5y4x1 | 5 | 1,4,0 |
| 5y4z1 | 5 | 0,4,1 |
| 5z4x1 | 5 | 1,0,4 |
| 5z4y1 | 5 | 0,1,4 |
| 10x3y2 | 10 | 3,2,0 |
| 10x3z2 | 10 | 3,0,2 |
| 10y3x2 | 10 | 2,3,0 |
| 10y3z2 | 10 | 0,3,2 |
| 10z3x2 | 10 | 2,0,3 |
| 10z3y2 | 10 | 0,2,3 |
| 20x3y1z1 | 20 | 3,1,1 |
| 20y3x1z1 | 20 | 1,3,1 |
| 20z3x1y1 | 20 | 1,1,3 |
| 30x2y2z1 | 30 | 2,2,1 |
| 30x2z2y1 | 30 | 2,1,2 |
| 30y2z2x1 | 30 | 1,2,2 |
Example 5
(x+y+z)6 = x6 + y6 + z6 + 6x5y1 + 6x5z1 + 6y5x1 + 6y5z1 + 6z5x1 + 6z5y1 + 15x4y2 + 15x4z2 + 15y4x2 + 15y4z2 + 15z4x2 + 15z4y2 + 30x4y1z1 + 30y4x1z1 + 30z4x1y1 + 20x3y3 + 20x3z3 + 20y3z3 + 60x3y2z1 + 60x3z2y1 + 60y3x2z1 + 60y3z2x1 + 60z3x2y1 + 60z3y2x1 + 90x2y2z2
| Term | Coefficient | Value of exponents i, j, k, for x, y, z, respectively |
| x6 | 1 | 6,0,0 |
| y6 | 1 | 0,6,0 |
| z6 | 1 | 0,0,6 |
| 6x5y1 | 6 | 5,1,0 |
| 6x5z1 | 6 | 5,0,1 |
| 6y5x1 | 6 | 1,5,0 |
| 6z5x1 | 6 | 1,0,5 |
| 6z5y1 | 6 | 0,1,5 |
| 15x4y2 | 15 | 4,2,0 |
| 15y4x2 | 15 | 2,4,0 |
| 15y4z2 | 15 | 0,4,2 |
| 15z4x2 | 15 | 2,0,4 |
| 15z4y2 | 15 | 0,2,4 |
| 30x4y1z1 | 30 | 4,1,1 |
| 30y4x1z1 | 30 | 1,4,1 |
| 30z4x1y1 | 30 | 1,1,4 |
| 20x3y3 | 20 | 3,3,0 |
| 20x3z3 | 20 | 3,0,3 |
| 20y3z3 | 20 | 0,3,3 |
| 60x3y2z1 | 60 | 3,2,1 |
| 60x3z2y1 | 60 | 3,1,2 |
| 60y3x2z1 | 60 | 2,3,1 |
| 60z3x2y1 | 60 | 2,3,1 |
| 60z3y2x1 | 60 | 1,2,3 |
| 90x2y2z2 | 90 | 2,2,2 |
| 15x4z2 | 15 | 4,2,0 |
| 60y3z2x1 | 60 | 1,3,2 |
| 6y5z1 | 6 | 0,5,1 |
Result
A pattern can be identified between the values of i, j, and k, and the parity of the coefficient. If we observe the values from the table, the parity of the term can be found from the following patterns:
- If the values of i, j and k are of the form: n-1,1,0 (or any arrangement of these 3 values), the parity of the term is odd when the parity of n-1 in the arrangement is even. When the parity of n-1 in the arrangement is odd, the parity of the term is even.
- If all three values of i, j, and k are equal, then the parity of this term is even.
- If the majority of the values of i, j and k have an odd parity and the parity of n is odd, then the parity of the expanded term is even.
- If the parity of the values of i j and k is even and the parity of the n value is even, then the parity of the expanded term is even.
- If the majority (two or more terms) is even and n is an even multiple of 3, then the parity of the expanded term is odd.
Discussion
Hence, the following rules, collectively called Parity of Coefficients Through Patterns (PCTP) rules, is defined:
The coefficient of the term is even, when –
- Rule (1) Even: All three values of i, j, and k are equal and non-zero.
- Rule (2) Even: All the values of i, j, and k are even and the parity of the n value is even.
- Rule (3) Even: All three values of i, j and k are odd and the parity of n is odd.
- Rule (4) Even: One of the values of i, j and k have an even parity while the other two values (j and k or any other arrangement), are odd and the parity of n is even.
- Rule (5) Even: One of the values of i, j and k is even, while the other 2 are equal to 1, and the parity of n is even.
- Rule (6) Even: One of the values of i, j and k is odd, while the other 2 are equal to 1, and the parity of n is odd.
- Rule (7) Even: One of the values of i, j and k is odd, while the other two are even and the parity of n is odd.
The coefficient of the term is odd, when –
- Rule (1) Odd: The values of i, j and k are of the form n, 0, 0.
- Rule (2) Odd: All the values of i, j and k are even and n is an even multiple of 3.
- Rule (3) Odd: The values of i, j and k are of the form n-1,1 and 0 (or any arrangement of this form) and the parity of the n-1 term is even.
In short, a pattern has emerged that can potentially be used to identify the parity of a term using the value of exponents (i, j, k).
Proof
Now that we have a hypothesis on how to go about identifying the parity of a term, let us look at the proof that is applicable for different cases.
Axiom One
The axiom: When the multinomial coefficient theorem is applied to the (x+y+z) n expression:
![\[\frac{n!}{i! j! k!}\]](https://nhsjs.com/wp-content/ql-cache/quicklatex.com-c6143e7ac2ea39663ba737858c1116d4_l3.png "Rendered by QuickLaTeX.com")
The quotient that results is a whole number and hence there are no remainders.
Now, let us first prove the first observation in the even coefficient section which is: If the values of i, j, and k are equal to each other and are non-zero, then the parity of the expanded term is even.
Now, let us apply a proof.
Assumptions: Let us assume the following:
- Two or more values of i, j, and k exponents are equal.
- Value of quotient from the multinomial coefficient formula is a whole number.
Taking the above assumptions into account, the multinomial coefficient formula will be of the form:
![\[n!/(i!)^3\]](https://nhsjs.com/wp-content/ql-cache/quicklatex.com-a785b016f7e979ec4365df305f3bd357_l3.png "Rendered by QuickLaTeX.com")
Here i=j=k, which when multiplied by itself becomes (i!)3. According to Kummer’s theorem13, the result of this is even when there is at least one binary carry during the binary addition of i If i’s value is greater than or equal to 1, then the addition of i 3 times will lead to at least one carry over (1+1+1=11), hence the result is always even except when i is zero (which is a trivial case). Hence, the result of this expression is always even. This expression can also be defined as: 3i! / (i!)3.
Axiom Two
The axiom: If the majority of the values of i, j and k have an even parity and the value of n is even, then the multinomial coefficient form will be:
Assumptions:
- The quotient from the above division is always a whole number.
It’s possible that all the values of i, j and k can be even or only two of them (i.e. i and j or any 2 terms from i, j, k) are even. This expression cannot be completely proven or backed up by a standard theorem such as Kummer’s theorem, since Kummer’s theorem states that the result of n! / (i! j! k!) is going to be even when there’s a binary transfer during the binary addition of i, j and k. Since, the parity of these terms only affect the first binary place value of a number, a binary transfer may occur in the first-place value addition or it may not occur in the further digit places. Hence, there’s not enough details outlined to prove this rule and hence this can be considered a conjecture. This will hence be more of a heuristic based pattern that can be applied to different cases.
Axiom Three
The axiom: If the majority of the values of i, j and k have an odd parity and the parity of n is odd, then the multinomial form will be:
![\[\frac{n!}{even\ product\ (i! j! k!)}\]](https://nhsjs.com/wp-content/ql-cache/quicklatex.com-4940ec68cae94e67dab3b8719d21abd9_l3.png "Rendered by QuickLaTeX.com")
Assumptions:
- The above division leads to a whole number quotient.
- The factorial of an odd or even number always leads to an even product18.
The result of the above expression can be determined by Kummer’s theorem. Kummer’s theorem states that when there is a carry-over during binary addition of i, j and k, then the result will be an even number. The data that can be inferred from the fact that the parity of i, j and k is odd, is the fact that the last digit of each of their values in binary has to be 1. Since all three of these values end with 1 in base 2, when these 1’s are added in base two, there’s always a carry that occurs. Hence, since there’s at least one carry in binary addition, the result will be even.
Axiom Four
The axiom: If the majority of the values of i, j and k are odd while there’s one even value and the parity of n is even, then the general form will be:
Now, we know that i+j+k=n18,19. Since, the parity of two of these terms: i, j and k have a parity of odd while one of terms has an even parity, then the binary addition will lead to a transfer. Since the 2 odd terms will end in 1 while the even term will end in 0, the result will be the binary addition of 1+1+0, which leads to 10 in binary addition. Since there’s a transfer, the result is going to be even.
Axiom Five
The axiom: When one of the values of i, j and k is equal to an even number while the other 2 are equal to 1, then the multinomial coefficient form will be:
![\[\frac{n!}{(n-2)!}\]](https://nhsjs.com/wp-content/ql-cache/quicklatex.com-4035d50b12a7e6f7d72e4212dd40b254_l3.png "Rendered by QuickLaTeX.com")
Assumption:
- i+j+k=n18.
- The above division will lead to a whole number quotient
- The parity of n is even in the above expression.
This would mean that all the common factors of (n-2)! Will be canceled from n! which will lead to the product of an even number and an odd number(n*(n-1)), this will lead to an even number and hence the parity of this expression is even.
Axiom Six
The axiom: When one of the values of i, j and k have an odd parity while the other two are equal to 1 and the parity of n is odd. Then, the multinomial coefficient form of this expression will be:
In the above division all the common factors of (n-2)! Will be cancelled out which leads to the multiplication of n*(n-1) which will lead to an even result as an odd number into an even number is always an even number.
Axiom Seven
The axiom: When two terms from the variables i, j and k are even while the other term’s parity is odd and the parity of n is odd, then the resulting multinomial expression will be:
When the values of all the three terms (i, j and k) are converted to base two, the result is, the least significant digit (the left-most part) will always have a 1 for all 3 of these values. When these values are all added in binary, there will be a transfer of 1 since the values of 1 will align with each other in the least significant digit. When one of the values is zero, the other two numbers will be odd and even in parity. When these two numbers are added, the result will be at least 1 carry over in binary due to the value of 1 being in both the first places of the two terms. Hence, according to the Kummer’s theorem, the result will always be even in parity.
Additionally, there can be a situation wherein there are no carry overs. Hence, according to the Kummer’s theorem, the result will always be odd in parity. As there can be both situations of 1 carry over and no carry overs of 1, the parity of i, j, k alone is not sufficient to identify the parity the co-efficient. Hence to identify the parity the co-efficient, it becomes necessary to use the binary expansions of i, j, and k. The Kummer’s theorem is a fallback to cases where the PCTP rule framework does not classify a configuration.
This proves –
- All three values of i, j, and k are equal and nonzero.
- When the majority of the values of i, j and k have an odd parity and the parity of n is odd (n is not an odd multiple of 3).
- When the values of i, j and k are of the form: n-1,1 and 0 (and any arrangement of these 3 terms) and the parity of the n-1 term is odd.
- When one of the values of i, j and k is even while the other 2 are equal to 1 and the parity of n is even.
- When the one of the values of i, j and k is odd while the other 2 are equal to 1 and the parity of n is odd.
- When one of the values of i, j and k is odd, while the other two are even and the parity of n is odd or even.
Axiom Eight
Five observations have been proved and one conjecture exists. Let’s prove the seventh observation, which is, when none of the values of i, j, and k are equal, then the coefficient of the term is odd.
The axiom: If the value of i, j and k are of the form: n,0,0, then their multinomial coefficient form will be:
![\[\frac{n!}{n!}\]](https://nhsjs.com/wp-content/ql-cache/quicklatex.com-444205854b6cde5326c84e72e66bbf37_l3.png "Rendered by QuickLaTeX.com")
Assumptions: Let us assume the following:
- The sum of i, j and k are equal to n18.
- Value of quotient from the multinomial coefficient formula is a whole number.
If the multinomial coefficient form is of the above form, then the division of n! /n! will always lead to 1 which is odd in parity. Hence the result will always be 1.
Axiom Nine
The axiom: If the majority of the value of I, j and k are even and parity and the value of n is a multiple of 3, then the multinomial coefficient will be of the form:
Assumptions:
- i+j+k is equal to n.
- The quotient of the above division is always a whole number.
- n is a multiple of 3.
Now, when this factorial function is applied, an even number will be in the numerator and there will be an even number in the denominator. When division like this occurs and we know that the number in the numerator is greater than the number in denominator, then there will be some factors left. Now, since we know that n is a multiple of 3, it’s likely that the remaining factor will be multiples of 3 since the denominator will have common factors for dividing the product in the numerator. Hence, the result will be odd due to it being a multiplication of 3’s.
Axiom Ten
The axiom: When the values of i, j and k are of the form: n-1,1,0 and the value of n-1 is even, then the value multinomial coefficient form will be:
![\[\frac{n!}{(n-1)! 1!}\]](https://nhsjs.com/wp-content/ql-cache/quicklatex.com-5bf6ce102054e050be3d98a0558cb463_l3.png "Rendered by QuickLaTeX.com")
Where n will be an odd number and n-1 is an even number. Now, this expression will evaluate to:
![\[\frac{n!}{(n-1)!}\]](https://nhsjs.com/wp-content/ql-cache/quicklatex.com-b99fa2fc466252f6e2131d9db8bba636_l3.png "Rendered by QuickLaTeX.com")
Since (n-1)! will cancel out all the common factors of n except for n itself, the quotient for this division will be n. Since n is an odd number, the parity of this expanded term will be odd.
Benchmark
The rules are proved. Thus, the parity of expanded terms from (x+y+z)n can be determined by using them. But there are a few limitations that must be taken into account while using these rules.
Let’s perform our benchmark in order to check if these rules are better than the multinomial coefficient expression for finding the parity of an expanded term. In order to apply the rules to this, here is the sequence in which these rules are going to be applied: Start → Rule (1) Even → Rule (4) Even → Rule (3) Odd → Rule (2) Even → Rule (3) Even → Rule (2) Odd → Rule (5) Even → Rule (6) Even → Use Kummer’s theorem through binary expansions → Stop.
Case 1: (x+y+z) 8
Let’s predict the parity of a few multinominal coefficients for the expansion, (x+y+z) 8:
- x5y2z1
As per PCTP rules, the predicted parity is even. It required 18 seconds to arrive at this result. It required 4 steps to arrive at this answer (it had to check the parity of i, j, k and n).
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 2 minutes and 14 seconds to arrive at this answer. It required 6 steps (factorial of 8, 5, 2 and 1, then multiplication, division, division by 2 while checking for even parity). - x6y1z1
As per PCTP rules, the predicted parity is even. It required 49 seconds to arrive at the result. It required 24 steps since it needed to reach Rule (5) Even to arrive at this answer.
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 1 minute 56 seconds to arrive at this answer. It needed 6 steps in total to arrive at the result. - x5y1z2
As per PCTP rules, the predicted parity is even. It required 19 seconds to arrive at the answer. It required 4 steps to arrive at this answer.
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 1 minute 49 seconds to arrive at the answer. It needed 6 steps in total. - x4y3z1
As per PCTP rules, the predicted parity is even. It required 13 seconds to arrive at the answer. It required 4 steps in total.
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 2 minutes and 6 seconds to arrive at the answer. It required 6 steps in total. - x4y2z2
As per PCTP rules, the predicted parity is even. It required 21 seconds to answer at the answer. It required 12 steps in total.
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 1 minute 58 seconds to arrive at the answer. It required 6 steps in total. - x4y1z3
As per PCTP rules, the predicted parity is even. It required 13 seconds to arrive at the answer. It took 4 steps in total.
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 1 minute 47 seconds to arrive at the answer. It required 6 steps in total. - x3y3z2
As per PCTP rules, the predicted parity is even. It took 12 seconds to arrive at the answer. It took 4 steps in total.
As per Multinomial Coefficient Theorem, the predicted parity is even. It took 1 minute 19 seconds to arrive at the answer. It required 6 steps in total. - x3y2z3
As per PCTP rules, the predicted parity is even. It required 15 seconds to arrive at the answer. It required 4 steps in total.
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 1 minute and 23 seconds to arrive at this. It required 6 steps in total. - x3y4z1
As per PCTP rules, the predicted parity is even. It required 14 seconds to arrive at the answer. It required 4 steps in total.
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 1 minute and 5 seconds to arrive at the answer. It required 6 steps in total. - x2y5z1
As per PCTP rules, the predicted parity is even. It required 18 seconds to arrive at the answer. It required 4 steps in total.
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 1 minute 11 seconds to arrive at the answer. It took 6 steps in total. - x2y6z0
As per PCTP rules, the predicted parity is even. It required 19 seconds to arrive at the answer. It required 12 steps (3 rules) in total.
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 1 minute and 17 seconds to arrive at the answer. It required 6 steps in total. - x1y3z4
As per PCTP rules, the predicted parity is even. It required 14 seconds to arrive at the answer. It needed 4 steps in total.
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 1 minute 3 seconds to arrive at the answer. It needed 6 steps.
Case 2: (x+y+z) 9
Let’s predict the parity of a few multinominal coefficients for the expansion, (x+y+z) 9:
- x6y2z1
As per PCTP rules, the predicted parity can either be even or odd. To identify the exact parity of the coefficient, a binary expanded form of i, j, k is required and the Kummer’s theorem must be used. Kummer’s theorem predicted even. It required 1 minute and 12 minutes to arrive at this. It required 33 steps.
As per Multinomial Coefficient theorem, It predicted even. It required 2 minutes and 25 seconds of calculation. It required 6 steps to arrive at the answer. - x5y3z1
As per PCTP rules, the predicted parity is even. It required 25 seconds and 20 steps to arrive at the result.
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 1 minute and 57 seconds to arrive at the result. It took 6 steps. - x4y2z3
As per PCTP rules, the predicted parity can either be even or odd. To identify the exact parity of the coefficient, a binary expanded form of i, j, k is required and the Kummer’s theorem must be used. Kummer’s theorem predicted even. It required 51 seconds to arrive at this answer. It required 33 steps to arrive at the answer.
As per Multinomial Coefficient theorem: It predicted even. It required 2 minutes to calculate this. It took 6 steps in total. - x3y3z3
As per PCTP rules, the predicted parity is even. It required 8 seconds to arrive at this result. It required 3 steps to arrive at the result.
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 1 minute and 18 seconds to arrive at the answer. It required 6 steps to arrive at the result. - x7y0z2
As per PCTP rules, the predicted parity can either be even or odd. To identify the exact parity of the coefficient, a binary expanded form of i, j, k is required and the Kummer’s theorem must be used. Kummer’s theorem predicted even. It required 58 seconds to arrive at the answer. It required 33 steps.
As per Multinomial Coefficient Theorem, it predicted even. It required 1 minute and 1 second to arrive at this answer. It took 6 steps to arrive at this answer. - x2y6z1
As per PCTP rules, the predicted parity can either be even or odd. To identify the exact parity of the coefficient, a binary expanded form of i, j, k is required and the Kummer’s theorem must be used. Kummer’s theorem predicted even. It required 1 minute and 12 minutes to arrive at this. It required 33 steps.
As per Multinomial Coefficient Theorem, it predicted even. It required 45 seconds of calculations to arrive at this answer. It required 6 steps to arrive at this answer. - x1y5z3
As per PCTP rules, the predicted parity is even. It required 21 seconds to arrive at the answer. It required 18 steps.
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 51 seconds to arrive at the answer. It required 6 steps to arrive at the answer. - x0y7z2
As per PCTP rules, the predicted parity can either be even or odd. To identify the exact parity of the coefficient, a binary expanded form of i, j, k is required and the Kummer’s theorem must be used. Kummer’s theorem predicted even. It required 47 seconds to arrive at the answer. It required 33 steps to arrive at the answer.
As per Multinomial Coefficient theorem, It predicted even. It Required 35 seconds to arrive at this answer. It required 6 steps to arrive at this answer. - x0y8z1
As per PCTP rules, the predicted parity is odd. It required 26 seconds to arrive at the answer. It required 12 steps to arrive at the answer.
As per Multinomial Coefficient Theorem, the predicted parity is odd. It required 48 seconds to arrive at this answer. It required 3 steps to arrive at the answer. - x4y4z1
As per PCTP rules, the predicted parity can either be even or odd. To identify the exact parity of the coefficient, a binary expanded form of i, j, k is required and the Kummer’s theorem must be used. Kummer’s theorem predicted even. It required 42 seconds to arrive at the answer. It required 32 steps.
As per Multinomial Coefficient Theorem, the predicted parity is even. It required 1 minute and 7 seconds. It required 6 steps in total.
After conducting the test on the sample set, it was found that the PCTP rules are able to classify all 12 terms of n=8 with 100% accuracy. It was able to classify 4 terms of n=9 and for the rest of the terms it required use of binary expansion and fall back to the Kummer’s theorem for prediction.
The average time required to identify the parity of coefficient by direct application of the PCTP rule is 19 seconds. Where a direct application of PCTP rule was not available, a binary expansion was done and the Kummer’s theorem was used, the average time taken was 57 seconds. So, for the sample set (n=8 and n=9), the average time required to identify the parity of coefficient by use of PCTP rules, supplemented by use of the Kummer’s theorem was, 29 seconds.
In comparison, when multinomial coefficient theorem was used to classify the terms that PCTP rules were able to classify, the average time required was 90 seconds. Additionally, when multinomial coefficient theorem was used on all the terms that PCTP rules were used to classify, with the supplement of binary expansion with the Kummer’s theorem, the average time was 87 seconds.
In summary, when PCTP rules were used to classify, it took 71 seconds less than the multi-nominal coefficient theorem for the sample set. It’s a 79% reduction in time. Additionally, when PCTP rules plus the use of binary expansion with the Kummer’s theorem was used, it took 58 seconds less than the multinomial coefficient theorem. It’s a 67% reduction in time.
Significance
The rules are significant to the field of math as finding the parity of an expanded term can significantly reduce the computation required to find the parity of a term from the expansion (x+y+z)n. These rules are useful in probability problems where counting the outcomes of an event involves combinatorial conditions, since they let the parity of a coefficient be read off quickly in common cases. The exact and general test for the parity of a multinomial coefficient is already known — by Kummer’s theorem, the coefficient is odd precisely when adding i, j, and k in base 2 produces no carries — and it can potentially be applied by hand. The contribution here is not a new criterion but a more accessible reformulation of it: for several frequently occurring configurations of i, j, k, and n, the parity can be determined directly from simple parity conditions, without carrying out the binary addition or evaluating the multinomial coefficient. For the cases they cover, these shortcuts reduce the work needed to classify a term as even or odd. Since this method can be applied to a wide
range of cases it’s a step forward for computational mathematics.
Limitations
The rules can only be used to find the parity of an expanded term; it does not produce the coefficient of each expanded term. In order to find the coefficient of each expanded term, the Multinomial Coefficient theorem has to be used. Additionally, every expanded term cannot be classified under the PCTP framework as the number of terms in an expansion increases combinatorically and thus the number of combinations of values for i, j and k increase at a similar pace. This is the reason why, if a term is not classified under any PCTP rule, Kummer’s theorem must be used. It does not classify every permutation and combination of the values of i, j and k; thus, the Kummer’s theorem must be used as a fallback if any combination does not trigger a rule.
Conclusion
In conclusion, it has been proved there is a pattern to identify the parity of a multinomial term. And each of the rules, except for one conjecture, has been mathematically proven. Hence, it is safe to say that if one needs to find the parity of a term (with guidelines followed) from the expansion (x+y+z) n, the following rules can be applied:
The coefficient of the term is even, when –
- All three values of i, j, and k are equal and nonzero.
- The majority of the values of i j and k are even and the parity of the n value is even.
- The majority of the values of i, j and k have an odd parity and the parity of n is odd (n is not an odd multiple of 3).
- The values of i, j and k are of the form: n-1,1 and 0 (and any arrangement of these 3 terms) and the parity of the n-1 term is odd.
- One of the values of i, j and k is even while the other 2 are equal to 1 and the parity of n is even.
- One of the values of i, j and k is odd while the other 2 are equal to 1 and the parity of n is odd.
- One of the values of i, j and k is odd, while the other two are even and the parity of n is odd or even. To identify the exact parity of the coefficient, a binary expanded form of i, j, k must be used with the Kummer’s theorem.
The coefficient of the term is odd, when –
- The values of i, j and k are of the form n,0,0.
- The majority is even and n is an even multiple of 3, then the parity of the expanded term is odd.
- The values of i, j and k are of the form n-1,1 and 0(or any arrangement of this form) and the parity of the n-1 term is even.
Following is a representation of the PCTP rules in a tabular format.
| i parity | j parity | k parity | n parity | PCTP rule to apply | Predicted Coefficient parity |
| Even | Even | Even | Even | Rule (2) Even | Even |
| Even | Even | Odd | Odd | This requires binary expansion of i, j, and k. | Even or Odd |
| Even | Odd | Even | Odd | This requires binary expansion of i, j, and k. | Even or Odd |
| Odd | Even | Even | Odd | This requires binary expansion of i, j, and k. | Even or Odd |
| Even | Odd | Odd | Even | Rule (4) Even | Even |
| Odd | Even | Odd | Even | Rule (4) Even | Even |
| Odd | Odd | Even | Even | Rule (4) Even | Even |
| Odd | Odd | Odd | Odd | Rule (3) Even | Even |
| 1 | 1 | Even | Even | Rule (5) Even | Even |
| 1 | 1 | Odd | Odd | Rule (6) Even | Even |
| 1 | 0 | 0 | 1 | Rule (1) Odd | Odd |
| 0 | 1 | 0 | 1 | Rule (1) Odd | Odd |
| 0 | 0 | 1 | 1 | Rule (1) Odd | Odd |
| n | 0 | 0 | n | Rule (1) Odd | Odd |
| n-1 | 1 | 0 | n | Rule (3) Odd | Odd |
| n-1 | 0 | 1 | n | Rule (3) Odd | Odd |
| 1 | n-1 | 0 | n | Rule (3) Odd | Odd |
| 1 | 0 | n-1 | n | Rule (3) Odd | Odd |
| 0 | 1 | n-1 | n | Rule (3) Odd | Odd |
In order to apply the rules in the form of a framework, the sequence of rule can be as follows:
Start → Rule (1) Even → Rule (4) Even → Rule (3) Odd → Rule (2) Even → Rule (3) Even → Rule (2) Odd → Rule (5) Even → Rule (6) Even → Use Kummer’s theorem through binary expansions → Stop.
A sequential application of the rules ensures identification of the parity of each expanded term as-and-when the said criteria in each rule is fulfilled.
Reference
- Bolton, D. W. “The Multinomial Theorem.” The Mathematical Gazette 52.382 (1968): 336–342. Web. [↩]
- Abramson, M. (1968). Multinomial Coefficients. Mathematics Magazine, 41(4), 199–205. https://doi.org/10.1080/0025570X.1968.11975878 [↩]
- Annamalai, Chinnaraji. (2022). Computing Method for Combinatorial Geometric Series and Binomial Expansion. SSRN Electronic Journal. 10.2139/ssrn.4168016. [↩]
- Annamalai, Chinnaraji. (2022). Novel Multinomial Expansion and Theorem. SSRN Electronic Journal. 10.2139/ssrn.4275263. [↩]
- Annamalai, Chinnaraji. (2022). Algorithmic Approach for Computation of Binomial Expansions. 10.31219/osf.io/a9cwh. [↩]
- Ma, N. (2001). Complete multinomial expansions. *Applied Mathematics and Computation*, 124(3), 365–370. https://doi.org/10.1016/S0096-3003(00)00102-8. [↩]
- Flath, D., & Peele, R. (1991). A carry theorem for rational binomial coefficients. In G. E. Bergum, A. N. Philippou, & A. F. Horadam (Eds.), *Applications of Fibonacci numbers*. Springer. https://doi.org/10.1007/978-94-011-3586-3_13 [↩] [↩]
- Kummer, E. (1852). Über die Ergänzungssätze zu den allgemeinen Reziprozitätsgesetzen. Journal für die reine und angewandte Mathematik, 44, 93–146. [↩] [↩] [↩]
- Noble, E. (2022). A history of the binomial and multinomial theorems. In *The rise and fall of the German combinatorial analysis* (pp. 17–66). Springer. https://doi.org/10.1007/978-3-030-93820-8_2. [↩]
- Spiegelhofer, L., & Wallner, M. (2018). Divisibility of binomial coefficients by powers of two. Journal of Number Theory, 192, 221–239. https://doi.org/10.1016/j.jnt.2018.04.010 [↩]
- Bennett, C. D., & Shpectorov, S. (2001). A remark on a theorem of J. Tits. *Proceedings of the American Mathematical Society*, 129, 2571–2579. https://doi.org/10.1090/S0002-9939-01-06234-7 [↩]
- Granville, A. (1997). Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers. In Organic Mathematics (CMS Conference Proceedings, Vol. 20, pp. 253–276). American Mathematical Society [↩]
- Singmaster, D. (1974). Notes on binomial coefficients I—A generalization of Lucas’ congruence. Journal of the London Mathematical Society, s2-8(3), 545–548. https://doi.org/10.1112/jlms/s2-8.3.545 [↩]
- Volodin, N. A. (1999). Multinomial coefficients modulo a prime. *Proceedings of the American Mathematical Society*, 127(2), 349–353. https://doi.org/10.1090/S0002-9939-99-05079-0 [↩]
- Lee, N., Harris, J., Clark, B., & Eteng, S. (2026, February 27). Efficient methods for determining coefficients in multinomial expansions. ResearchGate. https://www.researchgate.net/publication/402709586_Efficient_Methods_for_Determining_Coefficients_in_Multinomial_Expansions [↩] [↩] [↩]
- Granville, A. (1997). Arithmetic properties of binomial coefficients. I. Binomial coefficients modulo prime powers. In Organic Mathematics (CMS Conference Proceedings, Vol. 20, pp. 253–276). American Mathematical Society. [↩]
- Wilks, D. S. (2019). Statistical methods the atmospheric sciences (4th ed.). Academic Press.in [↩]
- Andrews, G. E., Knopfmacher, A., & Zimmermann, B. (2006). On the number of distinct multinomial coefficients. Journal of Number Theory, 118(1), 15–30. https://doi.org/10.1016/j.jnt.2005.08.012. [↩] [↩] [↩] [↩]
- Erdös, P. (1954). The number of multinomial coefficients. The American Mathematical Monthly, 61(1), 37-39 [↩]
