

A215940


Difference between the nth and the first (identity) permutation of (0,...,m1), interpreted as a decimal number, divided by 9 (for any m for which 10! >= m! >= n).


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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,3


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.
From M. F. Hasler, Jan 12 2013, edited by R. J. Cano, May 08 2017: (Start)
Let P be the sequence of permutations of (0,...,m1) interpreted as decimal numbers, P(n) = Sum_{i=1..m} 10^(mi)*s(i) where s=(s(1),...,s(m)) is the nth 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 welldefined 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 b1, (ii) the result is (and can be) written in base b. (This implies the restriction to terms which can be written using the digits 09 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 = 101. 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]
Contribution by R. J. Cano, Feb 09 2013, (Start)
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*(mk)*R^(mk1);
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)
From R. J. Cano, Apr 29 2016, (Start)
Although in the sequence name it reads: "permutation of (0,...,m1)", the most general statement that could replace it is: "permutation of any mtuple 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 x1 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..x1): 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 x1, 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 baseindependent treatment is possible using linear algebra: Column vectors and the strictly lower triangular matrix instead of the division by (r1) 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 n1 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)


LINKS

R. J. Cano, Table of n, a(n) for n = 1..10000
R. J. Cano, Additional information.
R. J. Cano, Template for a baseindependent sequencer in C.
Wikipedia, Polynomial remainder theorem.


FORMULA

a(n) = Sum_{k=1..n1} A217626(k).
a(n) = (A050289(n)A050289(1))/9, for n <= 9!.  M. F. Hasler, Jan 12 2013


EXAMPLE

From M. F. Hasler, Jan 12 2013, edited by R. J. Cano, May 09 2017) (Start)
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,...,m1) 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 ((102012)/9=10 resp. (201012)/9=21) would be ((10)*3^2+(01)*3+(22)*1)/(31) = 3 = 10[3], resp. ((20)*3^2+(01)*3+(12)*1)/(31) = 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 b1, 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^(i1)*d[i], i=1..M)/9;
od:
seq(A[i], i=1..N); # Robert Israel, Apr 19 2017


MATHEMATICA

maxm = 5; Table[dd = FromDigits /@ Permutations[Range[m]]; (Drop[dd, If[m == 1, 0, (m  1)!]]  First[dd])/9, {m, 1, maxm}] // Flatten (* JeanFranç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, u1, y=numtoperm(n, j)x; z[i++]=fromdigits(vector(#x1, k, vecsum(y[1..k])))); z} \\ R. J. Cano, Apr 19 2017


CROSSREFS

Cf. A207324, A217626, A211869.
Cf. A030299, A107346, A220664, A219664, A083449, A019566, A209280.
Sequence in context: A186438 A035284 A265403 * A320170 A082927 A108965
Adjacent sequences: A215937 A215938 A215939 * A215941 A215942 A215943


KEYWORD

nonn,easy,base


AUTHOR

R. J. Cano, Sep 21 2012


EXTENSIONS

Edited by M. F. Hasler, Jan 12 2013
Minor edits by N. J. A. Sloane, Feb 19 2013


STATUS

approved



