Wikipedia:Reference desk archive/Mathematics/2006 October 7

From Wikipedia, the free encyclopedia

< October 6	<<Sep | October | Nov>>	October 8 >

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.

Contents 1 quadratic equation 2 I'm taking image requests 3 Quadratic Equations 4 Modular arithmetic 5 Permutations with and without repetitions

[edit] quadratic equation

who has given the method to solve the quadratic equation?

See the article, quadratic equation. - Fredrik Johansson 07:03, 7 October 2006 (UTC)

[edit] I'm taking image requests

bumped from October 2 - I'm still open to requests

This seemed like the ideal place to ask because I know the right people are going to read this.

I've been very bored lately and I feel like contributing with some nice images to Wikipedia. Animations and 3D images are more fun to do, so those are preferred. Anything is cool as long as they're maths\physics related. Oh, and here are some sample images I created to replace the ugly old ones or to add new content:

Better-looking sphere instead of Image:Sphere.jpg	Better-looking torus instead of Image:Torus.jpg	Villarceau circles	Additive synthesis of a square wave
	Gyroscope in operation	Gyro wheel animation

Also, check my gallery to see what sort of thing I can do.

So, do you guys have any suggestions for images, graphics or diagrams that need to be improved or replaced? :) ☢ Ҡi∊ff⌇↯ 00:19, 2 October 2006 (UTC)

Just the other day there was a complementary posting at Wikipedia talk:WikiProject Mathematics#Suggestion to improve most math articles. I also note that John Reid, member of WikiProject Mathematics, states on the participants' list: "I do have considerable ability in graphic design and an interest in clear illustration. Yes, I take requests.", while Carl Peterson professes: "Will take requests for geometry-based vector images."

Now wouldn't it be cool if there was something like a subproject Wikipedia:WikiProject Mathematics/Images of a number of people who collaborate on improving the imagery of the mathematical articles in a coordinated fashion? A good idea might be to start with the more basic ones that are likely to be read by people without advanced mathemarical background, such as those listed on Wikipedia:Vital_articles#Mathematics.  --Lambiam^Talk 00:47, 2 October 2006 (UTC)

Follow-up: I see that in fact such a subproject exists: Wikipedia:WikiProject Mathematics/Graphics. It's not dead, but it looks like it could use more life.  --Lambiam^Talk 01:03, 2 October 2006 (UTC)

Thanks, I joined the project. I see they want an animation of a torus morphing into a coffee mug. I'll give it a shot. :) ☢ Ҡi∊ff⌇↯ 02:59, 2 October 2006 (UTC)

Hey Kieff! Well, since you asked, I've had Flexagons on my wishlist for almost a year. It would be really neat if you could show an animation of how to fold one, say, a hexaflexagon. --HappyCamper 03:46, 2 October 2006 (UTC)

I'm having problems with this one, but I'm still trying. ☢ Ҡi∊ff⌇↯ 08:31, 7 October 2006 (UTC)

Interesting. I'll have to make one of those to see how the folding goes, but I'll give it a shot. Oh, and to the right you'll see the coffee mug morphing into a torus that I just finished doing. :) ☢ Ҡi∊ff⌇↯ 06:09, 2 October 2006 (UTC)

Hey thats good stuff. I cant even draw a straight line. What I been looking fo for months is just a simple (scalable) circle that can be put onto pages. There is one page in particular that desperately needs some good diagrams and Im not capacble of doing them. THat page is Relativistic electromagnetism!--Light current 21:10, 2 October 2006 (UTC)

Will this one do? (White interior, transparent exterior) I didn't make it, it was already there. —Bromskloss 09:56, 3 October 2006 (UTC)

An illustration of gimbal lock would be great.--gwaihir 09:14, 7 October 2006 (UTC)

I'm thinking of it, just gotta find a nice way to illustrate it. Any ideas are welcome. ☢ Ҡi∊ff⌇↯ 11:51, 7 October 2006 (UTC)

[edit] Quadratic Equations

When using a formula, we often know the value of one variable to a greater degree of accuracy than we know the others. In your opinion, what affect, if any, does it make on our use of a formula if we know the value of one variable to a greater degree of accuracy than another? -13:37, 7 October 2006 (UTC)~***

In whose opinion? Is this question about propagation of uncertainty? —Keenan Pepper 17:20, 7 October 2006 (UTC)

