# How to get a closed form for $\sum m f(n,m)$ where $f(n,m)$ is number of weak compositions? [duplicate]

First, consider how many $n$-dimensional vector of non-negative integers $(x_1,x_2,\cdots,x_n)$ are there whose sum of all entries satisfies $x_1+x_2+\cdots+x_n=m$?

For example for $n=2,m=2$, there are $(2,0),(1,1),(0,2)$, so $f(2,2)=3$.

For $n=3,m=2$ there are $(2,0,0),(0,2,0),(0,0,2),(1,1,0),(0,1,1),(1,0,1)$, so $f(3,2)=6$.

How about for general $m,n$? What I know is $f(n,m)\le$ n+m choose n by How many $k-$dimensional non-negative integer arrays $(x_1,\cdots,x_k)$ satisfies $x_1+x_2+\cdots+x_k\le n$

--

Then, I would like a closed form solution for $$\sum_{m=0}^Mf(n,m)$$

## marked as duplicate by Ross Millikan combinatorics StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Apr 4 '18 at 2:41

• This seems a strange thing to be interested in. Where does it come from? The sum of the first term is $\frac 12M(M+1)$. The second is the sum of some of a row of Pascal's triangle. I am not aware of a nice form, though you can use the normal approximation. – Ross Millikan Apr 4 '18 at 3:06
• It comes from trying to derive algorithm complexity. How $N$ scales is more important here. – ZHU Apr 4 '18 at 3:07