I am considering to distribute N-kinds of different parts among M-different countries and I wan to know the "most probable" pattern of distribution. My question is in fact ambiguous, because I am not very sure how I can distinguish types or patterns.
Let me give an example. If I were to distribute 3 kinds of parts to 3 countries, the set of all distribution is given by a set
{aaa, aab, aac, aba, abb, abc aca, acb, acc, baa, bab, bac, bba, bbb, bbc, bca, bcb, bcc, caa, cab, cac, cba, cbb, cbc, cca, ccb, ccc}.
The number of elements is of course 33 = 27. I may distinguish three types of patterns:
(1) One country receives all parts:
aaa, bbb, ccc 3 cases
(2) One country receives 2 parts and another country receives 1 part:
aab, aac, aba, abb, aca, acc, baa, bab, bba, bbc, bcb, caa, cac, cbb, cbc, cca, ccb 17 cases
(3) Each county rceives one part respectively:
abc, acb, bac, bca, cab, cba 6 cases
These types may correspond to a partition of integer 3 with the condition that (a) number of summands must not exceed 3 (in general M). In fact, 3 have three partitions:
3, 2+1, 1+1+1
In the above case of 3×3, the number of types was the number of partitions of 3 (which is often noted p(n)). But I have to consider the case when M is smaller than N.
If I am right, the number of "different types" of distributions is the number of partitions of N with the number of summands less than M+1. Let us denote it as
p*(N, M) = p( N | the number of summands must not exceed M. )
N.B. * is added in order to avoid confusion with p(N, M), wwhich is the number of partitions with summands smaller than M+1.
Now, my question is the following:
Which type (a partition among p*(N, M)) has the greatest number of distributions?
Are there any results already known? If so, would you kindly teach me a paper or a book that explains the results and how to approach to the question?
A typical case that I want to know is N = 100, M = 10. In this simple case, is it most probable that each country receives 10 parts? But, I am also interested to cases when M and N are small, for example when M and N is less than 10.
Dear Yoshinori Shiozawa
As far as I have understood your problem, this is similar to draw a Hesse .diagram . But to find the best possible one , you can apply graph theory approach on Hesse diagram . For simplicity, the minimum number of nodes which make the graph complete will give you solution. One of the best applications of this problem is gene lineage tracing.
Thank you for your information. Can you explain the case M=3, N=4? How can you use Hasse diagram?
Let me explain my problem in the small case of M=3, N=4.
There are 81 distributions (combinations), because this is the repeated permutation (a sequence of length M with N elements) which is MN.
More explicitly, when we denote countries by {a, b, c, d}, the set of all permutations are given by the set
{aaaa aaab aaac aaba aabb aabc aaca aacb aacc
abaa abab abac abba abbb abbc abca abcb abcc
acaa acab acac acba acbb acbc acca accb accc
baaa baab baac baba babb babc baca bacb bacc
bbaa bbab bbac bbba bbbb bbbc bbca bbcb bbcc
bcaa bcab bcac bcba bcbb bcbc bcca bccb bccc
caaa caab caac caba cabb cabc caca cacb cacc
cbaa cbab cbac cbba cbbb cbbc cbca cbcb cbcc
ccaa ccab ccac ccba ccbb ccbc ccca cccb cccc}
There are four types or patterns:
{4} {3+1} {2+2} {2+1+1}.
These are different partitions of integer 4. But the type {1+1+1+1} must be excluded as the number of summands exceed 3. The partition {3+1} here means a permutation that has 3 same county symbols and one different symbol.
Here are set of permutations for each type:
{4} aaaa bbbb cccc 3
{3+1} aaab aaac aaba aaca abaa abbb acaa accc
baaa babb bbab bbba bbbc bbcb bcbb bccc
caaa cbbb cacc cbcc ccac ccbc ccca cccb 24
{2+2} aabb aacc abab abba acac acca baab baba
bbaa bbcc bcbc bccb caac caca cbbc cbcb
ccaa ccbb 18
{2+1+1} aabc aacb abac abbc abca abcc acab acba acbb acbc
accb baac babc baca bacb bacc bbac bbca bcaa bcab
bcba bcac bcba bcca caab caba cabb cabc cacb cbaa
cbab cbac cbba cbca ccab ccba 36
In total, we have listed 3* 24+ 18 + 36 = 81 permutations.
In view of this enumeration, we can say that the type {2+1+1} counts the biggest numbers. If we assume the equal probability to each permutations, we can also say that the type {2+1+1} is the most probable pattern when we distribute N elements in M boxes.
I want to know the results for more general cases.
Yoshinori Shiozawa Yeah now I have understood your problem.
Let me make an attempt with your example. There are N (=4) things to be distributed among M (=3) countries.
Total number of ways to distribute N things at M places are : D = M^N.
now the same problem can be interpreted as: "finding the non-negative integral solution of M dimensional linear equation a1 + a2 + ... + aM = N where each ai lies between 0 and N for i =1, 2, .., M. The total number of possible solutions are L = (M+N-1)C(N). By substituting M =3 and N = 4, L = 15 which are given as:
1. (4, 0 , 0) no. of solution L1= 3; no. of ways D1 = 3C1 * 1 = 3.
2. (1, 3, 0) no. of solution L2= 6; no. of ways D21 = 3C1 * 4 * 2C1 * 1 = 24.
3. (2, 2, 0) no. of solution L3= 3; no. of ways D22 = (3C1 * 4C2 * 2C1 * 1)/2 = 18.
4. (1, 1, 2) no. of solution L4 = 3; no. of ways D3 = (3C1*4*2C1*3*1C1 * 1)/2 = 36.
Now L1 + L2 + L3 + L4 = L = 15 and D1+ D21+ D22+ D3 = D = 81. and the best solution will be the max(Di/D), [here D4]. Now let's generalize this :
1. (N, 0, ..., 0); L1 = M; D1 = MC1*1 = M.
2. (1, N-1, 0, ..., 0); L2 = MC2 * 2! ; D21 = MC1 * NC1 * (M-1)C1 * 1= NM(M-1).
3. (2, N-2, 0, ..., 0); D22 = MC1*NC2*(M-1)C1*1 = NC2 * M (M-1).
if N is even, then it will continue as
3a. (N/2, N/2, 0,..., 0); D2N/2 = MC1*NC(N/2)*(M-1)C1*1 = NC(N/2)*M*(M-1).
if N is odd, then
3b. (N-1/2, N+1/2, 0,..., 0); D2N-1/2 = MC1*NC(N-1/2)*(M-1)C1*1 = NC(N-1/2)*M*(M-1).
To avoid such confusion : replace D2i = D2i/2 for all i = 1, 2, ....N-1
so in general, D2 = 0.5*M(M-1)*[NC1 + NC2 + NC3 + .... + NC(N-1)]
Now the next part can be generalized. It's very cumbersome to type all this here. I hope I have understood your exact problem and contributed sufficiently to solve the same.
In addition to the answer of @Bharat Soni maybe this could be helpful
Dear Bharat Soni and Zoran Maksimovic ,
thank you for precious information. Soni's idea must be right, but to count the dimension seems me to complicated, perhaps because I have no experience to challenge such problems. Maksimovic's illustration for the case M=3, N=6 is very easy to understand. According to this illustration, I can easily calculate the number of repeated permutations with a type given as partition of N which does not exceed M.
The remaining question is how to calculate the most probable type (a partition of N which has the largest number of repeated permutations). Have you or has someone any ideas?
Dear colleagues,
The problem proposed by Yoshinori Shiozawa is closely related to the determination of a “type” of summands in multinomial formula whose sum of coefficients attains a maximal value. In order to explain this idea, consider the cases presented in related answers:
First case: M =3, N=3 (considered in the question by Yoshinori Shiozawa). By the multinomial formula, we have
(a+b+c)³=(a³+b³+c³)+(3a²b+3ab²+3a²c+3ac²+3b²c+3bc²)+(6abc).
The terms of the above expansion are grouped by brackets into three classes, which under notations of Shiozawa, correspond to the types of patterns (partitions of 3) {3}, {2+1} and {1 +1+1}, respectively. Moreover, under concepts of Shiozawa, the number of distributions of any type is equal to the sum of coefficients of all terms of the above expansion that correspond. Accordingly, the numbers of distributions of types {3}, {2+1} and {1 +1+1}, are equal to 1+1+1=3, 3+3+3+3+3+3=18 and 6, respectively. Hence, the type {2 +1} counts the biggest numbers (equal to 18).
Second case: M =3, N=4 (considered in the answers by Yoshinori Shiozawa and Bharat Soni). By the multinomial formula, we have
(a+b+c)^4 = (a^4+b^4+c^4)+(4a^3b+4a^3c +4ab^3+4ac^3+4b^3c+4a^3c)+(6a^2b^2+6a^2c^2+6b^2c^2)+(12a^2bc+12ab^2c+12abc^).
The terms of the above expansion are grouped by brackets into four classes, which under notations of Shiozawa, correspond to the types of patterns (partitions of 4) {4}, {3+1}, {2+2} and {2 +1+1}, respectively. Moreover, under concepts of Shiozawa, the number of distributions of any type is equal to the sum of coefficients of all terms of the above expansion that correspond. Accordingly, the numbers of distributions of types {4}, {3+1}, {2+2} and {2 +1+1}, are equal to 3*1=3, 6*4=24, 3*12=36 and 12, respectively. Hence, the type {2 +1+1} counts the biggest numbers (equal to 36).
Third case: M =3, N=6 (considered in the answer by Zoran Maksimovic.
By the multinomial formula, we have (a+b+c)^6=∑a^6+6∑a^5b+15∑a^4b^2+30∑a^4bc+
20∑a^3b^3+60∑a^3b^2c+90a^2b^2c^2, where all the six sums ∑ are cyclic.
The terms of the above expansion are grouped by brackets into seven classes, which under notations of Shiozawa, correspond to the types of patterns (partitions of 4) {6}, {5+1}, {4+2}, {4+1+1}, {3+3}, {3+2+1} and {2 +2+2}, respectively. Moreover, under concepts of Shiozawa, the number of distributions of any type is equal to the sum of coefficients of all terms of the above expansion that correspond. Accordingly, the numbers of distributions of types {6}, {5+1}, {4+2}, {4+1+1}, {3+3}, {3+2+1} and {2 +2+2}, are equal to 3*1=3, 6*6=36, 15*6=90, 30*3=90, 20*3=60, 60*6=360 and 90*1=90, respectively. Hence, the type {3 +2+1} counts the biggest numbers (equal to 360).
Of course, for small values M and N, proceeding as in the above cases, it can be determined a related type that counts the biggest numbers. However, for large values N and/or M, it is necessary to find numerous computations for finding a desired type of distribution.
Dear Yoshinori Shiozawa,
Proceeding as in my previous answer, we obtain the following results:
1) If M =3, N=7, then the biggest number of related distributions is equal to 630 and it is attained by types {3+2+2} and {4+2+1};
2) If M =3, N=8, then the biggest number of related distributions is equal to 1680 and it is attained by types {3+3+2} and {4+3+1};
3) If M =3, N=9, then the biggest number of related distributions is equal to 7560 and it is attained by type {4+3+2};
4) If M =3, N=10, then the biggest number of related distributions is equal to 15120 and it is attained by type {5+3+2};
5) If M =3, N=11, then the biggest number of related distributions is equal to 41580 and it is attained by type {5+4+2};
5) If M =3, N=12, then the biggest number of related distributions is equal to 83160 and it is attained by type {5+4+3}.
Thank you, for your calculation, Romeo Meštrović . The cases (1) and (2) are particularly interesting, because two patters have the same highest possibilities.
Is it possible to know the form of the function f, when f is the number of distributions which has a given pattern? Does it form a kind of unimodal mountain which stands on a field of patterns?
All considered cases for M =3 with N=3, 4,…12, suggest the following general expressions for the biggest number of related distributions for M =3 and arbitrary N>5.
a) If N=3k with k>1, then the biggest number of related distributions for M =3 is
S(3,3k)=6*(3k)!/((k+1)!k!(k-1)!), and it is attained by type {(k+1)+k+(k-1)}.
b) If N=3k+1 with k>1, then the biggest number of related distributions for M =3 is S(3,3k+1)=6*(3k+1)!/((k+2)!k!(k-1)!), and it is attained by type {(k+2)+k+(k-1)}.
c) If N=3k+2 with k>1, then the biggest number of related distributions for M =3 is S(3,3k+2)=6*(3k+2)!/((k+2)!(k+1)!(k-1)!), and it is attained by type {(k+2)+(k+1)+(k-1)}.
These expressions are supported by the fact that for a given fixed N, a trinomial coefficient N!/(a!b!c!) attains a maximal value if a, b and c are close to N/3. However, if in the case N=3k, we assume the type {k+k+k}, then the number of related distributions is (3k)!/((k)!k!(k)!)< 6*(3k)!/((k+1)!k!(k-1)!=S(3,3k) (because of this, I have assumed the type {(k+1)+k+(k-1)} with distinct parts).
A determination of most probable type of distribution for large values N and/or M
is complicated by the fact that it does not depend only on the values of the corresponding multinomial coefficient, but also on the number of terms in this type of distribution, as well as on the number of distinct terms that appear in this type (as it was observed at the end of my previous answer for the case M=3 and N=3k, k>1, where it is attributed that {(k+1)+k+(k-1)} is the most probable type of distribution for this case).
Consider the case M=10, N=100 which is mentioned in the explanation of the problem proposed by Yoshinori Shiozawa. In this case, in terms of M=10 countries and N=100 parts, Shiozawa proposed the following question: “In this simple case, is it most probable that each country receives 10 parts? ”, If we assume the type with the same parts, i.e., the type {10+10+10+10+10+10+10+10+10+10}, then the number of related distributions is equal to 100!/10!^10 (= the coefficient of the term a_1^10a_2^10∙∙∙a_10^10 in the multinomial expansion (a_1+a_2+∙∙∙+a_10)^100)).
However, if we asuume the types with some distinct terms, then the number of related distributions will increase, since in this cases there are “many” corresponding terms in the multinomial expansion (a_1+a_2+∙∙∙+a_10)^100). For, example, the number of distributions which correspond to the type {11+9+10+10+10+10+10+10+10+10} is equal to (10*9)*100!/(11!*9!*10!^8), which is 900/11 ≈ 81.82 greater than 100!/10!^10. Accordingly, using some computations for comparing numbers of distributions for different types, I got (without rigorous proof!) the result that the biggest number of distributions in the case M=10, N=100 would be attained by the type {14+13+12+11+10+10+9+8+7+6}, and it is equal to
(10!/2)*(100!/(14!13!12!11!10!10!9!8!7!6!)).
Please see the attachement, where for all M and N, it is given a general formula (3) in closed form for numbers of related distributions of any type.
Dear Romeo,
thank you very much for your investigation. In this week, I was too busy to respond to your posts. i HIGHLY appreciate your efforts. The concept of "kind" is a good idea. With the aid of this concept, we could get a closed formula. It is great.
Dear Yoshinori,
Thanks for you interesting question. Here is how I would answer it. First, if N independent items are to be distributed into M different countries (a,b,c), then the problem can be modelled by the multinomial distribution: "the multinomial distribution is a generalization of the binomial distribution. For example, it models the probability of counts for each side of a k-sided die rolled n times." (wikipedia). Notice that the multinomial distribution requires that each country has its own fixed probability: (pa,pb,pc), where pa + pb + pc = 1.
Now, the question is what probability distribution should we assign to (pa,pb,pc). In all the N-times and M-countries cases discussed in this question you found a distribution that has the greatest number of ways of achieving it. Conducting a similar reasoning for the case of (pa,pb,pc) we can adopt the criteria of selecting the probability distribution that has the greatest information entropy
H(pm) = -[pa ln (pa) + pb ln (pa) + pc ln (pa)]
subject to
pa + pb + pc = 1
and NOTHING ELSE.
"Nothing else" is because your question does not involve any further information. Solving this maximization problem, i.e., finding the distributions (pa,pb,pc) using the Principle of Maximum Entropy (E.T. Jaynes), gives you the uniform distribution (1/3, 1/3, 1/3). H(pm) is a concave function and FOC are enough to find the maximum.
By adopting this principle, you can translate economic/institutional hypotheses as moment constraints in the problem and derive a probability distribution (pa,pb,pc) which you can plug into the multinomial distribution. Selecting a distribution that does not has the maximum entropy would be biased.
I'm pretty sure that the answer I gave can be set in just one part (and not in two). Jaynes's "Where do we stand in maximum entropy" and the "Concentration theorem" are two enjoyable papers presenting the philosophy and math for doing this.
I'll include this problem in a problem set next semester.
Thanks!
Stay safe!
Daniel
- Badges
- Science topic
- Similar topics
- Mathematics
- Applied Mathematics