Results 1 to 2 of 2

Math Help - Distribution problem

  1. #1
    Newbie
    Joined
    Sep 2010
    Posts
    2

    Distribution problem

    Hi,

    I have the following problem, which at first I thought should be really simple, but so far I can't seem to find any solution to this:

    Say I have a number of equal items that are to be distributed between a number of bins, like N pieces of cake that are to be distributed between M children. The number of possible distributions for this is (N over (M-1)).

    However, let's say I want to limit the number of items per bin to, say, 2? So I want to distribute the N pieces of cake between the M children, without any child getting more than 2 pieces of cake (assuming there are at least N/2 children). Does anyone have any suggestions how I can count the number of possibilities in this case?

    Henrik
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by henrikbe View Post
    Say I have a number of equal items that are to be distributed between a number of bins, like N pieces of cake that are to be distributed between M children. The number of possible distributions for this is (N over (M-1)).
    I don't agree with that. The number of ways of allocating N identical objects (or cakes) among M distinct bins (or children) is the binomial coefficient N+M-1\choose N.

    Quote Originally Posted by henrikbe View Post
    However, let's say I want to limit the number of items per bin to, say, 2? So I want to distribute the N pieces of cake between the M children, without any child getting more than 2 pieces of cake (assuming there are at least N/2 children). Does anyone have any suggestions how I can count the number of possibilities in this case?
    Let K denote the number of children who receive at least one piece of cake. It's clear that at least \lceil N/2\rceil children must receive at least one piece of cake (where \lceil N/2\rceil means the least integer greater than or equal to N/2). The greatest number of children who can receive at least one piece of cake is M or N, whichever is smaller.

    Therefore K can be any number between \lceil N/2\rceil and \min\{M,N\}. For each such value of K, we can give one piece of cake to each of those K children. There will then be NK remaining pieces of cake, which allows NK lucky children to receive a second piece of cake.

    There are M\choose K ways of choosing the children who receive at least one piece. For each such choice, there are K\choose N-K ways to choose the lucky children who get 2 pieces. Thus the total number of ways of allocating the cakes is \boxed{ \sum_{K=\lceil N/2\rceil}^{\min\{M,N\}}{M\choose K}{K\choose N-K}}. I don't see any way to simplify that answer.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Distribution Problem
    Posted in the Statistics Forum
    Replies: 1
    Last Post: November 16th 2010, 06:02 PM
  2. Distribution problem
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: February 24th 2010, 04:16 AM
  3. Replies: 0
    Last Post: October 8th 2009, 08:45 AM
  4. Distribution problem
    Posted in the Advanced Statistics Forum
    Replies: 2
    Last Post: August 3rd 2009, 12:08 AM
  5. F-distribution problem
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: April 30th 2009, 11:10 PM

Search Tags


/mathhelpforum @mathhelpforum