Triangular Combinations

          During my work on polynomial expansions, I came across this pleasing result.  Enjoy!

                    ²C₂ = 1

                            = (2 - 1)

                    Assuming that ^kC₂ = 1 + 2 + ... + (k - 1),

                    To prove that ^{k + 1}C₂ = 1 + 2 + ... + k,

                    Note that to choose 2 from a set with 1 more item than the previous, we simply include the new item and find the number of combinations of two that include that item.  The new sets contain the number in the old set, each combined with the new item, and hence we simply add k.  So:

                     ^{k + 1}C₂ = ^kC₂ + k

                                   = 1 + 2 + ... + (k - 1) + k    (as required)

                     ∴ if true for k, it is true for k + 1

                     But it is true for 2, so it is true for 2 + 1 = 3, 3 + 1 = 4 and so on for all integers > 2

                     ∴ By induction, all combinations of 2, in a set of x, are the triangular number for n = x - 1

General Polynomial Expansion

          This idea came to me while reading "Basic Concepts of Probability and Statistics -Second Edition," written by J. L. Hodges, Jr. and E. L. Lehmann It is based on the idea that the general binomial expansion is not general enough as it only allows for those expansions involving two initial terms.  To expand the current process (excuse the pun), we can simply look over how the original formula was obtained.  In the binomial expansion, we express (a₁ + a₂)ⁿ, as (a₁ + a₂)(a₁ + a₂)(a₁ + a₂)..., then choose a term from each of the n sets, to obtain a result where the terms are given with each possibility of combinations of powers on the two terms, the sum of the powers being n.  The coefficients of each term in the expansion is then given by the number of ways each term can be chosen from by taking one term from each bracket.  This gives the well known result:

                                        _n

                    (a₁ + a₂)ⁿ = ∑   ⁿC_ka₁^{n - k}a₂^k

                                      ^{k = 0} 

          The same principal can be applied to obtain the general polynomial expansion.  Thus, to expand (a₁ + a₂ + a₃ + … + a_x)ⁿ, we first must look at the process as that of choosing n terms, with replacement, from the set E = {a₁, a₂, a₃, …, a_x}.  From this we achieve all possible combinations of a₁^p, a₂^q, a₃^r, ..., a_x^x where q + r + s + ... + x = n.  By first choosing the objects of E that correspond to the power of a₁, then those for a₂, and so on through to a_x, we find the number of ways this particular term can be extracted, and thus the coefficient on the term in the expansion.  Thus, the coefficient on a₁^pa₂^qa₃^r...a_x^x in (a₁ + a₂ + a₃ + … + a_x)ⁿ is given by:

                    ⁿC_p.^{n - p}C_q.^{n – (p + q)}C_r...^{n – (p + q + r + …)}C_x

          From this we can observe that changing the position of a power (i.e. having a^qb^p, instead of a^pb^q), should not change the coefficient.  This corresponds to the intuitive notion that selecting p objects from a group of n objects, then choosing another set of q objects should have the same number of possibilities as if the q objects were chosen first, since the end result of two sets of p and q objects is the same.  Algebraically:

                    ⁿC_q.^{n - q}C_p = n! / q!(n - q)! . (n - q)! / p!(n - q - p)!

                                       = n! / q!p!(n - p - q)!

                    ⁿC_p.^{n - p}C_q = n! / p!(n - p)! . (n - p)! / q!(n - p - q)!

                                       = n! / p!q!(n - q - p)!

                                       = ⁿC_q.^{n - q}C_p                    (as required)

                     This then carries on to any rearrangement of powers as the first can then be expressed as (p + q) for further coefficients.  Notice, that when the sum of the powers reach n, subsequent coefficients will be equal to 1 (by definition of ⁿC_n), and subsequent powers (which must equal 0 to keep the sum of powers at n) will contribute nothing to the product (simply multiplying the current coefficient by 1)

          We can also determine a few properties of this expansion that relate to those found in the specific case for binomial expansions.  We determined in the binomial expansion that the sum of the coefficients is equal to 2ⁿ, by setting x = 1 in the expansion of (1 + x)ⁿ.  Similarly, by setting a₁ = a₂ = a₃ = ... = a_x = 1 in the polynomial expansion we find that the coefficients of the polynomial expansion sum to xⁿ.

          Another property studied in binomial theorem is that of maximum coefficients.  In the polynomial expansion there are ^xC₂ local maximums that exist between each pair of terms in the original, unexpanded form.  This can be represented by writing out the terms in the expansion in a set of rows, each containing all terms possible for each successive term of the unexpanded form, disregarding any terms that appear in previous rows.  When such a list is compiled (as below), generally, no row will contain more than one local maximum (see below for the exceptions).

                    a₁ⁿ, a₁^{n - 1}a₂, a₁^{n - 1}a₃, ..., a₁^{n - 1}a_x, a₁^{n - 2}a₂², a₁^{n - 2}a₃², ..., a₁^{n - 2}a_x², a₁^{n - 2}a₂a₃, ...

                    a₂ⁿ, a₂^{n - 1}a₃, a₂^{n - 1}a₄, ..., a₂^{n - 1}a_x, a₂^{n - 2}a₃², a₂^{n - 2}a₄², ..., a₂^{n - 2}a_x², a₂^{n - 2}a₃a₄, ...

                    a₃ⁿ, a₃^{n - 1}a₄, a₃^{n - 1}a₅, ..., a₃^{n - 1}a_x, a₃^{n - 2}a₄², a₃^{n - 2}a₅², ..., a₃^{n - 2}a_x², a₃^{n - 2}a₄a₅, ...

                    ...

                    a_{x - 1}ⁿ, a_{x - 1}^{n - 1}a_x, a_{x - 1}^{n - 2}a_x², ..., a_{x - 1}a_x^{n = 1}

                    a_xⁿ

          Of these maximums, if we define the largest term of the expression in unexpanded form as the term with the largest coefficient, for the m largest terms that are equal, there are mC₂ absolute maximums which are all equal.  Absolute maximums will only appear on the list in the rows for those original largest terms (Note: unless the last of these has a maximum when its power is n, its corresponding row on the list will not contain a maximum as they appear earlier in the list).  If there are only one or two largest terms then there is a unique absolute maximum between the largest two terms (whether the terms are equal or not), appearing in the list in the row of higher (in appearance) of the two largest terms.

          For either type of maximum, they may not always be mutually explicit.  As we have double and triple roots of polynomials, we also have poly-ple maximums of polynomial expansions.  This may occur when the local maximum between two terms is given when one of the powers is equal to 0 and the another set of two terms, having a term in common (that did not have a power of 0 at the local maximum) with the first set has its other term given a power of 0.  This also occurs with equal terms, a special result of which we discussed, which is when absolute maximums occur.  When these occur, the term appearing higher on the list will include the local maximum in its row, and this term will be ignored in the latter terms row.  This may lead to an exception of the rule stated above that no row will contain more than one maximum, as there may exist a set of maximums that are common to a few rows.

          The expansion list above, when fully expanded for any values of x and n, will actually form an odd sided triangle.  This reflects the following method for finding the number of terms in an expansion, which, for simplicity, will here be denoted as t(x, n).  This can be seen as a function which takes the input of x number of starting terms, and n the power of the expansion, outputting t the number of terms in the expanded (and simplified via gathering like terms) form.  In order to find the value for t given by a specific set of inputs, we use the following identities:

                    1.  t(x, n) = t(x - 1, n) + t(x - 1, n - 1) + ... + t(x - 1, 0)

                    2.             = t(x - 2, n) + 2t(x - 2, n -1) + ... + (k + 1)t(x - 2, n - k) + ... + (n + 1)t(x - 2, n - n = 0)

                    3.  t(2, n) = n + 1

                    4.  t(1, n) = 1

                    5.  t(0, n) = 0

                    6.  t(x, 0) = 1

                    7.  t(x, 1) = x

          The first two equations are derived from the fact that an expression can be represented by taking one of the terms, a_k, out and, for each power from 0 to n of this term, multiplying by the expansion of the remaining terms to the conjugate power, or n minus the power on a_k.  The second equation is found through a second application on the first and a gathering of like terms.  The other formulas are given by previously recognised relations; respectively, binomial expansions, power of a single term, power of empty set, taking the power of 0, and 1.  By subsequent applications of the first two equations, one can reduce the expression to a set of the other five, and evaluate.  For elaboration, look over the following examples.

