2
$\begingroup$

I do have $n\times m$ objects $o_{ij}$. I'm looking for the number of possible groupings these objects. A valid grouping must not have any two object of the same row in one group. For example in the case $3\times 2$, a valid grouping is $\{\{o_{11}, o_{22}, o_{31}\}, \{o_{12}, o_{32}\}, \{o_{21}\}\}$. An invalid grouping is $\{\{o_{11}, o_{12}, o_{31}\}, \{o_{22}, o_{32}\}, \{o_{21}\}\}$, since $o_{11}$ and $o_{12}$ must not be in the same group. What is the number of valid groupings of $n\times m$ such objects?

$\endgroup$
1
$\begingroup$

This is a case of Power Group Enumeration with the group acting on the slots being the trivial group containing the identity permutation on $n\times m$ elements and the symmetric group acting on the values going into the slots being the symmetric group $S_q.$ Here a slot receives as its value the number of the set it goes into and the set identifiers are being permuted by the symmetric group and we obtain set partitions into at most $q$ sets.

We evidently require a classification of the permutations in $S_q$ by the number of fixed points. We do the case $m=1$ first and should get Bell numbers. Observe that the species of permutations with fixed points marked is

$$\mathfrak{P}(\mathcal{U}\mathfrak{C}_{=1}(\mathcal{Z}) + \mathfrak{C}_{=2}(\mathcal{Z}) + \mathfrak{C}_{=3}(\mathcal{Z}) + \mathfrak{C}_{=4}(\mathcal{Z}) + \cdots).$$

This gives the generating function $$G(z, u) = \exp\left(uz + \frac{z^2}{2} + \frac{z^3}{3} + \frac{z^4}{4} + \frac{z^5}{5} + \cdots\right)$$

which is $$G(z, u) = \exp\left((u-1)z + \log\frac{1}{1-z}\right) \\ = \frac{\exp((u-1)z)}{1-z} = \exp(uz) \frac{\exp(-z)}{1-z}.$$

Therefore the number of permutations in $S_q$ having $p$ fixed points is given by

$$q! [z^q] \frac{z^p}{p!} \frac{\exp(-z)}{1-z} = \frac{q!}{p!} [z^{q-p}] \frac{\exp(-z)}{1-z} = \frac{q!}{p!} \sum_{k=0}^{q-p} \frac{(-1)^k}{k!}.$$

Now in the Power Group Construction we place copies of cycles from the group permuting the values on the cycles of the group permuting the slots, consisting of fixed points only in the present example. If a permutation from $S_q$ contains $p$ fixed points we get a contribution of $p^{n\times m}$ which is $p^n.$ This yields (the term for $p=0$ produces a zero value and may be omitted; the $q!$ was canceled by the average from the cycle index $Z(S_q)$)

$$\sum_{p=1}^q \frac{p^n}{p!} \sum_{k=0}^{q-p} \frac{(-1)^k}{k!}.$$

Continuing with the sanity check we should get Bell numbers when we put $n=q$ (partition of $[q]$ into at most $q$ sets). We get

$$\sum_{p=1}^q \frac{p^q}{p!} \sum_{k=0}^{q-p} \frac{(-1)^k}{k!}$$

which yields

$$1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678570, \\ 4213597, 27644437, 190899322, \ldots$$

which is indeed OEIS A000110, the sequence of Bell numbers.

Continuing with PGE we now treat the general case where the $m$ values in the $n$ rows may not occur together for a contribution of (we choose a set of unique fixed points -- no duplicates -- from the $p$ available ones and place them on the cycles, also fixed points, of the single slot permutation corresponding to that row, the $n\times m$ slots having been divided into $n$ blocks of size $m$):

