Not signed in

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

• Forgot your password?
• Apply for membership

1. • CommentRowNumber1.
   • CommentAuthorfastlane69
   • CommentTimeApr 17th 2016
   • (edited Apr 17th 2016)
   • PermaLink
   Author: fastlane69
   Format: MarkdownItexI 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

   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

2. • CommentRowNumber2.
   • CommentAuthorDavidRoberts
   • CommentTimeApr 18th 2016
   • (edited Apr 18th 2016)
   • PermaLink
   Author: DavidRoberts
   Format: MarkdownItexI recommend [[combinatorial species]], and the references there, as a first stop.

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

3. • CommentRowNumber3.
   • CommentAuthorfastlane69
   • CommentTimeApr 18th 2016
   • (edited Apr 18th 2016)
   • PermaLink
   Author: fastlane69
   Format: MarkdownItexI 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

   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

4. • CommentRowNumber4.
   • CommentAuthorTodd_Trimble
   • CommentTimeApr 18th 2016
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexI 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](http://www.lacim.uqam.ca/en/) are emblematic. If I find a little time, I might look at this and start a small nLab project.

   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.

5. • CommentRowNumber5.
   • CommentAuthorTodd_Trimble
   • CommentTimeApr 18th 2016
   • (edited Apr 18th 2016)
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexThere 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]].

   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.

6. • CommentRowNumber6.
   • CommentAuthorfastlane69
   • CommentTimeApr 18th 2016
   • PermaLink
   Author: fastlane69
   Format: MarkdownItexIt 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. Thanks for your advice on the Montreal School; I shall follow up on your leads right away.

   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.

   Thanks for your advice on the Montreal School; I shall follow up on your leads right away.

7. • CommentRowNumber7.
   • CommentAuthorTodd_Trimble
   • CommentTimeApr 20th 2016
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexWell, 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.

   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.

8. • CommentRowNumber8.
   • CommentAuthorDavidRoberts
   • CommentTimeApr 20th 2016
   • PermaLink
   Author: DavidRoberts
   Format: MarkdownItexRegarding "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/>.

   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/.