Journal of Integer Sequences, Vol. 10 (2007), Article 07.5.8

Enumeration of Factorizable Multi-Dimensional Permutations

Hao Zhang and Daniel Gildea
Department of Computer Science
University of Rochester
Rochester, NY 14627


A d-dimensional permutation is a sequence of d+1 permutations with the leading element being the identity permutation. It can be viewed as an alignment structure across d+1 sequences, or visualized as the result of permuting $n$ hypercubes of (d+1) dimensions. We study the hierarchical decomposition of d-dimensional permutations. We show that when d >= 2, the ratio between non-decomposable or simple d-permutations and all d-permutations approaches 1. We also prove that the growth rate of the number of d-permutations that can be factorized into k-ary branching trees approaches (k/e)d as k grows.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A006318 and A111111 .)

Received December 18 2006; revised version received June 5 2007. Published in Journal of Integer Sequences, June 5 2007.

Return to Journal of Integer Sequences home page