Content deleted Content added
Line 16:
A main problem in permutation codes is to determine the value of <math>M(n,d)</math>, where <math>M(n,d)</math> is defined to be the maximum number of codewords in such a code. There has been little progress made for <math>4 \leq d \leq n-1</math>, except for small lengths. We can define <math>D(n,k)</math> with <math>k \in \{0, 1, ..., n\}</math> to denote the set of all permutations in <math>S_n</math> which have exactly <math>k</math> distance from the identity.
<math>D(n,k)= \{ \sigma \in S_n: d_H (\sigma, id)=k\}</math> with <math>|D(n,k)|=\tbinom{n
The [[Gilbert–Varshamov bound|Gilbert-Varshamov bound]] is a very well known upper bound <ref name=":0">{{Cite journal |last=Gao |first=Fei |last2=Yang |first2=Yiting |last3=Ge |first3=Gennian |date=2013-05 |title=An Improvement on the Gilbert–Varshamov Bound for Permutation Codes |url=http://dx.doi.org/10.1109/tit.2013.2237945 |journal=IEEE Transactions on Information Theory |volume=59 |issue=5 |pages=3059–3063 |doi=10.1109/tit.2013.2237945 |issn=0018-9448}}</ref>, and so far outperforms other bounds for small values of <math>d</math>.
'''Theorem 1''': <math>\frac{n!}{\sum _{k=0} ^{d-1} |D(n,k)|} \leq M(n,d) \leq \frac{n!}{\sum _{k=0} ^{[\frac{d-1}{2}]} |D(n,k)|}
</math>
'''Theorem 2''': If <math>k^2 \leq n \leq k^2+k-2</math> for some integer <math>k \geq 2</math>, then
Line 29:
<math>\frac{n!}{M(n,4)} \geq 1 + \frac{(n+1)n(n-1)}{n(n-1)-(n-k^2)((k+1)^2-n)((k+2)(k-1)-n)}</math>.
For small values of <math>n</math> and <math>d</math>, researchers have developed various computer searching strategies to directly look for permutation codes with some prescribed [[Automorphism|automorphisms
==References==<!-- Inline citations added to your article will automatically display here. See en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->▼
▲<!-- Inline citations added to your article will automatically display here. See en.wikipedia.org/wiki/WP:REFB for instructions on how to add citations. -->
{{reflist}}
|