Jump to content

Wikipedia:Reference desk/Archives/Mathematics/2012 September 21

From Wikipedia, the free encyclopedia
Mathematics desk
< September 20 << Aug | September | Oct >> September 22 >
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.


September 21

[edit]

Integration of 1/x in Quadrant I

[edit]

Hi. First of all, this isn't an actual homework problem, but a conceptual question I asked a mixed crowd of people, some of whom know integration techniques and some of whom which who whom don't. Everybody seemed to know intuitively or by proof that the area underneath the curve in quadrant one is infinite, because since the graph never touches either axis, the area underneath each section is infinite. This didn't make sense to me, because I intuitively compared it to a converging sum such as 0.999..., but apparently the hyperbolic function does not converge. Therefore, I must be severely deluded. The integration technique also relies on the fact that zero invalidates the integration, resulting in infinity; if one of the axes were shifted away from the zero-point, the area would still be infinite. This brings up the question: since shifting both axes away from zero would immediately cause the function's area to become finite, is there a tipping point of some sort? This is hillarious because the hyperbola itself is tipping pointential. Therefore, perhaps at the exact tipping point upon which the area oscillates between finite and infinite, causing the creating of a complex number. However, since this is a bi-axial method, the convergence paradigm is both null and void.

I must admit, quite embarrassingly, that I've never done mathematical proofs for more than one hour in my entire life. Therefore, I may need to rely on intuitive techniques such as visual calculus to get the point across to myself about why this function has an infinite area. I incorrectly assumed that the total area underneath the hyperbola in the first quadrant is reducible to be equivalent to the area to the bottom left of a linear function with the slope -1. However, I then remembered my Cartesian plane-onto-sphere method, which was improperly answered because my method assumes an infinite Cartesian surface, whereas stereographic projection relies on a finite Earth. It would be more like taking the membrane of an open universe and reconstructing it to make it closed. Anyway, I proved to myself that in this projection, the four points of (0,0), (x-fin,x-infinlim), (y-fin,y-infinlim) and (±∞,±∞) together comprise the manifold geodesic of a sphere in 2.5 dimensions (clarification, citation, objectivity and sanity needed), in each of the four quadrants (actually, there are a total of eight). This is where {x,y-fin/infinlim} form the continuum where the grid system transforms from finite in one direction to infinite in the opposite direction (from the vantage point of the "anti-origin"), forming two points on a sort of central meridian line, though that's irrelevant largely to solve this problem. So in the Q-I space, the first quadrant forms a circle, and that circle's area is infinite. The perimeter of this circle must also be infinite. The area under the hyperbola, thus, represents an area around the circumference of this circle, although it is widest at one point of the circle and converges at the other end of the circle. Despite the distance from this circumference getting smaller as the function recedes from the 2-space origin, the area still goes onto infinity, thus allowing the total area by integration to be infinite. Phew, though this is not as clear to most people, so there has to be a better intuitive way of proving it.

Someone enlighten me by dialing 0 on the Hamiltonian operator. Thanks. ~AH1 (discuss!)

If you're having trouble seeing that the area under the curve y = 1/x in the first quadrant is infinite, consider the following picture, similar to those commonly drawn to illustrate Riemann sums:
All of the blue rectangles are included in the area under the red curve y = 1/x, so the area under the curve must be at least as large as the total area of all the rectangles. Every rectangle has width 1. The first rectangle has height 1, the second has height 1/2, the third has height 1/3, and so on. So the total area of the rectangles is the sum of the harmonic series 1 + 1/2 + 1/3 + …, and this sum is infinite:
Since the total area of the blue rectangles is infinite, the area under the curve y = 1/x must also be infinite. —Bkell (talk) 08:21, 21 September 2012 (UTC)[reply]
See also Gabriel's Horn for the nice paradox that the "horn" formed by rotation of y = 1/x (x>1) about the x axis has finite volume but infinite area, so it can be filled with paint but its surface can't be painted. AndrewWTaylor (talk) 09:51, 21 September 2012 (UTC)[reply]
Good example, but Gabriel's horn has x^2 in the denominator, and 1/x^2 has a finite integral from 1 to infinity. SemanticMantis (talk) 15:15, 21 September 2012 (UTC)[reply]
No, AndrewWTaylor was correct when he said that Gabriel's horn is constructed by rotating y = 1/x about the x-axis. The volume integral has a 1/x2 in it, but that's not the defining curve. —Bkell (talk) 02:59, 22 September 2012 (UTC)[reply]
  • Also, the "graph never touches either axis" is not a valid argument for infinite area, so perhaps your reticence to accept it was more correct than you knew! Consider a piecewise defined function, f=1/x^(0.5), x in (0,1), f=1/x^2, x in [1,infinity). This function has a finite integral over (0,infinity), and the graph never touches either axis. SemanticMantis (talk) 15:15, 21 September 2012 (UTC)[reply]

