Was solving the GO 2019 pdf when I encountered this question asked in TIFR 2017. Although I have understood this question, I have one doubt-
It is mentioned in the question that for a 3-bit number, the ordering (000, 100, 101, 111, 110, 010, 011, 001) is one of the possible Gray codes.
Then, how many such orders are there for an n-bit number?
it sounds correct.
In this problem we have 2 constraints,
therefore here we have to find the number of circular permutations of grey codes possible using n-bit.
here the solution would be to generate a recurrence relation and then solve it to get the answer.
I further tried to reduce this to a graph theory problem-
I considered the cells as nodes drew an edge between the nodes if they were adjacent (i.e. differed by 1 bit). Then the problem basically reduced to finding the no. of cycles from the node representing cell (0,0) (say, the origin) that pass through each vertex exactly once, i.e. finding the no. of distinct directed Hamiltonian cycles.
Am I correct in proceeding as such? Further, is there any formula to find the no. of distinct directed Hamiltonian cycles for any arbitrary graph?
It will look like this and we have to find hamiltonian cycles possible right ?
assume $\rightarrow$ is bidirectional
like this right ?