Wikipedia:Reference desk/Archives/Mathematics/2006 November 9

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.

November 9

Cycle notation

I'm having trouble getting through the article on cycle notation. If I have an ordered set {a,b,c,d}, and I apply the permutation (1,2,3) to it, what do I end up with? What about the permutation (1,2)(1,2,3), or something like that with two permutations? The "examples" section in the article doesn't help me much. (Feel free to provide a different example if you're worried that I'm doing this for homework or something, I'm just having trouble understanding the concept.) Thanks! -- Creidieki 02:24, 9 November 2006 (UTC)

I don't know if this helps.

You ask about the resulting ordering of the set... there are two reasonable things to do. The ordering can either be pushed forward or pulled back through a permutation. I remember the difference between these choices causing a lot of confusion when I studied the isometries of the square through relabelling the vertices. The professor thought one option was obvious, but I unconsciously wanted to use the other. The closest article we have is probably Active and passive transformation. I can elaborate, but does any of that possibly ring some bells? Melchoir 03:18, 9 November 2006 (UTC)

So you're saying that (1 2 3){a,b,c} could be either {c,a,b} or {b,c,a}? I was under the impression that there was a standard notation for this...I've been looking at things like the examples at the bottom of generating set of a group. There aren't really any bells for this to ring; I'm trying to do some circuit complexity homework with no background in field theory, and the professor was assuming we already knew this stuff. -- Creidieki 03:24, 9 November 2006 (UTC)

Now that I've looked for a bit longer at your addition, it's starting to make more sense. I'm still going to want to try adding some more explicit examples to the article. -- Creidieki 03:43, 9 November 2006 (UTC)

I think the standard notation would be (1 2 3){A,B,C} = {C,A,B}. Here one interprets f(A) = B as meaning that A is sent to B (or rather where B used to be), so A shows up in the B slot in {C,A,B}. On the other hand, you can interpret f(A) = B as meaning that A is turned into B, or that the A slot now has the value B, so (1 2 3){A,B,C} = {B,C,A}. I think this is the simpler option, since you're just applying f in place.

Here's an explanation for what's going on behind the scenes. An ordering of the set X = {A,B,C} is equivalent to a bijection b of X with the canonical ordered three-element set {1,2,3}. (Or {0,1,2}, depending on your background.) Given a permutation f of X, you can get a new ordering by composing b and f. You might say that the two choices correspond to whether you choose to compose b with f or f^-1. Or, and I think this is closer to the point: you can agree that it's more reasonable to always compose with f, but there's a choice of which way b goes. Is it a function b: X to 3 or a function b: 3 to X? That will determine whether you wind up forced to write b o f or f o b.

If you're just interested in the pure group theory, I wouldn't worry too much about the decision. At the very worst, it's just a choice between two equivalent representations of the same abstract structure. You can compute products and inverses and so on in whatever representation you like. For convenience, if you're reading a textbook or taking a class, then try to identify the flow and go with it. Melchoir 05:28, 9 November 2006 (UTC)

In the standard notation the elements listed in the cycle are elements of the set being permuted, and not indices. So if that set is {A,B,C,D}, a possible cycle is (A D B). Then (A D B)A = D, (A D B)B = A, (A D B)C = C, and (A D B)D = B. When this permutation is mapped over the sequence [A,B,C,D], you get [D,A,C,B]. If the same permutation is mapped over [A,B,A,C] you get [D,A,D,C]. Some confusion in terminology may arise because there is a separate notion of permuting a sequence. A sequence can be viewed as a mapping from some index set I (for example, {1,2,3,4}) to some set (for example, {A,B,C,D}). So [A,B,C,D] is the sequence S with S(1) = A, S(2) = B, etc. Now given some permutation on I, for example (1 4 2), you can apply the permutation "to" the sequence S by composing S with that permutation, giving as result S' = S o (1 4 2). So S'(1) = S((1 4 2) 1) = S(4) = D, and so on, giving S' = [D,A,C,B] as before. But applied to [A,B,A,C] we find [A,B,A,C] o (1 4 2) = [C,A,A,B].  --Lambiam^Talk 09:01, 9 November 2006 (UTC)

Ignore Melchoir's ramblings; they are irrelevant, and will only confuse you further.

Let's begin at the beginning. A permutation of an ordered set of items is a reordering of the items. For small numbers of items, it is easy to depict this graphically. Here's an example:

a	b	c	d	e	f
↓	↓	↓	↓	↓	↓
b	e	f	d	a	c

Unfortunately, this approach is bulky and inconvenient; and while it makes the mapping clear, it obscures some essential structure.

But suppose we start with the first item in the original ordering, a. We observe that a maps to b, which we could write as a→b. Continuing item by item we could "serialize" the columns of the display as a list of such before-and-after pairs. However, we know that the target of a, which here is b, must eventually be mapped, so we condense the notation. Instead of {a→b,b→e} we can write a→b→e.

Because we only have a finite number of items, eventually we must come to a target that we have already mapped. For example, in the given example we have a→b→e→a. A permutation can only reorder items, so it is impossible for two different source items to map to the same target item (the mapping is one-to-one). Therefore when we reach an already-mapped item, it must be the first in the chain. Condensing notation even further, we can write (a b e), with the understanding that the last item maps to the first one, forming a cycle.

Of course, usually that will not exhaust all the items, so we continue by picking any not-yet-used source item to begin a new cycle. In the example here, we eventually obtain three cycles: (a b e), (c f), and (d). We have exhausted the available items, so we are done. The one-to-one property of the mapping not only guarantees cycles, it also guarantees that each item appears in exactly one cycle.

The "singleton" cycles (containing only one item) convey no useful information, so long as we know the full list of items. Therefore we routinely omit these, with the understanding that any item not explicitly shown in a cycle is assumed to map to itself.

We do not have a unique notation for a given permutation, of course. For example, the cycle (f c) is a different way to write the same cycle as (c f). Also, disjoint cycles can be written in any order. However, a given list of cycles completely determines the permutation (so long as we either know the full list of items or else include singletons).

So, the existence and efficacy of cycle notation is a fairly direct consequence of the one-to-one property of permutations. But your question mixes apples and oranges, so to speak. First you give an ordered set of letters, then you ask about a permutation denoted by numbers. Instead, stick with apples, and understand that a list of cycles made of the items being permuted directly names a permutation. The one example in the article happens to take those items to be the numbers 1 through 4. Our example here is more typical.

Let's end with another example. Suppose we have a list of four items, ⟨w,x,y,z⟩, where we use angle brackets for the list so there is no confusion that this denotes a cycle. One permutation of these items is (x y z), which we can also write as (z x y). Since w is not mentioned, it maps to itself. Therefore the permutation is

w	x	y	z
↓	↓	↓	↓
w	y	z	x

A different permutation is given by the pair of 2-cycles (w z)(x y), which we can also write as (x y)(z w). This denotes the mapping

w	x	y	z
↓	↓	↓	↓
z	y	x	w

The composition of two permutations merely reorders twice, so is again a permutation. Let us apply these two in the order given, and determine a cycle notation for the result.

w	x	y	z
↓	↓	↓	↓
w	y	z	x
↓	↓	↓	↓
z	x	w	y

Beginning with w, we obtain the cycle (w z y), which leaves x as a singleton.

As a check on our calculation, we can determine the parity of these three permutations. A cycle is even if and only if its length is odd. (Note this is consistent with ignoring singletons.) So the first permutation, (z x y), is even, as is the composite permutation, (w z y). The permutation (w z)(x y) consists of two cycles of length two; and since both cycles are odd permutations, together they make an even permutation. In summary, we have composed an even permutation (a 3-cycle) with another even permutation (a pair of 2-cycles) to produce a result which is an even permutation (a different 3-cycle). Thus our parity check is satisfied. --KSmrq^T 10:09, 9 November 2006 (UTC)

Do not insult me again. Melchoir 15:16, 9 November 2006 (UTC)

I'm sure you were trying to help Creidieki with your answer. However, the effect of your comments was to introduce irrelevant confusion. That's unfortunate for the questioner, and I tried to make up for it; with what success, I do not know. Feel free to correct or extend my remarks if you think that would help lead to better understanding of cycle notation. --KSmrq^T 20:56, 9 November 2006 (UTC)

It is your responsibility to avoid creating a hostile environment for your peers. In the future, if you think you have a more instructive response to a question, give it without calling other answers irrelevant ramblings. Or even making the implication. Melchoir 21:23, 9 November 2006 (UTC)

I focus on giving helpful answers, not protecting my ego, nor yours. I'm satisfied that I have done that here. Again, if you have something useful to add about cycle notation, now would be an opportunity to contribute.

In a spirit of generosity, since you insist on viewing every correction as an insult, I did a little searching on the web to see if I could satisfy your cravings. Here's a selection:

• I’ll try being nicer if you’ll try being smarter.
• Don’t let your mind wander — it’s far too small to be let out on its own.
• So, a thought crossed your mind? Must have been a long and lonely journey.
• Anyone who told you to be yourself couldn’t have given you worse advice.
• Why, thou clay-brained guts, thou knotty-pated fool, thou whoreson obscene greasy tallow-catch.

The last is from the Bard himself. (Henry IV, Part 1, Act 2, Scene 4.) Enjoy. --KSmrq^T 07:32, 10 November 2006 (UTC)

KSmrq, I agree with Melchior. You started out by disparaging Melchior's answer, and your "quotations" response looks like a personal attack. Since you are so quick to openly criticise the conduct of others on the RDs, you ought to be more careful with your own behaviour. Gandalf61 07:50, 10 November 2006 (UTC)

I agree. As a very public forum it is essential to follow the highest standards of behaviour and not let problems with other users spill over to here. --Salix alba (talk) 08:39, 10 November 2006 (UTC)

Thanks for your criticisms. Perhaps in time you'll come to appreciate my style and my sense of humor. Perhaps not. But unless you honestly believe Melchoir is in real life the fictional character Falstaff in a Shakespeare play, that insult cannot be considered a personal attack on him. The quotations are there for entertainment — for me certainly, and I hope for others as well. I had fun finding them, discarding many others that were too lame or too vulgar.

And consider this: my first post began with one brief sentence about Melchoir's post. It was addressed to the original poster, and it was concerned with technical guidance. Melchoir characterized that as an insult. How, then, should I view the comments addressed to me, comments that completely ignore the original poster and the technical content of my post? Am I being insulted? Is the intent to create a hostile environment for me? I demand that these personal attacks cease immediately! How absurd. For the third time, I suggest that everyone put serving the poster above stroking a bruised ego. --KSmrq^T 11:52, 10 November 2006 (UTC)

Just don't do it again; that's all that matters. Melchoir 20:11, 10 November 2006 (UTC)

There are indeed some touchy people here, whose prickliness makes very tedious reading. I come to be entertained and informed, and this silly acrimony gets in the way. Here's a suggestion - let the first "insult" go, react only thereafter.--86.132.233.8 20:49, 10 November 2006 (UTC)

quotient

My son's sixth grade math homework question is:

Find the quotient of 1436 and 21.

A quotient is the end result of a division problem. How do you determine the divisor and the dividand?

• They're probably assuming that we're dividing the larger number by the smaller one, so we end up with an answer greater than one. This is indeed a very poorly-phrased homework question; if your son is feeling rebellious, he could always provide both possible answers. You can get more information by looking at what your son is currently studying; if he's doing long division right now, you're probably looking for 1436/21, whereas if he's doing reduced-form fractions, it's vaguely possible that he's supposed to perform 21/1436. But the ordering suggests 1436/21 to me. -- Creidieki 03:20, 9 November 2006 (UTC)

• The standard way of expressing this is: "the quotient of dividend by divisor". But I would normally assume that "the quotient of A and B" is a sloppy way of saying: "the quotient of A by B". The actual numbers of the homework question strongly suggest that indeed 1436 is meant to be the dividend and 21 the divisor.  --Lambiam^Talk 09:11, 9 November 2006 (UTC)

Really Easy(Or Hard?)Maths Riddle

Hi,I realise that my question isn't very important.I would love some help though!Someone sent me this riddle by email.I think I have worked it out,but could someone confirm to me that the answer is correct? I will post the question and my answer below:

There are seven monkeys.

For every monkey, there are seven snakes.

For every snake, there are seven bears.

For every snake, there are seven cats.

For every cat, there are seventeen ferrets.

For every ferret, there are seven eagles.

Every animal has six bugs.

Every bug has seven fleas.

How many fleas are there in total?

Answer:1728720

Is my answer correct?

Starkidstar 04:47, 9 November 2006 (UTC)

Well, a strict reading of the problem would indicate that there are an infinite number of fleas. Fleas are animals. Every animal has six bugs, and thus seven fleas. Thus every flea has forty-two fleas. -- Creidieki 05:12, 9 November 2006 (UTC)

So, nat'ralists observe, a flea

Hath smaller fleas that on him prey

And these have lesser fleas to bite 'em

And so proceed ad infinitum

--Trovatore 05:30, 9 November 2006 (UTC) (no, I didn't write it :-)

Clearly the whole thing is bogus; there are several more monkeys than just seven. I daresay there are dozens, at least. Melchoir 05:36, 9 November 2006 (UTC)

Okay,can you just disregard the fleaas and the bugs bit and use another animal like a crocodile and a gorilla or something? I don't really care what the animals are,in fact the bugs and fleas were originally something else but I changed it so my friend wouldn't accuse me of cheating by asking for help :) Starkidstar 05:43, 9 November 2006 (UTC)

No, I got a different answer. I assumed that "bugs" and "fleas" aren't counted as animals. Why don't you show your work so I can compare with mine ? StuRat 06:00, 9 November 2006 (UTC)

Taking all the steps in order, the answer is

${\Bigg \langle }\left\|7M\left(1+7{\frac {S}{M}}\left(1+7{\frac {B}{S}}\left(1+7{\frac {C}{B}}\left(1+7{\frac {F}{C}}\left(1+7{\frac {E}{F}}\right)\right)\right)\right)\right)\right\|_{\to A}\left(1+6{\frac {B}{A}}\left(1+7{\frac {F}{B}}\right)\right){\Bigg |}F{\Bigg \rangle }$

where capital letters are orthonormal units and the norm genericizes all animals. You can express it in decimal notation if you prefer. But don't just set all the units equal to unity, or the last two (1 + …) groups won't make sense, and your AP Chemistry teacher will also mark you down on general principle. Melchoir 06:09, 9 November 2006

That notation is enough to confuse me. Note, however, that there are 17 ferrets, not 7, for every cat. StuRat 06:21, 9 November 2006 (UTC)

Ah, but good notation lets you identify and correct flaws instantly...

${\Bigg \langle }\left\|7M\left(1+7{\frac {S}{M}}\left(1+7{\frac {B}{S}}\left(1+7{\frac {C}{B}}\left(1+17{\frac {F}{C}}\left(1+7{\frac {E}{F}}\right)\right)\right)\right)\right)\right\|_{\to A}\left(1+6{\frac {B}{A}}\left(1+7{\frac {F}{B}}\right)\right){\Bigg |}F{\Bigg \rangle }$

Also note that both bears and cats are based directly on the number of snakes. StuRat 06:26, 9 November 2006 (UTC)

Yeah, I assume that's a typo. Melchoir 14:51, 9 November 2006 (UTC)

I assumed it's a trick, to teach the student to pay attention to the question, like the 17. StuRat 05:13, 10 November 2006 (UTC)

This isn't for chemistry..but htanks for your help anyway.I'm sorry if I've been making you tear your hair out because I'm such a dunce at maths.:) Starkidstar 06:13, 9 November 2006 (UTC)

