Wikipedia:Reference desk/Archives/Mathematics/2006 September 10

< September 9 Mathematics desk archive September 11 >
Humanities Science Mathematics Computing/IT Language Miscellaneous 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 at one of the pages linked to above.
< August September October >


September 10 edit

Answer to a Problem edit

Ok, this is a question about a specific aspect of an extra credit thing that my math teacher gave us. We were given the following problem:

"Find an easy and useful way to determine the sum of all of the number between 1 and 500. Then, using this, determine the sum."

Now, I used the summation symbol to accomplish this as such:

 

where n=500. and then using the sum sequence feture of my graphing calculator I calculated the sum because I didn't feel like typing out all of the numbers between 1 and 500 and adding them together. Turns out, she didn't like this particular solution and asked me "well how does the summation symbol work." I was taught (by a different though very qualified teacher) that the summation symbol is just a short hand way of writing out 1+2+3 and so on. Any help would be very much appreciated and if I'm not specific enough, let me know.

Deltacom1515 01:54, 10 September 2006 (UTC)[reply]

I think your problem is that the teacher is trying to get you to use your mathematical skills, not your skills at taking advantage of the computational abilities of your graphing calculator. What you've done makes it easier for you to compute that sum. As you've noted, your calculator is doing, internally, exactly what you would have done if you'd actually typed in "1+2+3+....", which is just as much work.
What your teacher almost certainly wanted you to do is describe can be rewritten as a closed form; this is very useful for two reasons. Firstly, the closed form can be calculated much more easily (an addition, a multiplication, and a division, no matter how big "i" is). The second is that rewriting in this way allows you to do all sorts of things you can't do with a summation, which come in very useful in more advanced maths.

If you're really clever you might consider using proof by induction to show that the closed form you work out is correct :)--Robert Merkel 02:24, 10 September 2006 (UTC)[reply]

Wow, thanks for your help. I appreciate that. One thing though, which link do I click on at the colsed form page? Deltacom1515 02:34, 10 September 2006 (UTC)[reply]

Well, let's put it this way - you're not using any calculus, are you? Try Solution in closed form. Confusing Manifestation 02:53, 10 September 2006 (UTC)[reply]

Nope, no calcus is necessary. Deltacom1515 03:12, 10 September 2006 (UTC) Ok, I got it on the page [[1]] I didn't even know such a thing existed. You guys were a BIG help. Deltacom1515 03:30, 10 September 2006 (UTC)[reply]

IIRC, Gauss first noticed the technique you are trying to find, when he was a child. Dysprosia 05:12, 10 September 2006 (UTC)[reply]
Is that the story about the teacher giving the class busywork? --jpgordon∇∆∇∆ 05:21, 10 September 2006 (UTC)[reply]
Yes. Dysprosia 06:43, 10 September 2006 (UTC)[reply]
Are you saying that Gauss was the first to discover it (which I strongly doubt), or simply that he came up with it when he was a child (which is indeed well known)? -- Meni Rosenfeld (talk) 06:52, 10 September 2006 (UTC)[reply]
The latter. Dysprosia 07:33, 10 September 2006 (UTC)[reply]


Happy Numbers edit

About Happy Numbers, do they serve any practicable function or are they merely another way for mathematicians to humor themselves. (this really is a serious question, I myself came across this article and was laughing all the way through it) Autopilots 08:48, 10 September 2006 (UTC)[reply]

I have no prior knowledge of happy numbers, but this quote from the Wikipedia article suggests the latter: "The study of happy numbers is an example of recreational mathematics in that it can involve extensive mathematical knowledge, but the topic is not a central part of serious research." Note that base 10 (or any other base, other than 2) is completely arbitrary, so definitions that are based on manipulating the decimal digits of a number are very unlikely to have serious uses. -- Meni Rosenfeld (talk) 10:51, 10 September 2006 (UTC)[reply]
I have met this concept some years ago in the context of teaching UK school students about mathematical investigations. It was chosen as something which would be unlikely (at that time) to have ben encountered previously by students, so giving no advantage to students who might have read more widely than others. Apart from that pedagogical use, I think they only have recreational interest to mathematicians. Madmath789 11:03, 10 September 2006 (UTC)[reply]

