Enumeration of Colored Tilings on Graphs via Generating Functions

In this paper, we study the problem of partitioning a graph into connected and colored components called blocks. Using bivariate generating functions and combinatorial techniques, we determine the expected number of blocks when the vertices of a graph G , for G in certain families of graphs, are colored uniformly and independently. Special emphasis is placed on graphs of the form G × P n , where P n is the path graph on n vertices. This case serves as a generalization of the problem of enumerating the number of tilings of an m × n grid using colored polyominoes.