$$\bbox[5px,border:2px solid #00A000]{ m!^n \sum_{p=1}^{n\times m} {p\choose m}^n \frac{1}{p!} \sum_{k=0}^{n\times m-p} \frac{(-1)^k}{k!}.}$$

We get e.g. for $m=2$ the sequence

$$1, 7, 87, 1657, 43833, 1515903, 65766991, \\ 3473600465, 218310229201, 16035686850327, \ldots$$

which is OEIS A020556 and for $m=3$ we obtain

$$1, 34, 2971, 513559, 149670844, 66653198353, 42429389528215, \\ 36788942253042556, 41888564490333642283, 60862147523250910055785, \ldots$$

which is OEIS A069223 and has highly relevant data.

Remark. We use the follwing method for the proof that we get Bell numbers when $m=1$: starting from

$$\sum_{k=0}^n {n\brace k} x^{\underline{k}} = x^n$$

we find

$$\sum_{p=1}^q \frac{p^q}{p!} \sum_{k=0}^{q-p} \frac{(-1)^k}{k!} = \sum_{p=1}^q \frac{1}{p!} \sum_{r=0}^q {q\brace r} {p\choose r} r! \sum_{k=0}^{q-p} \frac{(-1)^k}{k!}.$$

This becomes

$$\sum_{r=0}^q {q\brace r} \sum_{p=r}^q \frac{1}{(p-r)!} \sum_{k=0}^{q-p} \frac{(-1)^k}{k!}.$$

We have it if we can show the coefficient is one. We get

$$\sum_{p=r}^q \frac{1}{(p-r)!} \sum_{k=0}^{q-p} \frac{(-1)^k}{k!} = \sum_{p=0}^{q-r} \frac{1}{p!} \sum_{k=0}^{q-p-r} \frac{(-1)^k}{k!} = \sum_{p=0}^l \frac{1}{p!} \sum_{k=0}^{l-p} \frac{(-1)^k}{k!}$$

with $l$ a positive number. Continuing

$$\sum_{p=0}^l \frac{1}{p!} [z^{l-p}] \frac{\exp(-z)}{1-z} = \sum_{p=0}^l \frac{1}{p!} [z^l] z^p \frac{\exp(-z)}{1-z} = [z^l] \sum_{p=0}^l \frac{1}{p!} z^p \frac{\exp(-z)}{1-z}$$

As we are extracting the coefficient on $[z^l]$ we may extend the sum to infinity without any additional contributions and get

$$[z^l] \sum_{p\ge 0} \frac{1}{p!} z^p \frac{\exp(-z)}{1-z} = [z^l] \frac{\exp(-z)}{1-z} \exp(z) = [z^l] \frac{1}{1-z} = 1$$

as claimed.

The following Maple code was used to investigate these numbers (somewhat optimized).

X :=
proc(n, m)

    (m!)^n*add(binomial(p,m)^n
               *1/p!*add((-1)^k/k!, k=0..n*m-p),
               p=1..n*m);
end;

ENUM :=
proc(n, m)
    option remember;
    local src, recurse, res; 

    src :=
    [seq(seq([A[p], B[q]], q=1..m), p=1..n)];

    res := 0;

    recurse :=
    proc(pos, spart, len)
        local idx, nxt, var;

        if pos > n*m then
            res := res + 1;
            return;
        fi;

        nxt := src[pos]; var := op(1, nxt) * op(2, nxt);

        for idx to len do
            if degree(spart[idx], op(1, nxt)) = 0 
            then
                spart[idx] := spart[idx] * var;

                recurse(pos + 1, spart, len);

                spart[idx] := spart[idx] / var;
            fi;
        od;

        spart[len + 1] := var;
        recurse(pos + 1, spart, len + 1);
        spart[len + 1] := 1;
    end;

    recurse(1, Array([seq(1, q=1..n*m)]), 0);

    res;
end;

CHECK :=
proc()
    {seq(ENUM(n, 1) - X(n, 1), n=1..10),
     seq(ENUM(n, 2) - X(n, 2), n=1..6),
     seq(ENUM(n, 3) - X(n, 3), n=1..4),
     seq(ENUM(n, 4) - X(n, 4), n=1..3),
     seq(ENUM(n, 5) - X(n, 5), n=1..2)};
end;

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

Addendum. Here is the code with some superfluous variables optimized out.

ENUM :=
proc(n, m)
    option remember;
    local src, recurse, res; 

    src :=
    [seq(seq(A[p], q=1..m), p=1..n)];

    res := 0;

    recurse :=
    proc(pos, spart, len)
        local idx, nxt;

        if pos > n*m then
            res := res + 1;
            return;
        fi;

        nxt := src[pos];

        for idx to len do
            if degree(spart[idx], nxt) = 0 
            then
                spart[idx] := spart[idx] * nxt;
                recurse(pos + 1, spart, len);
                spart[idx] := spart[idx] / nxt;
            fi;
        od;

        spart[len + 1] := nxt;
        recurse(pos + 1, spart, len + 1);
        spart[len + 1] := 1;
    end;

    recurse(1, Array([seq(1, q=1..n*m)]), 0);

    res;
end;
$\endgroup$
  • $\begingroup$ This will take some time to digest, but this is an excellent answer. $\endgroup$ – Michael Mar 1 '17 at 10:15

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.