1

Question: Let $n, m \in \mathbb{Z}_{+}$ and let $A(p; n, m)$ be the number of rectangular arrays of non-negative integers with $n$ rows and $m$ columns where the sum of the entries in each row equals $p$.

Although I believe I have this question figured out, I can't find a way to express it that generalizes nicely.

In particular, each row is a partition of the integer $p$ into $m$ parts, but the parts into which it is divided need not be distinct. So you have to account how many of each part you have, which is proving to be a frustrating and tedious exercise.

My approach has been to count all such arrays by summing over all such partitions of $p$ into $m$ parts with $m$ distinct parts, $m-1$ distinct parts, $m-2$ distinct parts, and so forth. But then for each possibility, the number of parts which are repeated varies, and it's hard to account for this.

Is there a better approach to this question, or a way to generalize my approach nicely?

combinator
  • 1,356

1 Answers1

2

The number of possible different rows is

$$\binom{p+m-1}{m-1}=\binom{p+m-1}p\;;$$

this is a standard stars-and-bars problem, and the linked article has a reasonably good explanation. Thus, you have

$$\binom{p+m-1}p^n$$

matrices of the desired type.

Brian M. Scott
  • 616,228