What is the maximum number of indices one can create on a table with N columns?

Question

Say, I have a database table with $N$ columns. What is the (theoretical) maximum number of indices I can create on that table? For $N = 1,2,3$ it's easy enough to calculate the answer $(1, 4, 15)$, but is there any formula? Also, is there a "name" for this number?

Answer 1

I assume you mean the following: given $N$ columns, there are

• $N$ single columns, giving $N$ different indices
• $N(N-1)/2$ pairs of columns, and 2 ways to combine each pair, giving $N(N-1)$ different indices
• $\frac{N(N-1)(N-2)}{2 \cdot 3}$ triples of columns, and $3 \cdot 2$ ways to combine each triple, giving $N(N-1)(N-2)$ different indices

and so on. This number doesn't have a (well-known) name, but the sequence does have its own OEIS entry:

Eighteenth- and nineteenth-century combinatorialists call this the number of (nonnull) "variations" of n distinct objects, namely the number of permutations of nonempty subsets of {1,...,n}.

Various formulas are given to compute it, including a recurrence relation $a_n = n(a_{n-1} + 1)$ and the rather surprising $a_n = \lfloor{e \cdot n! - 1}\rfloor$.

One could argue that you can create more indices by taking into account that columns can be used in ascending and descending mode. For indices with more than one column, this even has an influence on which records are 'near' each other.