0
$\begingroup$

This question already has an answer here:

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)$$

$\endgroup$

marked as duplicate by Ross Millikan combinatorics Apr 4 '18 at 2:41

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ You can search the site for weak compositions and read Wikipedia about bit $\endgroup$ – Ross Millikan Apr 4 '18 at 2:42
  • $\begingroup$ I changed the question, it this okay now? $\endgroup$ – ZHU Apr 4 '18 at 3:00
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Apr 4 '18 at 3:06
  • $\begingroup$ It comes from trying to derive algorithm complexity. How $N$ scales is more important here. $\endgroup$ – ZHU Apr 4 '18 at 3:07
  • $\begingroup$ @RossMillikan made a mistake, just edited it. $\endgroup$ – ZHU Apr 4 '18 at 3:14

Browse other questions tagged or ask your own question.