Half-BPS and quarter-BPS operators in N=4 super Yang Mills theories with SO(N) gauge group are related to giant graviton branes in an orientifold of AdS5 times S5 string theory. The orientifold projection operation on the half-BPS operators can be calculated using domino tilings of Young diagrams. Through the AdS/CFT correspondence, this reveals a connection between domino combinatorics and branes in orientifolds of AdS5 times S5. The large N limit of counting functions for the quarter BPS operators in U(N) and SO(N) theories reveals a rich structure related to the combinatorics of words. The underlying perspective leading to these results is a permutation approach to gauge invariants, which has proved to be a surprisingly rich source of insights on AdS/CFT.