2
$\begingroup$

It must be less than $B_6$ (where $B_6$ is the Bell number of $6$) since the elements are "duplicated". I would most appreciate a generating function that gives the number of set partitions of $\{1,1,2,2, ...n,n\}$.

$\endgroup$
  • 3
    $\begingroup$ What kind of thing is $\{1,1,2,2,3,3\}$ here? I assume it's not a set, because that would be equal to $\{1,2,3\}$. $\endgroup$ – Henning Makholm Aug 1 '15 at 22:30
  • $\begingroup$ {1,1,2,2,3,3} is a multiset. $\endgroup$ – Geoffrey Critzer Aug 2 '15 at 10:24
  • 1
    $\begingroup$ Using the Polya Enumeration Theorem twice in an algorithm with rather poor complexity I get the sequence $$2, 9, 66, 712, 10457,\ldots$$ which is OEIS A020555. The references therein may prove useful reading if indeed this is your sequence. They have a generating function for efficient calculation of these numbers. $\endgroup$ – Marko Riedel Aug 2 '15 at 23:12
  • $\begingroup$ The formula that I used is $$[B_1^2\cdots B_n^2] \sum_{q=1}^{2n} Z(S_q)\left(\sum_{k=1}^{2n} Z(S_k) (B_1+\cdots + B_n) \right),$$ which has limited utility for actual computations. $\endgroup$ – Marko Riedel Aug 2 '15 at 23:25
  • 1
    $\begingroup$ The first comment in the OEIS entry would appear to confirm that this sequence is a match. $\endgroup$ – Marko Riedel Aug 2 '15 at 23:34
1
$\begingroup$

Using the hint given in the OEIS entry we can write an optimized program that makes it possible to compute the sequence in question even for large values of $n$ for example this segment:

$$2, 9, 66, 712, 10457, 198091, 4659138, 132315780, 4441561814, \\ 173290498279, 7751828612725,393110572846777, 22385579339430539, \\ 1419799938299929267, 99593312799819072788, \ldots $$

The aforementioned hint says that we can equivalently count multigraphs with $n$ labeled edges where the vertices of the graph represent the multisets of the multiset partition and are connected by an edge $k$ if the two instances of the value $k$ are included in the sets represented by the two vertices that constitute the edge.

Supposing that we have the cycle index $Z(G_n)$ of the action on the edges of the symmetric group permuting the $n$ vertices of a graph where loops are allowed the desired value is thus given by ($2n$ is the maximum number of vertices we can cover with the $n$ labeled edges and these are multi-edges so they may be labeled with any subset of the $n$ labels)

$$[B_1 B_2 \cdots B_n] Z(G_{2n}) \left(\prod_{q=1}^n (1+B_q)\right).$$

But this cycle index is easy to compute with the computation being documented at this MSE link.

Observe that we have a special case here that admits radical simplification. Suppose we have a term $\alpha\in Z(G_{2n})$ which has the form $$p(\alpha) \prod_k a_k^{j_k(\alpha)}$$

with $p(\alpha)$ being the leading coefficient (a number) and $j_k(\alpha)$ the degree of $a_k$ in $\alpha.$

Now we have that any possible factors $a_k$ where $k\gt 1$ only contribute through the constant term because we are extracting the product $B_1 B_2\cdots B_n.$ This leaves $$p(\alpha) a_1^{j_1(\alpha)}.$$

Finally observe that $$[B_1 B_2\cdots B_n] \left(\prod_{q=1}^n (1+B_q)\right)^{j_1(\alpha)} \\ = [B_1 B_2\cdots B_n] \prod_{q=1}^n (1+B_q)^{j_1(\alpha)} = \prod_{q=1}^n {j_1(\alpha)\choose 1} = j_1(\alpha)^n.$$

The key effect here is that we have eliminated costly exponentiations of multivariate polynomials and are only working with numbers, computing this value: $$\sum_{\alpha\in Z(G_{2n})} p(\alpha) j_1(\alpha)^n.$$

This is the code:


pet_cycleind_symm :=
proc(n)
local p, s;
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_term :=
proc(varp)
local terml, d, cf, v;

    terml := [];

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

    [cf, terml];
end;


pet_cycleind_edg :=
proc(n)
option remember;
local s, t, res, cycs, l1, l2, flat, u, v;

    if n=0 then return 1; fi;

    s := 0:
    for t in pet_cycleind_symm(n) do
        flat := pet_flatten_term(t);

        cycs := flat[2]; res := 1;

        for u to nops(cycs) do
            for v from u+1 to nops(cycs) do
                l1 := op(1, cycs[u]); l2 := op(1, cycs[v]);
                res := res * a[lcm(l1, l2)]^(l1*l2/lcm(l1, l2));
            od;
        od;

        for u to nops(cycs) do
            l1 := op(1, cycs[u]);
            if type(l1, odd) then
                # a[l1]^(1/2*l1*(l1-1)/l1);
                res := res*a[l1]^(1/2*(l1-1));
            else
                # a[l1/2]^(l1/2/(l1/2))*a[l1]^(1/2*l1*(l1-2)/l1)
                res := res*a[l1/2]*a[l1]^(1/2*(l1-2));
            fi;
        od;

        s := s + res*t;
    od;

    s;
end;



Q :=
proc(n)
option remember;
    local res, flat, term;

    res := 0;
    for term in pet_cycleind_edg(2*n) do
        flat := pet_flatten_term(term);
        res := res + flat[1]*degree(term, a[1])^n;
    od;

    res;
end;
$\endgroup$
  • $\begingroup$ I am very grateful for and interested in your reply. I am taking a final exam in two days so I cannot review your post right away. $\endgroup$ – Geoffrey Critzer Aug 4 '15 at 12:20
  • $\begingroup$ Supposing that we have the cycle index Z(Gn) of the action on the edges of the symmetric group permuting the n vertices of a graph where loops are allowed. $\endgroup$ – Geoffrey Critzer Aug 7 '15 at 16:24
  • $\begingroup$ I can generate the cycle indices Z(G_n) for small values of n on Mathematica. I do not understand how your Polya substitution formula ( the first formula in your post) would count the number of labeled multigraphs. $\endgroup$ – Geoffrey Critzer Aug 7 '15 at 16:43
  • 1
    $\begingroup$ Good observation. The formula that you ask about is of the same type. Note that $$\prod_{q=1}^n (1+B_q)$$ generates all sets of labels (choose between it being included or not included) and a multi-edge has full symmetry between the constituent single edges so we are effectively dealing with a set. Now if we were to omit the coefficient extractor we would get all multigraphs with $n$ types of labels on the edges where off edges are admitted (constant coefficient). Hence after we apply the coeffcient extractor we get those graphs with exactly one instance of each type. $\endgroup$ – Marko Riedel Aug 7 '15 at 21:03
  • 1
    $\begingroup$ The above gadget can only be used to compute multiset partitions where each element occurs twice. This is because the concept of an edge is wired into the gadget to represent two instances of a given value, which are included in the multisets represented by the two end points. For your question you may use the poor complexity formula that I worked with initially. It is possible to construct a gadget for multisets where each element occurs three times and so on although the cycle indices require a CAS. $\endgroup$ – Marko Riedel Aug 8 '15 at 0:03

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.