|
| |
|
|
A008303
|
|
Triangle read by rows: T(n,k) (n >= 1, 0 <= k <= ceiling(n/2)-1) = number of permutations of [n] with k peaks.
|
|
18
|
|
|
|
1, 2, 4, 2, 8, 16, 16, 88, 16, 32, 416, 272, 64, 1824, 2880, 272, 128, 7680, 24576, 7936, 256, 31616, 185856, 137216, 7936, 512, 128512, 1304832, 1841152, 353792, 1024, 518656, 8728576, 21253376, 9061376, 353792, 2048, 2084864, 56520704, 222398464, 175627264, 22368256
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
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)
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)
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)
|
|
|
REFERENCES
|
Florence Nightingale David and D. E. Barton, Combinatorial Chance, Charles Griffin, 1962; see Table 10.6, p. 163. [They use the notation T_{N,t^*}^{**}, where N is the length of the permutation and t^* is the number of peaks in the permutation. They also give André's recurrence. So, here n = N and k = t^*. - Petros Hadjicostas, Aug 09 2019]
Florence Nightingale David, Maurice George Kendall, and D. E. Barton, Symmetric Functions and Allied Tables, Cambridge, 1966, p. 261, Table 7.3.
I. P. Goulden and D. M. Jackson, Combinatorial Enumeration, John Wiley and Sons, N.Y., 1983, Ex. 3.3.46. - Emeric Deutsch, Jul 26 2009
T. K. Petersen, Eulerian Numbers, Birkhäuser, 2015, Chapter 4.
|
|
|
LINKS
|
Louis W. Shapiro, Wen-Jin Woan, and Seyoum Getu, Runs, slides and moments, SIAM J. Algebraic and Discrete Methods 4 (1983), 459-466; see p. 461.
|
|
|
FORMULA
|
E.g.f.: G(t,z)=[exp(bz)-exp(az)]/[b*exp(az)-a*exp(bz)], where a+b=2 and ab=t, i.e., a=1+sqrt(1-t), b=1-sqrt(1-t) (see the Goulden-Jackson reference). -
Sum_{k>=0} k*T(n,k) = n!*(n-2)/3 = A090672(n-1).
Row n has ceiling(n/2) terms. (End)
E.g.f.: tan(t*sqrt(x-1))/(sqrt(x-1)-tan(t*sqrt(x-1))) = Sum_{n>=0} P(n,x)*t^n/n! = t + 2*t^2/2! + (4+2*x)*t^3/3! + (8+16*x)*t^4/4! + .... The row generating polynomials P(n,x) satisfy x^(n-1)*P(n,1+1/x^2) = R(n-1,x), where R(n,x) are the row polynomials of A185896. A000670(n) = (3/2)^(n-1)*P(n,8/9). - Peter Bala, Oct 14 2011
T(n, k) = (n - 2*k + 2)*T(n-1, k-1) + 2*k*T(n-1, k) for n > 1 and k > 1; T(n, 1) = 2^(n - 1); T(1, k) = 0 for k > 1.
|
|
|
EXAMPLE
|
Triangle T(n,k) (with rows n >= 1 and columns k >= 0) starts as follows:
[ 1] 1;
[ 2] 2;
[ 3] 4, 2;
[ 4] 8, 16;
[ 5] 16, 88, 16;
[ 6] 32, 416, 272;
[ 7] 64, 1824, 2880, 272;
[ 8] 128, 7680, 24576, 7936;
[ 9] 256, 31616, 185856, 137216, 7936;
[10] 512, 128512, 1304832, 1841152, 353792;
T(3,1) = 2 because we have 132 and 231.
In terms of André's (1895) notation (see the comments above), we have Q(4, 2) = T(3, 0) = 4 and Q(4, 4) = T(3, 1) = 2.
Out of the (4-1)! = 6 circular permutations of [4], each of the permutations 1324 and 1423 has exactly 4 so-called "séquences" ("alternate runs"), while each of the rest (1234, 1243, 1342, and 1432) has exactly 2 so-called "séquences" ("alternate runs").
In detail, we list the so-called "séquences" ("alternate runs") of the above circular permutations:
1234 --> 1234 and 41 (maximum 4 and minimum 1).
1243 --> 124 and 431 (maximum 4 and minimum 1).
1324 --> 13, 32, 24, and 41 (maxima 3, 4, and minima 1, 2).
1342 --> 134 and 421 (maximum 4 and minimum 1).
1423 --> 14, 42, 23, and 31 (maxima 3, 4 and minima 1, 2),
1432 --> 14 and 4321 (maximum 4 and minimum 1).
(End)
|
|
|
MAPLE
|
# The Maple program yields (by straightforward counting) the generating polynomial of the row n specified in the program.
n := 8: with(combinat): P := permute(n): st := proc (p) local ct, j: ct := 0: for j from 2 to nops(p)-1 do if p[j-1] < p[j] and p[j+1] < p[j] then ct := ct+1 else end if end do: ct end proc: sort(add(t^st(P[j]), j = 1 .. factorial(n))); # Emeric Deutsch, Jul 26 2009
# Second Maple program:
a := 1+sqrt(1-t): b := 1-sqrt(1-t): G := (exp(b*z)-exp(a*z))/(b*exp(a*z)-a*exp(b*z)): Gser := simplify(series(G, z = 0, 15)): for n to 12 do P[n] := sort(expand(factorial(n)*coeff(Gser, z, n))) end do: for n to 12 do seq(coeff(P[n], t, j), j = 0 .. ceil((1/2)*n)-1) end do; # yields sequence in triangular form - Emeric Deutsch, Jul 26 2009
# Third Maple program:
b:= proc(u, o, t) option remember; expand(`if`(u+o=0, 1,
add(b(u-j, o+j-1, 0)*x^t, j=1..u)+
add(b(u+j-1, o-j, 1), j=1..o)))
end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0$2)):
# Recurrence of D. André (1895).
T := proc(n, k) option remember;
if n < 1 or 2*k > (n-1) then return 0 fi;
if k = 0 then return 2^(n-1) fi;
(2*k + 2)*T(n-1, k) + (n - 2*k)*T(n-1, k-1) end:
seq(seq(T(n, k), k=0..(n-1)/2), n=1..12); # Peter Luschny, Aug 06 2019
|
|
|
MATHEMATICA
|
From Luc Roy, Jul 08 2010: (Start)
It appears that one-half of the sequence A008303 can be obtained with this Mathematica program:
Expand[CoefficientList[Simplify[InverseSeries[Integrate[
Series[(1 + m Sinh[x]^2)^(-1), {x, 0, 15}, {m, 0, 15}], x]]], x]
Denominator[CoefficientList[Series[Exp[x], {x, 0, 15}], x]]]
(* Mathematica Output of Luc Roy's program *)
{0, 1, 0, 2 m, 0, 8 m + 16 m^2, 0, 32 m + 416 m^2 + 272 m^3, 0, 128 m + 7680 m^2 + 24576 m^3 + 7936 m^4, 0, 512 m + 128512 m^2 + 1304832 m^3 + 1841152 m^4 + 353792 m^5, 0, 2048 m + 2084864 m^2 + 56520704 m^3 + 222398464 m^4 + 175627264 m^5 + 22368256 m^6, 0, 8192 m + 33497088 m^2 + 2230947840 m^3 + 20261765120 m^4 + 41731645440 m^5 + 21016670208 m^6 + 1903757312 m^7}
(End)
(* Another Mathematica program *)
m = 14; a = 1 + Sqrt[1 - t]; b = 1 - Sqrt[1 - t];
g[z_] = (E^(b*z) - E^(a*z))/(b*E^(a*z) - a*E^(b*z));
gser = Series[g[z], {z, 0, m}];
Do[p[n]=n!*Coefficient[gser, z, n]//Simplify, {n, 0, m}];
Flatten[ Table[ Coefficient[p[n], t, j], {n, 0, m}, {j, 0, Ceiling[n/2] - 1}]]
FormTable[Table[Coefficient[p[n], t, j], {n, 0, m}, {j, 0, Ceiling[n/2] - 1}]]
gf := Sqrt[x - 1] Cot[y Sqrt[x - 1]] - 1; ser := Series[1/gf, {y, 0, 16}];
cy[n_] := n! Coefficient[ser, y, n]; row[n_] := CoefficientList[cy[n], x];
Table[row[n], {n, 1, 12}] // Flatten (* Peter Luschny, Aug 06 2019 *)
|
|
|
PROG
|
(C++)
#include <vector>
#include <iostream>
using namespace std;
int peaks(const vector<int> & perm) {
int pks=0;
for(int i=1 ; i < perm.size()-1; i++)
if ( perm[i]>perm[i+1] && perm[i]> perm[i-1] ) pks++;
return pks ;
}
int main(int argc, char *argv[]) {
int n=1;
if ( argc > 1 ) n=atoi(argv[1]);
int nmax = n+12;
if ( argc > 2 ) nmax=atoi(argv[2]);
for (; n < nmax ; n++) {
const int kmax = (n+1)/2;
vector<int> Tnk(kmax);
vector<int> perm(n);
for(int i=0 ; i < n ; i++) perm[i]=i+1;
int pks = peaks(perm);
Tnk[pks]++;
while ( next_permutation(perm.begin(), perm.end()) ) {
pks = peaks(perm);
Tnk[pks]++;
}
for (int i=0; i < Tnk.size(); i++) cout << Tnk[i] << ", " ;
}
}
(PARI) {T(n, k) = if(n<1, 0, my(z = sqrt(1 - y + y*O(y^(n\2)))); n!*polcoef(polcoef(z/(z - tanh(x*z)), n, x), k))}; /* Michael Somos, May 24 2023 */
|
|
|
CROSSREFS
|
Sum of entries in row n is n! = A000142(n).
T(2n, n-1) = T(2n+1, n) = A000182(n+1) (the tangent numbers). (End)
|
|
|
KEYWORD
|
nonn,tabf
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