I suggest trying out all the minimum and maximum values, given the error range on each, to see how they effect the result. StuRat 20:37, 7 October 2006 (UTC)

[edit] Modular arithmetic

Does this have a theorem of some sort?

x42bn6 Talk 16:33, 7 October 2006 (UTC)

In modular arithmetic, isn't two integers x and always equivalent (by definition)? I believe so, and therefore think that your statement follows directly from that definition, and does probably not have a name. But, I could be wrong, of course. :-) —Bromskloss 17:11, 7 October 2006 (UTC)

Sorry, I was looking for a name or something. x42bn6 Talk 17:12, 7 October 2006 (UTC)

There's nothing to be sorry for. I just don't think there is a name for it. —Bromskloss 18:01, 7 October 2006 (UTC)

Depending on why you ask, you may want to read up on Congruence relation and Modular exponentiation.  --Lambiam^Talk 21:14, 7 October 2006 (UTC)

Mm, doesn't help.  :( Busy computing both sides of the equation using Haskell and getting wrong results.  :( Never mind, thanks for the help. x42bn6 Talk 11:04, 8 October 2006 (UTC)

You could call it the binomial theorem. Let x = sn + t where t = xmod n. Then, but all terms of this sum except for the one with k = 0 is divisable by n, and this term is t^y so indeed .

On the other hand, that's not IMO the "real" reason why this is true. I think of this as just a direct consequence of that if and then . Applying this repeatedly with a = x, b = x^{y − 1}, a ^* = amod n and b ^* = bmod n, we get by induction that . – b_jonas 11:59, 8 October 2006 (UTC)

[edit] Permutations with and without repetitions

Shuffle a standard deck of cards. What is the probability that two cards of the same value (e.g. two aces) are next to each other? More generally, suppose you have X equivalent copies each of Y different kinds of objects. How many of the permutations have repetitions? Is there a closed–form solution? —Keenan Pepper 17:26, 7 October 2006 (UTC)

The problem is, whether one card has an adjacent match isn't an independent event with whether another card has an adjacent match. So, it would necessary to look at every possible deck arrangement which has a match, and divide by the total number of possible deck arrangements (52!). StuRat 20:29, 7 October 2006 (UTC)

Yup, that's what makes it hard. Anyone have an answer, a reference, or just a glimmer of insight? BTW, we're ignoring suits, so the total number of permutations is not 52! but .

Have you tried working it out for small X / Y and looking the result up on OEIS? – Meni Rosenfeld (talk) 21:49, 7 October 2006 (UTC)

For the case Y = 2 this is the number of ways X couples can sit in a row without any spouses next to each other (sequence A007060 in OEIS). There are no OEIS entries for Y = 3 or Y = 4.  –Lambiam^Talk 22:10, 7 October 2006 (UTC)

I think I may be switching X and Y here compared to the intention of the question. I'm also not sure I interpreted "ignoring suits" correctly.  –Lambiam^Talk 22:30, 7 October 2006 (UTC)

Yes, I said X was the number of copies of each kind, and Y the number of kinds, so (sequence A007060 in OEIS) is for X = 2. For Y = 2 there are always exactly 2 permutations without repetitions. By "ignoring suits" I meant that permutations of the cards with the same sequence of values (ace, two, three...) are considered equivalent, even if the suits of the cards (clubs, diamonds...) are different. It doesn't matter for the probability, because both the numerator and denominator would change by the same factor of (4!)^13. —Keenan Pepper 22:42, 7 October 2006 (UTC)

The sequence A007060 is without upfront division; with division you get [1, 0, 2, 30, 864, ...], which is not in OEIS.  –Lambiam^Talk 22:55, 7 October 2006 (UTC)

Also for X = 3 (throw out all diamonds) ([1, 6, 30, 174, ...]) I get no hit in OEIS.  –Lambiam^Talk 23:01, 7 October 2006 (UTC)

For a card deck, X = 4, Y = 13, I find that 63394531038905867912088 out of 92024242230271040357108320801872044844750000000000 permutations are repetition–free, giving a probability of 0.68888946545492·10^–27.  –Lambiam^Talk 02:34, 8 October 2006 (UTC)

Care to tell us how you've got this result? Some sort of sieve? It seems too large to be calculated with brute force. – b_jonas 12:55, 8 October 2006 (UTC)

Yes, the number itself is next to useless without some explanation, or a symbolic representation with factorials or something. —Keenan Pepper 02:32, 9 October 2006 (UTC)

