partitioning numbers from 1 to n in 4 non-empty subsets so no subset has 2 consecutive numbers.

Question

Attempt: We have to find the number of ways to partition the numbers 1 to n into four non-empty subsets so that none of them are empty. let $f(n)$ be the way to do that and let $f'(n)$ be the way to partition into 3 none-empty subsets so that none of them contains consecutive integers.

first off we know $f(4)=1,f'(3)=1$

Recursive relations:

$f(n)=3f(n-1)+f'(n-1)$

$f'(n)=2f'(n-1)+1$

The second relation is well-known and tabulating some values we find it is $2^{n-2}-1$ for $n\geq3$. Using this we rewrite the first recursion as:

$f(n)=3f(n-1)+2^{n-3}-1$

but here I am stuck.

Answer 1

It appears that what you have is Stirling numbers of the second kind $S(n,3)$.

Answer 2

I just realized this function was not-well defined and that the eqivalence is between $4rp(n)$ and $S(n-1,3)$. I will be fixing it briefly