Limits of Integration

[edit]

Is it true in general that ?


Widener (talk) 02:57, 21 September 2012 (UTC)[reply]

Consider
     
Or
     
CiaPan (talk) 05:30, 21 September 2012 (UTC)[reply]
Good answer. Interchange_of_limiting_operations has scant information, and could use some improving if anyone is interested. SemanticMantis (talk) 15:03, 21 September 2012 (UTC)[reply]
Oh, of course, but what if you add the condition that the limits and exist? Widener (talk) 16:34, 21 September 2012 (UTC)[reply]
. -- Meni Rosenfeld (talk) 17:04, 22 September 2012 (UTC)[reply]
Hm. Okay. I think it is true that though.
If you can interchange the limit and integral somehow you get
Widener (talk) 18:12, 22 September 2012 (UTC)[reply]
If the integrand in the last integral is finite (bounded) in the neighbourhood (x,ε) → (1,0), then ... — Quondum 20:56, 22 September 2012 (UTC)[reply]

Inverse birthday problem

[edit]

The birthday problem of course describes the probability that two people in a given set of people will share birthdays.

But what are the odds in a group of n people that there are days where there are no birthdays?

The birthday problem's solution implies that birthdays often cluster. Would that mean that unbirthdays are also clustered?

This isn't homework of any sort; I'm just curious. I have ~500 Facebook "friends" — what are the odds that none of them have a birthday today? --Mr.98 (talk) 13:39, 21 September 2012 (UTC)[reply]

Off the top of my head, I think this is easier than the birthday problem, because we don't have to be careful about things like Alice and Bob share some birthday, OR Alice and Charles share some birthday, etc... If we assume that birthdays are uniformly distributed, and each person's birthday is independent of all the others, then we can just multiply to answer your final question. Because they are uniformly distributed, the probability that person A's birthday is not today is 364/365. Likewise for person B. Because they are independent, we can multiply to get the probability that today is not A's birthday AND is not B's birthday is 364/365 X 364/365. So the probability (not odds) that no friend has a birthday today is (364/365)^500=0.2537. Note that your last question is different from your second (i.e. some B-day free day exists, vs today is a B-day free day); that one takes a little more work. SemanticMantis (talk) 16:15, 21 September 2012 (UTC)[reply]
More concisely, the last question is the same as "if 500 people roll a 365-sided die, what is the probability that none of them roll a 265 (today)", while the second question is "if n people roll a 365-sided die, what is the probability that there is some number which does not occur." SemanticMantis (talk) 16:20, 21 September 2012 (UTC)[reply]
It's not so easy to work out a formula, but the probability that there is some day with no birthday is near certainty until the number of people gets well up into the thousands. Looie496 (talk) 16:24, 21 September 2012 (UTC)[reply]
Isn't the chance that a day exists where nobody in a group of 365 or more has the same birthday given by 1-(1-(364/365)n)365 ? So, when n = 500, we get 1-(1-(364/365)500)365 = 1-(1-0.2537)365 = 1-(0.7463)365 = 1 - 4.1779×10-47, or, for all practical purposes 1.0, a virtual certainty that at least one birthday-free day exists. Here's the calculations with different values of n plugged in:
  n     probability of a birthday-free day existing
-----   -------------------------------------------
  500   ≈1.0
 1000    0.99999999997
 1500    0.9975
 2000    0.78
 2500    0.32
 3000    0.093
 4000    0.0062
 5000    0.00040
 6000    0.000026
 7000    0.0000017
 8000    0.00000011
 9000    0.0000000069