I looked at your answer, and it seems you assumed that only bears and eagles would have bugs and fleas on them, while I assumed every animal (except bugs and fleas) would have bugs and fleas on them. StuRat 06:51, 9 November 2006 (UTC)

Er, I was kidding. Most people wouldn't try to represent the entire problem in one line. It's a worthwhile exercise to do once or twice in a lifetime, but realistically I'd attack this problem step by step. Melchoir 06:25, 9 November 2006 (UTC)

I get a different answer. Step by step:

To start there are 7 monkeys

There are 7 monkeys, so there are 7 × 7 = 49 snakes

There are 49 snakes, so there are 49 × 7 = 343 bears

There are 49 snakes, so there are 49 × 7 = 343 cats

There are 343 cats, so there are 343 × 17 = 5831 ferrets

There are 5831 ferrets, so there are 5831 × 7 = 40817 eagles

So we have:

7 monkeys

49 snakes

343 bears

343 cats

5831 ferrets

40817 eagles

-----

47390 animals

There are 47390 animals, so there are 47390 × 6 = 284340 bugs

There are 284340 bugs, so there are 284340 × 7 = 1990380 fleas

(It looks like StuRat got the same result.)  --Lambiam^Talk 09:45, 9 November 2006 (UTC)

I do wonder if the problem has been presented accurately. It appears to be a variation of a puzzle found in the Rhind papyrus, written in ancient Egypt, around 1650 BCE (as a copy of something older still):

