Re: Re: The number of solutions to n_1 + n_2 + n_3 + ... + n_k = m
- To: mathgroup at smc.vnet.net
- Subject: [mg38408] Re: [mg38305] Re: [mg38267] The number of solutions to n_1 + n_2 + n_3 + ... + n_k = m
- From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
- Date: Sat, 14 Dec 2002 03:19:30 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
Rob Pratt is of course right, that is just Binomial[m-1,k-1]! I always
look for a generating series first, but how blind can one sometimes be!
Andrzej
On Thursday, December 12, 2002, at 03:31 PM, Andrzej Kozlowski wrote:
> I don't think there is a "simple expression" in a conventional sense,
> but you can give a simple "formula" in terms of a generating power
> series:
>
> f[k_, m_] := SeriesCoefficient[Series[1/(1 - x)^k, {x, 0, m - k}], m -
> k]
>
>
> Andrzej Kozlowski
> Yokohama, Japan
> http://www.mimuw.edu.pl/~akoz/
> http://platon.c.u-tokyo.ac.jp/andrzej/
>
>
>
> On Tuesday, December 10, 2002, at 06:11 PM, 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.
>>
>> 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
>>
>>
>>
>>
>>
>>
>>
>
>
>
>
Andrzej Kozlowski
Yokohama, Japan
http://www.mimuw.edu.pl/~akoz/
http://platon.c.u-tokyo.ac.jp/andrzej/