Number of permutations with at least one 2-cycle edit

I was asked this question: "There are 70 people at a party and they put their names into a basket. What is the probability that two people get each-other's, if each person then picks one name from the basket." I thought this should be a high-school math puzzle, but I can't seem to find any solution to it. Mathematically, I'm asking for the number of permutations of length 70 with at least one cycle of length 2. I've looked at Stirling numbers and searched the encyclopaedia of integer sequences, but I can't find anything about this ... Any ideas? —Preceding unsigned comment added by 88.196.100.193 (talkcontribs)

Do you mean the probability that at least one pair get each other's name? Exactly one pair get each other's name? One pair in particular, and only they, get each other's name? One pair in particular, regardless of other possible matches, get each other's name? There is something of a difference.—86.132.167.165 13:00, 10 September 2006 (UTC)[reply]
It seems like the asker (a reminder: it's recommended to sign your posts by typing --~~~~) is referring to the first variant (the number of permutations ... with at least one cycle of length 2). That's an interesting question! But let's try to build a recursion. Let there be   people; let the asked number of permutations be  . If we number the people  , then for any such permutation there is a unique person who is part of one such cycle (a "pair") and whose number ( ) is the lowest. Let's call him/her the "lowest paired person" and the pair he/she is part of the "lowest pair". For every combination of   and   there are   different ways of choosing the other person to form the lowest pair together with  . The   people with lower numbers than   may be permuted, provided they don't form any pairs with anyone (by assumption). Thus, if we denote the number of permutations with the lowest paired person   and total length   by  , there is a relation:
 ,
because removing the lowest pair from a permutation with the lowest person   (and lowering the people's indices as necessary to fill in the two gaps), we get a new permutation either without any pairs or with a lowest paired person  ; there are   possible places for the person   is paired with. Now we need some initial conditions. Clearly,  . Also, for any  ,  , because if we say that the first person is paired with anyone, then there are   people who can be his/her "companions" and the other people may permute freely. To sum up:
 
To get the asked total number, we have to sum over all the possible  -s:
 
All that can be done in a table:
n a = 1 2 3 4 5 6  
1 0 0
2 1 0 1
3 2 1 0 3
4 6 2 1 0 9
5 24 12 6 3 0 45
6 120 72 48 30 15 0 285
So, the sequence   answers your question. But is there a way to calculate it more easily (such tables are quite error-prone on paper and need   of computer memory)? Let's see... (sequence A027616 in the OEIS)... we have the answer! The formula is:
 
Don't ask me to prove that right now.   Anyhow, combinatorics is fun!  Pt (T) 19:24, 10 September 2006 (UTC)[reply]
Since the question was about probabilities, don't we actually want  ? -GTBacchus(talk) 19:33, 10 September 2006 (UTC)[reply]
That's true. So, the probability is:
 
a sum which Mathematica (but not yet I) can handle:
 
Here in the numerator, we're dealing with the incomplete gamma function. Putting in  , we get:
 
By the way, there exists a limit:  .   differs from it by only  !  Pt (T) 19:53, 10 September 2006 (UTC)[reply]
(somewhat prolonged edit conflict, rendering my addition rather moot) He means, the probability that at least one pair of people got each other's names. I think I've figured out a way to solve it. It's like Pascal's triangle, but more complicated. Take the number of people, n. The nth level of the triangle (more like a pyramid) is an (n+1)xfloor(n/2+1) matrix. Each element (r,c) is the number of ways r of those people could have gotten their own name while c pairs of people switched names. The pyramid is recursive, then, with each level determined from the information in the level above. Imagine lining a group of five people up and numbering them 1-5. Mix up their names. Now add a sixth person to the line. Every possible permutation of the 6-group is identical to a permutation of the 5-group or a permutation of the 5-group plus a switch between the sixth person and one of the others. Take a particular permutation of the 5-group, with a particular (r,c) category. Adding a sixth person and allowing them to keep their name adds 1 to the (r+1,c) bin of the 6-level for each such permutation. Adding a sixth person and switching their name with someone who had kept their own name adds 1 to the (r-1,c+1) bin of the 6-level, for a total of r per permutation. Adding a sixth person and switching their name with someone who had already traded names adds 1 to the (r,c-1) bin of the 6-level, for a total of 2c per permutation. Adding a sixth person and switching their name with someone who hadn't traded names but didn't have their own name adds 1 to the (r,c) bin of the 6-level, for a total of n-r-2c per permutation. And that produces every possible 6-group permutation. So, each element (r,c)n+1 = A(r-1,c)n + B(r+1,c-1)n + C(r,c+1)n + D(r,c)n where A=1, B=r+1, C=2c+2, and D=n-r-2c. Anything that involves coordinates outside the matrix (coordinates less than zero, in this case), can be ignored or set to zero, like in Pascal's regular triangle. The level 1 matrix would be {{0},{1}}, making level 2 {{0,1},{0,0},{1,0}}, level 3{{2,0},{0,3},{0,0},{1,0}}, etc. You can get the number of permutations involving no switches by adding up column zero (0+1, 0+0+1, 2+0+0+1, etc). Subtracting that from n! and dividing by n! gives the probability that there will be at least one switch. It might be possible to get this in closed form, but I don't see how. Black Carrot 19:59, 10 September 2006 (UTC)[reply]
Searching the first few terms in the OEIS yields A027616. – b_jonas 22:10, 10 September 2006 (UTC)[reply]
Oh, sorry, I just see Pt has already found that. For the record, I calculated the terms using brute force with the following J snippet:
      (+/@:(2&e.@:(#@>)@:C."1)@:(i.@:!A.i.))"0>:i.9
which gave this answer:
      0 1 3 9 45 285 1995 15855 142695
b_jonas 22:13, 10 September 2006 (UTC)[reply]

One more question on the question: If a person draws their own name, do they return their name and draw again ? StuRat 22:38, 10 September 2006 (UTC)[reply]

On the subject of drawing one's own name, the probability of at least one person doing this tends to 1 - 1/e or 0.63212... as n tends to infinity, a result possibly better known from the "letter in envelope" equivalent problem. The similarity in result, with the square root missing, is noteworthy.—86.132.234.126 18:19, 11 September 2006 (UTC)[reply]
Thanks to a friend of mine I now know a way to prove and even generalize this property. But firstly let's prove the formula for pairs:
 .
  gives us the number of the permutations of   people, where there is at least one 2-cycle. Numbering the people as I earlier did, let   be the set of all the permutations of   people, where people with numbers   and   are paired:
 .
Here   denotes the set of all the permutations of the first   natural numbers.   is the number of different elements in the set of all possible  -s. Without loss of generality we may assume that  , because that way we already go through all the possible pairs. Let   denote the cardinality of a set (that equals the number of elements in it, since we'll only be dealing with finite sets); let   be the set of all the natural numbers  . Then:
 .
Clearly, there can be at most   pairs among   people. Let's make (for every  ) the set of all the unique collections of exactly   pairs of people (within a collection every person can be in at most one pair) and denote it by  :
 .
Now, by the inclusion-exclusion principle, we can write   as:
 .
  is simply the set of all possible permutations of the people, where the people  ,  , …,   are paired. Others may or may not be paired. Thus, the cardinality of this intersection of sets is equal to the number of possible permutations of "the others", the people not fixed with the combination of  -s and  -s. (As we fixed earlier that  , there is no way we could permute the paired people anymore.) There are, in total,    -s and    -s. So we are left with:
 ,
not depending on the particular choice of  -s and  -s! So far we have:
 .
  is the number of ways to choose   non-overlapping pairs from among our   people. Let's calculate it! Firstly, for the first people of the pairs (the  -s) there are   different possibilities. If we, for one moment, omit the requirement that the pairs must be ordered for counting, we count each pair twice, choosing the  -s completely freely from among the people not referred to by any  . As long as we take care of it a moment later, we may do so. Thus, we can choose the    -s from   people, giving us   possibilities (since order matters here, we must use the formula for permutations, not combinations). This must be now divided by the total number of different orderings of the   pairs,  , giving us:
 .
Therefore:
 
and:
 .
For   the summand is  , so after taking a   out of the sum, we get what we wanted to:
 ,
Q.E.D. This derivation can be quite readily be generalized from 2-cycles to  -cycles, where   is an abitrary natural number. Then we simply observe the patitions into  -tuples etc., the same principles apply. Thus, the number of such pemutations of   people that contain at least one  -cycle is:
 .
The probability for   people to contain an  -cycle is:
 .
I'm sure this is a known result, because, for example, the formula for   lies neatly in the OEIS (sequence A027617 in the OEIS). Now what about the limit   of this probability? Well, writing the limit of the sum as  , it's evidently just the Taylor series for   taken at  , that is,  . Thus:
 
Really, it's fun!  Pt (T) 16:15, 12 September 2006 (UTC)[reply]

Hello, I'm the one who originally posted the question, and I'm just so impressed with the quality of the response here that I have to say a big THANK YOU!!!! I was quite surprise that the integer sequence entry have almost the same keywords as I have in the title of this post, yet I was not able to find it! Anyway, thanks again for the explanations, and sorry for not signing, I will create an account :) --193.40.37.156 10:52, 15 September 2006 (UTC)[reply]

SPPS graph edit

Hi: Is it possible to do a histogram or bar chart with SPSS for a grouped frequency distribution table? Thanks much.-- Hersheysextra 20:22, 10 September 2006 (UTC)[reply]

Area Problem. Shapes etc. edit

 

Ok well I encountered this problem (I added the y to simplify some calculations a bit, but otherwise its exactly the same information i got). I tried to solve but I wasnt sure wether I had done it correctly. So I thought I'd post here for someone to maybe review it and find the faults or confirm wether its correct. So heres what I went about doing. I numbered the steps for reference in your replies.

  1. Well firstly isnce the triangles in the corners have x on both sides, we can assume they are isoceles right angled triangles, therefore the angles are 90, 45, and 45, thus meaning that all the angles in any of the shapes in this case are either 45 or 90.
  2.   (pythagorus)
  3. The white triangle in the centre of the right hand edge is (assuming the two sides identical in length are variable z)
    1.   (pythagorus)
comment - this line should be   Richard B 22:10, 10 September 2006 (UTC)[reply]
    1.  
    2.  
    3.  
  1. the L shape can now be divided into 3 segments, one square in the centre which is  , and 2 identical rectangles which are y by z. And as such the grey area consists of
    •  
  2. As such the entire grey area works out to equal this when the left part of the shape is included
    •  
  3. Therefore, the entire size of the shape should equal
    1.  
    2.  
    3.  
  4. The two triangles with their sides against the x by 2006 shaded areas two identiacal sides can be calculated (assuming the two sides identical in length are variable a)
    1.  
    2.  
    3.  
    4.  
  5. Substituting in the other formulae, to give in terms of x leaves
    •  
  6. So the formula for the entire square equals
    •  
  7. So now we have 2 formula for the entire shape, so we can substitute them together
    •  

Unfortunately this is where I got stuck. So if anyone knows where to go from here... The help would be appreciated. Philc TECI 21:15, 10 September 2006 (UTC)[reply]

You could work out the total unshaded area. It's just the sum of 5 triangles. The leftmost two triangles have a total area of 10032 - they're isosceles - and they meet at exactly half way down the shape (i.e. 2006/2). The 2 small triangles at top and bottom right corners have a total area of x2. The larger triangle on the right side has an area of (1003-x)2. So the sum of all unshaded area = x2 + 10032 + (1003-x)2.
Total area must be 2006(1003 + 2x) - so
  •  
  •  
Now it's just a quadratic in x - and straightforward to solve - one of the roots of the equation will lead to a negative length - so choose the other one. Richard B 21:55, 10 September 2006 (UTC)[reply]
You can simplify the arithmetic by introducing y = x/1003, which gives
 
Both roots are positive, but you can discard the root that is greater than 1, as this would make x greater than 1003. Gandalf61 10:45, 11 September 2006 (UTC)[reply]
I don't get the same number for the 5th white triangle as Richard B. Rather than an area of (1003-x), I have   (based on the 1-1-root2 ratio for 45-degree right triangles). Plugging this into the resulting quadratic, I get imaginary roots, as my c term is roughly double the size of Richard's. I also attempted finding the area of the shaded stuff and had imaginary roots there, too. Am I missing something re: that (1003-x) area triangle? — Lomn | Talk 15:35, 11 September 2006 (UTC)[reply]
But you do get the same as me for the 5th white triangle. My area is (1003-x)2 - yours is;
 
 
 
 
 
 
So we actually do agree on the area of the 5th triangle Richard B 16:42, 11 September 2006 (UTC)[reply]
I seem to have skimmed right over the "squared" term in your original math. That clears it up. — Lomn | Talk 16:57, 11 September 2006 (UTC)[reply]
Take the lower half of your diagram. By symmetry, it's 5/8ths shaded as well. Label the unshaded (middle) segment on the lower edge u. Labe the unshaded upper segment on the right edge v. Then we know the following things:
  1. u = 1003. It's the height of the half we kept.
  2. x+v = 1003. Same reason.
  3. (2x + u)(x+v) = the area. This is (2x + 1003)(1003).
  4. 1/2 (u^2 + v^2 + x^2) is the unshaded area. This is 1/2 (1003^2 + (x - 1003)^2 + x^2).
  5. 1 - 5/8 = 3/8 = unshaded fraction = 1/2 (1003^2 + (x - 1003)^2 + x^2) / ((2x + 1003)(1003))
Solving the resulting quadratic ( 8x^2 - 14042x + 5030045 = 0) gives x = 1003/2 and x = 5014/4. -- Fuzzyeric 23:04, 11 September 2006 (UTC)[reply]

How can you prove the top half and bottom half are symmetrical, or that they're even halves for that matter?

because the triangle in the corner are isosceles right angled, meaning the diagonal lines are all at 45 degrees, therefore they can only intersect at one point, the line of symettry. Philc TECI 20:33, 27 September 2006 (UTC)[reply]

Earwig apartment complex edit

This is a bit mathsy, I guess, so it goes here. If there were some tiny people whose eyes were at the level of an earwig's, and we built them a building that was the same height as the average human male (average for us, not for the earwig-people :P), how many stories would it have? Vitriol 21:17, 10 September 2006 (UTC)[reply]

As many as you give it. You didnt define a storey height. Philc TECI 21:32, 10 September 2006 (UTC)[reply]
I thought there was a standard size or something. More fool me, I guess. Vitriol 22:05, 10 September 2006 (UTC)[reply]

Well, we can approximate something, I suppose. Let's say an earwig's eyes are at 1cm, and that an average human's eyes are at 150 cm. So we're at 1/150 scale. So, if we were earwig people, your question could be rephrased as: how many storeys is a building that's the height of a giant person 150 times normal size. If normal is around 5'6" (switching from metric to imperial), then 150 x normal would be 825 feet, which is like an 80 storey building or so, roughly? -GTBacchus(talk) 22:12, 10 September 2006 (UTC)[reply]

That sounds good, except for the average story being 5'6". I'd say the interior distance from floor to ceiling is typically more like 7 feet, with an additional foot for the thickness of the floor, for a total story height of 8 feet. This is for residential structures, industrial structures tend to have stories more like 10 feet high. StuRat 22:23, 10 September 2006 (UTC)[reply]
I didn't take the average storey to be 5'6", that was the height of an average human. I took the average story to be about 10 feet: hence 825' ~ 80 storeys. If it's more like 8 feet per storey, that'd be a 100 storey apartment building. -GTBacchus(talk) 00:54, 11 September 2006 (UTC)[reply]

calculate edit

there is $100,000 invested in a c.d. at 5.1 interest for 5 months....how is the money earned calculated....thanks

More info is needed, is that 5.1% interest annually, compounded monthly ? StuRat 22:27, 10 September 2006 (UTC)[reply]
Sounds very much like a homework question. We do not solve such questions for people (they would learn nothing that way), but we are prepared to give hints if people tell us how far they have got, and where they hit a snag ... Madmath789 22:25, 10 September 2006 (UTC)[reply]
See compound interest and interest Richard B 22:32, 10 September 2006 (UTC)[reply]