2
$\begingroup$

Let's say we want to enumerate maps $f$ between two finite sets $X$ and $Y$ modulo the action of groups $G$ on $X$ and $H$ on $Y$. Additionally we want $f$ to satisfy a certain property $P$ that is invariant with respect to both actions.

Without the property restriction, the problem is solved with generalized PET (De Bruijn theorem or the Power Group Enumeration theorem). Without the actions, the problem is often approachable with the inclusion-exclusion principle. However, I'm puzzled with how to do both at the same time.


Example. For integers $m>n>0$, let $X = \{1, 2, \dots, 2n\}$ with $G = L\times R$, where $L$ and $R$ are some subgroups of $S_n$ independently acting on the numbers $\leq n$ and on the numbers $>n$ in $X$, respectively, and let $Y=\{1,2,\dots,m\}$ with $H=S_m$ shuffling the whole $Y$. Then let $P$ be the property that $f(1), f(2), \dots, f(n)$ are pairwise distinct.

Here I think I can enumerate $f$'s in some easy cases like $L=R=S_n$, but not in general.

$\endgroup$

0

You must log in to answer this question.

Browse other questions tagged .