1
$\begingroup$

I filled in from the definition of a Stirling number of the second kind that the following holds. $${2n\brace 2} = \frac{1}{2} \sum_{i=0}^{2} (-1)^i \binom{2}{i} (2-i)^{2n}$$

And I've visually confirmed in Desmos that the following equality 'appears' to hold.

$${2n\brace 2} = 2^{2n-1}-1$$

How do I prove that this equality does in fact hold?

$\endgroup$
1
  • 1
    $\begingroup$ Hint, instead of using any formulas, ask yourself the question what $S(2n,2)$ means from a counting point of view. It is the number of ways to do what? Then find another way to count the same thing and you will immediately get the answer for $S(2n,2)$. $\endgroup$ Oct 1, 2021 at 5:07

2 Answers 2

4
$\begingroup$

I guess the most straight-forward way is to expand the summation:
\begin{align} {2n\brace 2} = &\frac{1}{2} \sum_{i=0}^{2} (-1)^i \binom{2}{i} (2-i)^{2n} = \\ & \frac{1}{2} \Bigg( \Big[(-1)^0 \binom{2}{0} (2-0)^{2n}\Big] + \Big[(-1)^1 \binom{2}{1} (2-1)^{2n}\Big] + \Big[(-1)^2 \binom{2}{2} (2-2)^{2n}\Big] \Bigg) = \\ &\frac{1}{2} \Bigg( \Big[1 \cdot 1 \cdot 2^{2n}\Big] + \Big[(-1) \cdot 2 \cdot 1^{2n}\Big] + \Big[1 \cdot 1 \cdot 0^{2n}\Big] \Bigg) = \\ &\frac{1}{2} \Bigg( 2^{2n} - 2 + 0 \Bigg) = \\ & \frac{2}{2} \Bigg( 2^{2n-1} - 1 \Bigg) = 2^{2n-1} - 1 \end{align}

$\endgroup$
2
$\begingroup$

The definition of ${2n \brace 2}$ is dividing set $A= \{ a_1,...,a_{2n} \}$ into two sets which is not an empty set.

First, lets say that we are dividing set A to set B and set C. For an integer $i$ such that $1 \le i \le 2n$,

$a_i \in B$ or $a_i \in C$, which means for every $i$, there are 2 cases.

Considering that B and C shouldn't be an empty set,

Dividing set A into set B and set C has $2^{2n}-2$ cases.

So, there are $2^{2n-1}-1$ cases.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .