Wikipedia:Reference desk/Archives/Mathematics/2009 August 3

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.

August 3

how many ways are there of arranging 8 pairs of socks on a clothesline so that no two socks from a pair are next to each other?

The subject says it all. How many ways are there of arranging 8 pairs of socks on a clothesline, so that no two socks from a pair are next to each other? The clothesline is "open" (it's not circular) and there is no distinction between left and right socks. This is not homework. —Preceding unsigned comment added by 82.234.207.120 (talk) 00:02, 3 August 2009 (UTC)

My guess: 1394852659200

16 * 14!? I'm sure it's not right though, but I think it's a good estimate. 65.184.21.210 (talk) 04:31, 3 August 2009 (UTC)

Inclusion-exclusion. Let n pairs of socks be given. Let's count the wrong arrangements of them: for k from 1 to 2n-1 call A_k the configurations in which there is a pair of socks occupying the k-th and the k+1-th place. We need to count the cardinality of any intersection of r of these sets $A_{i}$: for $1\leq i_{1}<i_{2}<..i_{r}\leq 2n-1$ the set $A_{i_{1}}\cap ..\cap A_{i_{r}}$ is either empty (which happens if and only if $i_{h+1}=i_{h}+1$ for some h), or it has cardinality

$|A_{i_{1}}\cap ..\cap A_{i_{r}}|={\frac {n!}{(n-r)!}}{\frac {(2n-2r)!}{2^{n-r}}}$.

Indeed, in the latter case you can put r pairs of socks in ${\frac {n!}{(n-r)!}}$ ways in the positions $i_{1},i_{1}+1$ (first pair); $i_{2},i_{2}+1$ (second pair),..$i_{r},i_{r}+1$ (r-th pair). The remaining 2n-2r positions are occupied freely by the remaining n-r pairs in ${\frac {(2n-2r)!}{2^{n-r}}}$ ways. This is agreable in that the cardinality only depends on r, and all you need to know is how many non-zero terms are there in the r-th sum of the I-E formula. That is, how many r-subsets of {1..2n-1} with no consecutive elements are there? If you think, there are ${2n-r \choose r}$ of them. Now you can put everything together and write a formula for a(n)= the number of ways n pair of socks can be made in a clothline according to your rule. After computing the first 8 or 10 values of a(k), you can put them in the OEIS [1] and you will surely find more info. --pma (talk) 10:34, 3 August 2009 (UTC)

Spoiler alert: it's A114938. -- BenRG (talk) 10:48, 3 August 2009 (UTC)

;) So, from the computation above I got

$a(n):=\sum _{r=0}^{n}(-1)^{r}{n \choose r}{\frac {(2n-r)!}{2^{n-r}}}$;

the OEIS gives the equivalent

$a(n):=\sum _{r=0}^{n}(-1)^{n-r}{n \choose r}{\frac {(n+r)!}{2^{r}}}$.

--pma (talk) 11:34, 3 August 2009 (UTC)

what is a quarternion?

What is a quarternion?? I'm quite familiar with the concept of complex numbers, their notation in Euler's form, their calculations on complex plane, their extended application in solving geometric problems et cetera. Out of curiosity, I googled if there was a bigger set of numbers that surpassed the concept of complex numbers, and it came up with quarternions. I've read and reread wikipedia's article on quarternions, and it describes their basic calculations and applications to 4 dimensional space quite thoroughly But it seems that the author had written the article on the basis that all the readers are at least familiar with the concept of i, j, and k, and I just can't grasp the concept of the "extra" imaginary parts. How can there be another imaginary number(s) besides the common "i" where j^2 and k^2 both equal -1? I thought that polynomials to the nth degree only had n roots, and as a result, shouldn't the polynomial P(x)=x^2 +1 have only two roots i, -i? And granted that these imaginary numbers j, k do exist, why did mathematicians define them so that ijk=-1? And why was it ever invented (or thought of) anyway? Aren't complex numbers enough? I just can't understand it, and the curiosity's killing me! Can anybody explain these concepts to me in layman's terms (so to speak) so that i can at least understand the basic concept of quarternions? Please enlighten me! Thanks----Johnnyboi7 (talk) 11:23, 3 August 2009 (UTC)

