| Displaying 1-4 of 4 results found.
page
1
Repeating part of A220664: First differences of the numbers given as concatenation of permutations of (1,...,m) for sufficiently large m.
+20
8
9, 81, 18, 81, 9, 702, 9, 171, 27, 72, 18, 693, 18, 72, 27, 171, 9, 702, 9, 81, 18, 81, 9, 5913, 9, 81, 18, 81, 9, 1602, 9, 261, 36, 63, 27, 594, 18, 162, 36, 162, 18, 603, 9, 171, 27, 72, 18, 5814, 9, 171, 27, 72, 18, 603, 9, 261, 36, 63, 27, 1584, 27, 63, 36
COMMENTS
First 5!-1 terms are identical to A107346, and the 9!-1 terms are identical to A209280. (Updated by M. F. Hasler, Jan 12 2013, Mar 03 2013) Because of the self-similar nature of A220664, this sequence can be also constructed by picking appropriate terms from there with the auxiliary sequence A220655, cf. formula. Similarly, differences between successive permutations of {1,2,...,k} in lexicographic order interpreted as decimal numbers, for any k=2..9, produce the first (k!)-1 terms of this sequence. But for k=10 the result is ill-defined, so we can consider the sequence finite, well-defined only for n=1..362879. [See however the following comment. - Editor's note]
In sequence A030299 it is clearly defined how it extends beyond index n = 1!+2!+...+9! = A007489(9), so the sequence A220664 of its first differences is well-defined up to infinity. (The "result" mentioned above is ill defined because the meaning of "interpreted" is not clear.) But the preceding comment is misleading by speaking of "self similar nature", and the sequence definition as "repeating part" is also misleading: If the sequence is defined to be of finite length 9!-1 (thus equal to A209280), then it is indeed infinitely often repeated as a subsequence (of consecutive terms) in A220664 (even when the latter was defined using concatenation for permutations of more than 9 elements, but then not as differences of the terms following 12345678910 where it was expected, but, e.g., as differences of the terms following 10123456789, etc.). Since A030299 has been defined through a ("simpler") sum rather than concatenation, the nice mathematical properties of A220664, and even more this sequence A219664, persist beyond n=9!. - M. F. Hasler, Jan 12 2013
EXAMPLE
The first four permutations of nine elements at A030299( A003422(9).. A003422(9)+3) (the terms A030299(46234..46237)) are: 123456789, 123456798, 123456879, 123456897. As 123456897-123456879 = 18, thus we have a(3) = 18. We could compute the same value from any smaller set of permutations of at least three elements, for example, from the five element permutations used in A107346. In that case, the permutations A030299( A003422(5).. A003422(5)+3) (the terms A030299(34..37)) are: 12345, 12354, 12435, 12453, ... and we get the same result, a(3) = 12453-12435 = 18.
PROG
(PARI) A219664(n)=for(k=2, n+1, k!>n || next; k=vecsort( vector( (#k=vector(k, j, 10^j)~\10)!, i, numtoperm(#k, i)*k )); return(k[n+1]-k[n])) \\ (It is of course more efficient to calculate a whole vector of the first k!-1 terms. Also, for n>9!, this might yield incorrect terms.) - M. F. Hasler, Jan 12 2013
Decimal representation of permutations of lengths 1, 2, 3, ... arranged lexicographically.
+10
34
1, 12, 21, 123, 132, 213, 231, 312, 321, 1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, 2314, 2341, 2413, 2431, 3124, 3142, 3214, 3241, 3412, 3421, 4123, 4132, 4213, 4231, 4312, 4321, 12345, 12354, 12435, 12453, 12534, 12543, 13245, 13254, 13425
COMMENTS
This is a list of the permutations in "one-line" notation (cf. Dixon and Mortimer, p. 2). The i-th element of the string is the image of i under the permutation. For example 231 is the permutation that sends 1 to 2, 2 to 3, and 3 to 1. - N. J. A. Sloane, Apr 12 2014 Precise definition of the term "Decimal representation" (required for indices n>409113): Numbers N(s) = Sum_{i=1..m} s(i)*10^(m-i), where s runs over the permutations of (1,...,m), and m=1,2,3,.... This also defines the "lexicographical" order: Obviously 21 comes before 123, etc. The lexicographical order of the permutations, for given m, is the same as the natural order of the numbers N(s). - M. F. Hasler, Jan 28 2013 An alternate variant, using concatenation of the permutations, is very clumsy once the length exceeds 9. For example, after 987654321 (= A030299(409113), where 409113 = A007489(9)) we would get 12345678910, 12345678109, ... In A030298 this problem has been avoided by listing the elements of permutations as separate terms. [Edited by M. F. Hasler, Dec 2012 and Jan 28 2013] Sequence A051845 is a base-independent version of this sequence: Permutations of 1...m are considered as numbers written in base m+1. - M. F. Hasler, Jan 28 2013
REFERENCES
John D. Dixon and Brian Mortimer, Permutation groups. Graduate Texts in Mathematics, 163. Springer-Verlag, New York, 1996. xii+346 pp. ISBN: 0-387-94599-7 MR1409812 (98m:20003).
MAPLE
seq(seq(add(s[i]*10^(m-i), i=1..m), s=combinat:-permute([$1..m])), m=1..5); # Robert Israel, Oct 14 2015
MATHEMATICA
Flatten @ Table[FromDigits /@ Permutations[Table[i, {i, n}]], {n, 9}] (* For first 409113 terms; Zak Seidov, Oct 03 2015 *)
PROG
(PARI) is_ A030299(n)={ (n>1234567890 & print("maybe")) || vecsort(digits(n))==vector(#Str(n), i, i) } \\ /* use digits(n)=eval(Vec(Str(n))) in older versions lacking this function */ \\ M. F. Hasler, Dec 12 2012 (define (vector->base-k vec k) (let loop ((i 0) (s 0)) (cond ((= (vector-length vec) i) s) ((>= (vector-ref vec i) k) (error (format #f "Cannot interpret vector ~a in base ~a!" vec k))) (else (loop (+ i 1) (+ (* k s) (vector-ref vec i)))))))
(Python)
from itertools import permutations
def pmap(s, m): return sum(s[i-1]*10**(m-i) for i in range(1, len(s)+1))
def agen():
m = 1
while True:
for s in permutations(range(1, m+1)): yield pmap(s, m)
m += 1
def aupton(terms):
alst, g = [], agen()
while len(alst) < terms: alst += [next(g)]
return alst
CROSSREFS
A007489(n) gives the position (index) of the term corresponding to last permutation of n elements: (n,n-1,...,1).
See A240763 for preferential arrangements.
First differences of A215940, or first differences of permutations of (0,1,2,...,m-1) reading them as decimal numbers, divided by 9 (with 10>=m, and m! > n).
+10
10
1, 9, 2, 9, 1, 78, 1, 19, 3, 8, 2, 77, 2, 8, 3, 19, 1, 78, 1, 9, 2, 9, 1, 657, 1, 9, 2, 9, 1, 178, 1, 29, 4, 7, 3, 66, 2, 18, 4, 18, 2, 67, 1, 19, 3, 8, 2, 646, 1, 19, 3, 8, 2, 67, 1, 29, 4, 7, 3, 176, 3, 7, 4, 29, 1, 67, 2, 8, 3, 19, 1, 646, 2, 8, 3, 19, 1
COMMENTS
Terms do not depend on the choice of m, provided that m!>n (the index of the considered term), and the numbers associated to a permutation s of {0,...,m-1} are N(s)=sum_{i=1..m} s(i)*10^(m-i). This defines the present sequence for any arbitrarily large index, not limited to n <= 10!, for example.
Similar sequences might be built in another base b, they would always start (1, b-1, 2, b-1, 1, ...). The partial sums of this kind of sequence would yield the analog of A215940 in the corresponding base. There are at least two palindromic patterns which are repeated throughout this sequence: one of them is "1,b-1,2,b-1,1" (It is optional here whether or not to include the 1's), another is built from the first 4!-1 terms (See the corresponding link for details).
There are more palindromic patterns than those mentioned above: Similar to the first 3!-1 and the first 4!-1 terms, the first k!-1 terms are repeated for all other k>4. Frequent are also multiples of these, e.g., k*[1,9,2,9,1] = [2,18,4,18,2], [3,27,6,27,3], ...), [1, 19, 3, 8, 2, 67, 1, 29, 4, 7, 3, 176, 3, 7, 4, 29, 1, 67, 2, 8, 3, 19, 1], and others. The "middle part" of roughly half the length (e.g., [9,2,9] or [67,...,67] in the last example), is repeated even more frequently. - M. F. Hasler, Jan 14 2013 Conjecture 1: Given 1<n<=M two positive integers, the first n!-1 terms of this sequence are inserted (M-n+1)! times with (anti)symmetric distribution among the first M!-1 terms of this sequence. The described count and alternating pattern of symmetry is conserved whenever it is possible (i.e., when having enough terms) through successive differences and for the corresponding sequences (i.e., the first differences of A217626 and so on). Lemma: Let P be an arbitrary set consisting of m integers; let x[i] be an element in P (with 1<=i<=m); let y[j] = x[j+1] - x[j] (with 1 <= j <= m-1) be the 1st differences of P. These differences are symmetric if y[j]=y[m-j] which for P implies the condition x[j]+x[m-j+1]=x[j+1]+x[m-j];
Consequence: When m=n! and P is a set with all the permutations for the letters 0..n-1, the preceding lemma implies P has associated at least a set Q such that 1st differences in Q are symmetric.
Generating algorithm: Such Q can be built based upon P and the condition given by the preceding lemma if it is removed from P (until P becomes empty) its 1st element tau, inserting them both in Q tau and its arithmetic complement to repdigit (n-1)*111...1 (n times 1) removing the mentioned complement from P.
Conjecture 2: The autosimilarity shown by a(n) is a consequence of the fact that the corresponding P is the set of the n! permutations in increasing sequence for the letters 0..n-1, and Q=P (it holds if they are replaced "a(n)" and "increasing" respectively with "-1*a(n)" and "decreasing").
Note: "Q=P" is a necessary but not sufficient condition for observing the autosimilarity in a(n).
Application: The "generating algorithm" described previously might be potentially useful for parallel computing. In combination with the partition scheme proposed at links in A237265, and multiple indirection. For example notice that in such sense an algorithm for generating k! permutations with an increasing sequence would require only k!/2 iterations because the other half would be already determined by symmetry. Conjecture 3: For n>2, given P the set of permutations in increasing sequence for the letters 0..n-1, there are distributed with a symmetric pattern among its (n!)! permutations all those A000165(n!\2) of them such that their 1st differences are symmetric. Moreover by setting to zero the other elements whose 1st differences are not symmetric, we obtain an antisymmetric sequence. (End)
Conjecture 4: If 2<=m<n, and S is defined as the first differences of a sequence giving the starting position of each repetition for the first m!-1 terms inside the first n!-1 terms, then each element in S is 0 mod m!. - R. J. Cano, Apr 19 2017 Consider the first y!-1 terms for even y; The central term a(y!/2) is determined by the difference between the (y/2+1)th row from the yth matrix defining the irregular table in A237265 and the consecutive permutation preceding it in lexicographic order (See EXAMPLE). - R. J. Cano, May 09 2017
EXAMPLE
On the central terms for subsequences consisting of the first y!-1 terms with even y: Let us pick y=4; The first y!-1=23 terms are,
(1,9,2,9,1,78,1,19,3,8,2,77,2,8,3,19,1,78,1,9,2,9,1)
the central term there is a(12)=77; If we look into A237265, the 4th matrix defining it contains as its (4/2+1)th or third row, the permutation 3124 which in lexicographic order is preceded by 2431, therefore by subtracting and dividing by 9 we obtain: (3124-2431)/9 = 693/9 = (2013-1320)/9 = 77 = a(12); [End]
MATHEMATICA
maxm = 5; Table[dd = FromDigits /@ Permutations[Range[m]]; (Drop[dd, If[m == 1, 0, (m - 1)!]] - First[dd])/9, {m, 1, maxm}] // Flatten // Differences (* Jean-François Alcover, Apr 25 2013 *)
PROG
(C) // See LINKS.
(PARI) first_terms(n)={n=max(3, n); my(m:small=n!); my(a:vec=vector(m-1), i:small=0, x:vec=numtoperm(n, 0), y:vec, z:vec, u:small, B:small=11); m\=2; m--; while(i++<=m, u=!(i%6); y=numtoperm(n, i); z=(y-x)[1..n-1]; if(u, z=vector(#z, j, vecsum(z[1..j]))); a[i]=fromdigits(z, B-u); a[#a-i+1]=a[i]; x=y; ); z=(numtoperm(n, m+1)-y)[1..n-1]; a[m+1]=fromdigits(vector(#z, j, vecsum(z[1..j])), B--); return(a)} \\ Computes the first either 5 or n!-1 terms. - R. J. Cano, May 28 2017
CROSSREFS
Cf. A219995 [ On the summation of 1/a(n) ].
Difference between the n-th and the first (identity) permutation of (0,...,m-1), interpreted as a decimal number, divided by 9 (for any m for which 10! >= m! >= n).
+10
7
0, 1, 10, 12, 21, 22, 100, 101, 120, 123, 131, 133, 210, 212, 220, 223, 242, 243, 321, 322, 331, 333, 342, 343, 1000, 1001, 1010, 1012, 1021, 1022, 1200, 1201, 1230, 1234, 1241, 1244, 1310, 1312, 1330, 1334, 1352, 1354, 1421, 1422, 1441, 1444, 1452, 1454, 2100
COMMENTS
Original definition: "Quotients of the polynomial remainder theorem for Diophantine equations among permutations."
The set built from the first terms of this sequence {0, 1, 10, 12, 21, 22, ....} contains the general solutions for a class of Diophantine linear equations among permutations, if one takes into account the unlimited number of distinct bases where these may be read.
Let P be the sequence of permutations of (0,...,m-1) interpreted as decimal numbers, P(n) = Sum_{i=1..m} 10^(m-i)*s(i) where s=(s(1),...,s(m)) is the n-th permutation (in lexicographical order), n <= m!. Then the difference P(n)-P(1) is independent of the choice of m, and divisible by 9. (Since 10 == 1 (mod 9), the numbers P(n) are all congruent (mod 9) to the sum s(1)+...+s(m).) This yields well-defined terms a(n)=(P(n)-P(1))/9.
For n>10!, P(n) will no longer be the concatenation of the "digits" (some of which will exceed 9). The pattern present in the decimal representation of the first terms will also be lost since there will be digits as large as d+1.
Note that the same a(n) is obtained independently of the chosen base b, provided that (i) 10 and 9 in the above are replaced with b and b-1, (ii) the result is (and can be) written in base b. (This implies the restriction to terms which can be written using the digits 0-9 to which the OEIS is limited.) See EXAMPLES for an illustration. (End)
We have P(n)-P(1)=a(n)*g(n), with g(n) = 9 = 10-1. Considering this and P(n) as polynomials in x=10, one can see an analogy with the polynomial remainder theorem. [Given as "formula" by R. J. Cano, rephrased by M. F. Hasler, Jan 12 2013] The maximum of the first m! terms of this sequence is given in base R by the explicit formula (please see A211869): max(m,R)=Sum_{k=1..m} k*(m-k)*R^(m-k-1); If the first m! terms of this sequence were computed reading the permutations in base A033638(m), dividing their differences by A033638(m)-1, the resulting quotients would be written in the same way (with the same digits) in every base > A033638(m). (End)
Although in the sequence name it reads: "permutation of (0,...,m-1)", the most general statement that could replace it is: "permutation of any m-tuple of integers all of them in arithmetic progression", obtaining a multiple of this sequence, lambda*a(n), where lambda is the common difference for the progression. It works in such way because only the differences is what matters here.
Given x>1 and k>=0, if a polynomial G(x) of degree k is divided by x-1 then the remainder will be the sum of all the coefficients in G. Let us consider the case in which those coefficients are the differences among the letters ("digits") of two permutations for the same set of letters (0..x-1): The sum of all those differences must vanish. This explains how the difference between two of such permutations expressed in base x is 0 mod x-1, particularly why differences for pairs of permutations are divisible by 9.
Another way of introducing this sequence takes advantage of the fact that for n>1, n! is even. Consider for n>1 to obtain only the first n! terms. This can be done by subtracting the last permutation from the first, the penultimate permutation from the second, and so on by following the pattern (P(k)-P(n!-k+1))/9 with 1<=k<=n!. Such procedure generates an antisymmetric sequence f(k) from which a(k)=(f(k)+f(n!))/2. This partially explains why A217626 is symmetric. Also a base-independent treatment is possible using linear algebra: Column vectors and the strictly lower triangular matrix instead of the division by (r-1) where r is the base (and r=10 here for this sequence). This approach leads one to conclude that terms in this sequence are the differences between pairs of vectors made from the first n-1 partial sums of letters ("digits") taken from permutations for n consecutive letters, when components in these vectors are viewed as coefficients for a power series in r=10. (End)
EXAMPLE
The permutations of {0,1,2}, read as numbers, are {12, 21, 102, 120, 201, 210}. Subtracting the first one (12) from each of these numbers yields the differences {0, 9, 90, 108, 189, 198}. These are all multiples of 9, see comment and links. Dividing the differences by 9 yields {0, 1, 10, 12, 21, 22}, which are by definition the first six terms of this sequence.
Using all permutations of 0123 would yield 4!=24 terms, where the first 6 would be identical to those above. For n>10! we must consider permutations of (0,...,m-1) with m>10. These are no longer valid digits in base 10, and the numbers P(n) as defined in the comment are no longer equal to the concatenation. However, the first 10! terms obtained as (P(n)-P(1))/9, are still the same as for m=10;
In order to illustrate that the result is independent of the base chosen to make the calculation, let us consider permutations of 012 in base 3. The 3rd resp. 5th term ((102-012)/9=10 resp. (201-012)/9=21) would be ((1-0)*3^2+(0-1)*3+(2-2)*1)/(3-1) = 3 = 10[3], resp. ((2-0)*3^2+(0-1)*3+(1-2)*1)/(3-1) = 7 = 21[3]. The same terms would also be "10" and "21" if the calculation were made in base b=11. In that base, with digit "A" having the value b-1, we have (1023456789A - 0123456789A)/A = 0A000000000[11], (2013456789A - 0123456789A)/A = 02100000000[11], and (0A123456789 - 0123456789A)/A = 0A987654321[11] (the analog of (40123[5]-01234[5])/4[5] = 04321[5]). (End)
MAPLE
N:= 100: # to get a(1)..a(N)
for M from 3 while M! <= N do od:
p0:= [$1..M]: p:= p0: A[1]:= 0:
for n from 2 to N do
p:= combinat:-nextperm(p);
d:= p - p0;
A[n]:= add(10^(i-1)*d[-i], i=1..M)/9;
od:
MATHEMATICA
maxm = 5; Table[dd = FromDigits /@ Permutations[Range[m]]; (Drop[dd, If[m == 1, 0, (m - 1)!]] - First[dd])/9, {m, 1, maxm}] // Flatten (* Jean-François Alcover, Apr 25 2013 *)
PROG
(C) See links.
(PARI) A215940(n)=for(k=2, n+1, k!<n & next; k=vecsort( vector( (#k=vector(k, j, 10^j)~\10)!, i, numtoperm(#k, i)*k )); return((k[n]-k[1])/9)) \\ (It is of course more efficient to calculate a whole vector of the first k! terms.) - M. F. Hasler, Jan 12 2013 (PARI) first_n_factorial_terms(n)={my(u=n!); my(x=numtoperm(n, 0), y, z=vector(u), i:small); i=0; for(j=0, u-1, y=numtoperm(n, j)-x; z[i++]=fromdigits(vector(#x-1, k, vecsum(y[1..k])))); z} \\ R. J. Cano, Apr 19 2017
Search completed in 0.059 seconds
| 