The number of solutions to n_1 + n_2 + n_3 + ... + n_k = m
- To: mathgroup at smc.vnet.net
- Subject: [mg38267] The number of solutions to n_1 + n_2 + n_3 + ... + n_k = m
- From: "Kumar Chellapilla" <kumarc at microsoft.com>
- Date: Tue, 10 Dec 2002 04:11:53 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
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.
Basically, I am trying to figure out the number of ways of partitioning
a set with m unique elements into k non-empty disjoint subsets.
For example, if k = 2, then the number of solutions to
n_1 + n_2 = m is (m-1) = M_2(m) (say)
if k = 3, then the number of solutions to
n_1 + n_2 + n_3 = m is M_3(m) = sum_{i=1}^{m-2} (m-i-1) =
sum_{i=1}^{m-2} M_2(m-i)
I can think of a recursive solutions wherein
M_2(m) = (m-1) and
M_k(m) = sum_{i=1}^{m-k+1} M_(k-1)(m-i), k > 2
Thanks,
Kumar