Seven houses contain seven cats. Each cat kills seven mice. Each mouse had eaten seven ears of grain. Each ear of grain would have produced seven hekats of wheat. What is the total of all of these?

A more recent variation is found in the nursery rhyme "As I Was Going to St Ives". --KSmrq^T 11:07, 9 November 2006 (UTC)

And here it is:

As I was going to St. Ives,

I met a man with seven wives;

every wife had seven sacks,

every sack had seven cats,

and every cat had seven kits.

Kits, cats, sacks, and wives,

how many were going to St. Ives ?

StuRat 18:11, 9 November 2006 (UTC)

Yes, but that's a trick question. JoshuaZ 18:15, 9 November 2006 (UTC)

There were also a couple tricks in the original poster's question. StuRat 05:15, 10 November 2006 (UTC)

I think it's just a trick question. Considering it's meant to be a "riddle", i really don't think it's just a matter of simple multiplication and adding. I have a feeling the "Every animal has six bugs" is probably where the trick is. You know there are 7 monkeys...and 42 snakes...and so on. But you don't know how many animals there are in total. The question doesn't really have an answer. --`/aksha 10:55, 10 November 2006 (UTC)

In common (rather unscientific) US English, "animal" excludes insects, arachnids and humans. It includes fish, amphibians, reptiles, birds, and mammals (except humans). StuRat 18:25, 10 November 2006 (UTC)

This is a reworded Lenny Conundrum contest question for Neopets, so I have removed the solutions from easy viewing for the duration of the contest. See http://www.neopets.com/games/conundrum.phtml . —AySz88\^-^ 21:15, 11 November 2006 (UTC)

Now restored. —AySz88\^-^ 06:54, 19 November 2006 (UTC)