Derangements on the n-cube

Chen, W.Y.C. and R.P. Stanley, Derangements on the n-cube, Discrete Mathematics 115 (1993) 65-15. Let Q. be the n-dimensional cube represented by a graph whose vertices are sequences of O’s and l’s of length n, where two vertices are adjacent if and only if they differ only at one position. A k-dimensional subcube or a k-face of Q. is a subgraph of Q. spanned by all the vertices u1 u2 u, with constant entries on n-k positions. For a k-face Gx of Q. and a symmetry w of Q., we say that w fixes Gt if w induces a symmetry of Gt; in other words, the image of any vertex of G,, is still a vertex in Gk. A symmetry w of Q. is said to be a k-dimensional derangement if w does not fix any k-dimensional subcube of Q.; otherwise, w is said to be a k-dimensional rearrangement. In this paper, we find a necessary and sufficient condition for a symmetry of Q. to have a fixed kdimensional subcube. We find a way to compute the generating function for the number of k-dimensional rearrangements on Q.. This makes it possible to compute explicitly such generating functions for small k. Especially, for k =O, we have that there are 1.3 . (2n- 1) symmetries of Q. with at least one fixed vertex. A combinatorial proof of this formula is also given.