Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We have z objects (all different), and we want to distribute them among k people ( k < = z ) so that the distribution is almost even.

i.e. the difference between the number of articles given to the person with maximum articles, and the one with minimum articles is at most 1.

We need to find the total number of ways in which this can be done

for example if there are 5 objects and 3 people the number of such ways should be 90.

I am not sure how we get this value.

share|improve this question
    
Next time, try to make clear what is the question. –  leonbloy Jun 9 '13 at 1:55

4 Answers 4

up vote 2 down vote accepted

Let $k_1$ be the number of people that receive $n_1 = \lfloor \frac{z}{k}\rfloor $ objects, $k_2$ receive $n_2= n_1 +1$ objects. Clearly, $k_2 = z \bmod k$, $k_1+k_2=k$, $k_1 n_1 + k_2 n_2 = z$.

Assuming the objects are distinguishable, the total number of ways is

$$ {k \choose k_1} \frac{z!}{(n_1!)^{k_1} (n_2!)^{k_2}} $$

share|improve this answer
    
the value for z=14 and k=7 mod 3046201 should have been 2065880. you seem wrong. –  Alice Jun 9 '13 at 3:02
    
I think the answer is correct. My own, somewhat more complicated, reasoning below leads to the same result. –  Christian Blatter Jun 26 '13 at 9:22

Each person will get either $\lfloor \frac{z}{k}\rfloor$ or $\lceil \frac{z}{k}\rceil$ objects. These are the floor and ceiling functions.

share|improve this answer
    
yes I figured that out. but how to find the number of ways? –  Alice Jun 9 '13 at 1:18

As k is always less than z; First choose k elements from z; distribute it one for each person. Then the remaining objects for your condition to be true;

Lets call a(1) = z-k;

Again repeat the process [n is the number of cycles] till a(n) = z-n*k < k

Then distribute the remaining; Randomly. one person will only get one This way the difference between the number of articles given to the person with maximum articles, and the one with minimum articles is at most 1.

share|improve this answer
    
I am interested in the number of ways this could be done. Not that how to do this. –  Alice Jun 9 '13 at 1:33
    
@Chinu: Welcome to MSE! This post does not currently provide an answer and maybe is better as a comment (although you do not have enough reputation yet). Maybe it can be improved to be more specific to what the OP is asking. Also, it really helps readability to format math using MathJax (see FAQ). Regards –  Amzoti Jul 6 '13 at 13:21

(Edit: I just realize that this coincides with leonbloy's answer which has been questioned by the OP.)

Put $n:=\left\lfloor{z\over k}\right\rfloor$ and $r:=z-nk$. Then $r$ happy people receive $n+1$ objects and $k-r$ people $n$ of them. The $r$ happy people can be selected in $${k\choose r}$$ ways and will receive a total of $r(n+1)$ objects. These objects can be selected in $${z\choose r(n+1)}$$ ways and can then be distributed among the $r$ happy people in $${\bigl(r(n+1)\bigr)!\over \bigl((n+1)!\bigr)^r}$$ ways. The remaining $(k-r)n$ objects can be distributed among the remaining $k-r$ people in $${\bigl((k-r)n\bigr)!\over (n!)^{k-r}}$$ ways. The number $N$ you are looking for is given by the product of the displayed expressions: $$N={k\choose r}{z\choose r(n+1)}{\bigl(r(n+1)\bigr)!\over \bigl((n+1)!\bigr)^r}{\bigl((k-r)n\bigr)!\over (n!)^{k-r}}={k\choose r}{z!\over \bigl((n+1)!\bigr)^r (n!)^{k-r}} .$$

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.