Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

Discussion Tag Cloud

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

• CommentRowNumber1.
• CommentAuthorfastlane69
• CommentTimeApr 17th 2016
• (edited Apr 17th 2016)

I recently came across this concept yet have not seen a CT treatment of it. Its clearly set based but the “up to a permutation”, i.e. up to an isomorphism, caught my categorical eye. At worst, it seems like a good sandbox to develop a set intuition, IMO the first rung needed to climb the CT ladder. At best, I don’t know.

Any guidance on this topic and how it fits into CT would be most welcome.

“In combinatorics, the twelvefold way is a name given to a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a set or of a number. “

https://en.wikipedia.org/wiki/Twelvefold_way

• CommentRowNumber2.
• CommentAuthorDavidRoberts
• CommentTimeApr 18th 2016
• (edited Apr 18th 2016)

I recommend combinatorial species, and the references there, as a first stop.

• CommentRowNumber3.
• CommentAuthorfastlane69
• CommentTimeApr 18th 2016
• (edited Apr 18th 2016)

I could not find or deduce a “systematic classification of 12 related enumerative problems concerning two finite sets” in that link or the related Schur functors.

Further, I’ve read Awoldy, Mac Lane, Lawvere and more and maybe I’m missing it but AFAIK, none of those books explicitly state the above or the below, both which seems to me an important points to be made explicitly about small categories.

I fully admit to being new to CT and thus maybe not seeing the obvious, but I am not seeing any OVERT evidence of this in the literature.

“There are four different equivalence relations which may be defined on the set of functions f from N to X:

equality;

equality up to a permutation of N;

equality up to a permutation of X;

equality up to permutations of N and X.”

https://en.wikipedia.org/wiki/Twelvefold_way

• CommentRowNumber4.
• CommentAuthorTodd_Trimble
• CommentTimeApr 18th 2016

I think David Roberts was suggesting that methods of combinatorial (Joyal) species are relevant, rather than saying we have anything explicitly about this set of problems on an nLab page.

Of course you’re not going to find anything in Awodey, Mac Lane, etc., but you might have more success looking more at literature coming out of the “Montréal school” comprising researchers such as Gilbert Labelle, Pierre Leroux, François Bergeron, and of course André Joyal. Publications coming out of LACIM are emblematic.

If I find a little time, I might look at this and start a small nLab project.

• CommentRowNumber5.
• CommentAuthorTodd_Trimble
• CommentTimeApr 18th 2016
• (edited Apr 18th 2016)

There are snippets of relevant concepts on some nLab pages, for example binomial theorem and falling factorial. If there isn’t an nLab page that describes the famous formulas relating Stirling numbers to surjections, then there ought to be.

Added: Oh, there is this: bijective proof.

• CommentRowNumber6.
• CommentAuthorfastlane69
• CommentTimeApr 18th 2016

It stands to reason that one would find all these concepts piecemeal. But in your opinion, is there a benefit to organizing these problems as a set of 12? If they are systematic and cover all possible combinatoric operations between two finite sets (up to an isomorphism), then I would think so.

Maybe this not n-POV enough to get its own page…

… but as a way to exhaust the ways that two finite sets combines (IF in fact twelve does exhaust all combinatoric possibilities, which I do not know that it does) I’m curious to know how useful you think this “set of twelve” is.

• CommentRowNumber7.
• CommentAuthorTodd_Trimble
• CommentTimeApr 20th 2016

Well, it seems clear that this “twelvefold way” is not an unnatural thing to consider. If you have any category $C$ and objects $a, b$ and distinguished classes of morphisms in $\hom(a, b)$ definable in the language of category theory (e.g., monomorphisms, epimorphisms), then you can consider the actions of $Aut(a)$ or $Aut(b)$ or both on $\hom(a, b)$. If the categories involved are locally finite, then there is potential for interesting problems of enumerative combinatorics in connection with such actions.

Combinatorics is a pretty big field, and insofar as an “nPOV” may have something useful to say about techniques that crop up in this area, such things would be fair game for the nLab. Occasionally some combinatorial problems arise at the nLab; one simple case I recall is counting morphisms in hom-sets in the simplex category, using a “stars and bars” technique (among other things).

… but as a way to exhaust the ways that two finite sets combines (IF in fact twelve does exhaust all combinatoric possibilities, which I do not know that it does) I’m curious to know how useful you think this “set of twelve” is.

I think it’s a nice set of problems to consider together, especially in view of epi-mono factorizations of functions in the category of finite sets and the aforementioned actions. This leads to a number of interactions between binomial coefficients, falling powers, Stirling numbers, etc., and certainly there are nice stories that can be told.

But (even though I am not a professional combinatorialist) I wouldn’t consider this set of twelve problems “exhaustive” in any very significant sense.

• CommentRowNumber8.
• CommentAuthorDavidRoberts
• CommentTimeApr 20th 2016

Regarding “stars and bars”, which I’d never heard of until recently: https://blogs.adelaide.edu.au/maths-learning/2015/10/17/a-story-of-stars-and-bars/.