Timeline for Maximum number of subsets in which people co-exist with their friends
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 28, 2021 at 19:55 | vote | accept | mgus | ||
| Jan 27, 2021 at 22:14 | answer | added | Max Alekseyev | timeline score: 3 | |
| Jan 27, 2021 at 21:34 | comment | added | mgus | Thanks for your comments. Can you help me prove (or disprove) the argument that setting $F_i$'s to be all equal to each other maximizes the desired quantity? Based on your first observation, rewriting $\forall j\in A^c\cap S, j \in F_i \text{ for all } i\in A\cap S$ as $(A^c\cap S) \subseteq \bigcap\limits_{i\in A\cap S}F_i$ seems to make this argument more intuitive. But, I am still not sure whether this is rigorous to serve as a proof. | |
| Jan 27, 2021 at 20:56 | comment | added | Max Alekseyev | It was included in summation -- as the term with $i=r$. It was ok to keep the upper limit as $a$ as the product of binomial coefficients is simply zeros when $i>r$. If you like to have $\max$ in the limit, then $\max\{a,r\}$ would be better to incorporate this extra term $\binom{a}{r}$. In either case, the sum still simplifies to just $\frac{1}{2}\binom{2a}{r}$. | |
| Jan 27, 2021 at 20:04 | comment | added | mgus | Hello, I have incorporated your first comment to the expression. Now, the term $\binom{a}{r}$ refers to the number of subsets that consist exclusively from people in $A$ since I have assumed that $a\geq r$. This quantity is not included in the summation. But, I have corrected the summation bounds so that $i = r', r'+1,\dots, \max\{a, r-1\}$. | |
| Jan 27, 2021 at 19:58 | history | edited | mgus | CC BY-SA 4.0 |
changed summation bounds to be more precise
|
| Jan 27, 2021 at 15:30 | comment | added | Max Alekseyev | Where the term $+\binom{a}{r}$ comes from? | |
| Jan 27, 2021 at 15:28 | comment | added | Max Alekseyev | Just a couple of cents: (i) "$\forall j\in A^c\cap S, j \in F_i \text{ for all } i\in A\cap S$" simply means that $$(A^c\cap S) \subseteq \bigcap\limits_{i\in A\cap S}F_i$$ (ii) we have $$\sum_{i=r'}^a{{a}\choose{i}}{{a}\choose{r-i}} = \frac{1}{2}\binom{2a}{r}.$$ | |
| Jan 26, 2021 at 18:50 | review | First posts | |||
| Jan 26, 2021 at 19:20 | |||||
| Jan 26, 2021 at 18:43 | history | asked | mgus | CC BY-SA 4.0 |