In the sense that you can invent any mathematics you so choose, so long as you can provide a consistent framework for them, why NOT invent such a thing as quaternions, octonions etc.? They are interesting fields of study in their own right. If I recall correctly quarternions were "invented" for the purpose of describing physical quantities in 3 dimensions, so were completely nothing to do with roots of polynomials. Just try to separate out those ideas in your head.

In physics and applied mathematics quarternions came to be almost entirely replaced by vectors in R^3. Quarternion multiplication (of the pur imaginary part) follows the same rules as the cross product in vector multiplication. In fact, in the sense that all hypercomplex numbers are isomorphic to n-dimensional vectors with some extra structure on them, one can define any type of number at all, but only a few of them permit a structure that is both consistent and interesting to study. Zunaid 11:43, 3 August 2009 (UTC)

They are quite popular in computer games and graphics because they don't have any funny points in their representations of rotations, they are much more stable than trying to do it with the usual 3d formulae, see Quaternions and spatial rotation Dmcq (talk) 12:04, 3 August 2009 (UTC)

In a commutative field, a quadratic equation can have only two solutions. Some rings are not commutative fields. A simple example is the integers mod 8. In that ring, the quadratic equation x² = 1 has four solutions. And the same thing happens in various rings of matrices.

The book Visualizing Quaternions by Andrew J. Hanson, published in 2005, treats present-day applications to geometry and engineering, including computer graphics. Michael Hardy (talk) 12:06, 3 August 2009 (UTC)

ijk=-1 doesn't have to be taken as a definition, it can be deduced from some basic assumptions. Just assume there is one extra square root of -1 and that the concept of the modulus of a number extends from complex numbers in the obvious way (and has the same basic properties) and everything else just follows. Consider $(i+j)^{2}=i^{2}+ij+ji+j^{2}=ij+ji-2$ (I'm keeping ij and ji separate because I know what is coming next). The modulus of i+j is ${\sqrt {2}}$, so we know the modulus of ij+ji-2 must be 2, the triangle inequality gives us |ij+ji-2|=<|ij+ji|+2, so ij+ji must be zero, ie. ij=-ji. Then consider (ij)² and you'll find you need to introduce a k and that ijk=-1. So, the quarterions really are the obvious way of extending the complex numbers to have extra square roots of -1. --Tango (talk) 12:43, 3 August 2009 (UTC)

You know the way you can interpret rotation around a circle as multiplication by a complex number? Quaternions are the same way except it's rotation (in some arbitrary direction) around a sphere in 3-space. John Baez has an interesting article about quaternions and their generalization to octonions, sedenions, and so forth. WP's article History of quaternions might also be of interest. 67.117.147.249 (talk) 15:21, 3 August 2009 (UTC)

There are ways of seeing the quaternions which are purely mathematical in nature (mathematically, computations in the quaternions are pointless unless the computations are done for a reason - compare to the complex numbers). Three-dimensional Euclidean space has 3 "axis" and thus any point in this space can be uniquely described by three coordinates. Therefore, (1, 2, 3) or (5, 3.424, 0) are points in three-dimensional Euclidean space. These points can be also written as 1i + 2j + 3k and 5i + 3.424j + 0k, respectively. Think of four-dimensional Euclidean space as simply adding another axis, so that (1, 2, 3, 4) can be written as 1 + 2i + 3j + 4k. The natural question to ask now, is how we can "multiply" two points in 4-dimensional Euclidean space. Certainly we may use real number multiplication so that (for example):

$(1+2i+3j+4k)(0+2i+0j+0k)=2i+4i^{2}+6ji+8ki$

Notice how we have used real number multiplication to define "quaternion multiplication". Now it is necessary to compute $i^{2},ji,andki$. It should be possible to describe these products in terms of i, j and k, only so that the final product is also a quaternion. In general, defining a "nice multiplication on a set" (such as {1, -1, i, -i, j, -j, k, -k} as we have done) and extending it to a multiplication of arbitrary "linear combinations" of elements in the set (1 - 2i + 3j - 9k is an example of a linear combination) defines a Group algebra over a field. Group algebras are very important since they occur in character theory.

