X-Ids: 164 X-MimeOLE: Produced By Microsoft Exchange V6.5 Content-class: urn:content-classes:message MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Subject: RE: Permutations of the positive integers Date: Tue, 19 Jun 2007 09:11:13 -0500 Message-ID: <5C7554D82F4671478985015814A65B7708000CFF@UEEXCHANGE.evansville.edu> X-MS-Has-Attach: X-MS-TNEF-Correlator: Thread-Topic: RE: Permutations of the positive integers Thread-Index: AceyepHauiU1S8L8TRGTrxQ8c2ZmrwAANXDA From: "Kimberling, Clark" To: X-OriginalArrivalTime: 19 Jun 2007 14:11:14.0540 (UTC) FILETIME=[B24C12C0:01C7B27B] X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-3.0 (shiva.jussieu.fr [134.157.0.164]); Tue, 19 Jun 2007 16:13:03 +0200 (CEST) X-Virus-Scanned: ClamAV 0.88.7/3466/Tue Jun 19 08:21:58 2007 on shiva.jussieu.fr X-Virus-Status: Clean X-Miltered: at shiva.jussieu.fr with ID 4677E46E.001 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! Content-Transfer-Encoding: 8bit X-MIME-Autoconverted: from quoted-printable to 8bit by idf.ext.jussieu.fr id l5JED4BM064691 Max and all seqfans, Thanks, Max, for the note. However, when you wrote that the inversion vector of p equals "the vector t with every element decreased by 1," did you mean for this t to be the same as the trace sequence (also denoted by t) of p? If so, you're your t doesn't seem to be the t as originally given in the message copied below. Here is a "formula" for the kth term of the trace t (using the symbol P for the inverse of p): t(k) = the number of numbers p(i) such that 1<=i<=P(k) AND p(i)>=k. In the next sentence, t(k) is t_p(k) in order to show that t belongs to p. Likewise, we can write t_q and t_r for other permutations q and r. Unfortunately, the above "formula" refers to p and P. In contrast, WHAT I HOPE SOMEONE CAN FIND is a formula for t_r in terms of t_p and t_q, where r is the composite permutation, p-of-q. Because of isomorphism, the operation defined by such a formula would be as "natural" (in the set T of all sequences t of positive integers that include infinitely many 1's) as the operation of composition is in the set of permutations of N. So, if there is no nice formula...well...that's interesting. And if there is a nice formula, I'd sure like to get my hands on it. Example: (your t), applied to p = (1,3,2,5,7,4,9,11,6,13,15,8,...), is your t) = (1,1,2,1,1,3,1,1,4,1,4,1,4,1,4,1,...; whereas (my t) = (1,2,1,3,1,4,1,5,1,6,1,7,1,8,1,9,... . Best regards, Clark Kimberling -----Original Message----- From: Max Alekseyev [mailto:maxale@gmail.com] Sent: Sunday, June 17, 2007 3:35 PM To: Kimberling, Clark Cc: seqfan@ext.jussieu.fr Subject: Re: Permutations of the positive integers There is two known objects related to the trace t that you may find helpful. First is an inversion vector of p that equals to the vector t with every element decreased by 1. See http://mathworld.wolfram.com/InversionVector.html Second is an inversion table of p that can be obtained by applying the permutation p to the inversion vector. See http://www.liafa.jussieu.fr/~rossin/Enseignement/MPRI/Cours1/index.php#h toc2 Max On 6/17/07, Kimberling, Clark wrote: > > > Dear Seqfans - > > Suppose p is a permutation of the positive integers, N. If we > subtract 1 from every term and then delete 0, what's left is another > perm. Iterate, and we get many perms. > > Now, let t(k) be the position of 1 in the kth iterate. > > Example: p = (1,3,2,5,7,4,9,11,6,13,15,8,...) = A006369 (related to > 3X+1 problem) This choice of p yields trace sequence t = > (1,2,1,3,1,4,1,5,1,6,1,7,...) = > A057979 essentially. > > A sequence t of positive integers is the trace of a perm if and only > if t has infinitely many 1's. Let T be the set of all such t. > > Suppose t_p and t_q are traces of perms p and q. Can someone find a > decent formula for t_r, where r is the composite perm p-of-q? > > I'd like to see such a formula - it would define a group operation on > the set T. > > Clark Kimberling