2
$\begingroup$

How do I count all sets $S$ containing sequences which contain values of an alphabet $A$ where:

$\displaystyle\quad\sum_{x\in S} |x| = n$

And two sets are equivalent under permutation of alphabet symbols. eg: $\{[1,2],[1]\} = \{[2,9],[2]\}.$)

$n=1$ has only a single option: $\{[0]\}$, for $n=2$ there are 4: $\{[0,0]\},\{[0],[0]\},\{[0,1]\},\{[0],[1]\}$

$n=3$ has 13 ($[0,1,0]$ notated as $010$): $\{000\},\{0,00\},\{0,0,0\},\{001\},\{0,01\},\{0,11\},\{0,0,1\},\{010\},\{0,10\},\{011\},\{012\},\{0,12\},\{0,1,2\}$

And so forth, the first couple values are: $1,4,13,57,252,1322,7361$.

I haven't really gotten anywhere beyond that, but the amount of sets with a single sequence of length $n$ is equal to the $n$th Bell number. The amount of divisions for each sequence of length $n$ is $2^{n-1}$, but at that point you count sets that are equivalent under a permutation of $A$ and I'm not sure how many are equivalent.

$\endgroup$
  • 1
    $\begingroup$ Is the cardinality of the alphabet known? Is it independent of $n$ or is it always at least $n$ or something similar? Your $n=2$ set solution contains the set $\{[0],[0]\}$. How is that set different from just the set $\{[0]\}$ that already appears for $n=1$? $\endgroup$ – Ingix Mar 10 '17 at 12:46
  • $\begingroup$ Ah you're right, it's a multiset I suppose, I'm sorry. The size of alphabet is <= n because otherwise you could choose a permutation of the alphabet that "compacts" it. $\endgroup$ – Bob Lucassen Mar 10 '17 at 12:53
1
$\begingroup$

This interesting problem may be solved by Power Group Enumeration. The challenging part is that the sequence is almost impossible to compute beyond the initial five terms by total enumeration. The computation is done by a particularly simple form of PGE as presented by e.g. Harary and Palmer and (in a different publication) Fripertinger. The present case does not involve generating functions. and can in fact be done with Burnside's lemma. The scenario is that we have two groups, one permuting the slots and another the elements being placed into these slots. The easy part is that $n$ letters go into the slots and these letters have the symmetric group $S_n$ acting on them. What is somewhat more challenging is the cycle index of the group permuting the slots but only moderately so. We implement the concept of a multiset by partitioning the $n$ slots according to one of the $p(n)$ partitions of $n.$ (These are not combinations. We use combinations in the total enumeration routine but not here.) The partition corresponds to a multiset of sequences where the lengths of the sequences are given by the constitutents of the partition. E.g. the partition $2+2+3$ of $n=7$ corresponds to two sequences of length two and one of length three. It is now easy to describe the action of the group acting on the slots (there is one such group for each partition): it permutes the $q$ constituents of the partition of the same length $m$ aocording to the symmetric group $S_q$. This means it must move these slots in parallel since the sequences form inseparable blocks. Therefore a cycle from $S_q$ must have its variables $a_p$ replaced by $a_p^m$ as there is one copy of $a_p$ moving the first elements of the blocks of equal length, another for the second elements and so on until the copy of $a_p$ that moves elements at position $m.$ These movements must happen simultaneously. We then obtain the desired cycle index corresponding to a given partition by combining the action on sequences of the same length for all lengths that appear (multiplication of cycle indices). This effectively implements the concept of a multiset of sequences. We can then compute the number of configurations by Burnside's lemma which says to average the number of assignments fixed by the elements of the power group. But this number is easy to compute. Suppose we have a permutation $\alpha$ from the slot permutation group $Q$ and a permutation $\beta$ from $S_n.$ If we place the appropriate number of complete, directed and consecutive copies of a cycle from $\beta$ on a cycle from $\alpha$ then this assignment is fixed under the power group action for $(\alpha,\beta)$, and this is possible iff the length of the cycle from $\beta$ divides the length of the cycle from $\alpha$. The process yields as many assignments as the length of the cycle from $\beta.$ In what follows we have implemented one extra optimization which was absent from earlier contributions like those in the links shown at the end. This is that instead of flattening $\alpha$ and $\beta$ into lists of single cycles and iterating over these singletons to discover the number of coverings of a cycle from $\alpha$ by cycles from $\beta$ we have made use of the fact that the existence of a covering only depends on the lengths of the two cycles and hence we may process sets of cycles having the same length all at once, a significant savings. This is achieved by multiplying the number of coverings by the number of cycles of the same length in $\beta$ as the one used in the covering and raising the number of coverings to the appropriate power that represents the number of cycles of the current length in $\alpha$, which reflects the fact that we may freely combine any admissible covering of a cycle from $\alpha$ with any other.

