Bootstrap percolation, indecomposable permutations, and the n-kings problem

We study the process of bootstrap percolation on n n permutation matrices, inspired by Shapiro and Stephens' article (SS): "Bootstrap percolation, the Schrder numbers, and the n-kings problem" (1991).In this percolation model, cells mutate (from 0 to 1) if at least two of their cardinal neighbors contain a 1, and thereafter remain unchanged; the process continues until no further mutations are possible.After carefully analyzing this process, we consider how it interacts with the notion of (in)decomposable permutations.We prove that the number of indecomposable permutations whose matrices "fill up" to contain all 1's (or are "full") is half of the total number of full permutations.This leads to a new proof of a key result in (SS), that the number of full n n permutations is the (n -1) st large Schrder number.Finally, after rigorously justifying a heuristic argument in (SS), we find a new formula for the number of n n "no growth" permutation matrices, and hence a new solution to the well-known n-kings problem.