Restricted growth strings

[Peter Luschny]

Time, I thought, to look at the second part of George's double
enumerations.
Set partitions are the theme.

So I started to translate George's Mathematica code to Maple,
a program I am more familiar with. The third line was: sn =
SetPartitions[n];

Surprise: there is no such function in Maple. The number of set
partitions are
given by combinat[bell](n). You can also specify a grammar spec :=
Set(Set(Z,card>=1))
and count([B,{B=spec},labelled],size=n) the generated universe;
however I did not
succeed to get the set partitions as a set or as an iteration
structure. Strange.

By the way, A000110 gives the Maple snippet

with(combstruct); spec := [S, {S=Set(U, card >= 1), U=Set(Z, card >=
1)},
labeled]; [seq(combstruct[count](spec, size=n), n=0..40)];

which does not give the correct value for n=0. It should be replaced
by

with(combstruct); seq(count([B,
{B=Set(Set(Z,card>=1))},labelled],size=n),n=0..40);

(Dear editors, what is the correct way to proceed in the case of
such an observation?)

OK, so let us implement the generation of sets. Open Knuth 7.2.1.5.
Don
recommends a generation scheme by George Hutchinson (1963). The
algorithm
goes by the name 'restricted growth strings'. This name is absent from
A000110.
However Bill Blewett and Neven Juric give examples under the name
'distinct rhyme
schemes'. A123895 gives the "Restricted growth string for the (decimal
expansion
of the) number n", whatever this is. Anyway, Google will not direct
someone
looking for restricted growth strings to A000110.

These are the 'restricted growth strings' corresponding to the
set partitions of 4.
{[0, 1, 0, 1], [0, 1, 0, 2], [0, 1, 1, 0], [0, 0, 1, 2],
[0, 1, 1, 2], [0, 1, 0, 0], [0, 1, 1, 1], [0, 1, 2, 2],
[0, 1, 2, 0], [0, 1, 2, 1], [0, 1, 2, 3], [0, 0, 0, 0],
[0, 0, 0, 1], [0, 0, 1, 1], [0, 0, 1, 0]}

iverson := b -> `if`(b,1,0):
RestrictedGrowthStrings := proc(n) # Algo H
local a, b, m, state, j, S;
a := array(1..n, [seq(0,i=1..n)]):
b := array(1..n-1,[seq(1,i=1..n-1)]):
m := 1: state := 3; S := {convert(a,list)};
while state > 0 do
if state = 3 then a[n] := a[n] + 1; state := `if`(a[n]=m,4,3);
elif state = 4 then state := 5; j := n-1; while a[j] = b[j] do j :=
j-1 od;
elif state = 5 then state := `if`(j=1,-1,6); if j > 1 then a[j] :=
a[j]+1 fi;
elif state = 6 then m := b[j] + iverson(a[j]=b[j]); j := j+1;
while j < n do a[j] := 0; b[j] := m; j := j+1
od; a[n] := 0;
state := `if`(a[n]=m,4,3);
else state := -1 fi;
S := S union {convert(a, list)};
od;
S end:

Test: S := RestrictedGrowthStrings(4);nops(S);

When I found out how to convert rg-strings to 'real' set partitions I
may
be able to proceed finally to a comment on George's double
enumerations.

Any ideas which matter computational?

Cheers Peter

[Peter Luschny]

Hmm, looking further into set partitions more strange things
show up. Let us say a set partition is a fundamental notion
in combinatorics (and it goes, as Knuth describes, under many
different names in all sorts of sciences and art, 'coalitions',
'cache-hit patterns', 'rhyme schemes', 'equivalence classes' etc.

So we can expect that the most elementary ways to count these
entities are in the OEIS? Sure... Well, if I am right, this is
not case.

First let us look up the definition as given by an authority.
These are the links from OEIS A000110:

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 15
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 65
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 73
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 291

For me these links are broken; at least they do not work as
intended. On the search page http://algo.inria.fr/ecs/?doc=1
we see:

ECSnumber =
searchType =
searchTerms =
nbResults =

Again things are broken for me: The ECSnumber does not work.
However this might work:

ECSnumber = 0
searchType = 1
searchTerms = ESCnumber
nbResults = 10

In our case the ESCnumber is one out of 15,65,73,291.
Even then the amount of information you see can depend on
the browser (or on the weather conditions?, I do not know).

Let's come back to more serious observations. With the
definitions of IAP (the approach taken goes back to the work of
Philippe Flajolet, http://algo.inria.fr/flajolet/ , we can
compute with Maple:

with(combstruct):
seq(count([B,{B=Set(Set(Z,card>=1))},labelled],size=n),n=1..9);

1, 2, 5, 15, 52, 203, 877, 4140, 21147, OEIS A000110
as expected. So what is the most natural thing to do next?

seq(count([B,{B=Set(Set(Z,card>=k))},labelled],size=n),n=1..9);
with 1<=k<=n, isn't it? So let's do it:

for n from 1 to 11 do
seq(count([B,{B=Set(Set(Z,card>=k))},labelled],size=n),k=1..n) od;

1
2, 1
5, 1, 1
15, 4, 1, 1
52, 11, 1, 1, 1
203, 41, 11, 1, 1, 1
877, 162, 36, 1, 1, 1, 1
4140, 715, 92, 36, 1, 1, 1, 1
21147, 3425, 491, 127, 1, 1, 1, 1, 1
115975, 17722, 2557, 337, 127, 1, 1, 1, 1, 1
678570, 98253, 11353, 793, 463, 1, 1, 1, 1, 1, 1

Sure I expected this triangle in OEIS. Can you find it?
Next let's us look at

for n from 1 to 11 do
seq(count([B,{B=Set(Set(Z,card=k))},labelled],size=n),k=1..n) od;


1
1, 1
1, 0, 1
1, 3, 0, 1
1, 0, 0, 0, 1
1, 15, 10, 0, 0, 1
1, 0, 0, 0, 0, 0, 1
1, 105, 0, 35, 0, 0, 0, 1
1, 0, 280, 0, 0, 0, 0, 0, 1
1, 945, 0, 0, 126, 0, 0, 0, 0, 1
1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1

Again, not in OEIS. Perhaps to many zeros for OEIS?
At last these two sequences are in OEIS:

seq(count([B,{B=Set(Set(Z,card>=2))},labelled],size=n),n=1..11);
seq(count([B,{B=Set(Set(Z,card=2))},labelled],size=2*n),n=1..11);

Aha, I see the pattern. Let's try it:
seq(count([B,{B=Set(Set(Z,card>=3))},labelled],size=n),n=1..11);

This time the sequence is /twice/ in OEIS: A005000 and A006505.
Well, the first with offset 1 the second with offset 0.
If this policy is generalized we can have a big party:
The 200K_E-Party and the 300K_E-Party on the same day,
actually tonight.

http://oeis.org/wiki/OEIS_100K_E-Party_%28Page_1%29

Let's us see what the editors will say. I brought this issue
to their attention.

Though I definitely go to a party tonight :)
Cheers, Peter

[Peter Luschny]

> When I found out how to convert rg-strings to 'real' set partitions I
> may be able to proceed finally to a comment on George's double
> enumerations.

Update: This hurdle is taken.
https://sites.google.com/site/seqcomp/home/listings/setpartitions