Take the set $\{a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8\}$.

We can partition according to rules.

  1. Every member in the partition has even number of elements.

  2. Every member in partition have to be consecutive.

For example partitions above are:

  1. $\{(a_1,a_2),(a_3,a_4,a_5,a_6,a_7,a_8)\}$.

  2. $\{(a_1,a_2),(a_3,a_4),(a_5,a_6,a_7,a_8)\}$.

  3. $\{(a_1,a_2),(a_3,a_4),(a_5,a_6),(a_7,a_8)\}$.

  4. $\{(a_1,a_2),(a_3,a_4,a_5,a_6),(a_7,a_8)\}$.

  5. $\{(a_1,a_2,a_3,a_4,a_5,a_6),(a_7,a_8)\}$.

  6. $\{(a_1,a_2,a_3,a_4),(a_5,a_6,a_7,a_8)\}$.

  7. $\{(a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8)\}$.

Essentially asking if we are given even number how many ways can write as sum of evens?

Here $2+6=2+2+4=2+2+2+2=2+4+2=6+2=4+2+2=4+4=8$.


In the example, imagine that there is a wall between $a_2$ and $a_3$, another between $a_4$ and $a_5$ and a third between $a_6$ and $a_7.$ Then you're just selecting which of the three walls to raise, so there are $2^3=8$ possibilities.

In you examples, $1$ corresponds to raising the first wall only, $3$ to raising all the walls, and $7$ to raising none of the walls. You have overlooked the partition $$(a_1,a_2,a_3,a_4)(a_5,a_6)(a_7,a_8.)$$


Think about partitioning this set as placing a wall between two elements. We can only place a wall after an element with an even index, i.e., after 2, 4, or 6, if we place a wall at all. The question then amounts to "how many subsets are there of the collection of possible walls $\{2,4,6\}$"? You might remember that there are $2^n$ subsets of any set with $n$ elements, so there are $8$ such partitions of $8$.

The only one you did not list was $\{(a_1,a_2,a_3,a_4),(a_5,a_6),(a_7,a_8)\}$.

In general, if instead of 8 elements you had $2k$, then there would be a possible wall for each even number less than $2k$, of which there are $k-1$. So there are $2^{(n/2)-1}$ such "partitions" of any even number.


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.