Re: The number of solutions to n_1 + n_2 + n_3 + ... + n_k = m
- To: mathgroup at smc.vnet.net
- Subject: [mg38398] Re: [mg38267] The number of solutions to n_1 + n_2 + n_3 + ... + n_k = m
- From: Rob Pratt <rpratt at email.unc.edu>
- Date: Fri, 13 Dec 2002 04:13:24 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
On Tue, 10 Dec 2002, Kumar Chellapilla wrote: > Hi, > > I was wondering if there was a simple expression (as a function of m and k ) > to compute > the total number of solutions to the "integer programming" problem: > > n_1 + n_2 + n_3 + ... + n_k = m > > where m > k, each ni >= 1. [rest snipped] The answer is the same as the number of solutions to n_1 + n_2 + n_3 + ... + n_k = m - k, where m > k, each n_i >= 0. But this count is simply Binomial[(m - k) + (k - 1), k - 1] = Binomial[m - 1, k - 1], by the "dots-and-dividers" argument. (Each solution can be represented uniquely by a sequence of m - k dots and k - 1 dividers. We are free to place the k - 1 dividers in any of the (m - k) + (k - 1) = m - 1 available positions.) Rob Pratt Department of Operations Research The University of North Carolina at Chapel Hill rpratt at email.unc.edu http://www.unc.edu/~rpratt/