permutation  7 identical items, 32 distinct containersby rcgldr Tags: containers, distinct, identical, items, permutation 

#1
Mar2012, 04:45 PM

HW Helper
P: 6,925

I already have the answer for this, but wondering if there's some efficient way to calculate this. There are 7 identical items, each with a equally random chance of being placed in 1 of 32 containers. What are the possible permutations?
00000000032 = 7 identical items into 1 of 32 distinct containers 00000062496 = 7 identical items into 2 of 32 distinct containers 00008957760 = 7 identical items into 3 of 32 distinct containers 00302064000 = 7 identical items into 4 of 32 distinct containers 03383116800 = 7 identical items into 5 of 32 distinct containers 13701623040 = 7 identical items into 6 of 32 distinct containers 16963914240 = 7 identical items into 7 of 32 distinct containers  34359738368 = total number of cases = 32^{7} This was originally done for ecc (error correction code) analysis. A bit suprising was the fact that the probability of 7 identical items into 7 of 32 distinct containers is less than 1/2, 16963914240 / 34359738368 ~= 0.4937 As an example of grinding this out, the worst case is 7 identical items into 4 of 32 distinct containers. There are 6C3 = 20 possible scenarios, scenario 1  1st item goes into any of 32 containers, 2nd, 3rd, and 4th item go into same container as first item, 5th item goes into any of the remaining 31 containers, 6th into the remaining 30 containers, 7th into the remaining 29 containers. The number of ways to do this would be 32x1x1x1x31x30x29. scenario 2  similar to scenario 1, but 4th item goes into any of the remaining 31 containers, 5th item into either of the 2 occupied containers, 6th into remaining 30, ... . The list looks like this: (32x1x1x1x31x30x29) + (32x1x1x31x2x30x29) + (32x1x1x31x30x3x29) + (32x1x1x31x30x29x4) + ... (32x31x30x3x29x4x4)+ (32x31x30x29x4x4x4) At the time, I used a summation series like this: [tex]\binom{32}{4} \sum_{i=1}^4 (1)^{4+i} \binom{4}{i} i^7[/tex] The summation part can be explained as the number of ways (7 items into 1>4 of 4 containers)  (7 items into 1>3 of 4 containers)   (7 items into 1>2 of 4 containers)    (7 items into 1>1 of 4 containers) to result in (7 items into 4 of 4 containers). 



#2
Mar2012, 08:00 PM

P: 144

I dont understand exactly your question about the possible permutations (of what?), but I do have some comments.
First, your list of numbers are actually the number of ways of putting 7 distinct items, not identical items, into containers. And you use this, in the middle paragraph, when you mention the 1st, 2nd, 3rd item etc. Then, the numbers in the list can be expressed by S(7,k)(32 k)k! where S(m,n) is the stirling number of second kind (which btw, multilplied by n! give the number of surjections from an melement set, to an nelement set), and (32 k) is a binomial. The Stirling numbers are computed using inclusion/exclusion just like your summation, so I doubt you can find something more efficient if you insist on creating that list. Your surprising fact about the chance of all items going into different containers, can btw also be obtained by 31*30*29*28*27*26/32^{6}=49.37%. 



#3
Mar2012, 10:01 PM

HW Helper
P: 6,925

So if all of the balls ended up in 1 slot, they could all be in slot #1, slot #2, ..., or slot #32. There are 32 patterns where all 7 balls are in one slot. I was assuming that this meant identical items, distinct containers. This was the original statement of problem: if you have 7 items and 32 containers, with equal likelyhood of any item ending up in any container, what is the probablity that the 7 items will end up in 7 different containers, (and the probablity of ending up in 6 containers, ..., probability of ending up in 1 container) ? 



#4
Mar2112, 07:13 AM

P: 329

