Let $M(n, k)$ be a minimal number $m$ such that there exists set $C$ ($|C|=m$) of colorings of n-element set $[n]$ with $k$ colors such that for every $k$-element subset $K$ of $[n]$ there exists coloring $c\in C$ such that $c$ assigns different colors for all elements of $K$.


* Is there any research about this object?
* Is there any closed-form formula for $M(n, k)$? May be for small $k$?


It's obvious that $M(n, 2)=\lceil\log\_2(n)\rceil$ (simple divide and conquer idea), but $M(n, 3)$ is not so obvious for me.



What number of colorings can guarantee that for every k-element subset there exists a coloring assigns different colors for elements from this subset?
These are known as *Perfect Hash Families*. The notation $PHF(N;n,v,k)$ denotes a set $\mathcal H$ (hash functions) with $|\mathcal H|=N$, of $v$-colorings of the base $[n]$, such that for any $X\subset [n]$ with $|X|=k$, there exists at least one hash function which assigns it different colors. Let's denote by $f(n,v,k)$ the smallest $N$ for which a $PHF(N;n,v,k)$ exists. In this notation, you are interested in $f(n,k,k)$.


M. L. Fredman and J. Komlós prove in the paper ["On the Size of Separating Systems and Families of Perfect Hash Functions"](https://epubs.siam.org/doi/10.1137/0605009) the following bounds:


$$\frac{v^{k-1}}{(v)\_{k-1}}\cdot\frac{\log n}{\log(v-k+2)}\le f(n,v,k)\le \frac{k\log n}{\log\left(1-\frac{(v)\_k}{v^k}\right)}$$
where $(v)\_k=v(v-1)\cdots (v-k+1)$ is the falling factorial. This bound was improved by J. Körner and K. Marton in ["New Bounds for Perfect Hashing via Information Theory"](https://www.sciencedirect.com/science/article/pii/S0195669888800489) and there is a large literature making sharper bounds for particular families of parameters. [Here](http://www.public.asu.edu/~redoughe/phf_pages/phf_tables.html) is a large table of known parameters of realizable perfect hash families maintained by Ryan Dougherty.


