The size of a maximum agreement subtree of two phylogenetic trees is a statistic that is often used to test the null hypothesis that no cospeciation occurred between two families of species of interest. The size of the maximum agreement subtree can be computed in polynomial time but the distribution of this statistic is not fully understood. In a simple case the problem of finding a maximal agreement subtree simplifies to finding the longest increasing subsequence of a permutation and so understanding the distribution of the statistic in this case is equivalent to understanding the distribution of the longest increasing subsequence of a random permutation. I will present some famous combinatorial algorithms and identities that were used to approach the longest increasing subsequence problem and then introduce the new problem of finding the longest increasing subsequence of an ordered set partition. I will discuss some approaches to this problem and prove some identities that are analogous to those that appear in the standard longest increasing subsequence problem.