10000    0.00000000044
StuRat (talk) 17:35, 21 September 2012 (UTC)[reply]
I am immediately suspicious of that formula 1-(1-(364/365)n)365 as it gives a smooth transition of probabilities at the point n = 365. 86.160.216.189 (talk) 17:59, 21 September 2012 (UTC)[reply]
It does seem odd that it gives a probability of almost 1, but not exactly 1, when used for fewer than 365 people. It's within 1.5×x10-78 of 1, though. Is this the chance that the universe will end before the year ends ?  :-) StuRat (talk) 18:08, 21 September 2012 (UTC)[reply]
The formula is only an approximation, because it treats the days as independent, which they aren't really. Looie496 (talk) 18:40, 21 September 2012 (UTC)[reply]
In what sense ? I suppose birthdays aren't completely evenly distributed, in that slightly more people are born at some parts of the year than others. However, I don't think that's the issue here. StuRat (talk) 18:44, 21 September 2012 (UTC)[reply]
I agree with you StuRat, independence of birthdays is not the problem with your formula (that is why I phrased the problems with dice above, just to be clear about the assumptions.) Nevertheless, I also think your formula is wrong. Why should it be right? You haven't explained your reasoning at all. Also, you can easily write a program to get some good approximate answers. I bet if you do that (correctly), you'll get answers noticeably different from your table above. SemanticMantis (talk) 18:53, 21 September 2012 (UTC)[reply]
Well, if the chance of a given day being birthday free is 0.2537, then the probability that it has at least one birthday is 1-0.2537, or 0.7463. The chances of 2 such independent days having one or more birthday each then becomes 0.74632. The chances of 365 independent days having one or more birthday each then becomes 0.7463365. The chance of this not being the case then becomes 1-0.7463365. StuRat (talk) 19:07, 21 September 2012 (UTC)[reply]
I think I see what Looie means, though. Once we know that one day contains (or doesn't contain) a birthday, this can change the count of potential birthdays that can fall on the other dates. So, yes, in this sense my formula is an approximation, with an error under 1.5×x10-78, in the case of 364 people. StuRat (talk) 19:12, 21 September 2012 (UTC)[reply]
I haven't actually checked anything numerically, but the fact that the formula is inexact, and the error bounds have not been mathematically quantified, leaves open the possibility that it is badly wrong for other values. The 1.5×10-78 example by itself not necessarily confidence-inspiring. 86.160.216.189 (talk) 19:31, 21 September 2012 (UTC)[reply]

Consider the total number of ways to distribute the birtdays of the n persons over the 365 possible dates. You can represent each possible distribution as a string of the form

00|0|0000|0||00|0|00|....

where each "0" represents a birtday of the person and the "|" are the separations between different days. So, on Januari 1 you have two birtdays, on Januari 2 there is one birtday etc. etc. Then everyu possible string o can write down corresponds to a valid distribution and voce versa, so you just need to count the number of strings. We have n "0"'s and we have 364 "|"'s so the total number is Binomial[364 + n,n].

Then if we demand that on every day you have at least one birtday, then this means that you must leave at least one "0" at each position in the string. This means that you have n-365 "0"'s that you can freely shuffle around. You can, of course, also consider strings with n -365 "0"s, themapping between a birthday distribution is then the number of "0"'s at some date plus one. So, the total number of such distributions is Binomial[n-1,n-365].

The probability that you always have at least one birtday on each date is thus Binomial[n-1,n-365]/Binomial[364 + n,n], the probability that there are days where you don't have birthdays is thus given by:

1 - Binomial[n-1,n-365]/Binomial[364 + n,n]

Count Iblis (talk) 17:08, 21 September 2012 (UTC)[reply]


I corrected the above problem, I found that the probability p for there being one or more days on which there are no birthdays is given by:

where r = 365

Count Iblis (talk) 19:50, 21 September 2012 (UTC)[reply]

What is k ? Also, would you like to run that against the numbers in my chart above, to see how the two compare ? StuRat (talk) 23:27, 21 September 2012 (UTC)[reply]
I tried it earlier and they seem to correspond quite well, so assuming Count Iblis' formula is correct, it seems like yours is a pretty good approximation after all. (As far as evaluating the formula is concerned, k is just an internal counter which does not need to be assigned a meaning, but probably you know that and are asking about its meaning in terms of the formula derivation.) 86.160.216.189 (talk) 00:17, 22 September 2012 (UTC)[reply]
Looks ok. There are possibilities. To get the ones with birthdays on every day, you have to subtract the ones where at least one day has no birthdays. There are ways to distribute them over 364 days, and 365 ways to choose those 364, so ; however, now you removed the ones with two "birthless" days twice. So you add those: there's ways to choose those days, giving you . Same thing again: some are counted twice, so you must subtract ; repeat the same proces till you arrive at all birthdays on one day, divide by total number of possibilities gives the odds of all days having birthdays, subtract from 1 to get the odds you wanted. Ssscienccce (talk) 01:30, 22 September 2012 (UTC)[reply]

About the derivation, you can use inclusion/exclusion as Ssscienccce explained above. Another way is to directly evaluate evaluate the number of ways you can have one or more birthday on each date by summing over each distribution of the birth dates over the year. So, if there are birthdays on the jth date, then the total number of ways to have such a distribution is:

If we sum this over all possible values of we should find . In the summation, you have to impose the constraint . You can do this using generating functions. You compute the function:

The coefficent of x^n is then the desired answer. Taking out the factor n!, the summation factors into identical summations, and each summation is the series expansion of exp(x), so f(x) = n! exp(rx), the coefficient of x^n is thus r^n. If we now consider only cases where you have one or more birthdays on each date, then each of the summation starts at 1 instead of zero, so, you get f(x) = n! [exp(x) - 1]^r. The coefficient of x^n can be obtained by first expanding [exp(x) - 1]^r and then extracting the coefficient of x^n from each term, you then get the above formula.

You can also use the generating function directly to find approximations for large n, you can write the coefficient of x^n as the contour integral of f(z)/z^(n+1) around the origin and then using the saddle point method obtain approximations to that integral. Count Iblis (talk) 02:00, 22 September 2012 (UTC)[reply]

see Coupon collector's problem. Robinh (talk) 08:28, 23 September 2012 (UTC)[reply]
Sorry if I'm making a mistake here, but I think the formula
is not correct. Let n=4 (number of people) and r=3 (number of days in the year). The number of ways to get at least one untaken day is the number of ways to get 2 untaken days (=3) plus the number of ways to get 1 untaken day (=3×24), for a total of 51 out of 34=81 possible arrangements. But the above formula gives
due to the alternating signs term (-1)r-k, whereas every term in the numerator except the last should have a minus sign. Duoduoduo (talk) 13:56, 23 September 2012 (UTC)[reply]
So, here the formula gives 15/27 for the probability. Let's then count the number of ways to arrange the 4 persons so that you have one or more untaken days. I can put all four on the same day, there are 3 ways to do that. Then I can divide the group of 4 into one group of 3 and one of one and put these two groups on two days. There are 4 ways to make two such groups and there are 3 ways to choose a day for the group of 3 and having made that choice, 2 ways to choose a day for the remaning person. So, there are a total of 4*3*2 = 24 ways for such a distribution. Finally we can divide the four into two groups of 2, there are binomial(4,2)/2! = 3 ways to do that (we divide by a symmetry factor of 2! so that interchanging the dates of the two groups yields configurations that are not already accounted for by the different ways one can divide the persons in the two groups). Given the two groups there are 3 ways to choose a date for one group and given that choice, 2 ways to chose a date for the other. So, there are a total of 3*3*2 = 18 such possibilities. There are thusa total of 3 + 24 + 18 = 45 possibilities, the probability is thus 45/81 = 15/27. Count Iblis (talk) 17:01, 23 September 2012 (UTC)[reply]
You're right--thanks! Duoduoduo (talk) 19:54, 23 September 2012 (UTC)[reply]

cells within a table

[edit]
A B
C D
E F
G H

The above table has 2 columns and 4 rows. In the above example I have assigned 8 different values to the 8 cells of that table. Let us say that we can rearrange the values at will. By rearranging the values, how many different arrangements are possible? Bus stop (talk) 19:46, 21 September 2012 (UTC)[reply]

see permutation. Widener (talk) 21:53, 21 September 2012 (UTC)[reply]
Thanks, Widener. That number surprises me as I would have guessed a far lower number. By the way I see the number at Factorial. Bus stop (talk) 01:31, 23 September 2012 (UTC)[reply]
A B C D E F G H
Followup question: Does the same calculation apply in the case of the above arrangement? Bus stop (talk) 11:06, 23 September 2012 (UTC)[reply]
Yes. The formula is not based on the physical arrangement. The idea is this: There are 8 choices for where to put A. After A has occupied a box, there are 7 choices for where to put B. So we could have had A in the first box and B in any of 7 other boxes, or we could have had A in the second box and B in any of 7 other boxes,...,so for each of 8 possibilities for A there are 7 possibilities for B, hence we have 8×7 possibilities so far. Then for each of those 8×7 possibilities there are 6 remaining possible choices for where to put C, giving 8×7×6 possibilities so far. And so on until the end, where we have 8×7×6×5×4×3×2×1 possibilities. Duoduoduo (talk) 13:36, 23 September 2012 (UTC) possibilities possibilities[reply]
Thank you. That is really interesting. I have to think about that. Bus stop (talk) 14:08, 23 September 2012 (UTC)[reply]

Friendship combinations

[edit]

Let say there are 6 people: A, B, C, D, E, F. Each of them has 2 internet friends in the group. None of them has any internet friend outside of the group. How many different ways can this happen? I already know the answer which is 70 but I'm confused on how to find the answer. Can anyone explain to me in details how to get the answer? Thanks!65.128.190.136 (talk) 21:23, 21 September 2012 (UTC)[reply]

I find problems like this usually require some fiddling around. A special case is when you have two groups of three; there are of those. WLOG you can look at the group of three containing A - then you vary the other two. Widener (talk) 22:05, 21 September 2012 (UTC)[reply]
You could do this systematically by starting with A, then going through all possible pairs that could be both partnered with A. Then for each person in each of those pairs, you could go through all possible pairs that could be partnered with them - this process will terminate when you get back to someone you have already considered. That's the brute-force approach; there may be a quicker approach but I'm not aware of it off the top of my head. Widener (talk) 22:17, 21 September 2012 (UTC)[reply]
Think of the 6 people as points/nodes; friendship is designated by connecting two points/nodes. Given the condition that each person has exactly 2 friends, you need to connect them with lines so that every point/node is paired off with 2 other points/nodes. Then there are only two possible shapes that these nodes can take that satisfy these conditions: 2 rings/circles of 3 points/nodes each, or 1 ring/circle of 6 points/nodes. Now consider each of those shapes in turn:
  • 2 rings/circles of 3 points/nodes: You need to select 3 out of 6 points/nodes for the first ring/circle. Then, since there are two rings/circles and order doesn't matter, you need to divide by the possible number of ways to order those 2 rings/circles:
  • 1 ring/circle of 6 points/nodes: The general formula for a ring permutation is (n - 1)! / 2 = 5! / 2 = 60. (To see why the formula is thus, consider that after choosing any arbitrary node in the ring as your starting point, you have 5 nodes left to order, so 5!, but then you have to account for the shape being a circle and looping back to the beginning, so you have to divide by 2 since clockwise and counterclockwise orderings are equivalent upon reflection.)
10 + 60 = 70, and there's your answer.
SeekingAnswers (reply) 22:31, 21 September 2012 (UTC)[reply]
Nice!65.128.190.136 (talk) 23:06, 21 September 2012 (UTC)[reply]
P.S. The problem is equivalent to asking for the number of undirected 2-regular graphs given n labeled nodes (sequence A001205 in the OEIS), where in this case n = 6. Also, the number of partitions of n into parts of size at least 3 (sequence A008483 in the OEIS) is useful in the calculations for determining how many shapes you need to consider. —SeekingAnswers (reply) 04:28, 22 September 2012 (UTC)[reply]

nPr?

[edit]

How do I calculate nPr by hand? Let say in Ti 89 calculator, I type in nPr(9 , 2) = 72. So how can I do it without the calculator? Thanks!65.128.190.136 (talk) 23:06, 21 September 2012 (UTC)[reply]

, or or . Widener (talk) 23:23, 21 September 2012 (UTC)[reply]
Or in simpler terms: P(15,4)=15*14*13*12, just multiply, first number is where you start with, second one is the number of factors to use. P(12,3)= 12*11*10 you get the idea. Ssscienccce (talk) 01:41, 22 September 2012 (UTC)[reply]
Wasn't this discussed on NPR ? :-) StuRat (talk) 01:44, 22 September 2012 (UTC) [reply]
Facepalm... all right, I laughed a little. --Kinu t/c 04:36, 22 September 2012 (UTC)[reply]