Given a set $A$ which contains $n$ elements. For any two distinct subsets $A_{1}$, $A_{2}$ of the given set $A$, we fix the number of elements of $A_1 \cap A_2$. Find the sum of all the numbers obtained in the described way.
Problem
Source:
Tags: combinatorics
01.04.2017 19:03
Are there any empty subsets?
02.04.2017 00:57
if they will be empty the number of same elements will be 0 so the sum will be 0 so you can just exclude it.
02.04.2017 22:21
Can someone solve it please
03.04.2017 03:46
03.04.2017 03:55
by induction we'll have $a_{n+1}=4a_n+2^{n-1}(2^n+n-1)\cdots $
03.04.2017 04:40
shinichiman wrote:
i think if i am not mistaken you have overestimated the number of pair of subsets that have $i$ shared elements : for example take the set as $\{ 1,2,3,4,5,6\}$ you have count for instance $\{1,2\}\cup \{ 3,4,5\}$ and $\{1,2\}\cup \{ 6,5\}$ as subsets having $i$ shared elements ! RH HAS
03.04.2017 05:20
PROF65 wrote: i think if i am not mistaken you have overestimated the number of pair of subsets that have $i$ shared elements : for example take the set as $\{ 1,2,3,4,5,6\}$ you have count for instance $\{1,2\}\cup \{ 3,4,5\}$ and $\{1,2\}\cup \{ 6,5\}$ as subsets having $i$ shared elements ! RH HAS Thanks. I edited my solution. Hope I didn't make any other mistake.
01.01.2021 14:57