Statistical estimates of then-bit Gray codes by restricted random generation of permutations of 1 to2^n
Jerry Silverman, Virgil E. Vickers, John L. Sampson · IEEE Transactions on Information Theory · 1983
The number ofn-bit Gray codes is the number in a well-defined subset of the permutations of the integers1to2^{n}. Generating random permutations with associated estimates under suitably restrictive selection rules produces a discrete distribution whose expectation value is the number of such codes. The number of Hamiltonian circuits on then-cube (cyclic Gray codes) is a further subset which can readily be estimated also. Reliable statistical estimates up ton=6were produced with reasonable speed by computer implementation of this Monte Carlo process; excellent agreement with the exact values forn=4and5was obtained. Proofs are given of the validity of the technique and of an upper bound for the total number of Gray codes. The technique could also be used to count permutation subsets other than Gray codes.