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.

here's a question I had in an exam today:

Four people are checking 230 exams. In how many ways can you split the papers between the four of them if you want each one to check at least 15?

So, after checking $4 \cdot 15$ papers we are left with 170 and so the result is $$\binom{170+(4-1)}{4-1}=\binom{173}{3}$$ And here's the twist: Following the last question, in how many ways can you split the papers between the four of them, only now the papers are different and its important to count who checks how many. Meaning - The number of ways to divide 230 elements to 4 different groups.

My initial attemp was $$\sum_{x_1,x_2,x_3,x_4=230}\binom{230}{x_1,x_2,x_3,x_4}=4^{230}$$ But that's obviously a mistake since I wasn't counting the first 60 papers correctly. I think it probably involves using inclusion-exclusion, but I'm not sure how.

Would love to hear some ideas. Thanks!

share|improve this question
    
I am still thinking of a mathematical solution, but after a quick verification via computer program gives a number $848046= 2 \times 3 \times 19 \times 43 \times 173 =\binom{173}{3} $. Not sure yet, but will see if I can find a solution –  Kirthi Raman Mar 14 '12 at 19:56
    
Thanks. I have an exam tomorrow :) –  yotamoo Mar 14 '12 at 21:37
    
Can you clarify exactly what you are trying to count in the followup question? –  Aryabhata Mar 15 '12 at 0:17

2 Answers 2

up vote 1 down vote accepted

I don't see an easy way to do this analytically.

Numerically it is possible by looking at each of the 848,046 ways of dividing up the numbers of papers and adding up the multinomial coefficients. Even this is not trivial as $230!$ can be too large for some systems, so it may be sensible to use logarithms at some stage. For example in R, using

require(partitions)
papers <- compositions(230 - 4*15, 4) + 15
sum(  exp( lfactorial(230) - colSums(lfactorial(papers)) )  )   

gives

[1] 2.977131e+138

which is close to $4^{230}$, and the difference is near the precision of the calculation.

How close? A similar approach, but looking at where at least one of the examiners gets strictly fewer than 15 papers, would give 1,233,110 patterns of numbers and 5.015953e+125 ways of distribution the different papers. So in a sense "very close".

share|improve this answer

Consider all possible ways to divide $230$ labeled objects among $4$ labeled people, and for $i=0$, $\ldots$, $3$ and $j=0$, $\ldots$, $14$, let $A_{ij}$ be the set of ways where person $i$ receives exactly $j$ objects. We wish to count the size of $S$, where $S$ is the complement of $\bigcup_{i,j} A_{ij}$. Observe that $A_{ij}\cap A_{ik}=\emptyset$ if $j\ne k$. This implies that any intersection of five or more distinct $A_{ij}$'s must be empty; in fact, any intersection of four distinct $A_{ij}$'s must also be empty, since apart from those with repeated $i$'s, any such intersection will be of the form $$A_{0j}\cap A_{1j'} \cap A_{2j''} \cap A_{3j'''},$$ which is empty since it requires each person to get at most $14$ objects, but $4\cdot 14<230$. Therefore, applying the inclusion-exclusion principle will give $$ \#S=4^{230}-\sum_{i,j} \#A_{ij}+\sum_{i,j,i',j': i<i'} \#(A_{ij}\cap A_{i'j'}) $$ $$ -\sum_{i,j,i',j',i'',j'': i<i'<i''} \#(A_{ij}\cap A_{i'j'}\cap A_{i''j''}). $$ However, $\#A_{ij}$ is the number of ways to pick $j$ labeled objects out of $230$ to give to person $i$ and divide the remainder among $3$ people, so $$\# A_{ij}=\binom{230}{j} 3^{230-j}.$$ Similarly, $$\# (A_{ij}\cap A_{i'j'})=\binom{230}{j\ \ j'\ \ 230-(j+j')}2^{230-(j+j')}$$ and $$\# (A_{ij}\cap A_{i'j'}\cap A_{i''j''})= \binom{230}{j\ j'\ j''\ 230-(j+j'+j'')} ,$$ so $$ \#S =4^{230}-4 \sum_{0\le j\le 14} \binom{230}{j} 3^{230-j} +\binom{4}{2} \sum_{0\le j, j'\le 14} \binom{230}{j\ j'\ 230-(j+j')} 2^{230-(j+j')} $$ $$ -\binom{4}{3} \sum_{0\le j, j', j''\le 14} \binom{230}{j\ j'\ j''\ 230-(j+j'+j'')}, $$ which can be computed to be

2977131414714304228375163768128492513800825122727620839102462174397915143246224081981112746784016599181459879137390109633489003108916312960.

As Henry says, this is very close to $4^{230}$: $$1-\frac{\#S}{4^{230}}\approx 1.6848\cdot 10^{-13}.$$

share|improve this answer
    
Indeed: 5.015953e+125 / 2.977131e+138 gives 1.684828e-13 –  Henry Mar 15 '12 at 1:08

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.