Derangements on the \(n\)-cube (Q1801689): Difference between revisions

The \(2^ n\) vertices of the \(n\)-cube \(Q_ n\) are \(n\)-tuples of 0's and 1's. The vertices of a \(k\)-subcube \(G_ k\) have constant entries in \(n- k\) positions. A symmetry \(w\) of \(Q_ n\) fixes \(G_ k\) if the image of any vertex of \(G_ k\) is still a vertex of \(G_ k\). If \(w\) fixes no \(k\)-subcube then \(w\) is a \(k\)-derangement; otherwise \(w\) is a \(k\)- rearrangement. The authors establish a necessary and sufficient condition for a symmetry of \(Q_ n\) to have a fixed \(k\)-subcube. They also find a way to compute the generating function for the number of \(k\)- rearrangements on \(Q_ n\).