[Math] The number of ways to represent a natural number as the sum of three different natural numbers

ceiling-and-floor-functionscombinatoricscontest-mathnatural numberstelescopic-series

Prove that the number of ways to represent a natural number $n$ as the sum of three different natural numbers is equal to $$\left[\frac{n^2-6n+12}{12}\right].$$
It was in our meeting a year ago, but I forgot, how I proved it.

Let the needed number be $a_n$, where $n\geq6$ and let $b_n$ be number of ways to represent a natural number $n$ as the sum of two different natural numbers.

Thus, $a_n=b_{n-3}+b_{n-6}+…$ because we can go from $(a,b)$, where $a<b$, to $(1,a+1,b+1)$, $(2,a+2,b+2)$…

Thank you for your help!

Best Answer

If $n=r+s+t$ is a representation of a positive integer as a sum of integers which $r>s>t>0$, then $n-6=(r-3)+(s-2)+(t-1)$ is a representation of $n-6$ as a sum of integers $(r-3) \ge(s-2)\ge(t-1)\ge0$, that is a partition of $n-6$ into at most three parts. Therefore $a_n=c_{n-6}$ where $c_n$ is the number of partitions of $n$ into at most three parts.

By conjugation of partitions, $c_n$ is the number of partitions of $n$ into parts of size at most $3$. So the generating function of the $c_n$ is $$C(x)=\sum_{n=0}^\infty c_nx^n=\frac1{(1-x)(1-x^2)(1-x^3)}.$$ Now use the normal manoeuvres with rational functions to find the $n$-th term: write in partial fractions $$C(x)=\frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{(1-x)^3}+ \frac{D}{1+x}+\frac{E+Fx}{1+x+x^2}$$ and go from there.

Related Solutions

[Math] Ways to sum to $n$ with $m$ integers that are $\le k$

There are many known formulas for the restricted integer composition problem. The one you have given,

$$p(n,m,k)=\sum_{i=0}^k p(n-i,m-1,k)$$

characterizes restricted integer compositions as extended binomial coefficients. If $k=1$, this is simply the formula for the binomial coefficients ($C(m,n)=C(m-1,n)+C(m-1,n-1)$). So, your problem can be seen as a natural generalization of binomial coefficients and your numbers generate a Pascal triangle like array.

This sequence may also be of relevance http://oeis.org/A008287

EDIT To compute the number $p(n,m,k)$ based upon the above recurrence, set up a (sufficiently) large matrix $T(i,j)$, with all elements initialized to zero. Set $T(0,0)=1$. Then, for $i>0$, compute $T(i,j)=\sum_{i=0}^k T(i-1,j-i)$, until you arrive at your desired row $m$ and column $n$. This should be pretty fast, there is no need for exhaustive enumeration. For instance, a python script to compute $p(n,m,k)$ would be

  n=8; m=6; k=9
  T=[[0 for i in xrange(100)] for j in xrange(100)] # enough memory
  T[0][0]=1
  for j in xrange(1,m+1):
      for i in xrange(n+1):
          for r in xrange(k+1):
             if i-r>=0: T[j][i]+=T[j-1][i-r]
  print T[m][n]

Runtime is $O(mnk)$.

[Math] Sum/Product of two natural numbers is a natural number

I'm going to do something I rarely do, namely defining $\Bbb N$ to include $0$ as an element. It makes the treatment herein a little easier or at least a little more Peano-conventional; feel free to adjust it, as an exercise, to start $\Bbb N$ at $1$.

From $$0\in\Bbb N,\,\forall n\in\Bbb N (Sn\in\Bbb N),\,a+0=a,\,a+Sb=S(a+b),\,a\times 0=a,\,a\times Sb=a\times b+a$$and $$\varphi(0)\land\forall n(\varphi(n)\to\varphi(n+1))\to\forall n\in\Bbb N(\varphi(n))$$we'll prove $\forall a,\,b\in\Bbb N(a+b\in\Bbb N)$, and as a separate theorem $\forall a,\,b\in\Bbb N(a\times b\in\Bbb N)$. For both proofs we'll induct on $b$.

First, addition. The case $b=0$ is trivial because $a+0=a\in\Bbb N$. Now we just need the inductive step; if it works when $b=k$ then $a+k\in\Bbb N\implies a+Sk=S(a+k)\in\Bbb N$.

Next, multiplication; the addition result is actually needed in the inductive step. Again, $b=0$ is trivial because $a\times 0=0\in\Bbb N$. Now the inductive step, assuming $a\times k$ exists; then $a\times Sk=(a\times k)+a$ is the sum of two elements of $\Bbb N$, completing the proof by the above result.

You may also wish as an exercise to use this result about multiplication to in turn prove $a^b\in\Bbb N$ using $a^0=1,\,a^{Sb}=a^b\times a$.

Best Answer

Related Solutions

[Math] Ways to sum to $n$ with $m$ integers that are $\le k$

[Math] Sum/Product of two natural numbers is a natural number

Related Question