How often will this test fail?

Question

Preamble

There was a unit test in our codebase which was shuffling a string of length \$52\$ formed from the set of letters \$[A-Z]+[A-Z]\$ and then using the first \$20\$ characters of that shuffled string.
It failed quite a while after being written due to no repeated character being present in those twenty and we wondered how often such a test would be likely to fail. (A little more than one in five hundred and twenty-two times it turns out).

Challenge

Given an alphabet size (\$a\$), a number (\$n\$) of occurrences of each letter, and a prefix length (\$p\$), output the probability that a (uniformly chosen) random permutation of the \$a\times n\$ letters begins with \$p\$ distinct letters.

You may assume that:

• There will be enough letters to make the prefix: \$p \le n\times a\$
• Each of the three inputs will be non-negative integers: \$p,n,a\in\Bbb{Z}_{\ge 0}\$

Output in any reasonable format - e.g. a float, a fraction, a pair containing the numerator and denominator (no requirement to simplify); if you're unsure, just ask!

Potential method

This is the method we used to calculate the result we were interested in (from the preamble).

If one thinks of the \$n\times a\$ elements as a bag from which one repeatedly picks the next element of the prefix, then the probability of extending the prefix by one element such that it remains fully distinct is the number of elements remaining in the bag which do not yet appear in the prefix divided by the total number of elements remaining in the bag. As such the probability that the final length \$p\$ prefix will be fully distinct is the product of these probabilities starting with a full bag and an empty prefix:

$$ \prod_{i=0}^{p-1}\frac{n\times(a-i)}{n\times a-i} $$

Test cases

Floating point inaccuracy is acceptable; fractions, if used, do not need to be in simplest form.
Ideally these test cases will all be runnable in a reasonable amount of time, but if golf means crazy inefficiency so be it!

 a   n   p    output                          (as a fraction)
 2   1   0    1                               (1/1)
 2   1   1    1                               (1/1)
 2   1   2    1                               (1/1)
50   1  50    1                               (1/1)
 3   2   0    1                               (1/1)
 3   2   1    1                               (1/1)
 3   2   2    0.8                             (4/5)
 3   2   3    0.4                             (2/5)
 3   2   4    0                               (0/1)
26   2   0    1                               (1/1)
26   2   1    1                               (1/1)
26   2   2    0.9803921568627451              (50/51)
26   2  13    0.13417306435734888             (77824/580027)
26   2  20    0.001916063061695329            (2097152/1094510949)
32   8  11    0.1777403166811693              (31138512896/175191051065)
32   8  22    0.00014139946994082153          (3477211257894250479616/24591402353555723779476075)
32   8  33    0                               (0/1)

Answer 1

Wolfram Language (Mathematica), 32 bytes

#3~b~#/b[#2#3,#]#2^#&
b=Binomial

Try it online!

Input [p, n, a].

The formula can be rewritten \$\dfrac{a\choose p}{an\choose p}n^p\$.

---

Incidentally, this is fairly trivial using Mathematica's statistics built-ins:

Wolfram Language (Mathematica), 69 bytes

