Total number of unique permutations in a lexicographic set

Question

Given N digits that can form a set, how many total unique permutations of the set can be generated if we do not care about the order of the digits in the set? Specifically, I'd like to ask for assistance in deriving an equation if possible to derive the total number of permutations.

For example, N = 4 .. Total permutations = ( appears to be 15 ): 1, 1-2, 1-2-3, 1-2-3-4, 1-2-4, 1-3, 1-3-4, 1-4, 2, 2-3, 2-3-4, 2-4, 3, 3-4, 4

Also, N = 3 .. Total permutations = ( appears to be 7 ): 1, 1-2, 1-2-3, 1-3, 2, 2-3, 3

Thank you!

Answer 1

This answer is based off the examples you gave, which appear not to ask after permutations, but rather after after the number of ordered lists from a set of size $n$.

Let $[n]=\{1,2,\ldots,n\}$. Note that for each subset of $[n]$, there exists a unique ordering. The number of subsets of $[n]$ is just $2^n$. If you don't count the empty set, then you get $2^n-1$ ordered lists.

Answer 2

Count the permutations in order of size. For arbitrary $N$:
- There are $N \choose 1$ permutations of length 1
- For the permutations of length 2, we choose any 2 digits and put them in order, so there are $N \choose 2$ permutations.

In general there are $N\choose r$ permutations of length $r$.

Hence the total number of permutations is $\sum_{r=1}^{r=N} {N\choose r} = 2^N -1$.

Answer 3

Hint: Each digit can either be included or not. If you have those 2 possibilities for each digit, what will be the total number of possibilities? Remember to exclude the possibility where you exclude all the digits.

Answer 4

The value you want to determine is just the number of nonempty subsets of an $N$ element set; this value equals $2^N -1$.