Why are two answers different using the two equivalent formulas in combinatorics ?

[Dhamnekar Win,odd]

[Genady]

3 hours ago, Dhamnekar Win,odd said:

They are not equivalent.

[Dhamnekar Win,odd]

  If I am not wrong,  both formulas are meant for the computation of number of distinguishable distributions of indistinguishable r objects putting into n cells so that none of the n cells remains empty. 

[Genady]

10 minutes ago, Dhamnekar Win,odd said:

  If I am not wrong,  both formulas are meant for the computation of number of distinguishable distributions of indistinguishable r objects putting into n cells so that none of the n cells remains empty. 

I don't know about this, but they are different for r=n=2. What is the source of the statement above?

[Dhamnekar Win,odd]

 Please read my  post under the heading "Elements of Combinatorial Analysis". Source " An Introduction to Probability Theory and Its Applications" by W.Feller, Chapter 2 and 4.

[Genady]

23 minutes ago, Dhamnekar Win,odd said:

 Please read my  post under the heading "Elements of Combinatorial Analysis". Source " An Introduction to Probability Theory and Its Applications" by W.Feller, Chapter 2 and 4.

I just did. The equation (2) there is very similar although not identical to your formula 2 here. And, nothing there says that the two formulas in the OP are equivalent, does it?

[Dhamnekar Win,odd]

Did you go through the corrected equation (2) in my last post? v and k are the same variable i-e we are to select v or k cells from the n cells. That's it. 

[Genady]

27 minutes ago, Dhamnekar Win,odd said:

Did you go through the corrected equation (2) in my last post? v and k are the same variable i-e we are to select v or k cells from the n cells. That's it. 

Here is your other post:

 

 

Of course v or k doesn't make a difference. There is an actual difference between (2) above and the second formula in the OP:

 

 

Do you see it?

 

Plus, I don't see anything there about the equivalence you're talking about here.

[Dhamnekar Win,odd]

[Genady]

OK. Now, the first formula in the OP says, 

A(r,n) = C(r-1,n-1)

Where did it come from?

[Dhamnekar Win,odd]

 

The proof of the above formula was given in the book on probability by W.Feller

Edited March 8, 2022 by Dhamnekar Win,odd

[Genady]

28 minutes ago, Dhamnekar Win,odd said:

 

The proof of the above formula was given in the book on probability by W.Feller

Yes, this formula is correct.

However, the equation (2) is not. Take for example r=2 objects and n=2 cells. There is only 1 way to distribute them with no empty cells, i.e. 1+1. But the equation (2) gives 2. This would be so if, for example, the objects were distinguishable.

[Dhamnekar Win,odd]

Assuming equation(2) to hold, how to express A(r-k, n) in equation (1) accordingly?

 

How to change the order of summation and use the binomial formula to express A(r, n+1) as the difference of two simple sums as feller suggested?

 

How to replace in the second sum v+1 by a new index of summation and use the following important property of binomial theorem

[math]\binom{x}{r-1} + \binom{x}{r} = \binom{x+1}{r}[/math]?

Edited March 9, 2022 by Dhamnekar Win,odd

[Genady]

4 hours ago, Dhamnekar Win,odd said:

Assuming equation(2) to hold, how to express A(r-k, n) in equation (1) accordingly?

You can substitute A(r-k, n) in eq.(1) using the right side of eq.(2) while instead of (n-v)^r you should put (n-v)^r-k. Let's see what you get.

[Dhamnekar Win,odd]

 I did those computations for case(1) r=2, n=2 and case(2)r=2 and n=3.

For case(1) The number of distinguishable distributions of 2 indistinguishable objects putting into 2 cells   is 1 (equation or formula 1) and the numbers of distinguishable distributions of 2 distinguishable objects putting  into 2 cells are 2(equation or formula 2)

For case(2) The number of distinguishable distributions of 2 indistinguishable objects putting into 3 cells is -1 (equation or formula 1) and the number of distinguishable distributions of 2 distinguishable putting into 3 cells is  0(equation or formula 2) 

So, now how can we change the order of summation and use the binomial formula to express A(r, n+1) or in our case A(2,3) as the difference of two simple sums?

 

 

[Genady]

21 hours ago, Dhamnekar Win,odd said:

In the eq (1) here your upper limit of summation is k=r. Are you sure about it? I don't think it is correct.

1 hour ago, Dhamnekar Win,odd said:

 I did those computations for case(1) r=2, n=2 and case(2)r=2 and n=3.

The case (2) doesn't make sense. You cannot distribute 2 objects in 3 cells such that there are no empty cells. I think, you have to have at least as many objects as there are cells for these formulas to make sense. That's why I think that the upper limit of summation in eq (1) is incorrect.

Did you derive the eq (1) by a combinatorial argument, as requested?

[Dhamnekar Win,odd]

 I am trying to derive the formula (1) by combinatorial argument, but I didn't succeed.

My difficulty to understand the Author's suggestions:

1) This is a classical occupancy problem. Assuming that all [math]n^r[/math] possible placements are equally probable, the probability to obtain the given occupancy numbers [math]r_1,...r_n[/math] equals [math] \frac{r!}{r_1! r_2!...r_n!} n^{-r}[/math]  Here, we are concerned with only indistinguishable particles or objects. In Physics, this probability is known as Maxwell-Boltzmann statistics.