There is yet a more mathematical way to view the quaternions. Notice how each complex number can be associated to an "inverse"; that is, given a complex number z, we can find a w, such that:

$zw=wz=1+0i$

We think of w as 1/z, intuitively. Notice also that the complex numbers form a two-dimensional vector space over the real numbers (in milder language, this means that any complex number can be described in terms of 1 and i. The complex numbers 2(1) + 3(i), 5(1) + 7(i) and 0(1) + 0(i) serve as examples). These two facts (together with associativity of multiplication on the complex numbers) implies that the complex numbers forms a finite dimensional (two-dimensional, in fact), associative division algebra (the existence of an inverse for every complex number implies "division" is possible) over the real numbers. A theorem of Frobenius asserts that there is only one other non-trivial mathematical object having this property - the quaternions (the real numbers are a trivial case). This characterizes the quaternions completely. Another consequence is that one cannot move to higher dimensional analogs of the complex numbers (although the octonions seem to constitute such an example, for instance, the multiplication is not associative so it fails to be a higher dimensional analog). Hope this helps. --PST 04:52, 4 August 2009 (UTC)

Notice though, that the quarternions are not a group algebra. The real group algebra constructed from the quarternion group G would be an 8-dimensional algebra with $1\in G$ and $-1\in G$ linearly independent. All four dimensional group algebras are commutative since all the groups of order 4 are commutative. Aenar (talk) 12:27, 5 August 2009 (UTC)

Another lovely complex integral

Hi. I've been knocking my head against the following problem: Prove that $\int _{0}^{\infty }{\frac {\ln(x)}{x^{2}-1}}\,dx={\frac {\pi ^{2}}{4}}$.

The idea (as I see it) is to make some complex function, $f(z)={\frac {\operatorname {L} (z)}{z^{2}-1}}$, where L is some appropriate branch of the complex logarithm, one that restricts to the real natural log on the positive real axis. Then we cleverly choose a contour, avoiding singularities of f, apply the residue theorem, rinse for 5 minutes in cold running water, and solve for our integral. I either keep choosing the wrong contour, and/or the wrong branch or Log, and/or I mess up the calculus. I keep getting imaginary numbers, 90° off from the desired value.

The function has a removable singularity at $z=1$, which is taken care of by setting $f(1)={\tfrac {1}{2}}$, and a simple pole at $z=-1$, with residue $\operatorname {Res} (-1,f)=1-{\tfrac {\pi i}{2}}$. I need a contour that includes a chunk of the positive real axis, and then I can take limits. I also think I should stay away from the pole at -1. My latest attempt is as follows:

Attempt using a weird contour

