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$.


2 Answers 2


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.


You must log in to answer this question.

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