CDF[MultivariateHypergeometricDistribution[#~Max~1,a=Table@##2],1^a]&

Try it online!

Unfortunately, 38-character name aside (the longest name in the default namespace), MultivariateHypergeometricDistribution doesn't handle a nonpositive prefix length, and overall this approach is quite slow for this particular problem.

Answer 2

Haskell, ⁴¹ 40 bytes

(a#n)p|p<1=1|i<-p-1=(a-i)/(a-i/n)*(a#n)i

Try it online!

Someone's got to post the trivial solution, right? ...Right?

The only reason I don't feel too ashamed is that I managed to save 2 bytes by using the formula (a-i)/(a-i/n) instead of the more obvious n*(a-i)/(n*a-i)

Answer 3

Jelly, 9 bytes

×\c÷/×Ṫ*¥

Try it online!

Uses att's formula. Takes [a, n] on the left and p on the right

Uses the formula

$$\frac {\binom a p} {\binom {an} p} n^p$$

Unfortunately, the more elegant version of this formula

$$\frac {a!} {(an)!} \frac {(an - p)!} {(a - p)!} n^p$$

takes a lot more bytes in Jelly due to its poor handling of 3 variables

How it works

×\c÷/×Ṫ*¥ - Main link. Takes [a, n] on the left and p on the right
×\        - Scan multiply. Yield [a, a×n]
  c       - Binomial with p. Yield [aCp, (a×n)Cp]
   ÷/     - Reduce by division; aCp ÷ (a×n)Cp
        ¥ - Previous 2 links as a dyad f([a, n], p):
      Ṫ   -   Extract n
       *  - Raise it to the power p
     ×    - Multiply aCp ÷ (a×n)Cp by nᵖ

Answer 4

Excel, 48 bytes

=IFERROR(COMBIN(A2,C2)*B2^C2/COMBIN(A2*B2,C2),0)

Using att's formula. 37 bytes if an error is acceptable when p > a.

Spreadsheet

Answer 5

Python 3, 48 47 bytes

Saved a byte thanks to xnor!!!

f=lambda a,n,p:p<1or(p+~a)/(~-p/n-a)*f(a,n,~-p)

Try it online!

Straightforward calculation of the given formula. Returns either a float or an int or True (for \$1\$).

Answer 6

JavaScript (ES6), 35 bytes

A trivial recursive function expecting (a)(n)(p). May return true instead of 1.

a=>n=>g=p=>!p--||(a-p)/(a-p/n)*g(p)

Try it online!

Commented

a =>            // 1st function taking a
n =>            // 2nd function taking n
g = p =>        // 3rd recursive function taking p
  !p-- ||       //   if p = 0, stop and yield true (coerced to 1)
                //   (decrement p afterwards)
                //   otherwise:
  (a - p) /     //     compute (a - p) / (a - p / n)
  (a - p / n) * //     (same formula as Delfad0r)
  g(p)          //     and multiply by the result of a recursive call

Answer 7

Retina, 116 114 bytes

.+,(.+),
*_,$'*$1*_,$1*_,
["1/1¶"Lv$`_(_*),\1(_*),\1(_*),(.+)
$.($4*$3)/$.2
+`.+/(.+)¶(.+)/(.+)
$.($2**)/$.($1*$3*

Try it online! Link includes test cases. Takes input in the order p,a,n. Explanation:

.*,(.*),
*_,$'*$1*_,$1*_,

Convert p, na and a to unary.

["1/1¶"Lv$`_(_*),\1(_*),\1(_*),(.+)

Loop i from the maximum of a and p-1 down to 0, also prefix a dummy 1/1 fraction in case p is 0. Calculate na-i and a-i. (If p>a, there will always be an entry where i=a so the final result is zero anyway.)

$.($4*$3)/$.2

Create the fraction n(a-i)/(na-i) in decimal.

+`.+/(.+)¶(.+)/(.+)
$.($2**)/$.($1*$3*

Multiply all of the fractions together.

Previous 116-byte solution:

\d+,
*_,
["1/1¶"Lv$`_(_*),(_*),(.+)
$3*$1,$3*$2/$1,$3*$2
+`_,_
,
+`(/.+)¶(.+)/
$2$1
_*,(_*)
,$.1
+`\d+,(\d+)
$.($1**

Try it online! Link includes test suite that reduces the output fraction to its lowest terms. Takes input in the order p,a,n. Explanation:

\d+,
*_,

Convert p and a to unary.

["1/1¶"Lv$`_(_*),(_*),(.+)

Loop i from p-1 down to 0, also prefix a dummy 1/1 fraction in case p is 0.

$3*$1,$3*$2/$1,$3*$2

Start calculating (na-ni)/(na-i).

+`_,_
,

Perform the subtractions.

+`(/.+)¶(.+)/
$2$1

Collect all the numerators and denominators together.

_*,(_*)
,$.1

Convert all the positive values to decimal. (Other values are converted to zero, but there is always at least one zero if there are any negative values, so extra zeros makes no difference.)

+`\d+,(\d+)
$.($1**

Take the products of all the numerators and denominators.

Answer 8

C (gcc), ^{66 59} 54 bytes

f(a,n,p,r)float*r,n;{for(*r=1;p--;)*r*=(a-p)/(a-p/n);}

Try it online!

Calculates the given formula. Returns a float through its last parameter (which is a pointer to an uninitialized float).