Big Theta for finding combinations of arbitrarily sized subsets from n total elements
If we denote by $q(n)$ the number of permutations, the first few values are
$$\begin{array}{ccccccccc}
n &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7\\
q(n) &amp; 1 &amp; 1 &amp; 3 &amp; 6 &amp; 14 &amp; 25 &amp; 56 &amp; 97
\end{array}$$
This sequence can be found at the online encyclopedia of integer sequences, which is a really helpful site. It has a lot of information about the sequence in question, including the fact that you were right in your guess that $q(n)=\Theta(3^{n/3})$.

[Yes, I'm aware that this doesn't answer all of your question, since this only counts how many permutations there are, and doesn't enumerate them.]