Choose 3 strings and output the exact minimum Hamming distance between any pair

Question

Consider \$3\$ binary strings of length \$n\$ chosen independently and uniformly at random. We are interested in computing the exact expected minimum Hamming distance between any pair. The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different.

Task

Given an input n between 2 and 10, inclusive, consider \$3\$ binary strings of length \$n\$ chosen independently and uniformly at random. Output the exact expected minimum Hamming distance between any pair.

Output should be given as a fraction.

Your code should run in TIO without timing out.

Answer 1

Pari/GP, 92 90 bytes

2 bytes saved thanks to @Nicolas!

n->sum(a=0,n,sum(b=0,n-a,sum(c=0,n-a-b,n!/a!/b!/c!/(n-a-b-c)!*min(a+b,min(a+c,b+c)))))/4^n

Try it online!

$$ f(n) = \frac{1}{4^n} \sum_{\substack{a+b+c+d=n\\a,b,c,d\geq 0}} \binom{n}{a,b,c,d}\min(a+b,a+c,b+c)$$

A more direct brute force approach may be shorter in some languages, but I'm not sure if that's true for Pari. Anyway, it's a shame that Pari's min only accepts two arguments.

I can avoid the min and be about 6 times faster, but the compensating additional code makes it longer. Maybe in another language this is the shorter way. And maybe it is possible to simplify further and get rid of the innermost sum.

n->sum(a=0,n,sum(b=a,n-a,sum(c=b,n-a-b,n!/a!/b!/c!/(n-a-b-c)!*(a+b)*6/(1+(a==b)+(b==c))!)))/4^n

Try it online!

Answer 2

Jelly, 31 bytes

Ḷṗ4S⁼¥Ƈɓ!×Ṗṁ4SƝṂƲ}:!P$}ð€S,4*$}

A monadic Link accepting an integer which yields a pair of integers, [numerator, denominator] (not reduced to simplest form).

Try it online! Or see all of n=2 to 10 reduced to simplest form.

How?

Uses the same approach as Christian Sievers' Pari/GP answer

Ḷṗ4S⁼¥Ƈɓ!×Ṗṁ4SƝṂƲ}:!P$}ð€S,4*$} - Link: integer, n
Ḷ                               - lowered range -> [0..n-1]
 ṗ4                             - Cartesian power 4 (all length 4 tuples using alphabet [0..n-1]
      Ƈ                         - filter keep those for which:
     ¥                          -   last two links as a dyad:
   S                            -     sum
    ⁼                           -     equals n?
       ɓ               ð€       - for each tuple do f(n, tuple):
        !                       -   factorial = n*(n-1)*...*1
                 }              -   use right argument:
                Ʋ               -     last four links as a monad:
          Ṗ                     -       pop i.e. (a,b,c,d)->(a,b,c)
           ṁ4                   -       mould like 4 -> (a,b,c,a)
              Ɲ                 -       for neighbours:
             S                  -         sum -> (a+b,b+c,c+a)
               Ṃ                -       minimum
         ×                      -   multiply
                      }         -   use right argument:
                     $          -     last two links as a monad:
                   !            -       factorial -> (a!,b!,c!,d!)
                    P           -       product -> a!×b!×c!×d!
                  :             -   integer division
                         S      - sum
                              } - use right argument:
                             $  -   last two links as a monad:
                           4    -     four
                            *   -     exponentiate -> 4^n
                          ,     - pair

Answer 3

05AB1E, 26 bytes

Ý4ãʒOQ}ε¨Ćü+ßI!*y!P÷}O4Im‚

Port of @JonathanAllan's Jelly answer, which uses the same formula as @ChristianSievers's Pari/GP answer.
Just like his answer, the output is not reduced to its simplest form.

Try it online or verify all test cases.

Explanation:

Ý                 # Push a list in the range [0, (implicit) input-integer]
                  # (NOTE: Jonathan's Jelly answer uses the range [0,input) instead of
                  #  [0,input], but that doesn't pose an issue, since the mapped value will
                  #  result in 0, not affecting the total sum)
 4ã               # Create all possible quartets by using the cartesian product with 4
   ʒ              # Filter these quartets by:
    O             #  Take the sum
     Q            #  And check if it's equal to the (implicit) input-integer
   }ε             # After the filter: map each remaining quartet [a,b,c,d] to:
     ¨            #  Remove the last item d: [a,b,c]
      Ć           #  Enclose the list, appending its own head: [a,b,c,a]
       ü+         #  Sum each consecutive pair: [a+b,b+c,c+a]
         ß        #  Pop and push the minimum of this
          I!      #  Push the input, and take its factorial
            *     #  Multiply both by each other
             y!   #  Take the factorial of each value in the quartet: [a!,b!,c!,d!]
               P  #  Take the product of this: a!*b!*c!*d!
                ÷ #  Integer-divide the two: (min(a+b,b+c,c+a)*n!) // (a!*b!*c!*d!)
    }O            # After the map: take the sum of all values in the list
       I          # Push the input-integer again
      4 m         # And take 4 to the power this
         ‚        # And finally pair both together
                  # (after which this pair is output implicitly as result)