From: rusin@vesuvius.math.niu.edu (Dave Rusin)
Newsgroups: sci.math
Subject: Re: Counting Problem
Date: 11 Mar 1998 06:22:03 GMT

In article <34FD69BE.125B@pitt.edu>,  <tjfst6+@pitt.edu> wrote:
>Let q be a natural number, and m another natural number.
>How many different decompositions can I obtain
>
>q^m= c_1 + c_2 * q + c_3 * q^2 + ...+ c_(m-1) * q^(m-1),
>
>where all of the c_k are non-negative integers?

I don't know how you expect the answer to look; I can show you how to
derive the answer as a polynomial in  q  for any fixed m. I assume a
minor typo: you wanted decompositions
	q^m = c_0 + c_1*q + c_2*q^2 + ... + c_(m-1) * q^(m-1).


With a fixed  q  understood, we can more generally let
	f_m( N ) = number of decompositions of  N  of the form above.

Then we have the obvious recursion
	f_(m+1) ( N ) = f_m( N ) + f_m( N-q^m ) + f_m( N - 2q^m ) + ...
and the starting expression
	f_1( N ) = 1, if  N >= 0;
	         = 0, if  N < 0.

So then if we define  k_i = floor( N/q^i ) + 1, we may write
	f_2( N ) = 1 + floor( N/q ) = k_1   (for  N >= 0);
	f_3( N ) = (1 + floor( N/q )) + (1 + floor( N/q - q )) + ...
	         = k_1 * k_2 - q * k2 * (k2-1)/2
	         = (1/2)*k2*(2*k1 - q*k2 + q)
In particular, of course, 
	f_1( q ) = 1
	f_2( q^2 ) = q + 1
	f_3( q^3 ) = (1/2) q^2 (q+1).

Now, in	general if we write  f_m( N ) = F(k_1, k_2, ...k_(m-1) )  then
	f_(m+1)( N ) = Sum F(k_1 - i*q^(m-1), k_2 - i*q^(m-2), ... ), 0<=i<k_m

So we can compute as many  f_m  as desired. For example, 
	f_4( N ) = sum( (k2-i*q)*(2*(k1-i*q^2)-q*(k2-i*q)+q)/2, i=0..k3-1 )
which Maple sums to
                   2                                                  2      2
  1/12 k3 (- 6 q k2  + 12 k1 k2 + 6 k2 q - 6 k1 q k3 + 6 k1 q - 3 k3 q  + 3 q

            3   2      3       3
       + 2 q  k3  - 3 q  k3 + q )

I won't recreate the next step but you can have maple execute
  f5:=factor(sum(subs({k1=k1-i*q^3, k2=k2-i*q^2, k3=k3-i*q},f4), i=0..k4-1));
and so on.

Now, originally you asked for  f_m( q^m ). For example, when  m=4, this is
>	factor(subs({k1=q^3,k2=q^2,k3=q},f4));
                                 3             2
                           1/12 q  (q + 1) (2 q  + q + 3)
and when  m=5  it's
                     4           5    4      3      2
               1/24 q  (q + 1) (q  + q  + 2 q  + 3 q  + 2 q + 3)

I believe one could show the general form of the expression you seek is
a polynomial in  q  of degree  m(m-1)/2  and leading coefficient 1/(m-1)!
It seems also to be true that  q^(m-1) (q+1)  is a factor for m > 2.

dave