Solving Constrained Sums of N Non-Negative Integers

[wdlang]

suppose i have N non-negative integers x_1, x_2, ,,, x_N

the constraint is that their summation is N

now for all the configurations, i.e., all the realizations of x_1, x_2, ,,, x_N

i want to find out the average value of

\sum_i x_i^2

i guess is on the order of unity, i.e., O(1).

i am concerned with the large N limit

 

[mathman]

The average value will be somewhere between 1 and N. It depends on what sort of distribution functions the x_k have.

 

[bpet]

First few numbers are (1, 10/3, 60/10).

It could be solved via a recurrence relation by defining M(k,n) as the number of way of summing to k with n terms and S(k,n) as the sum of x_i^2 over all possible ways, so we have

$$M(k,n) = M(k,n-1) + ... + M(0,n-1)$$
$$S(k,n) = 0 + S(k,n-1) + 1*M(k-1,n-1) + S(k-1,n-1) + ... + k^2*M(0,n-1) + S(0,n-1)$$

with M(k,1)=1, S(k,1)=k^2, e.g. M(2,2)=3, S(2,2)=10, though I don't know the general solution - perhaps generating functions would help?

 

[wdlang]

First few numbers are (1, 10/3, 60/10).

It could be solved via a recurrence relation by defining M(k,n) as the number of way of summing to k with n terms and S(k,n) as the sum of x_i^2 over all possible ways, so we have

$$M(k,n) = M(k,n-1) + ... + M(0,n-1)$$
$$S(k,n) = 0 + S(k,n-1) + 1*M(k-1,n-1) + S(k-1,n-1) + ... + k^2*M(0,n-1) + S(0,n-1)$$

with M(k,1)=1, S(k,1)=k^2, e.g. M(2,2)=3, S(2,2)=10, though I don't know the general solution - perhaps generating functions would help?

i can solve the problem already

it is actually simple

you just need to find the average value of x_1^2

then the average of the sum of the squares is N times of that

but the average of x_1^2 is simple to find, just a bit combination

 

[bpet]

Oh I see, then it reduces to

$$E[x_1^2] = \frac{1*M(n-1,n-1) + 2^2*M(n-2,n-1) + ... + n^2*M(0,n-1)}{M(n,n-1)+...+M(0,n-1)}$$

Did you find an expression for M(k,n)?

 

[wdlang]

Oh I see, then it reduces to

$$E[x_1^2] = \frac{1*M(n-1,n-1) + 2^2*M(n-2,n-1) + ... + n^2*M(0,n-1)}{M(n,n-1)+...+M(0,n-1)}$$

Did you find an expression for M(k,n)?

it is simple

it is a standard result in combination theory

 

[bpet]

Sorry you've lost me - can you post the details or a link to it please?

 

[wdlang]

Sorry you've lost me - can you post the details or a link to it please?

i bet you can find the expression of M in any combinational book

 

[bpet]

i bet you can find the expression of M in any combinational book

I don't have easy access to a library so that's not much help. Regardless, using generating functions M(k,n) would be the coefficient of x^k in (1+x+x^2+...)^n = 1/(1-x)^n, provided k<=n, and the kth derivative of this expression is (n+k-1)!/(n-1)!(1-x)^(n+k) so M(k,n)=^n+k-1C_n-1 and of course M(0,n-1)+...+M(n,n-1)=M(n,n). Did you find a simple expression for 1^2*M(n-1,n-1)+...+n^2*M(0,n-1) ?

 

[wdlang]

I don't have easy access to a library so that's not much help. Regardless, using generating functions M(k,n) would be the coefficient of x^k in (1+x+x^2+...)^n = 1/(1-x)^n, provided k<=n, and the kth derivative of this expression is (n+k-1)!/(n-1)!(1-x)^(n+k) so M(k,n)=^n+k-1C_n-1 and of course M(0,n-1)+...+M(n,n-1)=M(n,n). Did you find a simple expression for 1^2*M(n-1,n-1)+...+n^2*M(0,n-1) ?

you got it

i do not find a simple expression of that but i can prove it is convergent, that is what i want