Looking at n choose k, but you want to get at least one of a target t. For example you have a bag of blue marbles, which contains some number of red marbles. N is the total number of marbles in the bag. K is the number of marbles being chosen. T is the number of red marbles.<\/p>\n\n\n\n
This is probably well known, but I worked through it a few different ways anyway…<\/p>\n\n\n\n
First a simulation (C++):<\/p>\n\n\n\n
#include <iostream>\n#include <vector>\n\nusing namespace std;\n\n\nint main(int argc,char **argv) {\n\n int n = 3000;\n int k = 50;\n int t = 30; \/\/ targets\n\n vector<int> items(n,0);\n\n for(int i=0;i<t;i++) {\n int itm=rand()%items.size();\n for(;items[itm] !=0;) itm = rand()%items.size();\n items[itm] = 1;\n \/\/items[i] = 1;\n }\n\n \/\/cout << \"items: \";\n \/\/for(int i=0;i<items.size();i++) cout << items[i] << \" \";\n \/\/cout << endl;\n\n vector<int> count(t,0);\n\n \/\/ rounds of choosing\n int rounds=100000;\n for(int j=0;j<rounds;j++) {\n cout << \"round: \" << j << endl;\n int tcount=0;\n\n vector<int> selected;\n for(int i=0;i<k;i++) {\n\n int itm = rand()%items.size();\n for(;std::count(selected.begin(), selected.end(), itm);) itm = rand()%items.size();\n selected.push_back(itm);\n \/\/cout << \"selected: \" << itm << \" \" << items[itm] << endl;\n if(i%100000==0) cout << i << endl;\n }\n\n \/\/count items on target\n for(int i=0;i<selected.size();i++) {\n if(items[selected[i]] == 1) tcount++;\n }\n cout << \"tcount: \" << tcount << endl;\n\n count[tcount]++;\n }\n\n int morezero=0;\n for(int i=0;i<t;i++) {\n if((count[i] > 0) || (i==0)) cout << i << \" \" << count[i] << endl;\n if(i>=1) morezero+=count[i];\n }\n cout << \"One or more: \" << morezero << endl;\n cout << \"One or more fraction: \" << (double)morezero\/rounds << endl;\n}<\/code><\/pre>\n\n\n\nNext I calculated this by looking at the number of combinations calculating the fraction of combinations containing at least one target and total number of combinations:<\/p>\n\n\n\n
from math import comb\nimport sys\ndef totalcomb(n, k, t):\n return comb(n,k)\ndef targetcomb(n, k, t):\n\n total = 0\n total += comb(t,k)\n for i in range(k-1,0,-1): #(i=k-1;i>0;i--)\n # print(t,\" \",i, \", \", n, \" \", k-i)\n # Ways of choosing i items out of t. Multiply by\n total += comb(t,i)*comb(n-t,k-i)\n return total\n\nn = int(sys.argv[1])\nk = int(sys.argv[2])\nt = int(sys.argv[3])\nprint (targetcomb(n,k,t)\/totalcomb(n,k,t))\nprint (targetcomb(n,k,t))\nprint (totalcomb(n,k,t))<\/code><\/pre>\n\n\n\nThen in terms of probability, using the probability that each draw does not contain a target:<\/p>\n\n\n\n
from math import comb\nimport sys\n\ndef tprb(n, k, t):\n\n totalp = 1\n\n for i in range(0,k,1):\n p = 1 - (t \/ (n - i))\n totalp = totalp * p\n\n return 1-totalp\n\nn = int(sys.argv[1])\nk = int(sys.argv[2])\nt = int(sys.argv[3])\n\nprint (tprb(n,k,t))<\/code><\/pre>\n\n\n\nAll approaches give the same answer, the last is the least computationally taxing…<\/p>\n","protected":false},"excerpt":{"rendered":"
Looking at n choose k, but you want to get at least one of a target t. For example you have a bag of blue marbles, which contains some number of red marbles. N is the total number of marbles in the bag. K is the number of marbles being chosen. T is the number […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[1],"tags":[],"class_list":["post-6739","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p1RRoU-1KH","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/6739","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/comments?post=6739"}],"version-history":[{"count":1,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/6739\/revisions"}],"predecessor-version":[{"id":6740,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/posts\/6739\/revisions\/6740"}],"wp:attachment":[{"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/media?parent=6739"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/categories?post=6739"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/41j.com\/blog\/wp-json\/wp\/v2\/tags?post=6739"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}