cp's OEIS Frontend

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)

Also the number of vertex covers of Q_n. - Eric W. Weisstein, Jan 04 2014

A. Sapozhenko proved that a(n) ~ 2 * sqrt(e) * 2^(2^(n-1)). See link (Galvin, 2006). - Daniel Forgues, Feb 11 2015

The cardinality of the largest independent vertex set (the vertex independence number) of the n-hypercube graph Q_n is 1 for n = 0, 2^(n-1) for n >= 1. Except for n = 0, there are two such sets (whose elements have binary labels which are bitwise complement of each other) that represent a vertex coloring, with chromatic number 2, of Q_n. - Daniel Forgues, Feb 11 2015, Feb 16-17 2015

Number of independent vertex pairs for Q_n, n >= 1: 2^(n-1) * (2^n - (n+1)) = T_(2^n - 1) - n * 2^(n-1) = L_n - E_n = A006516(n) - A001787(n), where L_n is the number of vertex pairs and E_n is the number of vertex pairs yielding edges. The g.f. is 2 x^2 / ((1-2x)^2 (1-4x)). (A000431(n+1), n >= 1.) - Daniel Forgues, Feb 17 2015

Number of independent vertex sets with 2^(n-1) - 1 items for Q_n: 2^n = 2 * (2^(n-1) choose 2^(n-1) - 1). - Daniel Forgues, Feb 18 2015

Coefficient of the e^(2x) term in the numerator of the n-th derivative of 1/(2-e^x).

This sequence, multiplied by 8, appears in a combinatorial problem about DNA chips. - Bruno Petazzoni (bruno(AT)enix.org), Apr 18 2007

Number of permutations of length n with exactly four valleys.

From Petros Hadjicostas, Aug 10 2019: (Start)

The recurrence about T(n, k) and the equation that connects T(n, k) to P(n, k) = A059427(n,k), which are given below, appear on p. 159 of the book by David and Barton (1962). The initial conditions, however, for their triangular array S^*{N,t} are slightly different, but there is an agreement starting at t = k = 1. They do not provide tables for S^*{N,t} (that matches the current array T(n, k) for N = n >= 0 and t = k >= 1).

Despite the slightly different initial conditions between T(n, k) and S^*_{N,t} (from p. 159 in the book), the recurrence given below can be proved very easily from the recurrence for the row polynomials R_n(x) given in Shi-Mei Ma (2011, 2012). (End)