The Sequence Reconstruction of Permutations under Hamming Metric with Small Errors
The sequence reconstruction problem asks for the recovery of a sequence from multiple noisy copies, where each copy may contain up to errors. In the case of permutations on letters under the Hamming metric, this problem is closely related to the parameter , the maximum intersection size of two Hamming balls of radius . While previous work has resolved for small radii () and established asymptotic bounds for larger , we present new exact formulas for using group action techniques. In addition, we develop a formula for based on the irreducible characters of the symmetric group , along with an algorithm that enables computation of for larger parameters, including cases such as and .