# What number of colorings can guarantee that for every k-element subset there exists a coloring assigns different colors for elements from this subset?

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 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.
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)$$.
$$\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" and there is a large literature making sharper bounds for particular families of parameters. Here is a large table of known parameters of realizable perfect hash families maintained by Ryan Dougherty.