6
$\begingroup$

Here, $\min A$ and $\max A$ denote the minimum and maximum element respectively of the set $A$.

So I have to calculate how many subsets of S have min/max element $1$, how many subsets have min/max element $2$, ... all the way upto $n$? I am not being able to intuitively understand the problem.

I want to know if there is an elegant way to do this.

$\endgroup$
  • 1
    $\begingroup$ There are $2^{n-a}$ subsets whose minimal element is $a$ -- this is the number of subsets of $\{a+1,a+2,\ldots,n\}$. $\endgroup$ – Henning Makholm Jun 30 '16 at 16:43
  • $\begingroup$ But which term in the sum will correspond to $A=\varnothing$? $\endgroup$ – Henning Makholm Jun 30 '16 at 16:43
  • $\begingroup$ None. $\min$ and $\max$ are not defined in tihs case. $\endgroup$ – Daniel Jun 30 '16 at 16:46
  • $\begingroup$ @HenningMakholm I'm afraid you have to break it down for me. $\endgroup$ – StubbornAtom Jun 30 '16 at 16:49
  • $\begingroup$ For each $A$, let $\tilde{A}$ denote $n+1-A=\left\{n+1-a\,|\,a\in A\right\}$. Then, $\max(A)=n+1-\min\left(\tilde{A}\right)$. If you know $\sum\limits_{\substack{{A\subseteq S}\\{A\neq \emptyset}}}\,\max(A)$, then $$\sum_{\substack{{A\subseteq S}\\{A\neq \emptyset}}}\,\min(A)=(n+1)\left(2^n-1\right)-\sum_{\substack{{A\subseteq S}\\{A\neq \emptyset}}}\,\max(A)\,.$$ $\endgroup$ – Batominovski Jul 1 '16 at 11:09
1
$\begingroup$

You can work recursively. For the minimum: Denote the sum of the minimums with $m_n$ $$m_n:=\sum_{A\subset S_n}\min A$$ where $S_n=\{1,2,\dots,n\}$. Hence $S_n$ has $2^n$ subsets. Now consider the set $S_{n+1}=\{1,2,\dots,n,n+1\}$. The set $S_{n+1}$ has $2^{n+1}=2^n+2^n$ sets. The first $2^n$ sets are exactly the subsets of $S_n$ and the other $2^n$ are exactly the sets of $S_n$ with additionally the element $n+1$. So, the sum of the minimum of the first $2^n$ sets is again $m_n$ and the sum of the second $2^n$ is $m_n+(n+1)$ since $n+1$ is the minimum only of the set $\emptyset \cup \{n+1\}=\{n+1\}$. This gives you the recurrence relation $$m_{n+1}=2m_n+n+1$$ for $n\ge 1$, with $m_0=0$. Similarly, for the maximum you obtain the relation $$M_{n+1}=M_n+2^n(n+1)$$ for $n\ge 1$ with $M_0=0$.


To solve the recurrence relations, note that both are of the form $g_{n}=c\cdot g_{n-1}+f(n)$, for $n\ge 1$ with $g(0)=0$ (in the second case $c=1$ which makes things even simpler). For a general solution, rewrite this as $$\frac1{c^n}g_n=\frac{c}{c^n}g_{n-1}+\frac{f(n)}{c^n}\implies x_n=x_{n-1}+t(n)$$ with $x_n:=\dfrac{g_n}{c^n}$ and $t(n):=\dfrac{f(n)}{c^n}$. Hence, repeated substitution leads to $$x_n=x_{n-1}+t(n)=x_{n-2}+t(n-1)+t(n)=\cdots=x_0+\sum_{k=1}^nt(k)$$ Since in both cases the initial condition is $g_0=0$ you get here $$x_n=\sum_{k=1}^nt(k)\implies g_n=c^n\sum_{k=1}^nt(k)$$ or explicitly

  1. For the $\min$ $($ here $c=2, f(n)=n)$: $$m_n=2^n\sum_{k=1}^n\frac{k}{2^k}=\dots=2^{n+1}-n-2$$

  2. For the $\max$ $($ here $c=1, f(n)=2^{n-1}n)$: $$M_n=\sum_{k=1}^n2^{k-1}k=\dots=2^{n}(n-1)+1$$

