Permutation - 7 identical items, 32 distinct containers

  1. rcgldr

    rcgldr 7,462
    Homework Helper

    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 = 327

    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).
     
    Last edited: Mar 20, 2012
  2. jcsd
  3. 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 m-element set, to an n-element 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/326=49.37%.
     
  4. rcgldr

    rcgldr 7,462
    Homework Helper

    I only used this to enumerate possible results. I could start with 7 identical balls, and drop them all at once into a pachinko or plinko like box with 32 slots at the bottom where all slots have an equal chance of receving a ball (and where each slot could receive up to 7 balls at the same time, perhaps 7 parallel pachinko or plinko like boxes that share the same 32 container slots at the bottom). I'm thinking that the total number of possible patterns is 327 (is this wrong?). Then I want to separate the possible patterns into patterns where only 1 slot has items (in this case all 7 items), only 2 slots have items, ..., only 6 slots have items, or 7 slots have items (in this case 1 each).

    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.

    Yes I knew that. It can also be stated as 32x31x30x29x28x27x26/327 to correspond with the notation I've been using.

    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) ?
     
    Last edited: Mar 20, 2012
  5. 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 7-B 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}$$
     
  6. rcgldr

    rcgldr 7,462
    Homework Helper

    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?
     
    Last edited: Mar 21, 2012
  7. 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.
     
  8. rcgldr

    rcgldr 7,462
    Homework Helper

    Should that be (7+4-1)c4 = 10c4 = 210 distributions? update - no, it's (7+4-1)c(7) = 10c7 = 120.

    That's what I'm thinking, unless there something in between these two different methods.

    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.
     
    Last edited: Mar 21, 2012
  9. No, it's 10c7 = 10c3. Remember we're modelling this with bin dividers, and for 4 bins there are 3 dividers.

    XX|XXX||XX = (2,3,0,2)

    To convince yourself, it's not a massive task to list out the possible distributions (unlike the 32-bin case!).

    The rest of your question is interesting but I don't have time right now - I may get back to it.
     
  10. rcgldr

    rcgldr 7,462
    Homework Helper

    You're correct, not sure why I got that mixed up.
    r items into n containers is (n+r-1)c(r) = 10c7 = 120, if none empty, then (r-1)c(n-1) = 6c3 = 20.

    Yes, 120 of them (already had a similar program):

    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

    OK, to keep it simple, just use the 7 items into 4 containers situation.

    Seems that any set composed of {0,0,0,7} (in any order) would be lowest probability (my program counts (4/16384)), and any set composed of {1,2,2,2} (in any order) would be highest probability (my program counts 2520/16384). My program treats each instance as a 7 digit number in base 4, going from {0,0,0,0,0,0,0} (all items in first container), to {3,3,3,3,3,3,3} (all items in last container), so 47 = 16384 total instances, and counts the number of instances for each of the 120 container sets. Then container sets that are just permuations of each other can be combined (4 permutations for {0,0,0,7}, 24 permutaions for {0,1,2,4}).
     
    Last edited: Mar 21, 2012
  11. So, I thought about this a little more, and I think some case-by-case 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 distinguishable-events 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 four-bin 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 )
     
    Last edited: Mar 25, 2012
  12. 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.
     
    Last edited: Mar 25, 2012
  13. rcgldr

    rcgldr 7,462
    Homework Helper

    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 non-emtpy containers for n = 1 to 7.

    7 items into 1 container:
    (1c1)(17) = 1

    7 items into 2 containers:
    (2c2)(27) - (2c1)(17) = 126

    7 items into 3 containers:
    (3c3)(37) - (3c2)(27) + (3c1)(17) = 1806

    7 items into 4 containers:
    (4c4)(47) - (4c3)(37) + (4c2)(27) - (4c1)(17) = 8400.

    7 items into 5 containers:
    (5c5)(57) - (5c4)(47) + (5c3)(37) - (5c2)(27) + (5c1)(17) = 16800

    7 items into 6 containers:
    (6c6)(67) - (6c5)(57) + (6c4)(47) - (6c3)(37) + (6c2)(27) - (6c1)(17) = 15120

    7 items into 7 containers:

    (7c7)(77) - (7c6)(67) + (7c5)(57) - (7c4)(47) + (7c3)(37) - (7c2)(27) + (7c1)(17) = 5040

    For n = 7, the expansion series isn't needed, since 7 items into 7 bins has 7! permutations = 5040.

    Post #5 of
    https://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.
     
    Last edited: Mar 25, 2012
  14. 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.
     
  15. rcgldr

    rcgldr 7,462
    Homework Helper

    As mentioned, the second part of post #5 of

    https://www.physicsforums.com/showthread.php?t=589257

    uses an approach similar to yours.

    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.
     
    Last edited: Mar 25, 2012
  16. Sorry rcgldr, I didn't notice your link before. Amazingly similar lines of thought.
     
  17. rcgldr

    rcgldr 7,462
    Homework Helper

    A better way to explain the expansion series is to note by how much the terms in the series exceed 4of4, 3of4, 2of4, and 1of4. I have this in post #18.
     
    Last edited: Mar 26, 2012
  18. Ah. So the problem with just subtracting off the upto3 from the upto4 is that it has double-counted 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 double-count.
     
  19. rcgldr

    rcgldr 7,462
    Homework Helper

    Yes, only the first term of the series is an upto value, upto4 = 47, the rest of the terms are more complicated, but the final result is correct. I updated my previous post to refer to this post. Grinding out what the terms of the series actually represent:

    1of4 = 4 (1of1) = 4 (17)
    4 (17) = 1of4

    2of4 = 6 (2of2) = 6 (27 - 12) = 6 (27) - 3 (1of4)
    6 (27) = 2of4 + 3 (1of4)

    3of4 = 4 (3of3) = 4 (37 - 12 (27) + 12) = 4 (37) - 2 (2of4) - 3 (1of4)
    4 (37) = 3of4 + 2 (2of4) + 3 (1of4)

    4of4 = upto4 - 3of4 - 2of4 - 1of4 = 47 - 3of4 - 2of4 - 1of4
    47 = 4of4 + 3of4 + 2of4 + 1of4

    47 - 4 (37) + 6 (27) - 4 (17) =
    (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
    47 = 4of4 + 3of4 + 2of4 + 1of4 = 4of4 + 4 (3of3) + 6 (2of2) + 4 (1of1)
    4of4 = 47 - 3of4 - 2of4 - 1of4 = 47 - 4 (3of3) - 6 (2of2) - 4 (1of1)
    16384 = 47 - 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.

    Although my explanation may help, I think doing a few examples will convince you.
     
    Last edited: Mar 26, 2012
  20. rcgldr

    rcgldr 7,462
    Homework Helper

    Corrections (final terms were ok, the intemediate terms for 2of2 and 3of3 were multiplied but left inside parenthesis), corrected equations:

    2of4 = 6 (2of2) = 6 (27 - 2) = 6 (27) - 12 = 6 (27) - 3 (1of4)
    6 (27) = 2of4 + 3 (1of4)

    3of4 = 4 (3of3) = 4 (37 - 3 (27) + 3) = 4 (37) - 12 (27) + 12 = 4 (37) - 2 (2of4) - 3 (1of4)
    4 (37) = 3of4 + 2 (2of4) + 3 (1of4)

    The last 3 terms of the series -4 (37) + 6 (27) - 4 (17) = -7984 = -upto3 (which is expected since the entire series = upto4 - upto3 = 4of4), but the final 2 terms, 6 (27) - 4 (17) = 764 = upto2 + 1of4, so there doesn't seem to be any way to conveniently describe the series, and as you stated, it justs ends up adding and subracting terms to get a final answer.

    Note that 7 items into 4 containers is the same as rolling a 4 sided die 7 times and noting the outcome, so this method can be used for permutations or probability of rolling a die several times. 7 items into 32 containers would correspond to rolling a 32 sided die 7 times, where the probability is ~.4937 of getting 7 different numbers on the 7 rolls.
     
    Last edited: Mar 26, 2012
Know someone interested in this topic? Share a link to this question via email, Google+, Twitter, or Facebook

Have something to add?
Similar discussions for: Permutation - 7 identical items, 32 distinct containers
Loading...