Number of classes of k-digit strings when digit order and identity doesn't matter 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
 A: 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]
A: 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 an extremely straightforward Maple program.
Here 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.
Addendum Wed Oct 21  2015. Let me point out that  the fact that we
have  partitions   of  $k$   into  at  most   $n$  parts   follows  by
inspection. The fact that the  order does not matter creates multisets
and  the  digit permutations  render  multisets  with the  same  shape
indistinguishable from one another, leaving partitions.
At last, here is the code.

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;

strs :=
proc(k, n)
option remember;
local idx_coord, idx_digits, res, term_a, term_b,
    v_a, v_b, inst_a, inst_b, len_a, len_b, p, q;

    if k = 1 then return 1 fi;
    idx_coord := pet_cycleind_symm(k);

    if n = 1 then return 1 fi;
    idx_digits := pet_cycleind_symm(n);

    res := 0;

    for term_a in idx_coord do
        for term_b in idx_digits do
            p := 1;

            for v_a in indets(term_a) do
                len_a := op(1, v_a);
                inst_a := degree(term_a, v_a);

                q := 0;

                for v_b in indets(term_b) do
                    len_b := op(1, v_b);
                    inst_b := degree(term_b, v_b);

                    if len_a mod len_b = 0 then
                        q := q + len_b*inst_b;
                    fi;
                od;

                p := p*q^inst_a;
            od;

            res := res +
            lcoeff(term_a)*lcoeff(term_b)*p;
        od;
    od;

    res;
end;

part :=
proc(n, k)
option remember;
local res;

    if n=0 or k=0 then
        return `if`(n=0 and k=0, 1, 0);
    fi;

    if k=1 then return 1 fi;

    res := 0;
    if n >= 1 then
        res := res + part(n-1, k-1);
    fi;
    if n >= k then
        res := res + part(n-k, k);
    fi;

    res;
end;

strs_verif := (k, n) -> add(part(k, m), m=1..n);

A: 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.
