0

I am trying to solve a tricky problem that deals with total number of possible combinations. Basically, the input is an even number that represents the total length of possible digits. The goal is to determine how many combinations where the sum of the left side equals the sum of the right side. How might you represent this mathematically or in some formula ?

n(2) = 10

"00", "11", "22", "33", "44", "55", "66", "77", "88", "99"

n(4) = 385

"0000", "0101", "0110", "1001", "1010", "0202", "0211" etc.

n(6) = 4981 ?

turbofood
  • 1
  • To find $n(2k)$ Consider the expansion of $(1+x+x^2+\dots+x^9)^k$. Square each coefficient individually and then sum the results. For instance for $n(6)$ we have that $(1+x+x^2+\dots+x^9)^3 = 1+3x+6x^2+10x^3+15x^4+\dots+3x^{26}+x^{27}$ and we have $1+3^2+6^2+10^2+15^2+21^2+\dots+3^2+1^2=55252$. Note that $n(2)=10,~n(4)=670,~n(6)=55252$ and so on, your numbers were off for your initial attempts. – JMoravitz Jan 31 '22 at 18:24
  • See https://oeis.org/A174061 – JMoravitz Jan 31 '22 at 18:25
  • Thank you so much. So what would x be in those examples ? – turbofood Jan 31 '22 at 18:30
  • $x$ is a placeholder. It does not take a value. It appears only so as to facilitate calculations by allowing each term in the expansion to be kept separate and organized according to the exponents which here we have represent the sums of the first half of each combination. Read more about generating functions on wikipedia or in the freely available book Generatingfunctionology. – JMoravitz Jan 31 '22 at 18:32
  • Sorry I should have asked a different follow up, what would the expansion of n(4) look like with only the values & no variables? n(4) = 670 – turbofood Jan 31 '22 at 18:35
  • $(1+x+x^2+x^3+\dots+x^9)^2\mapsto 1+2x+3x^2+4x^3+5x^4+\dots+9x^8+10x^9+9x^{10}+\dots+2x^{17}+x^{18}\mapsto 1^2+2^2+3^2+\dots+9^2+10^2+9^2+\dots+2^2+1^2 = 670$. Again, start with the generating function for the number of ways to have the first half be some particular sum. Square each coefficient to have the generating function for the number of ways to have both halves with the same particular sum, and then add across all possible sums. – JMoravitz Jan 31 '22 at 18:37
  • Perfect, thanks a ton – turbofood Jan 31 '22 at 18:39
  • Sorry final ques, do you know why my math is wrong here ?

    31^2$ + 33^2$ + 36^2$ + 310^2$ + 315^2$ + 321^2$ + 328^2$ + 336^2$ + 345^2$ + 355^2$ + 366^2$ + 378^2$ = 55146

     – turbofood Jan 31 '22 at 19:49
  • Why would you multiply each term by three? Why does $66$ and $78$ appear in your calculations? There is specific reason why I opted to describe as the generating function as I had and not with stars-and-bars. While it may be true that for finding $n(2k)$ each of the first ten coefficients in the expansion could be seen as $\binom{i+k-1}{k-1}$ it is not true for the middle terms in the sum and this gets far worse for larger $k$. Some of the outcomes counted by stars and bars would have included situations where one or more of the "digits" exceeded nine. – JMoravitz Jan 31 '22 at 19:52
  • We very specifically expand $(1+x+x^2+\dots+x^9)^k$, not $(1+x+x^2+\dots)^k$. Sure, you can save a bit of time by noting the sum starts the same way as it ends, take care about the middle term if it is doubled or not. You can get here $2\cdot (1^2+3^2+6^2+10^2+15^2+21^2+28^2+36^2+45^2+55^2+\color{red}{63^2+69^2+73^2+75^2})=55252$ – JMoravitz Jan 31 '22 at 19:54

0 Answers0