2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.