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 × Pn, where Pn 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.