Timeline for Counting the number of weakly separated pairs
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 12, 2021 at 20:57 | comment | added | Jianrong Li | @FedorPetrov, using your formula, the number is $\sum_{s=1}^k s {n \choose k-s, 2s, n-k-s} - {n \choose 2} - n {n \choose k} + n^2$. Thanks a lot! | |
| Jan 12, 2021 at 20:28 | history | edited | Jianrong Li | CC BY-SA 4.0 |
added 249 characters in body
|
| Jan 12, 2021 at 20:25 | comment | added | Jianrong Li | @FedorPetrov, now I see why my result is different from your formula. I forgot to say that I assumed that $I, J$ are not of the form $a, a+1, \ldots, a+k$ (mod $n$). I also counted $(I, J), (J, I)$ as one pair (not two pairs). Sorry about the confusion. I will edit the file. | |
| Jan 12, 2021 at 18:20 | comment | added | Jianrong Li | @FedorPetrov, thank you very much. | |
| Jan 12, 2021 at 17:17 | comment | added | Fedor Petrov | because either $I-J$ or $J-I$ should be a segment of $s$ consecutive elements of $2s$ elements of $I\Delta J$ | |
| Jan 12, 2021 at 16:00 | comment | added | Jianrong Li | @FedorPetrov, I tried to verify your formula using some $k,n$. I think that in your formula, $s$ is from $1$ to $k$ (not $n$). But still in the case of $k=3, n=6$, I don't get $54$. Why there are $2s$ choices of $I-J$? Thank you very much. | |
| Jan 12, 2021 at 15:44 | comment | added | Jianrong Li | @FedorPetrov, thank you very much! | |
| Jan 12, 2021 at 15:40 | comment | added | Fedor Petrov | $n!/((k-s)!(2s)!(n-k-s)!)$ | |
| Jan 12, 2021 at 15:25 | comment | added | Jianrong Li | @FedorPetrov, thank you very much. What is the value of ${n \choose k-s,2s,n-k-s}$? | |
| Jan 12, 2021 at 11:58 | comment | added | Fedor Petrov | If we exclude $I=J$ case, and denote $|I-J|=|J-I|=s$, then if we fix the sets $I\cap J$ and $I\Delta J$ (that may be done by ${n\choose k-s,2s,n-k-s}$ ways), there are $2s$ choices of $I-J$. So the answer is $\sum_{s=1}^n 2s\cdot {n\choose k-s,2s,n-k-s}$. | |
| Jan 12, 2021 at 11:49 | comment | added | Jianrong Li | @FedorPetrov, thank you very much for your suggestions. | |
| Jan 12, 2021 at 10:05 | comment | added | Fedor Petrov | It's a certain binomial sum. You may write some generating function in a closed form. But not the entire sum, I am afraid. | |
| Jan 12, 2021 at 9:43 | history | edited | Jianrong Li | CC BY-SA 4.0 |
added 296 characters in body
|
| Jan 12, 2021 at 9:19 | history | asked | Jianrong Li | CC BY-SA 4.0 |