Register to reply

Permutation - 7 identical items, 32 distinct containers

Share this thread:
rcgldr
#1
Mar20-12, 04:45 PM
HW Helper
P: 7,034
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).
Phys.Org News Partner Mathematics news on Phys.org
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)
Norwegian
#2
Mar20-12, 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 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%.
rcgldr
#3
Mar20-12, 10:01 PM
HW Helper
P: 7,034
Quote Quote by Norwegian View Post
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.
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.

Quote Quote by Norwegian View Post
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%.
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) ?

Joffan
#4
Mar21-12, 07:13 AM
P: 361
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 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}$$
rcgldr
#5
Mar21-12, 08:30 AM
HW Helper
P: 7,034
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?
Joffan
#6
Mar21-12, 09:03 AM
P: 361
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.
rcgldr
#7
Mar21-12, 09:15 AM
HW Helper
P: 7,034
Quote Quote by Joffan View Post
There are 10c7 = 120 different distributions of 7 identical items into 4 containers.
Should that be (7+4-1)c4 = 10c4 = 210 distributions? update - no, it's (7+4-1)c(7) = 10c7 = 120.

Quote Quote by Joffan View Post
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.
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.
Joffan
#8
Mar21-12, 10:52 AM
P: 361
Quote Quote by rcgldr View Post
Should that be (7+4-1)c4 = 10c4 = 210 distributions?
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.
rcgldr
#9
Mar21-12, 04:26 PM
HW Helper
P: 7,034
Quote Quote by Joffan View Post
No, it's 10c7 = 10c3. Remember we're modelling this with bin dividers, and for 4 bins there are 3 dividers.
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.

Quote Quote by Joffan View Post
To convince yourself, it's not a massive task to list out the possible distributions.
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

Quote Quote by Joffan View Post
The rest of your question is interesting but I don't have time right now - I may get back to it.
OK, to keep it simple, just use the 7 items into 4 containers situation.

Quote Quote by Joffan View Post
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.
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}).
Joffan
#10
Mar25-12, 01:16 PM
P: 361
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 )
Joffan
#11
Mar25-12, 01:54 PM
P: 361
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.
rcgldr
#12
Mar25-12, 06:43 PM
HW Helper
P: 7,034
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
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.
Joffan
#13
Mar25-12, 07:17 PM
P: 361
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.
rcgldr
#14
Mar25-12, 07:55 PM
HW Helper
P: 7,034
Quote Quote by Joffan View Post
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.
As mentioned, the second part of post #5 of

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

Quote Quote by rcgldr View Post
7 items 4 containers ... variation on probability to calculate the number of ways to produce individual patterns, for each of the the 4 permuations of {1 2 2 2}, number of ways = (7!) / (1! 2! 2! 2!) = 630, for each of the 4 permutations of {1 1 1 4}, number of ways = (7!) / (1! 1! 1! 4!) = 210, ...
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.
Joffan
#15
Mar25-12, 08:43 PM
P: 361
Sorry rcgldr, I didn't notice your link before. Amazingly similar lines of thought.
rcgldr
#16
Mar25-12, 09:54 PM
HW Helper
P: 7,034
Quote Quote by rcgldr View Post
expansion series
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.
Joffan
#17
Mar25-12, 11:33 PM
P: 361
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.
rcgldr
#18
Mar26-12, 03:08 AM
HW Helper
P: 7,034
Quote Quote by Joffan View Post
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.
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.

Quote Quote by Joffan View Post
Now I just need to understand how that we're adding the right amount back in / subtracting off the double-count.
Although my explanation may help, I think doing a few examples will convince you.


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