permutation  7 identical items, 32 distinct containers
These numbers are way too high for a distribution of identical objects; basically you're going the long way around on this problem.
The total number of arrangements of 7 identical objects in 32 bins is given by [tex]\binom{38}{7} = \frac {38!}{31! 7!} = 12620256[/tex] The 31 is equivalent to the dividers between the bins  think of this as choosing the position of the objects in a field of 38 and then filling the remaining spaces with the dividers. In order to get the number of permutations with various numbers of bins used, first enumerate the possible bin choices for that chosen numbers of bins B  each of which takes one object initially  then calculate the ways of distributing the remaining 7B objects into those bins. For example, with 4 bins used: Choice of 4 bins [itex]= \binom{32}{4} = 35960[/itex] Distribution of remaining 3 objects into the chosen bins [itex]= \binom{6}{3} = 20[/itex] Total arrangements using 4 bins = 719200 $$\begin{array} \text{bins used} & \text{permutations} & \text{proportion of total} \\ 7 & 3365856 & 26.6703\% \\ 6 & 5437152 & 43.0827\% \\ 5 & 3020640 & 23.9349\% \\ 4 & 719200 & 5.6988\% \\ 3 & 74400 & 0.5895\% \\ 2 & 2976 & 0.0236\% \\ 1 & 32 & 0.0003\% \end{array}$$ 



#5
Mar2112, 08:30 AM

HW Helper
P: 6,925

Thanks for the response.
Is the logic in my first post treating the items or containers as distinct: "1st item goes into any of the 32 containers, 2nd item goes into any of the remaining 31 containers, ...."? The issue here is that I'm trying to determing the probability of each case where the containers are treated as distinct, as opposed to the number of permutations. Reduce this to the situation where there are 7 items and 4 containers. What is the probabilty that containers, a, b, c end up with 1 item, and container d ends up with 4 items? What is the probabilty that any 3 of the containers end up with 1 item and the remaining container ends up with 4 items (seems it should be 4 times the a,b,c,d = 1,1,1,4 probability)? What if the situation is changed to this: there is a container with 32x7 = 224 balls, 217 are white, and 7 are black. The distribution of balls in the container is random. Then the balls are dropped 7 at a time into each of 32 containers. Is the probability of the distribution of black balls the same as you described? 



#6
Mar2112, 09:03 AM

P: 329

Your logic treats both containers and objects as distinct. That might be appropriate for your application; I really don't know enough to judge. The number of different distributions of identical objects was the point I was trying to answer; probability is another subject again.
There are 10c7 = 120 different distributions of 7 identical items into 4 containers. However if we follow the logic of assigning each item randomly to one of the four bins, it is clearly not the case that the outcome of having all 7 items in the first bin has a probability of 1/120. So perhaps for your situation you do need to consider the whole space of distinct items. 



#7
Mar2112, 09:15 AM

HW Helper
P: 6,925

The orignal purpose was for error analysis, what are the odds of "x" random bad bursts of data affecting "x" of "n" blocks (blocks were interleaved, and bursts relatively small, so no single burst could affect more than one block in an interleave) as opposed to less than "x" of "n" blocks? Maximum "burst" size was fixed (via interleave), so there are "y" bursts per block. There were "n" blocks per group, and the goal was to determine the odds of exactly "x" bad blocks per "n" blocks in a group. The burst error rate could be used to calculate a block error rate. Then the block error rate could be used to calculate the odds of "x" bad blocks per "n" block group. This could also be done by calculating the odds of "x" bursts per "n" block ("n" x "y" burst) group. It turns out that the probabiliy for 7 bad bursts in a group of 32 blocks was about double that of 7 bad blocks in a group, which didn't make sense, since both were based on the same burst error rate, until with the math I used in the first post showed that 7 bad bursts only affected 7 blocks about 1/2 the time, and with that adjustment the total error rates came out to be the same. The same situation occurred for 5 bad bursts versus 5 bad blocks in a group of 16 blocks. This was over 10 years ago, and I'm no longer involved with this project, so it's just a matter of curiosity. I was wondering if there was a more elegant way of handling the summation formula in my first post. 



#8
Mar2112, 10:52 AM

P: 329

XXXXXXX = (2,3,0,2) To convince yourself, it's not a massive task to list out the possible distributions (unlike the 32bin case!). The rest of your question is interesting but I don't have time right now  I may get back to it. 



#9
Mar2112, 04:26 PM

HW Helper
P: 6,925

