0
$\begingroup$

I have been asked to count the number of subsets of $\{1,...,n\}$ whose maximal element is $t$ for some $1 \leq t \leq n$.

I said the following:

The size of a subset whose maximal element is $1 \leq t \leq n$ can be of sizes $1,2,...,t$. The element $t$ must be in the subset, and if the subset is of size $k$ then there are $\binom{t-1}{k-1}$ ways to choose the other elements. Therefore, the answer is: $\sum_{k=0}^{t-1} \binom{t-1}{k}$, which according to the binomial coefficient theorem is equal to $2^{t-1}$.

However, I'd like to verify my above answer.

Furthermore, I am interested in computing the below sum, which is related, but I can not find a closed form. How do I go about this?

$\sum_{t=1}^{n} t \cdot 2^{t-1}$

$\endgroup$
  • 1
    $\begingroup$ As a hint $\sum_{t=1}^{n} t \cdot 2^{t-1}$ is derivated from $\sum_{t=1}^{n} 2^{t}$, so if you could possibly find the main function, the answer will be provided but I don't know how. $\endgroup$ – Mehrdad Zandigohar Jan 29 '18 at 17:09
2
$\begingroup$

Another way to see the closed-form value of the sum you ask about at the end: Define $f(a) = \sum_{t = 1}^n t a^{t-1}.$ Then $$ f(a) = \frac{d}{da} \left[ \sum_{t = 1}^n a^t \right] = \frac{d}{da} \left[ \frac{a^{n+1} - a}{a - 1}\right] = \frac{[(n+1)a^{n} - 1](a-1) - (a^{n+1} - a)}{(a-1)^2} $$ and the sum you want is $f(2) = ((n+1) 2^n- 1) - (2^{n+1} - 2) = (n-1)2^n + 1.$

$\endgroup$
1
$\begingroup$

It's just equal to the number of subsets of $\{1,\ldots,t{-}1\}$ (that accompany the required element $t$)

That is, $2^{t-1}$, as you have found.

Your closed form is $(n-1)*2^n + 1$, as OEIS A000337 will quickly tell you, and can be shown by induction fairly easily.

$\endgroup$
  • $\begingroup$ Assume I do not have access to OEIS. How would I calculate the sum manually? $\endgroup$ – TheNotMe Jan 29 '18 at 17:00
  • $\begingroup$ Not sure I understand - calculating the sum manually for small numbers is not too hard. Are you asking how to arrive at the formula given? That kind of creativity is hard to give simple answers to. $\endgroup$ – Joffan Jan 29 '18 at 17:07
  • $\begingroup$ For this specific sum I meant... $\endgroup$ – TheNotMe Jan 29 '18 at 18:59
0
$\begingroup$

By taking the conditions into account, you should pick elements from this set: $\{1,...,t-1\}$

Each element of the set can be or not be in the subset, so there are 2 ways for each.

You have $t-1$ elements and each has $2$ ways, so the answer is like:

$2*2*...*2=2^{t-1}$

$\endgroup$

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.