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

[Genady]

  On 3/10/2022 at 12:23 PM, Dhamnekar Win,odd said:

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?  

Expand  

I've given you my suggestions in my previous post.

[Dhamnekar Win,odd]

Author said to change order of summation and use binomial formula to express A(r, n+1) as the difference of two simple sums. So, I did it. As regards derivation of equation(1) using combinatorial arguments, author didn't write anything about that in his book. So, I don't know how to derive it.     

[Genady]

  On 3/10/2022 at 1:00 PM, Dhamnekar Win,odd said:

Author said to change order of summation and use binomial formula to express A(r, n+1) as the difference of two simple sums. So, I did it.

Expand  

You need to do it algebraically, not numerically.

  On 3/10/2022 at 1:00 PM, Dhamnekar Win,odd said:

As regards derivation of equation(1) using combinatorial arguments, author didn't write anything about that in his book. So, I don't know how to derive it.     

Expand  

Did you see my suggestion about how to do it? Did you try it?

[Dhamnekar Win,odd]

My attempt to derive general formula for A(r,n) =$\displaystyle\sum_{k=1}^{r-1}\binom{r-1}{k}\cdot A(r-k-1,n-1)$ 

Edited March 10, 2022 by Dhamnekar Win,odd

[Genady]

  On 3/10/2022 at 2:24 PM, Dhamnekar Win,odd said:

My attempt to derive general formula for A(r,n) =∑k=1r−1(r−1k)⋅A(r−k−1,n−1)  

Expand  

The general form is OK, but the variables are not.

First, do it the way in which the eq (1) is given. I.e. use A(..., n) as given and derive A(r, n+1). It Should look like A(r, n+1) = .... A(r-k, n).

Second, provide explanation for each component, i.e. what is the coefficient in front of A(r-k, n) and what values of k are you summing for.

[Dhamnekar Win,odd]

 

$A(4-k,2)= (-1)^0 \cdot \binom{2}{0} \cdot(2-0)^{4-1} + (-1)^1\cdot \binom{2}{1} \cdot(2-1)^{4-2} = 8-1 =7$

Is this answer correct?

Edited March 10, 2022 by Dhamnekar Win,odd

[Genady]

  On 3/10/2022 at 4:15 PM, Dhamnekar Win,odd said:

 

A(4−k,2)=(−1)0⋅(20)⋅(2−0)4−1+(−1)1⋅(21)⋅(2−1)4−2+(−1)2⋅(22)⋅(2−2)4−3=8−1+0=7

Is this answer correct?

Expand  

Which question do you try to answer with this?

[Dhamnekar Win,odd]

This answer refers to r=4 objects and n=2 cells question. We know A(r,n) =A(4,2)= 14 , My answer to A(r-k,n))=A(4-k, 2)=7

 

Is this answer correct? 

[Genady]

  On 3/10/2022 at 4:55 PM, Dhamnekar Win,odd said:

This answer refers to r=4 objects and n=2 cells question. We know A(r,n) =A(4,2)= 14 , My answer to A(r-k,n))=A(4-k, 2)=7

 

Is this answer correct? 

Expand  

A(4-k, 2) depends on k. So, it is not 7. It is different for different values of k.

[Dhamnekar Win,odd]

So, for $k=1, A(3,2)=(-1)^0 \cdot \binom{2}{0} \cdot (2-v)^{4-1=3}$

Is this correct?

Edited March 10, 2022 by Dhamnekar Win,odd

[Genady]

  On 3/10/2022 at 5:39 PM, Dhamnekar Win,odd said:

So, for k=1,A(3,2)=(−1)0⋅(20)⋅(2−v)4−1=3

Is this correct?

Expand  

No.

[Dhamnekar Win,odd]

But as per formula (2)r=4 and k=1 , which results in $(-1)^0 \cdot \binom{2}{0}\cdot(2-v)^3$

Formula (2) = $A(r-k,n) =\displaystyle\sum_{v=0}^{n}(-1)^v\binom{n}{v}(n-v)^{r-k}$ 

Edited March 10, 2022 by Dhamnekar Win,odd

[Genady]

  On 3/10/2022 at 6:08 PM, Dhamnekar Win,odd said:

But as per formula (2)r=4 and k=1 , which results in (−1)0⋅(20)⋅(2−v)3

Formula (2) = A(r−k,n)=∑v=0n(−1)v(nv)(n−v)r−k  

Expand  

There is a summation in the formula (2) for A(), but in your calculation there is no summation. So, you have calculated only one components of A(3,2), rather than the value A(3,2).

In fact, A(3,2) = 6. For example, if your objects are a, b, and c, then there are these 6 ways to distribute them in 2 distinguishable cells with no empty cells:

a | bc

b | ac

c | ab

bc | a

ac | b

ab | c

 

[Dhamnekar Win,odd]

So, Eventually I did it.

Using formula (1) we get $A(4,2)= \displaystyle\sum_{k=1}^{3}\binom{4}{k}\cdot \displaystyle\sum_{v=0}^{1}(-1)^v\cdot \binom{1}{v}\cdot (1-v)^{4-k}=14$

 

Using formula (1)we get$A(4,3)=\displaystyle\sum_{k=1}^{2}\binom{4}{k}\cdot\displaystyle\sum_{v=0}^{2}(-1)^v\cdot \binom{2}{v} \cdot (2-v)^{4-k}=36$

Using formula (2) we get $A(4,2)=\displaystyle\sum_{v=0}^{2}(-1)^v \cdot \binom{2}{v}\cdot (2-v)^{4}=14$ as expected

Using formula (2) we get $A(4,3)=\displaystyle\sum_{v=0}^{3}(-1)^v\cdot  \binom{3}{v}\cdot(3-v)^{4}=36$ as expected.

 

Thanks for your guidance.

 

Edited March 11, 2022 by Dhamnekar Win,odd