r items into n containers is (n+r1)c(r) = 10c7 = 120, if none empty, then (r1)c(n1) = 6c3 = 20. 0007 0016 0025 0034 0043 0052 0061 0070 0106 0115 0124 0133 0142 0151 0160 0205 0214 0223 0232 0241 0250 0304 0313 0322 0331 0340 0403 0412 0421 0430 0502 0511 0520 0601 0610 0700 1006 1015 1024 1033 1042 1051 1060 1105 1114 1123 1132 1141 1150 1204 1213 1222 1231 1240 1303 1312 1321 1330 1402 1411 1420 1501 1510 1600 2005 2014 2023 2032 2041 2050 2104 2113 2122 2131 2140 2203 2212 2221 2230 2302 2311 2320 2401 2410 2500 3004 3013 3022 3031 3040 3103 3112 3121 3130 3202 3211 3220 3301 3310 3400 4003 4012 4021 4030 4102 4111 4120 4201 4210 4300 5002 5011 5020 5101 5110 5200 6001 6010 6100 7000 20 of the 120 with no empty containers: 1114 1123 1132 1141 1213 1222 1231 1312 1321 1411 2113 2122 2131 2212 2221 2311 3112 3121 3211 4111 



#10
Mar2512, 01:16 PM

P: 329

So, I thought about this a little more, and I think some casebycase work is probably inevitable.
Looking at the case of 7 items into 4 bins (with no bins empty) there are 20 cases that fall into 3 patterns: 4111 (4!/(1!3!) = 4 cases) 3211 (4!/(1!1!2!) = 12 cases) 2221 (4!/(3!1!) = 4 cases) We can switch back to a distinguishableevents view by looking at the order that the bins are filled. So taking one of the 3211 cases, suppose we have bin allocations: 1112234 then there are 7!/(3!2!1!1!) ways of ordering these numbers = 420. Similarly there are 210 orderings for each 4111 case and 630 for each 2221 case. So for a particular choice of 4 bins, we have 4x210+12x420+4x630 = 8400 ordered options for filling those 4 bins. For 7 items into a particular choice of 3 bins, we have {511, 421, 331, 322} with {3,6,3,3} cases and {42,105,140,210} orderings giving 1806 ordered options. For 7 items into a particular choice of 2 bins, we have {61, 52, 43} with {2,2,2} cases and {7,21,35} orderings giving 126 ordered options. Obviously for 7 items into a particular bin, there is only one option. Overall for the fourbin case, there is 1 choice of four bins, 4 choices of three bins, 6 choices of 2 and 4 of 1, so the chances I'd associate with each possibility of filling (4,3,2,1) bins are in ratio 8400:7224:756:4 (and the sum of these is 4^7 so something is working :D ) 



#11
Mar2512, 01:54 PM

P: 329

Extending these general cases to particular 5, 6 and 7 bins:
5 bins can be {31111, 22111} with {5, 10} cases, with {840,1260} orderings per case, total 16800. 6 bins can only be {211111}, 6 cases with 2520 orderings per case, total 15120 7 bins must be {1111111}, 1 case of 5040 orderings. The total orderings then for the {1..7} chosen bins cases are {1,126,1806,8400,16800,15120,5040} Applying these numbers to the 32 bins case, the choices of {1..7} bins from 32 are {32, 496, 4960, 35960, 201376, 906192, 3365856} giving total outcomes of {32, 62496, 8957760, 302064000, 3383116800, 13701623040, 16963914240}. Awesome. I can easily apply this to other numbers of bins, but changing the number of events is a little slower. 



#12
Mar2512, 06:43 PM

HW Helper
P: 6,925

This can be separated into 2 main steps. First calculate the number of ways 7 items can go into n bins, none empty, using this expansion series:
[tex]\sum_{i=1}^n (1)^{n+i} \binom{n}{i} i^7[/tex] then multipy by the number of ways 32 things can be taken n at a time: [tex]\binom{32}{n} \sum_{i=1}^n (1)^{n+i} \binom{n}{i} i^7[/tex] This is what I did in my first post of this thread. The expansion series for 7 items into n nonemtpy containers for n = 1 to 7. 7 items into 1 container: (1c1)(1^{7}) = 1 7 items into 2 containers: (2c2)(2^{7})  (2c1)(1^{7}) = 126 7 items into 3 containers: (3c3)(3^{7})  (3c2)(2^{7}) + (3c1)(1^{7}) = 1806 7 items into 4 containers: (4c4)(4^{7})  (4c3)(3^{7}) + (4c2)(2^{7})  (4c1)(1^{7}) = 8400. 7 items into 5 containers: (5c5)(5^{7})  (5c4)(4^{7}) + (5c3)(3^{7})  (5c2)(2^{7}) + (5c1)(1^{7}) = 16800 7 items into 6 containers: (6c6)(6^{7})  (6c5)(5^{7}) + (6c4)(4^{7})  (6c3)(3^{7}) + (6c2)(2^{7})  (6c1)(1^{7}) = 15120 7 items into 7 containers: (7c7)(7^{7})  (7c6)(6^{7}) + (7c5)(5^{7})  (7c4)(4^{7}) + (7c3)(3^{7})  (7c2)(2^{7}) + (7c1)(1^{7}) = 5040 For n = 7, the expansion series isn't needed, since 7 items into 7 bins has 7! permutations = 5040. Post #5 of http://www.physicsforums.com/showthread.php?t=589257 uses math similar to post #10 in this thread. Apparently there is no shorcut to the expansion series for n = 2 to n = 6 cases. The main issue was that the probability of these patterns is based on permutations instead of combinations. 



