Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose we look at $k$-digit strings with digits between $1$ and $n$. How many distinct classes of strings are there when digit identity and order doesn't matter?

More formally, what is the number of equivalence classes over strings $d_1,\ldots,d_k$ with $d_i\in \{1,\ldots, n\}$ where strings $d,\hat{d}$ are considered equivalent iff there exist bijections $\sigma$ over $\{1,\ldots, k\} $ and $\delta$ over $\{1,\ldots, n\}$ such that the following holds for all $j \in \{1,\ldots,k\}$

$$d_{\sigma(j)}=\delta(\hat{d}_j)$$

Edit: this seems to correspond to the number of ways to partition integer $k$ into at most $n$ parts

share|improve this question

3 Answers 3

up vote 3 down vote accepted

If I've read this right, you're looking to count k-tuples of integers in {1,..,n} that are inequivalent under the operations (a) permute the coordinates and (b) permute the integers.

So, for example, when k=7 and n=2, 1122212 would be equivalent to 2211121, 1112222 and 1111222 (and many others).

I believe it would be useful to construct a canonical form for each class: In this case, we can take the lexicographic first element in the equivalence class.

So these would be in canonical form:

1111222
1111122
1111112
1111111

whereas 1112222 would not be since it belongs to the same class as 1111222.

These canonical forms are equivalent to ordered partitions of k into n parts (some of which can be zero). For example 1111222 <-> 4+3 since there are four 1's and three 2's. [If instead n=3, then 1111222 <-> 4+3+0 since there are no 3's in the string.]

The number of these is the number $p_n(k)$ of partitions of k into at most n parts (afterwards, we can append the zeroes to achieve n parts).

We can compute $p_n(k)$ using the recurrence relation $p_n(k)=p_n(k-n)+p_{n-1}(k-1)$ (with some appropriate boundary conditions). [see: Enumerative combinatorics, Volume 1 By Richard P. Stanley p. 28]

share|improve this answer
    
Thanks, the page number reference is especially useful. –  Yaroslav Bulatov Oct 20 '10 at 2:24

You you consider your digit string to be a map $\{1,\ldots,k\}\to\{1,\ldots,n\}$ from positions to digit values, then what you want is counting such maps up to (composition with) permutations of the domain and of the codomain. This makes the problem one of the problems of the so-called Twelvefold way, in particular the one described here. The solution is the number of partitions of $k+n$ into $n$ (nonzero) parts.

share|improve this answer

I would like to contribute an experimental confirmation of the above result that we have the number $p_n(k)$ of partitions of $k$ into at most $n$ parts.

This is done by a particularly simple form of Power Group Enumeration as presented by e.g. Harary 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 permuting the slots and the elements being placed into these slots. We have $k$ slots and the symmetric group $S_k$ acting on them. Furthermore $n$ digits go into the slots and these digits have the symmetric group $S_n$ acting on them. We can 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, which has $n!\times k!$ elements. (The cycle indices have lower complexity.) But this number is easy to compute. Suppose we have a permutation $\alpha$ from $S_k$ 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.$

This yields the following extremely straightforward Maple program.

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;


strs :=
proc(k, n)
    option remember;
    local idx_coord, idx_digits, res, a, b,
    flat_a, flat_b, cyc_a, cyc_b, len_a, len_b, p, q;

    idx_coord := pet_cycleind_symm(k);
    idx_digits := pet_cycleind_symm(n);

    res := 0;

    for a in idx_coord do
        flat_a := pet_flatten_term(a);

        for b in idx_digits do
            flat_b := pet_flatten_term(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;
                    fi;
                od;

                p := p*q;
            od;

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

    res;
end;

This is some sample output from the program.

> seq(strs(k, 4), k=1..18);
    1, 2, 3, 5, 6, 9, 11, 15, 18, 23, 27, 34, 39, 47, 54, 64, 72, 84

> seq(strs(k, 5), k=1..18);
  1, 2, 3, 5, 7, 10, 13, 18, 23, 30, 37, 47, 57, 70, 84, 101, 119, 141

> seq(strs(k, 6), k=1..18);
  1, 2, 3, 5, 7, 11, 14, 20, 26, 35, 44, 58, 71, 90, 110, 136, 163, 199

Looking these up in the OEIS we can confirm that we indeed have the number $p_n(k)$ of partitions into at most $n$ parts. These are the sequences OEIS A001400, OEIS A001401 and OEIS A001402.

This MSE link points to some sophisticated power group enumeration examples.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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