Consider two countable families of objects, given as unions of finite subfamilies:


$F^k = \bigcup\_{n \in \mathbb{N}} F^k\_n$, *k* = 1,2.


Let there be a bijection $f: F^1 \rightarrow F^2$ such that $x \in F^1\_n \Leftrightarrow f(x) \in F^2\_n$ for all *n* $\in \mathbb{N}$.


This means: The two families have the same counting functions $f^1(n) = f^2(n)$ for all *n* $\in \mathbb{N}$ with $f^k(n) = |F^k\_n|$.


This may be *by sheer accident*, or it may be because the two families are in some sense *essentially the same*.



> 
> Can the notions of "by accident" and
>  "essentially the same" be distinguished in this context, and how?
> 
> 
> 


"Essentially the same" might mean: "there is a *computable* bijection" and "by accident" might mean: "there is *no* computable bijection". Or might category theoretical notions lead further?



> 
> Are there known examples of two
>  families as above that have the same counting
>  functions by accident (in the meaning just mentioned or another one)?
> 
> 
> 


PS: More sensible tags are welcome!



Equivalence of families of objects with the same counting function
If you adopt Philippe Nadeau's proposal to define "essentially the same" in terms of isomorphism of species, then a standard example of "accidental" is the following. For any finite set $S$, there are just as many linear orderings of S as there are permutations of $S$ (i.e., bijections from $S$ to itself), namely $|S|!$. But the two species are not isomorphic. There is a distinguished permutation, namely the identity, but there is no distinguished linear ordering (provided $|S|>1$). 


Some people feel that these two are, nevertheless, in some sense the same. (In fact, some people indiscriminately use the word "permutation" for both.) That feeling can be formalized in the observation that, if you choose one linear ordering of $S$, then it determines a natural bijection between the linear orderings and the permutations: Given a permutation, apply it to the chosen linear ordering. So people who want to think of these two species as essentially the same would want a weakening of "isomorphism of species" that would allow this sort of "isomorphism modulo an arbitrary choice." Unfortunately, it's not clear how big an object could reasonably be arbitrarily chosen --- presumably not a whole isomorphism. So I don't see a good way to make this intuition precise; as a result, I'm inclined to stick with "isomorphism of species" and to accept that linear orderings and permutations are not essentially the same. 