#13
Mar2512, 07:17 PM

P: 329

Well, the variation I used was to consider patterns of bin filling. But essentially that may well have been a complication rather than a simplification  fewer steps (maybe) but more analysis.




#14
Mar2512, 07:55 PM

HW Helper
P: 6,925

http://www.physicsforums.com/showthread.php?t=589257 The expansion series was a self invention based on observation (this was 20 years ago) from the numbers I was manually calculating similar to the approach you used. I also did a "ask dr math" and the response was the same expansion series, so it doesn't appear that the expansion series can be simplified. 



#15
Mar2512, 08:43 PM

P: 329

Sorry rcgldr, I didn't notice your link before. Amazingly similar lines of thought.




#16
Mar2512, 09:54 PM

HW Helper
P: 6,925





#17
Mar2512, 11:33 PM

P: 329

Ah. So the problem with just subtracting off the upto3 from the upto4 is that it has doublecounted a number of the upto2 solutions in the 4c3 multiplication. Now I just need to understand how that we're adding the right amount back in /subtracting off the doublecount.




#18
Mar2612, 03:08 AM

HW Helper
P: 6,925

1of4 = 4 (1of1) = 4 (1^{7}) 4 (1^{7}) = 1of4 2of4 = 6 (2of2) = 6 (2^{7}  12) = 6 (2^{7})  3 (1of4) 6 (2^{7}) = 2of4 + 3 (1of4) 3of4 = 4 (3of3) = 4 (3^{7}  12 (2^{7}) + 12) = 4 (3^{7})  2 (2of4)  3 (1of4) 4 (3^{7}) = 3of4 + 2 (2of4) + 3 (1of4) 4of4 = upto4  3of4  2of4  1of4 = 4^{7}  3of4  2of4  1of4 4^{7} = 4of4 + 3of4 + 2of4 + 1of4 4^{7}  4 (3^{7}) + 6 (2^{7})  4 (1^{7}) = (4of4 + 3of4 + 2of4 + 1of4)  (3of4 + 2 (2of4) + 3 (1of4)) + (2of4 + 3 (1of4))  1of4 = 4of4 = 16384  8748 + 768  4 = 8400 If the series was used 3 times to separately calculate 1of1, 2of2, 3of3, then 4^{7} = 4of4 + 3of4 + 2of4 + 1of4 = 4of4 + 4 (3of3) + 6 (2of2) + 4 (1of1) 4of4 = 4^{7}  3of4  2of4  1of4 = 4^{7}  4 (3of3)  6 (2of2)  4 (1of1) 16384 = 4^{7}  4 (1806)  6 (126)  4 = 16384  7224  756  4 = 8400 The upto values do not correspond to the series values. These would be: upto1 = 1of4 = 4 upto2 = 1of4 + 2of4 = 4 + 756 = 760 upto3 = 1of4 + 2of4 + 3of4 = 4 + 756 + 7224 = 7984 upto4 = 1of4 + 2of4 + 3of4 + 4of4 = 4 + 756 + 7224 + 8400 = 16384 Sorry for the confusion in my previous post. It's been about 20 years since I last worked with this stuff. 


Register to reply 
Related Discussions  
Data Management: Premutations Problem With identical Items  Precalculus Mathematics Homework  1  
Data Management: Premutations Problem With Some identical Items Chapter Problem  Set Theory, Logic, Probability, Statistics  0  
SUBSET K of elements in a group with finite distinct distinct conjugates  Linear & Abstract Algebra  1  
Tricky counting problem(n distinct balls in n distinct boxes)  Precalculus Mathematics Homework  1  
Why is n! the number of possible ways to arrange n distinct items?  Precalculus Mathematics Homework  3 