|
|
A008971
|
|
Triangle read by rows: T(n,k) is the number of permutations of [n] with k increasing runs of length at least 2.
|
|
5
|
|
|
1, 1, 1, 1, 1, 5, 1, 18, 5, 1, 58, 61, 1, 179, 479, 61, 1, 543, 3111, 1385, 1, 1636, 18270, 19028, 1385, 1, 4916, 101166, 206276, 50521, 1, 14757, 540242, 1949762, 1073517, 50521, 1, 44281, 2819266, 16889786, 17460701, 2702765, 1, 132854, 14494859
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
COMMENTS
|
Row n has 1+floor(n/2) terms.
T(n,k) is also the number of permutations of [n] with k "exterior peaks" where we count peaks in the usual way, but add a peak at the beginning if the permutation begins with a descent, e.g. 213 has one exterior peak. T(3,1) = 5 since all permutations of [3] have an exterior peak except 123. This is also the definition for peaks of signed permutations, where we assume that a signed permutation always begins with a zero. - Kyle Petersen, Jan 14 2005
In their book, David and Barton (1962) use the notation T_{N,v*}^* for this array, where N is the length of the permutation and v* is the so-called "number of runs up" in the permutation. In modern terminology, a "run up" in a permutation is an increasing run of length >= 2. See their discussion on p. 154 of their book and see p. 163 for the definition of T_{N,v*}^*.
They do not consider as "runs up" single elements b_i in a permutation b = (b_1, b_2, ..., b_n) even if they satisfy b_{i-1} > b_i > b_{i+1} (with b_{n-1} > b_n when i = n and b_1 > b_2 when i = 1). (The command Runs[b] for permutation b in Mathematica, using the package Combinatorica`, will generate not only the "runs up" of b but also the single elements in the permutation b that satisfy one of the above inequalities. For example, Runs[{3,2,1}] gives the set of runs {{3}, {2}, {1}}, none of which is a "run up".)
So, here n = N and k = v*. On p. 163 of their book they give the recurrence shown below in the FORMULA section from Charalambides' (2002) book: T(n+1, k) = (2*k + 1) * T(n,k) + (n - 2*k + 2) * T(n, k-1) for n >= 0 and 1 <= k <= floor(n/2) + 1. The values of T_{N,v*}^* = T(n, k) appear in Table 10.5 (p. 163) of their book.
Since the complement of a permutation (b_1, b_2, ..., b_n) is (n+1-b_1, n+1-b_2, ..., n+1-b_n), it is clear that the current array T(n, k) is also the number of permutations of [n] with k decreasing runs of length >= 2 (i.e., the number of permutations of [n] with k "runs down" according to David and Barton (1962)).
Note that the number of permutations of [n] with k runs of length >= 2 that are either increasing or decreasing (i.e., the number of permutations of [n] that contain k "runs up" and "runs down" in total) is given by array A059427. One half of array A059427 is given in Table 10.4 (p. 159) in David and Barton (1962)--see also array A008970.
A run that is either a "run up" or "run down" (i.e., an ascending or a descending run of length >= 2) is called "séquence" by André (19th century) and Comtet (1974). See the references for sequence A000708 or for array A059427. (Again, recall that David and Barton do not consider single numbers as either a "run up" or a "run down".)
Morley (1897) proved that in a permutation of [n], #("runs up") + #("runs down") + #(monotonic triplets of adjacent numbers in the permutation) = n - 1. (His definition of a run is highly non-standard!) See the example below.
The number Q(n,k) of circular permutations of [n] that contain k runs that are either "runs up" or "runs down" (that is, k ascending or descending runs of length >= 2) is given by array A008303. More precisely, Q(n+1, 2*(k+1)) = A008303(n, k) for n >= 1 and 0 <= k <= ceiling(n/2)-1. In addition, 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.
The numbers in array A008303 appear in Table 10.6 (p. 163) in David and Barton (1962).
(End)
|
|
REFERENCES
|
Ch. A. Charalambides, Enumerative Combinatorics, Chapman & Hall/CRC, Boca Raton, Florida, 2002.
F. N. David and D. E. Barton, Combinatorial Chance, Charles Griffin, 1962; see Table 10.5, p. 163.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 260.
|
|
LINKS
|
|
|
FORMULA
|
E.g.f.: G(t,x) = sum(T(n,k) t^k x^n/n!, 0<=k<=floor(n/2), n>=0) = sqrt(1-t)/(sqrt(1-t)*cosh(x*sqrt(1-t))-sinh(x*sqrt(1-t))) (Ira M. Gessel).
T(n+1,k) = (2*k+1)*T(n,k) + (n-2*k+2)*T(n,k-1) (see p. 542 of the Charalambides reference or p. 163 in the David and Barton book).
G.f.: T(0)/(1-x), where T(k) = 1 - y*x^2*(k+1)^2/(y*x^2*(k+1)^2 - (1 -x -2*x*k)*(1 -3*x -2*x*k)/T(k+1) ); (continued fraction). - Sergei N. Gladkovskii, Nov 08 2013
cos(x)^(n+1)*(d/dx)^n(1/cos(x)) = Sum_{k = 0..floor(n/2)} T(n,k)*sin(x)^(n-2*k).
Equivalently, let D be the differential operator sqrt(1 - x^2)*d/dx. Then sqrt(1 - x^2)^(n+1)*D^n(1/sqrt(1 - x^2)) = Sum_{k = 0..floor(n/2)} T(n,k)*x^(n-2*k). (End)
|
|
EXAMPLE
|
Triangle T(n,k) (with rows n >= 0 and columns k >= 0) starts as follows:
1;
1;
1, 1;
1, 5;
1, 18, 5;
1, 58, 61;
1, 179, 479, 61;
1, 543, 3111, 1385;
1, 1636, 18270, 19028, 1385;
1, 4916, 101166, 206276, 50521;
...
Example: T(3,1) = 5 because all permutations of [3] with the exception of 321 have one increasing run of length at least 2.
Row 6: cos(x)^7*(d/dx)^6(1/cos(x)) = sin(x)^6 + 179*sin(x)^4 + 479*sin(x)^2 + 61.
Equivalently, (sqrt(1 - x^2))^7*D^6(1/sqrt(1 - x^2)) = x^6 + 179*x^4 + 479*x^2 + 61, where D = sqrt(1 - x^2)*d/dx. (End)
Consider the permutations of [4]. We list the increasing runs of length at least 2 (= "runs up"), the decreasing runs of length at least 2 (= "runs down"), and the monotonic triplets of adjacent numbers in the permutation (which we abbreviate to MTAN for simplicity). The sum of the numbers of these three should be n-1 (see Morley (1897) but notice that his use of the word "run" is highly non-standard).
1234 -> "runs up" = {1234}, "runs down" = {}, MTAN = {123, 234}.
1243 -> "runs up" = {124}, "runs down" = {43}, MTAN = {124}.
1324 -> "runs up" = {13, 24}, "runs down" = {32}, MTAN = {}.
1342 -> "runs up" = {134}, "runs down" = {42}, MTAN = {134}.
1423 -> "runs up" = {14, 23}, "runs down" = {42}, MTAN = {}.
1432 -> "runs up" = {14}, "runs down" = {432}, MTAN = {432}.
2134 -> "runs up" = {134}, "runs down" = {21}, MTAN = {134}.
2143 -> "runs up" = {14}, "runs down" = {21, 43}, MTAN = {}.
2314 -> "runs up" = {23, 14}, "runs down" = {31}, MTAN = {}.
2341 -> "runs up" = {234}, "runs down" = {41}, MTAN = {234}.
2413 -> "runs up" = {24, 13}, "runs down" = {41}, MTAN = {}.
2431 -> "runs up" = {24}, "runs down" = {431}, MTAN = {431}.
3124 -> "runs up" = {124}, "runs down" = {31}, MTAN = {124}.
3142 -> "runs up" = {14}, "runs down" = {31, 42}, MTAN = {}.
3214 -> "runs up" = {14}, "runs down" = {321}, MTAN = {321}.
3241 -> "runs up" = {24}, "runs down" = {32, 41}, MTAN = {}.
3412 -> "runs up" = {34, 12}, "runs down" = {41}, MTAN = {}.
3421 -> "runs up" = {34}, "runs down" = {421}, MTAN = {421}.
4123 -> "runs up" = {123}, "runs down" = {41}, MTAN = {123}.
4132 -> "runs up" = {13}, "runs down" = {41, 32}, MTAN = {}.
4213 -> "runs up" = {13}, "runs down" = {421}, MTAN = {421}.
4231 -> "runs up" = {23}, "runs down" = {42, 31}, MTAN = {}.
4312 -> "runs up" = {12}, "runs down" = {431}, MTAN = {431}.
4321 -> "runs up" = {}, "runs down" = {4321}, MTAN = {432, 321}.
If we let k = number of increasing runs of length >= 2 (= number of "runs up") in a permutation of [4], then (from above) the possible values of k are 0, 1, 2, and we have T(n=4, k=0) = 1, T(n=4, k=1) = 18, and T(n=4, k=2) = 5.
If we let k = number of decreasing runs of length >= 2 (= number of "runs down") in a permutation of [4], then again the possible values of k are 0, 1, 2, and we have T(n=4, k=0) = 1, T(n=4, k=1) = 18, and T(n=4, k=2) = 5.
Finally, note that if b_i, b_{i+1}, b_{i+2} is an increasing triplet of adjacent numbers in permutation b, then n+1-b_i, n+1-b_{i+1}, n+1-b_{i+2} is a decreasing triplet of adjacent numbers in the complement of b, and vice versa. For example, 4213 is the complement of 1342. Their set of monotonic triplets of adjacent numbers are {421} and {134}, respectively, and we have 4 + 1 = 2 + 3 = 1 + 4 = 5.
(End)
|
|
MAPLE
|
G:=sqrt(1-t)/(sqrt(1-t)*cosh(x*sqrt(1-t))-sinh(x*sqrt(1-t))): Gser:=simplify(series(G, x=0, 15)): for n from 0 to 14 do P[n]:=sort(expand(n!*coeff(Gser, x, n))) od: seq(seq(coeff(t*P[n], t^k), k=1..1+floor(n/2)), n=0..14); # edited by Johannes W. Meijer, May 15 2009
# second Maple program:
T:= proc(n, k) option remember; `if`(k=0, 1, `if`(k>iquo(n, 2), 0,
(2*k+1)*T(n-1, k) +(n+1-2*k)*T(n-1, k-1)))
end:
|
|
MATHEMATICA
|
t[n_, 0] = 1; t[n_, k_] /; k > Floor[n/2] = 0;
t[n_ , k_ ] /; k <= Floor[n/2] := t[n, k] = (2 k + 1) t[n - 1, k] + (n - 2 k + 1) t[n - 1, k - 1];
Flatten[Table[t[n, k], {n, 0, 12}, {k, 0, Floor[n/2]}]][[1 ;; 45]] (* Jean-François Alcover, May 30 2011, after given formula *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
tabf,nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|