Mathematics desk | ||
---|---|---|
< October 27 | << Sep | October | Nov >> | October 29 > |
Welcome to the Wikipedia Mathematics Reference Desk Archives |
---|
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
There are n partygoers. At the door, each of them will get a mask that's printed by a computer. The computer chooses the design for each mask independently and uniformly at random, from a collection of m, where m < n.
I'm interested in calculating: (1) the probability that exactly k of the partygoers get a mask that nobody else has, and (2) the expected number of partygoers getting a mask that nobody else has?
Is there a simple way to express the above without using iterated sums? —Preceding unsigned comment added by 72.94.50.163 ( talk) 00:47, 28 October 2008 (UTC)
As to your first question, here are some hints. Let's denote the set of the first positive integers (that we use to label the masks) just by . Let's say that any in a string is a hapax entry in this string, if it occurs exactly once in it (for example, 3 and 4 are hapax entries in (1,2,3,1,1,2,4) whereas 1 and 2 are not). So your question is, how many strings in have exactly k hapax entries, out of the total number of strings ? Your probability is, of course, this number, say , divided by . The first thing to do should be: getting rid of the variable k, and reducing the problem to the case k=0. In fact, a string in with exactly k hapax entries is determined choosing: 1) the k-subset of [n] corresponding to the positions of its hapax entries, 2) an ordered list of the k entries to be hapax, and 3) the complement string, which has to be a generic hapax-free string of lenght (n-k) with entries choosen from a set of (m-k). This amounts to say that
Thus the question is: how many hapax-free strings are there in ? Look at the complement: the set of non hapax-free strings: it's the union of the n sets , where is the set of all strings whose i-th entry (at least) is hapax, that is
The union is not disjoint, of course, so you have to use the inclusion-exclusion formula; this means that you need to compute the cardinality of the sets , and also, the cardinality of their r-fold intersections, . That however depends only on r, besides n and m, and does not seem to be too hard to compute. If you can get through the computation I am curious to see the final result :) (well, as usual there is no final result) -- PMajer ( talk) 16:40, 28 October 2008
You should have found
It is instructive to consider the generating function of the numbers , that is
(it is a generating series of ordinary form in x and of exponential form in y and z: it is the best choice here). If you like manipulating power series, you can deduce from the above expression of the that, in fact
Indeed, the most efficient way to find the numbers would have been from the other way around: first, write down their generating function (you need a little theory to do it quickly), then deduce the coefficients. To check the validity now we can compute the expected numbers of strings in with exactly k hapax entries: that is the mean value where . Their generating function is easily deduced from :
that gives , in accordance with the computation by Algebraist. From the generating function you can deduce as well all the other momenta of the distribution for the number of hapax. Moreover, you can find asymptotics of the coefficients, even without computing them explicitly. Last observation: everything holds with no restriction on n and m, as was never required. -- PMajer ( talk) 08:55, 29 October 2008 (UTC)
Well, don't exhitate to ask, if you need further clarification. However, I've cleaned a couple of misprints and added some formulas. If you wish to try the computation of the generating function of the numbers , it is perhalps useful to consider first the generating function of the and find:
You can deduce from it using the relations stated at the beginning:
that are translated into the equation between their generating series. -- PMajer ( talk) 13:46, 29 October 2008 (UTC)
Simply put, I'm trying to figure out how to prove by induction that given , A and k are constants, e is euler's number, that . I've proven is true, so by induction, I have to show that implies that , but that gives me a problem. So I know that ; trying to reach . I've gotten to here: ; how could be shown to equal k? I'm not sure about the notation of , is it different from ? My textbook says that this induction is correct. Recently edited to add formatting, sorry for the mixup! - Blooooo ( talk) 03:28, 28 October 2008 (UTC)
Suppose I'm given a small collection of vectors with positive entries in , where . The goal is to choose precisely vectors to maximize
where is the standard th basis vector.
That is to say, I want to sum n different entries in n different vectors, choosing each coordinate only once, and maximize that sum. Does this problem break down easily? I know it has an instantiation as a 0-1 integer programming problem, but there's so much more structure here that I was hoping there would be a better way. Thanks, RayAYang ( talk) 04:19, 28 October 2008 (UTC)
Is there a way to solve for x in an un-factorable quadratic equation, such that a non-prime integer z is a factor, without using factorization? For example, solving x^2+x+3 such that it results in a number with a factor of 33 but without knowing that 33=3*11. 128.227.195.92 ( talk) 14:19, 28 October 2008 (UTC)poster
Mathematics desk | ||
---|---|---|
< October 27 | << Sep | October | Nov >> | October 29 > |
Welcome to the Wikipedia Mathematics Reference Desk Archives |
---|
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages. |
There are n partygoers. At the door, each of them will get a mask that's printed by a computer. The computer chooses the design for each mask independently and uniformly at random, from a collection of m, where m < n.
I'm interested in calculating: (1) the probability that exactly k of the partygoers get a mask that nobody else has, and (2) the expected number of partygoers getting a mask that nobody else has?
Is there a simple way to express the above without using iterated sums? —Preceding unsigned comment added by 72.94.50.163 ( talk) 00:47, 28 October 2008 (UTC)
As to your first question, here are some hints. Let's denote the set of the first positive integers (that we use to label the masks) just by . Let's say that any in a string is a hapax entry in this string, if it occurs exactly once in it (for example, 3 and 4 are hapax entries in (1,2,3,1,1,2,4) whereas 1 and 2 are not). So your question is, how many strings in have exactly k hapax entries, out of the total number of strings ? Your probability is, of course, this number, say , divided by . The first thing to do should be: getting rid of the variable k, and reducing the problem to the case k=0. In fact, a string in with exactly k hapax entries is determined choosing: 1) the k-subset of [n] corresponding to the positions of its hapax entries, 2) an ordered list of the k entries to be hapax, and 3) the complement string, which has to be a generic hapax-free string of lenght (n-k) with entries choosen from a set of (m-k). This amounts to say that
Thus the question is: how many hapax-free strings are there in ? Look at the complement: the set of non hapax-free strings: it's the union of the n sets , where is the set of all strings whose i-th entry (at least) is hapax, that is
The union is not disjoint, of course, so you have to use the inclusion-exclusion formula; this means that you need to compute the cardinality of the sets , and also, the cardinality of their r-fold intersections, . That however depends only on r, besides n and m, and does not seem to be too hard to compute. If you can get through the computation I am curious to see the final result :) (well, as usual there is no final result) -- PMajer ( talk) 16:40, 28 October 2008
You should have found
It is instructive to consider the generating function of the numbers , that is
(it is a generating series of ordinary form in x and of exponential form in y and z: it is the best choice here). If you like manipulating power series, you can deduce from the above expression of the that, in fact
Indeed, the most efficient way to find the numbers would have been from the other way around: first, write down their generating function (you need a little theory to do it quickly), then deduce the coefficients. To check the validity now we can compute the expected numbers of strings in with exactly k hapax entries: that is the mean value where . Their generating function is easily deduced from :
that gives , in accordance with the computation by Algebraist. From the generating function you can deduce as well all the other momenta of the distribution for the number of hapax. Moreover, you can find asymptotics of the coefficients, even without computing them explicitly. Last observation: everything holds with no restriction on n and m, as was never required. -- PMajer ( talk) 08:55, 29 October 2008 (UTC)
Well, don't exhitate to ask, if you need further clarification. However, I've cleaned a couple of misprints and added some formulas. If you wish to try the computation of the generating function of the numbers , it is perhalps useful to consider first the generating function of the and find:
You can deduce from it using the relations stated at the beginning:
that are translated into the equation between their generating series. -- PMajer ( talk) 13:46, 29 October 2008 (UTC)
Simply put, I'm trying to figure out how to prove by induction that given , A and k are constants, e is euler's number, that . I've proven is true, so by induction, I have to show that implies that , but that gives me a problem. So I know that ; trying to reach . I've gotten to here: ; how could be shown to equal k? I'm not sure about the notation of , is it different from ? My textbook says that this induction is correct. Recently edited to add formatting, sorry for the mixup! - Blooooo ( talk) 03:28, 28 October 2008 (UTC)
Suppose I'm given a small collection of vectors with positive entries in , where . The goal is to choose precisely vectors to maximize
where is the standard th basis vector.
That is to say, I want to sum n different entries in n different vectors, choosing each coordinate only once, and maximize that sum. Does this problem break down easily? I know it has an instantiation as a 0-1 integer programming problem, but there's so much more structure here that I was hoping there would be a better way. Thanks, RayAYang ( talk) 04:19, 28 October 2008 (UTC)
Is there a way to solve for x in an un-factorable quadratic equation, such that a non-prime integer z is a factor, without using factorization? For example, solving x^2+x+3 such that it results in a number with a factor of 33 but without knowing that 33=3*11. 128.227.195.92 ( talk) 14:19, 28 October 2008 (UTC)poster