0
$\begingroup$

I have a $m$ digit number of base $n$ where repeats are allowed. How do I find the number of combinations? I came across this trying to find the number of nonisomorphic graphs of order $m$.

Examples:

For a 2 digit number of base 2:

$00, 01, 11$

For a 3 digit number of base 4:

$000, 001, 002, 003, 011, 012, 013, 022, 023, 033, 111, 112, 113, 122, 123, 133, 222, 223, 233, 333$

$\endgroup$
5
  • 1
    $\begingroup$ I have a feeling finding the number of nonisomorphic graphs of order $k$ is a much harder problem than finding the number of $n$-digit base-$m$ numbers, and I'm not sure where the $k$ came from. $\endgroup$
    – genisage
    Sep 23 '14 at 21:49
  • $\begingroup$ @genisage I agree, I fixed the $k$. $\endgroup$
    – 0x41414141
    Sep 24 '14 at 17:18
  • $\begingroup$ Oops, I misread the question. I thought you were trying to solve this problem by counting nonisomorphic graphs. The number of ways to pick a string of length $m$ from an alphabet of size $n$ has a very simple formula, $n^m$. Good luck with your graphs. $\endgroup$
    – genisage
    Sep 24 '14 at 21:25
  • $\begingroup$ @genisage Yes, but I need strings that do not have the same combination of letters. Combinations may not be the right word, see my two examples. $\endgroup$
    – 0x41414141
    Sep 24 '14 at 22:30
  • 1
    $\begingroup$ oh yeah, sorry about that. You're looking for multisets. $n$ multiset $m$ is $m+n-1 \choose m$ $\endgroup$
    – genisage
    Sep 24 '14 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.