@RichardStanley I don't just want to compute these numbers, I'm interested in this alghorithm (and thus this counting problem) specifically. Showing that this is exponential is more usefull for me than giving an other algorithm that is quadratic (like computing the Möbius function).

@darijgrinberg No, I'm asking about (set theoretically) distinct upper sets. There is no reasoning with isomorphy here. This makes it of course even worse than if I was asking about non-isomorphic upper sets. But I am not asking about all of them. A lot of upper sets will never be reached by this recursion. The difficulty is counting the ones we do reach, not how many we have in total (which is of course O(2^n))

@JairTaylor Thanks for the tip!