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)
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
Full version: pdf,
(Concerned with sequences
Received December 18 2006;
revised version received June 5 2007.
Published in Journal of Integer Sequences, June 5 2007.
Journal of Integer Sequences home page