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

[Olivier Gerard]

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.

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