cp's OEIS Frontend

Coefficients of Gandhi polynomials.

a(n) = Sum_{pi in Symm(n)} Sum_{i=1..n} max(pi(i)-i,0), i.e., the total positive displacement of all letters in all permutations on n letters. - Franklin T. Adams-Watters, Oct 25 2006

a(n) is also the sum of the excedances of all permutations of [n]. An excedance of a permutation p of [n] is an i (1 <= i <= n-1) such that p(i) > i. Proof: i is an excedance if p(i) = i+1, i+2, ..., n (n-i possibilities), with the remaining values of p forming any permutation of [n]\{p(i)} in the positions [n]\{i} ((n-1)! possibilities). Summation of i(n-i)(n-1)! over i from 1 to n-1 completes the proof. Example: a(3)=8 because the permutations 123, 132, 213, 231, 312, 321 have excedances NONE, {2}, {1}, {1,2}, {1}, {1}, respectively. - Emeric Deutsch, Oct 26 2008

a(n) is also the number of doubledescents in all permutations of {1,2,...,n-1}. We say that i is a doubledescent of a permutation p if p(i) > p(i+1) > p(i+2). Example: a(3)=8 because each of the permutations 1432, 4312, 4213, 2431, 3214, 3421 has one doubledescent, the permutation 4321 has two doubledescents and the remaining 17 permutations of {1,2,3,4} have no doubledescents. - Emeric Deutsch, Jul 26 2009

Equals the second right hand column of A167568 divided by 2. - Johannes W. Meijer, Nov 12 2009

Half of sum of abs(p(i+1) - p(i)) over all permutations on n, e.g., 42531 = 2 + 3 + 2 + 2 = 9, and the total over all permutations on {1,2,3,4,5} is 960. - Jon Perry, May 24 2013

a(n) gives the number of non-occupied corners in tree-like tableaux of size n+1 (see Gao et al. link). - Michel Marcus, Nov 18 2015

a(n) is the number of sequences of n+2 balls colored with at most n colors such that exactly three balls are the same color as some other ball in the sequence. - Jeremy Dover, Sep 26 2017

a(n) is the number of triangles (3-cycles) in the (n+1)-alternating group graph. - Eric W. Weisstein, Jun 09 2019

From Petros Hadjicostas, Aug 06 2019: (Start)

André (1895) first defined these numbers. In his notation, T(n, k) = Q(n+1, 2*(k+1)) for n >= 1 and 0 <= k <= ceiling(n/2)-1.

His triangle is as follows (p. 148):

Q_{2,2}

Q_{3,2}

Q_{4,2} Q_{4,4}

Q_{5,2} Q_{5,4}

Q_{6,2} Q_{6,4} Q_{6,6}

Q_{7,2} Q_{7,4} Q_{7,6}

...

He has Q(n, s) = 0 when either s is odd, or n <= 1, or s > n. Also, Q_{n,2} = 2^(n-2) for n >= 2.

His recurrence is Q(n, s) = s * Q(n-1, s) + (n - s + 1) * Q(n-1, s-2) for n >= 3 and s >= 2. (Obviously, for s odd, we get Q(n, s) = 0 + 0 = 0.)

In terms of the current array, André's (1895) recurrence becomes T(n, k) = (2*k + 2) * T(n-1, k) + (n - 2*k) * T(n-1, k-1) for n >= 2 and 1 <= k <= n with T(n, 0) = 2^(n-1) for n >= 1. In this recurrence, we assume T(n, k) = 0 for k >= ceiling(n/2) or k < 0. (End)

From Petros Hadjicostas, Aug 07 2019: (Start)

We clarify further the quantity Q(n, s) defined by André (1895). In his paper, André considers circular permutations of [n] and deals with maxima, minima, and so-called "séquences" in a permutation.

The term "séquence" in a permutation, as used by André in several of his papers in the 19th century, means a list of consecutive numbers in the permutation that go from a maximum to a minimum, or vice versa, and do not contain any interior minima or maxima. This terminology is also repeated in Ex. 13 (pp. 260-261) by Comtet (even though he refers to the corresponding indices rather than the numbers in the permutation itself).

Some authors call these so-called "séquences" (defined by André and Comtet) "alternate runs" (or just "runs"). Here we are actually dealing with "circular runs" if we read these so-called "séquences" in ascending order in one of the two directions on a circle.

Q(n, s) is the number of circular permutations of [n] (out of the (n-1)! in total) that have exactly s of these so-called "séquences" ("alternate runs").

André (1895) proves that, in a circular permutation of [n], the number of maxima equals the number of minima and that the number of his so-called "séquences" ("alternate runs") is always even (i.e., Q(n, s) = 0 for s odd).

He also shows that, if v = floor(n/2), then the only possible values for the length of a so-called "séquence" ("alternate run") in a circular permutation of [n] are 2, 4, ..., 2*v. That is why Q(n, s) = 0 when either s is odd, or n <= 1, or s > n.

Note that Sum_{t = 1..floor(n/2)} Q_{n, 2*t} = Sum_{t = 1..floor(n/2)} T(n-1, t-1) = (n-1)! = total number of circular permutations of [n].

Since T(n, k) = Q(n+1, 2*(k+1)) for n >= 1 and 0 <= k <= ceiling(n/2)-1, we conclude that the number of (linear) permutations of [n] with k peaks equals the number of circular permutations of [n+1] with exactly 2*(k+1) of these so-called "séquences" ("alternate runs"). (End)

From Petros Hadjicostas, Aug 08 2019: (Start)

The author of this array indirectly assumes that a "peak" of a (linear) permutation of [n] is an interior maximum of the permutation; i.e., we ignore maxima at the endpoints of a permutation.

Similarly, a "valley" of a (linear) permutation of [n] is an interior minimum of the permutation; i.e., we ignore minima at the endpoints of the permutation.

Since the complement of a permutation a_1 a_2 ... a_n (using one-line notation, not cycle notation) is (n+1-a_1) (n+1-a_2) ... (n+1-a_n), it follows that, for n >= 2 and 0 <= k <= ceiling(n/2) - 1, T(n, k) is also the number of (linear) permutations of [n] with exactly k valleys. (End)

For n >= 3, a(n) = number whose factorial base representation (A007623) begins with digit {n-2} followed by n-1 zeros. Viewed in that base, this sequence looks like this: 0, 0, 0, 100, 2000, 30000, 400000, 5000000, 60000000, 700000000, 8000000000, 90000000000, A00000000000, B000000000000, ... (where "digits" A and B stand for placeholder values 10 and 11 respectively). - Antti Karttunen, May 07 2015

Sum of row n = n! = A000142(n).

The expected value of k is (n-2)/3. [Geoffrey Critzer, Dec 19 2009]

a(n) is the total displacement of all letters in all permutations on n letters as if the first letter were connected to the last letter, forming a loop.

For the sequence A090672 the displacement of the permutation "0123" is 0, while that of the permutation "3210" is 8 because each of the digits 0 and 3 is 3 places away from its original place and each of the digits 1 and 2 is one place away, so the total displacement is 3+1+1+3 = 8.

In this sequence, however, the displacement is calculated differently: that of "0123" is 0 as before, but the displacement of "3210" is no longer 8 because the first index and last index are connected, forming a loop; each of the digits 0 and 3 is now 1 place away from its original place (and each of the digits 1 and 2 is one place away, as before), so the total displacement is calculated as 1+1+1+1 = 4.