Given a set of free Polyominoes $\mathcal{P}$ (translation, flipping and rotating of pieces is allowed) and a test shape $S$ that is also a valid Polyomino, I am trying to find an algorithm $f(S, \mathcal{P}) : S \times \mathcal{P} \to (\mathcal{P}, \mathbb{N})$ that counts the number of times entries in $\mathcal{P}$ are used to generate every possible covering of $S$.
A simple example will clarify what I mean. Let
$$ \mathcal{P} = \left\{ a = \begin{pmatrix}⬛\end{pmatrix}, b = \begin{pmatrix}⬛\\⬛\end{pmatrix}, c = \begin{pmatrix}⬛&⬛\\⬛&\end{pmatrix}, d = \begin{pmatrix}⬛\\⬛\\⬛\\⬛\end{pmatrix} \right\}, $$
where I have labelled the individual Polyominoes for convenience.
For $S = \begin{pmatrix} ⬛&⬛\\ ⬛&⬛ \end{pmatrix} $, that is, the square Tetromino, there are four unique ways to cover $S$ using (possibly repeated) elements from $\mathcal{P}$: $\{ (a, a, a, a), (a, a, b), (b, b), (c, a)\}$. In this case, the algorithm $f(S, \mathcal{P})$ would output $\{a: 7, b: 3, c: 1, d: 0\}$. Note that in general, $S$ will not be rectangular, but any arbitrary Polyomino.
I don't care about efficiency, at the moment I'm simply seeking to define a general brute-force solution that will give the correct answer. My current approach is to treat this as a problem of finding collections of sub-graphs that collectively cover the graph of $S$, but ensuring I don't get duplicate coverings due to transformations of the elements of $\mathcal{P}$ seems like a tricky problem.
Does my specific problem have a name? Are there known solutions or bounds on the complexity?
After some more research, I've discovered that my problem is called the Multihedral Polyomino tiling problem, and after careful definition of the set $\mathcal{P}$ and shape $S$, can be formulated as a binary integer programming problem.
Burkardt, Garvie and Golomb provide a GPL licensed Matlab library that formulates and solves such problems!
Edit: If anyone else is curious, I've put together a Python package that wraps the Matlab library to make this easier to use :)