# How to count Isomorphism Types of arbitrary structures?

For all relational signatures $\sigma$ and nonnegative integers $n$, I want to count the number of isomorphism types of structures of order $n$ of the signature $\sigma$.

What I mean by structure is a pair $\mathfrak{A}=(A,( R(\mathfrak{A})_{R\in\sigma} ))$ for some relational signature $\sigma$ of predicates of arity $\geq 1$ and some finite set A. I think, I figured it out for the case when all predicates in $\sigma$ have arity $1$. Say, it is $\mathfrak{A}=(A, P_1(\mathfrak{A}),\ldots,P_m(\mathfrak{A}) )$ for some nonnegative integer $m$. Then each vertex is coloured in certain ways: It could be that it is in $P_1(\mathfrak{A}),P_2(\mathfrak{A})$ but not in $P_3(\mathfrak{A})$ (for $m=3$); so we can assign to each vertex a subset of all colours it possesses. Then two structures of this signature are isomorphic if and only if for each subset of $\sigma=\{P_1,\ldots,P_m\}$, there are exactly the same number of vertices coloured this way in both structures.

But there are exactly $2^m$ subsets of the above $\sigma$, and so what we look for is the number of all $2^m$-tuples $(a_1,\ldots,a_{2^m})$ s.t. $\sum_{i\in [1,2^m]}a_i = n$ where n is the order of structures we want to compute the number of isomorphism types for. Well and this is a simple combinatorial fact this number is equal to $\binom{n+2^m-1}{n}$.

I want to do the same thing without the restriction that $\sigma$ only contains predicates of arity $1$. I would be glad about ideas how to do this for structures of a signature with exactly one $r$-ary predicate for some arity $r\geq 2$, and also about ideas how to combine the numbers of isomorphism types of two such signatures (for some fixed $n$).

• You can do something similar with padding. A relation of arity k is just a subset of A^k. So you can pad a relation of smaller arity up to one of arity k by allowing the later places to range over all elements. Now you get a weak upper bound for an arbitrary signature, and a similar bound when all the relations have the same arity. Gerhard "Goes For Easy Cases First" Paseman, 2017.08.04. – Gerhard Paseman Aug 5 '17 at 0:14
• There is not going to be anything resembling a simple list of invariants, as in the unary case. You may be able to cook up something with the Pólya enumeration theorem. – Emil Jeřábek supports Monica Aug 5 '17 at 11:24
• So is giving lower and upper bounds all I can do here? Ok, this Polya enumeration theorem looks promising... – D. Rusin Aug 5 '17 at 15:52