# Number of ways to split a list of elements, such that no sublist has more than 2 elements.

Let's say I have a list of 4 elements : [a,b,c,d]. There are 5 ways to split this list, with no rearranging such that no sublist has more than two elements:

[a,b,c,d],[ab,c,d],[ab,cd],[a,bc,d] and [a,b,cd].

In general, with n elements, how can one count the number of ways to split a list? This is quite similar to the stars and bars problem; however, we have distinguishable stars, but indistinguishable bins.

If $$f(n)$$ denotes the number of ways of such splittings of $$n$$ elements set, then note that given $$a_1,\ldots , a_n$$ in any splitting either $$a_1$$ is alone or is paired with $$a_2$$. In first case number of splittings of remaining $$n-1$$ terms will be $$f(n-1)$$ in second case number of splittings of remaining $$n-2$$ terms will be $$f(n-2)$$. Therefore $$f(n)=f(n-1)+f(n-2)$$ for $$n\geq 3$$ , $$f(1)=1$$, $$f(2)=2$$.