<jupyter_start><jupyter_text>Interesting problem of finding the probability of getting r distinct numbers from n samples!Question: You have a set containing r distinct numbers say 0,1,2,...,r. You pick n (n>r) samples from this set with replacement (Equal probability of picking any number). What is the probability that in these n samples, you will have all of these r distinct numbers. Note: rest (n-r) samples can be anything, we want probability of having atleast r unique samples.<jupyter_code>import numpy as np
from IPython.display import Math<jupyter_output><empty_output><jupyter_text>Here, Brute-Force is applied to find the number of sets with 4 distinct numbers. n = 6, r = 4<jupyter_code>count = 0
r = 4
n = 6
for a in range(r):
    for b in range(r):
        for c in range(r):
            for d in range(r):
                for e in range(r):
                    for f in range(r):
                        if(len(np.unique([a,b,c,d,e,f]))==r):
                            count += 1
#                             print([a,b,c,d])
print("Number of sets possible with %d distinct numbers when %d samples are drawn is %d."%(r,n,count))<jupyter_output>Number of sets possible with 4 distinct numbers when 6 samples are drawn is 1560.<jupyter_text>Now, we can also calculate it using combintorics for r=4,n=6 i.e. $$\sum_{i=1}^{n-r+1} \sum_{j=i+1}^{n-r+2} \sum_{k=j+1}^{n-r+3} r^i * (r-1)^{j-i} * (r-2)^{k-j} * (r-3)^{n-k}$$<jupyter_code>r = 4
n = 6
count = 0
for i in range(1, n-r+2):
    for j in range(i+1, n-r+3):
        for k in range(j+1, n-r+4):
            count += r**i * (r-1)**(j-i) * (r-2)**(k-j) * (r-3)**(n-k)
print("Number of sets possible with %d distinct numbers when %d samples are drawn is %d."%(r,n,count))
print("Probability of getting atleast one unique set of %d numbers is " %r, count/(r**n))<jupyter_output>Number of sets possible with 4 distinct numbers when 6 samples are drawn is 1560.
Probability of getting atleast one unique set is  0.380859375<jupyter_text>Similarly, for r=3, n=6 the formula is,$$\sum_{i=1}^{n-r+1} \sum_{j=i+1}^{n-r+2} \sum_{k=j+1}^{n-r+3} r^i * (r-1)^{j-i} * (r-2)^{k-j} * (r-3)^{n-k}$$This boils down to:$$\sum_{i=1}^{n-r+1} \sum_{j=i+1}^{n-r+2} r^i * (r-1)^{j-i} * (r-2)^{n-j}$$<jupyter_code>r = 3
n = 6
count = 0
for i in range(1, n-r+2):
    for j in range(i+1, n-r+3):
        count += r**i * (r-1)**(j-i) * (r-2)**(n-j)
print("Number of sets possible with %d distinct numbers when %d samples are drawn is %d."%(r,n,count))
print("Probability of getting atleast one unique set of %d numbers is "%r, count/(r**n))<jupyter_output>Number of sets possible with 3 distinct numbers when 6 samples are drawn is 540.
Probability of getting atleast one unique set of 3 numbers is  0.7407407407407407<jupyter_text>Brute-Force verification for this scenario is simple as follows:<jupyter_code>count = 0
r = 3
n = 6
for a in range(r):
    for b in range(r):
        for c in range(r):
            for d in range(r):
                for e in range(r):
                    for f in range(r):
                        if(len(np.unique([a,b,c,d,e,f]))==r):
                            count += 1
#                             print([a,b,c,d])
print("Number of sets possible with %d distinct numbers when %d samples are drawn is %d."%(r,n,count))<jupyter_output>Number of sets possible with 3 distinct numbers when 6 samples are drawn is 540.
{'fraction_non_alphanumeric': 0.1488797169811321, 'fraction_numerical': 0.03331367924528302, 'mean_word_length': 3.0296912114014254, 'pattern_counts': {'":': 0, '<': 17, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '5', 'dir': 'jupyter-structured-clean-dedup', 'id': '467665', 'license': 'MIT', 'n_tokens_mistral': 1273, 'n_tokens_neox': 1185, 'n_words': 415, 'path': 'Probabilty_problem.ipynb', 'repo_name': 'RachithP/fun-stuff', 'size': '3392'}