2
$\begingroup$

I need to find the count of all possible combinations of length $K$ for a given string $N$. The characters cannot repeat.

For example, if the given string is $$a,b,c,d,\quad N=4$$

The possible number of combinations of length $K=2$ will be $12$: $$ ab,ac,ad,bc,bd,cd,ba,ca,cb,da,dc,db $$

The possible number of combinations of length $K=3$ will be $24$: $$ abc,abd,acb,acd,adb,adc,bac,bad,bcd,bca,bda,bdc,cab,cad,cba,cbd,cda,cdb,dab,dac,dba,dbc,dca,dcb $$

Is the formula $\dfrac{N!}{(N-K)!}$ correct?

$\endgroup$

2 Answers 2

1
$\begingroup$

Your formula is correct, and here is why:

There are $\displaystyle{N \choose K} = \frac{N!}{(N-K)!K!}$ ways to pick a set of $K$ non-repeating characters out of $N$ characters.

Also, once you have those $K$ different characters picked, you can order them in $K!$ ways.

So, there are

$$\frac{N!}{(N-K)!K!} \cdot K! = \frac{N!}{(N-K)!}$$

possible strings of $K$ different characters chosen from a group of $N$ characters.

$\endgroup$
1
$\begingroup$

Your result is correct. The number is $$ \frac{N!}{(N-K)!}. $$

Indeed there are $N $ ways to choose the first letter, $N-1$ to choose the second one and so on until $N-K+1$ ways to choose the $K $-th letter. Multiplication of these numbers gives the result.

For more information see this wikipedia page:

https://en.m.wikipedia.org/wiki/Permutation#k-permutations_of_n

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