If you look at the diagram on p. 173 for a 3-input decision tree, you'll notice that after the first comparison, the left and right of the tree are symmetrical, with a_1 replaced by a_2 in the right half. This should be true in the larger case as well.
So, instead of drawing 120 leaves, we're down to 60. That's still not very good. But at the next comparison, we again have a left and right half, and it should remain the case that the left and right are permutations of each other. So you can draw 30 leaves and be done. That's a much more reasonable amount of work, I think. If you're very careful, you can do this for part of a 3rd level, I believe.
Just be sure you're very clear about which subtree is permuted to where, and what the permutation is.