Definition. Let S be a finite set of cardinality N, σ = (σ1,...,σN) a permutation of the elements of S and X a subset of S. We say the σ prefix-covers (or simply covers) X if X is one of Ø, {σ1}, {σ1,σ2}, ... , {σ1,...,σM}.
For instance, if S = {a,b,c,d} and σ = (b,d,a,c), the following subsets of S are covered by σ: Ø, {b}, {b,d}, {a,b,d}, {a,b,c,d} = S.
In the following we use the notation C(a,b) for the binomial coefficient a choose b.
Theorem. C(N,floor(N/2)) is the minimum number of distinct permutations of S jointly covering all the subsets of S.
Proof. Let P be the power set of S partially ordered by inclusion. The sets covered by a permutation of S form a maximal chain of P, and this correspondence between permutations and maximal chains is clearly one-to-one. So, the minimum number of permutations of S required to cover S is the same as the minimum number of chains partitioning P. By Dilworth's Theorem, this number is equal to the partial order width of P, that Sperner's Theorem shows to be C(N,floor(N/2)).
The first values of C(n,floor(n/2)) are: 1, 1, 2, 3, 6, 10, 20, 35, 70, 126... The following table shows some possible permutation covers for |S| = 1,...,5.
| S | permutation cover |
| {a} | (a) |
| {a,b} | (ab), (ba) |
| {a,b,c} | (abc), (bca), (cab) |
| {a,b,c,d} | (abcd), (acbd), (bcda), (bdac), (cdab), (dabc) |
| {a,b,c,d,e} | (abcde), (bcdea), (cdeab), (deabc), (eabcd), (acdbe), (adbce), (bdeac), (becad), (ceabd) |
The proof of the theorem does not provide an efficient algorithm to construct a permutation cover. Finding such an algorithm is an interesting problem that we will address in a later entry.
No comments :
Post a Comment