Combinatorics question

philipcross · **Joined:** Sat, 6 Oct 2007 21:09:26 UTC **Posts:** 1

How many different partitions of the set {1, 2, ..., n} are there for which each set in the partition only contains adjacent integers? For example, with n=4 we have 8 such partitions of the set {1 2 3 4}, namely;
1. (1) (2) (3) (4)
2. (1 2) (3) (4)
3. (1) (2 3) (4)
4. (1) (2) (3 4)
5. (1 2) (3 4)
6. (1 2 3) (4)
7. (1) (2 3 4)
8. (1 2 3 4).
I want to know the number of such partitions for any arbitrary n.

Matt · **Joined:** Wed, 1 Oct 2003 04:45:43 UTC **Posts:** 9642

For arbitrary n, the number of partitions is: $$\sum_{k=0}^{n-1}\binom{n-1}{k}=2^{n-1}$

S.O.S. Mathematics CyberBoard

Combinatorics question

Who is online