Let R and r be two positive real numbers, larger and smaller than 1, respectively. Define the contour $\gamma =\gamma _{1}+\gamma _{2}+\gamma _{3}+\gamma _{4}+$, where $\gamma _{1}$ is a straight line from ir to R + ir, $\gamma _{3}$ is a straight line from R-ir to -ir, $\gamma _{2}$ and $\gamma _{4}$ are the obvious (positively oriented) arcs centered at 0. This contour avoids the positive real axis, and thus lies in the domain of the function $\operatorname {L} (z)$, a branch of the logarithm that maps onto $\left\{x+iy\,|\,0\leq y<2\pi \right\}$, discontinuous on $\left[0,\infty \right)$. This branch satisfies the identity $\operatorname {L} (t-ir)={\overline {\operatorname {L} (t+ir)}}+2\pi i$, for $t\in \mathbb {R} ,r\in \left[0,\infty \right)$. (We only care about 0 < r < 1.) Our pole lies inside the contour, and the winding number is 1, so we have: $\int _{\gamma }f(z)\,dz=2\pi i\,\operatorname {Res} \left(-1,f\right)=2\pi i\left(1-{\tfrac {\pi i}{2}}\right)=\pi ^{2}+2\pi i$ This leads to: ${\begin{aligned}\pi ^{2}+2\pi i&=\lim _{R\rightarrow \infty \atop r\rightarrow 0}\int _{\gamma }f(z)\,dz\\&=\lim _{R\rightarrow \infty \atop r\rightarrow 0}\left(\int _{\gamma _{1}}f(z)\,dz+\int _{\gamma _{2}}f(z)\,dz+\int _{\gamma _{3}}f(z)\,dz+\int _{\gamma _{4}}f(z)\,dz\right)\\&=\lim _{R\rightarrow \infty \atop r\rightarrow 0}\left(\int _{\gamma _{1}}f(z)\,dz+\int _{\gamma _{3}}f(z)\,dz\right)\end{aligned}}$ That last line works because $\gamma _{2}$ and $\gamma _{4}$ vanish as R and r go to their limits. The trick now is to express the $\gamma _{3}$ integral in terms of the $\gamma _{1}$ integral. Thus, we parameterize them as $\gamma _{1}(t)=t+ir$, $\gamma _{3}(t)=R-ir-t$, letting t run from 0 to R in both cases. Now: ${\begin{aligned}\int _{\gamma _{3}}f(z)\,dz&=\int _{0}^{R}{\frac {\operatorname {L} (\gamma _{3}(t))}{\left[\gamma _{3}(t)\right]^{2}-1}}{\dot {\gamma _{3}}}(t)\,dt\\&=-\int _{0}^{R}{\frac {\operatorname {L} (R-ir-t)}{(R-ir-t)^{2}-1}}\,dt\\&=-\int _{R}^{0}{\frac {\operatorname {L} (t-ir)}{(t-ir)^{2}-1}}\,(-1)dt\\&=-\int _{0}^{R}{\frac {\operatorname {L} (t-ir)}{(t-ir)^{2}-1}}\,dt\\&=-\int _{0}^{R}{\frac {{\overline {\operatorname {L} (t+ir)}}+2\pi i}{\overline {(t+ir)^{2}-1}}}\,dt\\&=-\int _{0}^{R}{\frac {\overline {\operatorname {L} (t+ir)}}{\overline {(t+ir)^{2}-1}}}\,dt\,-\int _{0}^{R}{\frac {2\pi i}{(t-ir)^{2}-1}}\,dt\\&=-{\overline {\int _{\gamma _{1}}f(z)\,dz}}-\int _{0}^{R}{\frac {2\pi i}{(t-ir)^{2}-1}}\,dt\end{aligned}}$ Ok, whew. Putting all of that together, we get: ${\begin{aligned}\pi ^{2}+2\pi i&=\lim _{R\rightarrow \infty \atop r\rightarrow 0}\int _{\gamma }f(z)\,dz\\&=\lim _{R\rightarrow \infty \atop r\rightarrow 0}\left(\int _{\gamma _{1}}f(z)\,dz+\int _{\gamma _{3}}f(z)\,dz\right)\\&=\lim _{R\rightarrow \infty \atop r\rightarrow 0}\left(\int _{\gamma _{1}}f(z)\,dz-{\overline {\int _{\gamma _{1}}f(z)\,dz}}-\int _{0}^{R}{\frac {2\pi i}{(t-ir)^{2}-1}}\,dt\right)\\&=\lim _{R\rightarrow \infty \atop r\rightarrow 0}\left(2i\cdot \operatorname {Im} \left(\int _{\gamma _{1}}f(z)\,dz\right)-2\pi i\int _{0}^{R}{\frac {dt}{(t-ir)^{2}-1}}\right)\\&=2i\cdot \lim _{R\rightarrow \infty \atop r\rightarrow 0}\left(\operatorname {Im} \left(\int _{\gamma _{1}}f(z)\,dz\right)-\pi \int _{0}^{R}{\frac {dt}{(t-ir)^{2}-1}}\right)\end{aligned}}$

That final expression is pure imaginary, and that's why I've got the blues. If anyone has the patience and understanding to help me figure out what I'm doing wrong, I'll be deeply grateful. I can clarify, if needed, why I think each of those equal signs is true. Thanks in advance. -GTBacchus^(talk) 18:51, 3 August 2009 (UTC)

