[seqfan] Re: Need help in understanding a combstruct specification in sequence A052886.

[Antti Karttunen]

On Mon, Jan 1, 2024 at 8:12 PM Olivier Gerard <olivier.gerard at gmail.com>
wrote:

> Dear Antti,
>
> It is not exactly what you asked (listing the production of the grammar by
> launching combstruct),
> but it is a decent replacement as I stopped using matlab.
>
> It is a pity I did not add a few comments to A052886 and A052895 many many
> years ago.
>
> One way to see A052886 is to start from ordered partitions of [n], better
> known as Fubini numbers, 1,3,13, 75,541,4683, ...
> You just add the possible parenthesizing grouping the subsets.  Here is a
> table decomposing A052886 by number of subsets
>
> 1
> 1 2
> 1 6 12
> 1 14 72 120
> 1 30 300 1200 1680
> 1 62 1080 7800 25200 30240
>
> and here is a table decomposing Fubini numbers by number of subsets
> A019538
> 1
> 1 2
> 1 6 6
> 1 14 36 24
> 1 30 150 240 120
> 1 62 540 1560 1800 720
>
>
>
> Illustration for n=3.
>
> There are 5 subset decompositions of  the set [3]  (Stirling numbers of the
> second kind)
>
> k=1
> {1,2,3}
>
> k=2
> {1} {2,3}
>
> {2} {1,3}
>
> {3} {1,2}
>
> k=3
> {1} {2} {3}
>
> There are 1*1 + 2 * 3 + 6 * 1 = 13 possible orderings of the subsets
> (Fubini numbers)
>
> {1,2,3}
>
> {1} {2,3}
> {2,3} {1}
> {2} {1,3}
> {1,3} {2}
> {3} {1,2}
> {1,2} {3}
>
> {1} {2} {3}
> {2} {1} {3}
> {3} {2} {1}
> {1} {3} {2}
> {2} {3} {1}
> {3} {1} {2}
>
> There are Catalan(k-1) parenthesizing for each ordered partition of k sets
> giving 1*1 + 1*6 + 2*6 = 19 cases.  (You also think of them of catalan
> trees of an ordered list of k subsets of the n first integers )
>
> ({1,2,3})
>
> ({1} {2,3})
> ({2,3} {1})
> ({2} {1,3})
> ({1,3} {2})
> ({3} {1,2})
> ({1,2} {3})
>
> (({1} {2}) {3})
> (({2} {1}) {3})
> (({3} {2}) {1})
> (({1} {3}) {2})
> (({2} {3}) {1})
> (({3} {1}) {2})
>
> ({1} ({2} {3})
> ({2} ({1} {3})
> ({3} ({2} {1})
> ({1} ({3} {2})
> ({2} ({3} {1})
> ({3} ({1} {2})
>
>
> Hope it helps.  It is just one out of many combinatorial interpretations of
> this sequence.
>
>
Thanks a lot, Olivier!

The above explanation made it clear to me that A277120, i.e., "Number of
branching factorizations of n", indeed gives A052886(n), when applied to a
product of n distinct primes. I hope you have time to add your explanation
to A052886 and A052895.

There is still an open question concerning A277120 (see the pending edits):
Does it obtain a unique value for each distinct prime signature?, which
question boils down to whether the sequences A366377 and A366884 (A277120
applied to representatives of prime signatures) are injective or not?
The problem could be also represented as a problem concerning partitions,
as each term in A025487 naturally maps to one.

Moreover, both A052886 and A366884 show an interesting distribution of the
last decimal digits. Apparently, no terms ending with 5's in the former,
while in the latter, there are a lots of them.

Sequence A277130 ("Number of planar branching factorizations of n") seems
to be in many respects similar to A277120. There the counterpart of A052886
is A319122 ("Number of phylogenetic plane trees on n labels").




Best regards,

Antti




> A052895 is just the same idea with say an empty set added systematically
> before parenthesizing at one end of the string of subsets.
>
> One should also add to the OEIS the grammar where one uses parentheses on
> the k subsets
> without creating all the permutations of the subsets.
>
> It starts
>
> 1
> 2
> 6
> 25
> 130
> 789
> 5390
> 40562
> 331460
> 2910903
>
> or decomposed by number of subsets, where extreme sides are 2^n -1 and
> Catalan
>
> 1
> 1 1
> 1 3 2
> 1 7 12 5
> 1 15 50 50 14
> 1 31 180 325 210 42
> 1 63 602 1750 1960 882 132
>
> I will probably do it tomorrow.
>
> Olivier
>
>
>
> On Mon, Jan 1, 2024 at 11:39 AM Antti Karttunen <antti.karttunen at gmail.com
> >
> wrote:
>
> > Dear SeqFans,
> >
> > I wonder whether anybody with Maple there could elaborate what kind of
> > combinatorial structures the following combstruct grammar:
> >   spec := [S, {C=Set(Z, 1 <= card), S=Prod(B, C), B=Sequence(S)},
> labeled]:
> > seq(combstruct[count](spec, size=n), n=0..20);
> > from https://oeis.org/A052886 produces?
> >
> > A quick starter to the library is here:
> >
> >
> https://www.maplesoft.com/support/help/Maple/view.aspx?path=combstruct%2fspecification
> >
> > If somebody could just list for me all structures of size 3 (there should
> > be 19 of them), it would help a lot. I tried to do this by emulating
> > combstruct library manually, but as the structure is labeled, I soon lost
> > the track, and I'm not sure how PROD actually works (it's not
> commutative,
> > right? Judging from examples in A000108). I used to know this stuff
> better
> > myself, but the years have gone by since then.
> >
> > BTW, there's a similar Haskell-library now:
> >
> >
> https://hackage.haskell.org/package/species-0.2/docs/Math-Combinatorics-Species.html
> >
> >
> > Best regards (and Happy New Year!),
> >
> > Antti
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>