We now share the results and the program that was used to compute them. The sequence goes

$$1, 4, 13, 57, 252, 1322, 7361, 45057, 294392, 2054394, 15172872, \\ 118175823, 966300054, 8268640847, 73825951226, \\ 686049132714, 6620780612228, \ldots$$

This is the PGE code that was used.

with(combinat);

pet_cycleind_symm :=
proc(n)
option remember;

    if n=0 then return 1; fi;

    expand(1/n*add(a[l]*pet_cycleind_symm(n-l), l=1..n));
end;

pet_flatten_termA :=
proc(varp)
local terml, d, cf, v;

    terml := [];

    cf := varp;
    for v in indets(varp) do
        d := degree(varp, v);
        terml := [op(terml), [op(1,v), d]];
        cf := cf/v^d;
    od;

    [cf, terml];
end;

pet_cycleind_mset :=
proc(msdata)
local msrep, res, cycs, num, slist;

    msrep := convert(msdata, `multiset`);

    res := 1;

    for cycs in msrep do
        num := op(2, cycs);
        slist := [seq(a[q]=a[q]^op(1, cycs), q=1..num)];

        res := res
        *subs(slist, pet_cycleind_symm(num));

    od;

    expand(res);
end;

set_seq :=
proc(n)
option remember;
local part, idx_slots, idx_syms, res, a, b,
    flat_a, flat_b, cyc_a, cyc_b, len_a, len_b, p, q;

    if n > 1 then
        idx_syms := pet_cycleind_symm(n);
    else
        idx_syms := [a[1]];
    fi;

    res := 0;

    for part in partition(n) do
        idx_slots := pet_cycleind_mset(part);

        if not type(idx_slots, `+`) then
            idx_slots := [idx_slots];
        fi;

        for a in idx_slots do
            flat_a := pet_flatten_termA(a);

            for b in idx_syms do
                flat_b := pet_flatten_termA(b);

                p := 1;
                for cyc_a in flat_a[2] do
                    len_a := op(1, cyc_a);
                    q := 0;

                    for cyc_b in flat_b[2] do
                        len_b := op(1, cyc_b);

                        if len_a mod len_b = 0 then
                            q := q + len_b*op(2, cyc_b);
                        fi;
                    od;

                    p := p*q^op(2, cyc_a);
                od;

                res := res + p*flat_a[1]*flat_b[1];
            od;
        od;
    od;

    res;
end;

set_seq_enum :=
proc(n)
option remember;
local orbits, orbit, ind, slist, perm, part, comb, item,
    entlst, sofar, sb, len;

    if n=1 then return 1 fi;

    slist := [];

    for perm in permute(n) do
        slist :=
        [op(slist), [seq(q-1=perm[q]-1, q=1..n)]];
    od;

    orbits := table();

    for ind from n^n to 2*n^n-1 do
        item := convert(ind, base, n)[1..n];

        for part in partition(n) do
            for comb in permute(part) do
                entlst := []; sofar := 0;

                for len in comb do
                    entlst :=
                    [op(entlst), item[1+sofar..len+sofar]];
                    sofar := sofar + len;
                od;

                orbit := [];

                for sb in slist do
                    orbit :=
                    [op(orbit), sort(subs(sb, entlst))];
                od;

                orbits[convert(orbit, `set`)] := 1;
            od;
        od;
    od;

    # nops([indices(orbits, `nolist`)]);
    numelems(orbits);
end;

PGE recently appeared at this MSE link I and this MSE link II.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.