I am looking for a formula to calculate the number or possible permutations when: a) repetition is not allowed and b) you don't have to pick all elements from the pool.
So I got n elements and I want to know how many combinations I can get when the position matters, I can't pick an element twice and I don't have to use all elements.
Thanks in advance!
On
The number of ways to pick $k\ge1$ elements is just $n(n-1)\cdots(n-k+1)=\dfrac{n!}{(n-k)!}$. This is because we have $n$ choices for the first element, $n-1$ choices for the second element, and so on and so forth.
Hence we have
$$\sum\limits_{k=1}^n\frac{n!}{(n-k)!}=n!\sum\limits_{k=1}^n\frac{1}{(n-k)!}=n!\sum\limits_{k=0}^{n-1}\frac{1}{k!}\approx e\cdot n!$$ possibilities.
Finally we should take into account the option of picking no elements - so we have an additional $1$ possibility.
In conclusion we have
$$1+n!\sum\limits_{k=0}^{n-1}\frac{1}{k!}=n!\sum\limits_{k=0}^{n}\frac{1}{k!}\approx e\cdot n!$$ possibilities.
If we are going to use $k$ elements, they can be chosen in $\binom{n}{k}$ ways, and lined up in $k!$ ways. That gives a number that simplifies to $\frac{n!}{(n-k)!}$. Add up from $k=0$ to $k=n$, if you will allow the "empty" string, or from $k=1$ to $n$ if you will not. (I like the empty string, it is unassuming.)
For attractiveness reverse the order of summation. We get $$n!\left(1+\frac{1}{1!}+\frac{1}{2!}+\cdots+\frac{1}{n!}\right)$$ if we allow the empty string. Otherwise we stop at the $\frac{1}{(n-1)!}$ term. I do not know of an exact "closed form" for this expression.