Bipartite representations of permutations are introduced, and the relation between the representations and the actions of permutation networks devised by Waksman et al is investigated. As an example of the application of the bipartite representations, a lucid algorithm for setting-up a permutation network to produce a given permutation is shown. An algorithm for counting the number of configurations of the network that produce a given permutation is derived. The computing time complexity of the algorithm by a random access machine is O (2N/2+O(log2N)).

Formal descriptions for constructing a Joel's permutation network are discussed. We show that a setting algorithm of the network can be described in terms of bipartite graphs. We then study a fast parallel algorithm for setting the network. We show that it can be implemented by a parallel computer with N processors in O((log2 N)2) time, where N is the size of permutations produced on the network.

In this paper we discuss some combinatorial problems related to the permutation network devised by Waksman et al. NUM(π) means the number of configurations of the permutation network producing a permutation π. The main result in this paper is that 23N-5-(log2N(log2N+1))/2 is a lower bound on the number of elements in the set {ππ is a permutation on {1, , N} and NUM(π)1}. This is a remarkable improvement on the previous best lower bound 22N-3+(log2N(log2N-3))/2 given by Opferman and Tsao-Wu.