# 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

-

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]

-
Thanks, the page number reference is especially useful. –  Yaroslav Bulatov Oct 20 '10 at 2:24