$\endgroup$
2
$\begingroup$

Note. I assume that $m(\emptyset)=0$.

Question. Consider the set $S=\{1,2,3,\dots,j\}$. Let $m(A)$ denote a maximum element of a subset $A$ of $S$. Prove that $$\sum_{A\subseteq S}m(A) = (j-1)2^j+1$$ where summation ranges over all subsets $A$ of $S$.

Solution. Let us consider the element $4$. $4$ will be maximum element if we pick elements from the set $\{1,2,3,4\}$. So basically we want to count number of subsets of the set $\{1,2,3,4\}$ which contain the element $4$. This is the same as counting the number of subsets of $\{1,2,3\}$ and for each subset of $\{1,2,3\}$ we append the element $4$ to it. There are $2^3$ subsets of $\{1,2,3\}$, namely \begin{align*} \binom30 &= \{\emptyset\} \to \{4\}=\{4\}\\ \binom31 &= \{\{1\},\{2\},\{3\}\} \to \{4\}=\{\{1,4\},\{2,4\},\{3,4\}\}\\ \binom32 &= \{\{1,2\},\{1,3\},\{2,3\}\} \to \{4\}=\{\{1,2,4\},\{1,3,4\},\{2,3,4\}\}\\ \binom33 &= \{1,2,3\} \to 4=\{1,2,3,4\} \end{align*} So this gives us a one-one correspondence between the subsets of $\{1,2,3,4\}$ containing $4$ and the subset of $\{1,2,3\}$. So in general the subset of $\{1,2,3,\dots,j\}$ containing $j$ is in one-one correspondence between the subsets of $\{1,2,3,\dots,(j-1)\}$. Therefore the sum $$\sum_{A\subseteq S}m(A) = \sum_{i=1}^j i \cdot 2^{i-1}= (j-1)2^j+1.$$ Note $1\cdot1+2\cdot2+3\cdot2^3+4\cdot2^3+\dots+n\cdot2^{n-1}= \frac{d}{dx} (x+x^2+x^3+\dots+x^n)_{x=2}$

$\endgroup$
  • 1
    $\begingroup$ Even if you are "too bored to tex", I think that mentioning the source of the image would be a useful information (and it would not require too much effort on your side). I suppose it is taken from some book. $\endgroup$ – Martin Sleziak Jul 1 '16 at 6:10
  • 1
    $\begingroup$ @MartinSleziak This is not taken from a book. The same question was asked in a entrance exam couple of years ago. I tried solving it and sent the .pdf file to friends to share. Unfortunately I don't have the .tex file of that. I already told, in the beginning that I solved it. Why should I mention the source?? $\endgroup$ – crskhr Jul 1 '16 at 6:25
  • $\begingroup$ @sc By source I meant the book from which the screenshot was taken. Now that you clarified that it is screenshot from the pdf you created and not from a book, this is no longer relevant. (And probably the page number should help me to guess that it is not from a book, if I had looked carefully enough. However, it seemed to me very likely that if this was from your own notes, you would have TeX-source, that's why asked.) In any case, since the screenshot looked like something from the book, it shows that you have TeX-ed it very nicely. $\endgroup$ – Martin Sleziak Jul 1 '16 at 6:32
  • $\begingroup$ @MartinSleziak No problem. IF I had the TeX source I wouldn't be lazy to copy paste it here ;) $\endgroup$ – crskhr Jul 1 '16 at 6:35
  • $\begingroup$ I have noticed that somebody downvoted your post - I am not sure whether the downvoter did this because of the picture instead of text or whether they had other reasons. In any case, I tried to edit the post based on your screenshot. It's up to you whether you will edit the text further. $\endgroup$ – Martin Sleziak Jul 1 '16 at 8:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.