0
$\begingroup$

I am working on a problem where I am supposed to count the number of arrays of size $N\times M$ where the sum of elements in the $i$-th row is greater than or equal to the the sum of elements in the $(i-1)$-th row. And the the sum of elements in $N$-th row (the last row) is less than or equal to $M$. All the elements are non negative integers.

For example, $N=2, M=2$ there are 25 solutions.

The solution that I have worked out so far is that for a row to have sum less than $M$, the number of possible ways is $C(2M,M)$. But I am unable to implement the remaining constraint.

$\endgroup$
  • 1
    $\begingroup$ @D.W. Turns out that the sequence $C(2,M)$ is OEIS A129763. They give a generating function solution, but no closed form. Also, it happens that this is a CodeChef competition problem, asked here and on math.SE by two apparently different people. $\endgroup$ – Rick Decker Jun 10 '15 at 1:24
  • $\begingroup$ Thanks, @RickDecker. Do you have a link to the Math.SE question? That might be helpful for others. If it's a CodeChef competition problem, maybe we should wait to answer until the competition is closed. The CodeChef code of conduct prohibits asking or discussing about CodeChef problems while the contest is ongoing (obviously this is not binding on us, but we could look to it for guidance). $\endgroup$ – D.W. Jun 10 '15 at 1:35
  • $\begingroup$ @D.W. If you're looking for my question, it's here. If you're looking for the question about the competition, it's here. Had I known it was a competition question, I'd have postponed my answer, of course. $\endgroup$ – Rick Decker Jun 10 '15 at 1:39
2
$\begingroup$

The case where $N=2$ is fairly easy. For $M\ge N$ we'll have an array $$\begin{array}{ccccc} a_{1,1} & a_{1,2} & a_{1,3} &\dotsm & a_{1,M}\\ a_{2,1} & a_{2,2} & a_{2,3} &\dotsm & a_{2,M}\\ a_{3,1} & a_{3,2} & a_{3,3} &\dotsm & a_{3,M}\\ &\dotsm & & & \\ a_{N,1} & a_{N,2} & a_{N,3} &\dotsm & a_{N,M}\\ \end{array}$$ Define $t(k,M)$ to be the number of integer solutions of $x_1+x_2+\dotsm+x_m=k$ with all $x_i\ge 0$. The stars and bars theorem tells us that $$ t(k,M)=\binom{M-1+k}{M-1} $$ Then if we let $C(N,M)$ denote the number of solutions to the original problem, it's not hard to see that for $N=2$, $$\begin{align} C(2,M) &= \sum_{i=0}^M\left[t(i,M)\sum_{j=0}^it(j,M)\right]\\ &= \sum_{i=0}^M\binom{M-1+i}{M-1}\sum_{j=0}^i\binom{M-1+j}{M-1}\\ &= \sum_{i=0}^M\binom{M-1+i}{M-1}\left[\binom{M-1}{M-1}+\binom{M}{M-1}+\dotsm+\binom{M-1+i}{M-1}\right]\\ &= \sum_{i=0}^M\binom{M-1+i}{M-1}\binom{M+i}{M} \end{align}$$ The last step above uses a fairly well-known result on the sum of a column of Pascal's triangle. So finally we'll have $$ C(2,M) =\binom{M-1}{M-1}\binom{M}{M}+\binom{M}{M-1}\binom{M+1}{M}+\dotsm+\binom{2M-1}{M-1}\binom{2M}{M} $$ For $N=M=2$ we have $C(2,2)=1+6+18=25$, which agrees with your example.


Added yet again. For a (not particularly useful) general form, it's not hard to see that $$ C(N,M)=\sum_{0\le i_1\le i_2\le\dotsm i_N\le M} t(i_1,M)t(i_2,M)\dotsm t(i_N,M) $$ In this expression, each of the $i_k$ represents the possible sum of the $k$-th row.

I asked on Math.SE whether the expression for $C(2,M)$ had a closed form and the consensus was that it didn't (although it can be expressed as a hypergeometric series, for what that's worth).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Answer for C(2,3) is 273. $\endgroup$ – aman Jun 9 '15 at 20:15
  • $\begingroup$ I really appreciate your effort. Can you give me the general form of the expression. $\endgroup$ – aman Jun 10 '15 at 5:32
  • $\begingroup$ Not necessarily a general form.... If we could use from the previous computed solution... Like for C(N,M) may be we can use results of C(N-1,M)... I hope I was clear $\endgroup$ – aman Jun 10 '15 at 5:35
  • $\begingroup$ @aman. I tried that with only partial success. It turns out that, as far as I could tell, some parts of $C(N,M)$ can be written in terms of $C(N',M)$ with $N'<N$, but not all of them. $\endgroup$ – Rick Decker Jun 10 '15 at 18:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.