First, I managed to get confused again about the roles of X and Y; the number 63394531038905867912088 above is for X = 13, Y = 4. The correct number for X = 4, Y = 13 is 4184920420968817245135211427730337964623328025600, which gives a much higher probability for a stutter–free random shuffle: about 4.5%.

Now about the method. Calling the card "values" A, B, C, ..., M, we need to count the number of strings containing exactly 4 of each of those that are stutter-free. One such string is CIFBAIBEALKCHGDGMLELIFCFMJDGDEMJFEKJBMLJDHKGIHBHACKA. Let f_v(a,b,c,...,m) stand for the number of stutter-free sequences containing a As, b Bs, c Cs, ..., and m Ms, and ending in the value v. So the length of the sequence is a+b+c+...+m. The string above contributes for one to f_A(4, 4, 4, ..., 4). By summing f_v(4, 4, 4, ..., 4) for all 13 possible values of v we get the desired result.

How much is f_A(a,b,c,...,m)? If a is 0 (or less), the count is 0: there are no sequences that end in A but contain no As. If a = 1 and all of b ... m are 0, we need to count the stutter-free sequences of length 1 that end in A. That is easy: there is precisely one such sequence. Otherwise. if a is at least 1 and the sequences have length > 1, each sequence counted can be turned into a shorter non-empty stutter-free sequences by removing the last element. Each such shortened sequence can end on any element except A. Conversely, each of the sequences counted by f_B(a–1,b,c,...,m) – or any other element than B, except of course A itself – can be lengthened by appending A to it. So then f_A(a,b,c,...,m) = f_B(a–1,b,c,...,m) + ... + f_M(a–1,b,c,...,m).

But wait, there are many symmetries. For one, if we permute the numbers b,c,...,m in f_A(a,b,c,...,m) it will not affect the outcome. So, using ((...)) for a multiset notation, in which ((1,3,3)) = ((3,1,3)), which is different from ((1,3)), we can, instead of f_A(a,b,c,...,m), consider f_A(a, ((b,c,...,m))). Similarly f_B(b, ((a,c,...,m))), and so on. But surely f_A(p, ((q,c,...,m))) is the same as f_B(p, ((q,c,...,m))). We don't need the subscript to f. Just find f(4, ((4,4,...,4))) – with 12 elements in the multiset – and multiply the result by 13.

Now, in general, how to find f(a, M), in which M is a multiset? We apply the earlier considerations to the new representation making use of the symmetries. If a = 1 and M contains no positive elements, the result is 1. Otherwise, f(a, M) is the sum over the elements v in M of f(v, M – ((v)) + ((a–1))), in which + and – are (also) used for multiset subtraction and addition in the obvious way. So f(a,((b,c,...,m))) = f(b,((a–1,c,...,m))) + ... + f(m,((b,c,...,a–1))).

We now have a recurrence relation that allows us to compute the function values. Doing that naively takes time proportional to the result value. The crucial step is to use the technique of dynamic programming, or tabulation, or memoization, or function caching, or whatever you wish to call it, to avoid repeatedly computing the function value for the same arguments. This can be finessed by discarding any number 0 from the multiset, and by recognizing that in the summing process equal values taken from the multiset will give equal results. But also without that the process is now fast enough to produce the sought result quickly enough.  --Lambiam^Talk 04:41, 9 October 2006 (UTC)

I think you had a slight mixup in the second paragraph - it should read: "...we need to count the number of strings containing exactly 4 of each of those...", and the following string should have 4 of each of A through M. -- Meni Rosenfeld (talk) 07:33, 9 October 2006 (UTC)

You are absolutely right. I've applied the correction in situ. There must be some Freudian reason why I don't mind having the Jack of Hearts and the Jack of Spades next to each other, but don't want the Queen of Hearts next to the King of Hearts. I guess I'm confused by the misleading analogy to the spouse-seating problem.  --Lambiam^Talk 11:10, 9 October 2006 (UTC)

So, the questions remain: Is there a closed-form solution? Can it be shown that there is not a closed-form solution? Is it an open problem? —Keenan Pepper 22:57, 9 October 2006 (UTC)

I think it is an open problem. If there is a closed-form solution, it's not going to look pretty, offering little incentive to look really hard for one.  --Lambiam^Talk 20:16, 10 October 2006 (UTC)