Example 1

          Find the number of terms in the general trinomial expansion, in terms of the power.

          t(x, 3) = t(2, n) + t(2, n - 1) + t(2, n - 2) + ... + t(2, 0)      (by equation 1)

                     = n + 1 + n + n - 1 + ... + 1                          (by equations 2 & 6)

          which is the triangular number  for n + 1.  As proven by induction on series, this is given by:

          ((n + 1)2 + (n + 1)) / 2 = (n2 + 2n + 2) / 2

Example 2

          Find the number of terms in a quadratic expansion in terms of the number of initial terms.

          t(x, 2) = t(x - 2, 2) + 2t(x - 2, 1) + 3t(x - 2, 0)                (by equation 1)

                     = t(x - 2, 2) + 2(x - 2) + 3                           (by equations 6 & 7)

                     = t(x - 2, 2) + 2x - 1

           This will continue, adding 2(x - 2k) + 3 for each of the k applications, until x - 2k is equal to 2 or 1 which can be solved by means of equations 3 & 4.  The number of applications required by this process is given by:

          1 + 2k = x (if x is odd)   OR    2 + 2k = x (if x is even)

                  k = (x - 1) / 2                            k = (x - 2) / 2

          This leads to the result (from working above):

                                     _{(x - 1) / 2}

          t(x, 2) = t(1, 2) +    ∑    [2(x - 2k) + 3]       (if x is odd)

                                      ^{k = 1}

                     = 1 + {the sum above}              (by equation 4)

                                       OR

                                    _{(x - 2) / 2}

          t(x, 2) = t(2, 2) +   ∑    [2(x - 2k) + 3]       (if x is even)

                                     ^{k = 1}

                     = 3 + {the sum above}               (by equation 3)

          Note: The result for even x could have been obtained using an extra application and equation 5 as follows:

                                     _{x / 2}

          t(x, 2) = t(0, 2) +  ∑  [2(x - 2k) + 3]

                                    ^{k = 1}

                     = 0 + {the sum above}               (by equation 5)

          So for the last value of k, 2(x - 2k) + 3 = 3, we can see why by the following result:

                2(x - 2k) + 3 = 3
                      2(x - 2k) = 0
                                  k = x / 2    (which is true for the last value of k)