Now, suppose, we have to put 4 objects in 2 cells. The number of distinguishable distributions of 4 identical objects into 2 cells is [math]\binom{3}{1}=3[/math].|***|*|, |*|***| or |**|**|

But if we use formula (2) we get 14 as answer |**|**|, |**|**|, |**|**|, |**|**|, |**|**|, |**|**|, |***|*|,|***|*|,|***|*|, |***|*|, |*|***|, |*|***|, |*|***|, |*|***| . In case of A,B,C,D objects, we get   |AB|CD|,|AC|BD|,|AD|BC|,|BC|AD|,|BD|AC|,|CD|AC|,|ABC|D|,|ACD|B|,|ABD|C|,|BCD|A|,|A|BCD|,|B|ACD|,|C|ABD|,|D|ABC|

 

Using formula (1), we get [math]A(4,3)=\displaystyle\sum_{k=1}^{4}\binom{4}{k}*\displaystyle\sum_{v=0}^{2}(-1)^v*\binom{2}{v}*(2-v)^{4-k}=35[/math]

I think this answer assumes distinguishable cells as well as objects. Now I don't understand , on what basis , we can say that this formula is derived assuming indistinguishable objects?   

Edited March 9, 2022 by Dhamnekar Win,odd

[Genady]

3 minutes ago, Dhamnekar Win,odd said:

 I am trying to derive the formula (1) by combinatorial argument, but I didn't succeed.

...

I think this answer assumes distinguishable cells as well as objects. Now I don't understand , on what basis , we can say that this formula is derived assuming indistinguishable objects?   

Yes, both equations (1) and (2) relate to distinguishable objects and distinguishable cells.

Eq (1) is recursive. That is, assume that there are A(x, n) ways to distribute x distinguishable objects between n distinguishable  cells, with no empty cells. Knowing this for any number of distinguishable objects x > n, we want to find A(r, n+1), number of ways to distribute r distinguishable objects between n+1 distinguishable cells, with no empty cells.

Start thinking about it in the following way. Take one of the n+1 cells aside. Let's call it a "new" cell. You have one new cell and n old cells. You have to put some number of objects, k>0, in the new cell.

The rest r-k objects will go into the n old cells. This can be done in A(r-k, n) ways, the number that we assume we know.

Can you continue from here so we get the expression for A(r, n+1), which is the eq (1)?

 

[Dhamnekar Win,odd]

Using formula (2), we get [math] A(4,2)= \displaystyle\sum_{v=0}^{2}(-1)^v\cdot \binom{2}{v}(2-v)^4=14[/math]

Using formula (1), we get [math]A(4,2)=\displaystyle\sum_{k=1}^{4} \binom{4}{k}\cdot\displaystyle\sum_{v=0}^{1}(-1)^v \binom{1}{v}(1-v)^{4-k}=15[/math]

 

Now, how can we remove the difference of one  between these two answers?

Edited March 9, 2022 by Dhamnekar Win,odd

[Genady]

I think, the difference appears because of the problem which I've pointed to earlier:

3 hours ago, Genady said:

In the eq (1) here your upper limit of summation is k=r. Are you sure about it? I don't think it is correct.

 

[Dhamnekar Win,odd]

That's what the author want to suggest. How can we change the order of summations in the answer which we got using formula (1) so that we get the answer 14?

[Genady]

4 minutes ago, Dhamnekar Win,odd said:

That's what the author want to suggest. How can we change the order of summations in the answer which we got using formula (1) so that we get the answer 14?

It is not the order of summation you need to change. It is the upper limit of summation.

[Dhamnekar Win,odd]

I changed the order of summation and the expressed A(4,1+1=2)as the difference of two simple sums [math]\displaystyle\sum_{k=1}^{4}\binom{4}{k} \cdot\displaystyle\sum_{v=0}^{1}(-1)^v\cdot \binom{1}{v}\cdot(1-v)^{4-k}-\displaystyle\sum_{v=0}^{1}(-1)^v\cdot \binom{1}{v}\cdot(1-v)[/math]

 

Now, what we can do?

Edited March 10, 2022 by Dhamnekar Win,odd

[Genady]

4 hours ago, Dhamnekar Win,odd said:

I changed the order of summation and the expressed A(4,1+1=2)as the difference of two simple sums ∑k=14(4k)⋅∑v=01(−1)v⋅(1v)⋅(1−v)4−k−∑v=01(−1)v⋅(1v)⋅(1−v)

 

Now, what we can do?

1. You need to derive the equations for generic variables r and n. Working with specific values, such as r=4 and n=2, will not give you a general derivation.

2. The upper limit of summation is still wrong.

3. I don't know where the second part of these two simple sums came from. From nowhere?

4. You still did not derive equation (1). I've given you a fat hint for that. If you derive it, you will see where your summation limit is wrong. 

Edited March 10, 2022 by Genady

[Dhamnekar Win,odd]

If I put r=2, I get answer=3. If I put 4=3, I get answer=7. If I put r=4, I get answer=15. Now what is your suggestion?