I'm entirely confused by your choice of contour, and I think that is where your problem is. It seems to me that a better choice is a quarter circle with indent at 0, running along the x-axis from e to r and along the y-axis from e to r. Then the integral round the whole contour is zero by the residue theorem. Now you get (part of) your integral on the real axis, both the curved parts will go to zero as e goes to 0 and as r goes to infinity by easy log estimates, and on the imaginary axis you'll have an imaginary contribution you can ignore and a real part that will be an arctan integral and give you the factor of pi you need. 87.194.213.98 (talk) 19:32, 3 August 2009 (UTC)

Actually, I started out using the quarter-circle you describe, but I ran into my professor partway through the calculation and I asked him about it. He suggested that including the imaginary axis as part of the contour wouldn't work, because of the "- 1" in the denominator. Since then, I have been trying to do it using the real axis + big and little arcs. However, doing it that way I had to avoid -1, which makes it awkward. I'll look again at the quarter-circle contour, and see if I can get it to work. Thank you. -GTBacchus^(talk) 20:04, 3 August 2009 (UTC)

I think your professor must have been confused about the function. The -1 is fine, it only causes problems on the negative real axis which we do not see. Trust me, I'm a doctor. 87.194.213.98 (talk) 22:01, 3 August 2009 (UTC)

Hey! here we shouldn't give medical advices --84.220.119.55 (talk) 12:03, 4 August 2009 (UTC)

With another contour: Success!

That worked out just as you said. Thanks for the advice. I'll trust myself more next time. -GTBacchus^(talk) 15:49, 4 August 2009 (UTC)

Could I hijack slightly and ask for an explanation of: "on the imaginary axis you'll have an imaginary contribution you can ignore." (in 87.194's first response)? Why can we ignore it, that is. I agree we get the answer if you do but I'm not sure why you can. 81.157.165.115 (talk) 21:59, 4 August 2009 (UTC)

I do not know if this is what 87 meant, but we can actually ignore (additive) imaginary contributions because we do know that the result is real: after all the integral of a real function is a real number (even if, as empirical rule, when computing it by the residue theorem it tends to be disrespectfully imaginary) --84.220.119.55 (talk) 22:40, 4 August 2009 (UTC)

Well, I agree that it should be real. However, if it should be real and we show that it has a complex part something has gone rather wrong. It doesn't seem sensible to just ignore the term without showing (or at least spotting a reason) why it'll vanish. 81.157.165.115 (talk) 01:54, 5 August 2009 (UTC)

84 is right, it must vanish, otherwise the residue theorem would be incorrect! 81, look at it this way: the residue theorem tells us a certain equation of the form "some number = some integrals" holds. We are free to take real or imaginary parts of this equation, and taking real parts amounts to ignoring terms we know to be pure imaginary. If the residue theorem is true then the imaginary part of the equation balances too, but this is no concern of ours since we're only interested in the real part. 87.194.213.98 (talk) 14:06, 5 August 2009 (UTC)

I appreciate that we expect a real answer for other reasons. All I'm saying is, although I agree that the imaginary part should vanish, you need to show that it has vanished if you are actually providing proof of the answer. My question is what is the reasoning behind the claim that it has vanished; it might be insultingly simple, I just don't see it. 81.157.165.115 (talk) 18:11, 5 August 2009 (UTC)

Here is a proof: f(x) = ln(x)/(x^2-1) is strictly real for real values of x. Therefore the integral of f from 0 to t must be real for positive t, and so the limit as t goes to infinity must be real (if the limit exists). It's not necessary to show it by any explicit calculation, even though you could. Rckrone (talk) 21:50, 5 August 2009 (UTC)

Good morning! --84.221.69.165 (talk) 22:30, 5 August 2009 (UTC)

[Back to left margin...] Fair enough, I agree that such a step is uneccessary but can anyone show by explicit calculation why the imaginary part vanishes. 81.157.165.115 (talk) 14:57, 6 August 2009 (UTC)

The integral you want to vanish is $\int _{0}^{\infty }\log(t)/(1+t^{2})dt$. Break it into an integral from 0 to 1 and from 1 to infinity, and make the substitution t--> 1/t in the first one. This should do it. 87.194.213.98 (talk) 16:19, 6 August 2009 (UTC)

Perfect! Thank you. 81.157.165.115 (talk) 18:37, 6 August 2009 (UTC)