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.

Wonderful explanation! Thank you very much.

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.