MathGroup Archive 2002

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: The number of solutions to n_1 + n_2 + n_3 + ... + n_k = m

  • To: mathgroup at smc.vnet.net
  • Subject: [mg38383] Re: The number of solutions to n_1 + n_2 + n_3 + ... + n_k = m
  • From: "Carl K. Woll" <carlw at u.washington.edu>
  • Date: Fri, 13 Dec 2002 04:09:56 -0500 (EST)
  • Organization: University of Washington
  • References: <at4d36$etl$1@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

Hi Kumar,

It seems to me that the answer is simply

Binomial[m-1,k-1]

Carl Woll
Physics Dept
U of Washington

"Kumar Chellapilla" <kumarc at microsoft.com> wrote in message
news:at4d36$etl$1 at smc.vnet.net...
> 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
>
>
>
>
>




  • Prev by Date: Re: convolution
  • Next by Date: Pure recursive functions
  • Previous by thread: Re: The number of solutions to n_1 + n_2 + n_3 + ... + n_k = m
  • Next by thread: Re: Re: The number of solutions to n_1 + n_2 + n_3 + ... + n_k = m