

A010027


Triangle read by rows: T(n,k) is the number of permutations of [n] having k consecutive ascending pairs (0<=k<=n1).


18



1, 1, 1, 1, 2, 3, 1, 3, 9, 11, 1, 4, 18, 44, 53, 1, 5, 30, 110, 265, 309, 1, 6, 45, 220, 795, 1854, 2119, 1, 7, 63, 385, 1855, 6489, 14833, 16687, 1, 8, 84, 616, 3710, 17304, 59332, 133496, 148329, 1, 9, 108, 924, 6678, 38934, 177996, 600732, 1334961, 1468457, 1
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,5


COMMENTS

A "consecutive ascending pair" in a permutation p_1, p_2, ..., p_n is a pair p_i, p_{i+1} = p_i + 1.
From Emeric Deutsch, May 15 2010: (Start)
The same triangle, but with rows indexed differently, also arises as follows: U(n,k) = number of permutations of [n] having k blocks (1<=k<=n), where a block of a permutation is a maximal sequence of consecutive integers which appear in consecutive positions. For example, the permutation 5412367 has 4 blocks: 5, 4, 123, and 67.
When seen as coefficients of polynomials with decreasing exponents: evaluations are A001339 (x=2), A081923 (x=3), A081924 (x=4), A087981 (x=1).
The sum of the entries in row n is n!.
U(n,n)=A000255(n1)=d(n1)+d(n), U(n,n1)=d(n), where d(j)=A000166(j) (derangement numbers). (End)
This is essentially the reversal of the exponential Riordan array [exp(x)/(1x)^2,x] (cf. A123513).  Paul Barry, Jun 17 2010
U(n1, k2) * n*(n1)/k = number of permutations of [n] with k elements not fixed by the permutation.  Michael Somos, Aug 19 2018


REFERENCES

F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.


LINKS

Table of n, a(n) for n=1..56.
A. N. Myers, Counting permutations by their rigid patterns, J. Combin. Theory, A 99 (2002), 345357. [Emeric Deutsch, May 15 2010]


FORMULA

E.g.f.: exp(x*(y1))/(1x)^2.  Vladeta Jovovic, Jan 03 2003
From Emeric Deutsch, May 15 2010: (Start)
U(n,k) = binomial(n1,k1)*(k1)!*Sum((1)^{kj1}*(j+1)/(kj1)!, j=0..k1) (1<=k<=n).
U(n,k) = (k+1)!*binomial(n,k)*Sum((1)^i/i!, i=0..k+1)/n.
U(n,k) = (1/n)*binomial(n,k)*d(k+1), where d(j)=A000166(j) (derangement numbers). (End)


EXAMPLE

Triangle starts:
1,
1, 1,
1, 2, 3,
1, 3, 9, 11,
1, 4, 18, 44, 53,
1, 5, 30, 110, 265, 309,
1, 6, 45, 220, 795, 1854, 2119,
1, 7, 63, 385, 1855, 6489, 14833, 16687,
1, 8, 84, 616, 3710, 17304, 59332, 133496, 148329,
1, 9, 108, 924, 6678, 38934, 177996, 600732, 1334961, 1468457,
...
For n=3, the permutations 123,132,213,231,312,321 have respectively 2,0,0,1,1,0 consecutive ascending pairs, so row 3 of the triangle is 3,2,1.  N. J. A. Sloane, Apr 12 2014
In the alternative definition, T(4,2)=3 because we have 234.1, 4.123, and 34.12 (the blocks are separated by dots).  Emeric Deutsch, May 16 2010


MAPLE

U := proc (n, k) options operator, arrow: factorial(k+1)*binomial(n, k)*(sum((1)^i/factorial(i), i = 0 .. k+1))/n end proc: for n to 10 do seq(U(n, k), k = 1 .. n) end do; # yields sequence in triangular form; # Emeric Deutsch, May 15 2010


MATHEMATICA

t[n_, k_] := Binomial[n, k]*Subfactorial[k+1]/n; Table[t[n, k], {n, 1, 12}, {k, 1, n}] // Flatten (* JeanFrançois Alcover, Jan 07 2014, after Emeric Deutsch *)


CROSSREFS

Diagonals, reading from the righthand edge: A000255, A000166, A000274, A000313, A001260, A001261. A045943 is another diagonal.
Cf. A123513 (mirror image).
A289632 is the analogous triangle with the additional restriction that all consecutive pairs must be isolated, i.e., must not be backtoback to form longer consecutive sequences.
Sequence in context: A171150 A111589 A259760 * A151880 A108990 A145080
Adjacent sequences: A010024 A010025 A010026 * A010028 A010029 A010030


KEYWORD

tabl,nonn


AUTHOR

N. J. A. Sloane.


EXTENSIONS

More terms from Vladeta Jovovic, Jan 03 2003
Original definition from David, Kendall and Barton restored by N. J. A. Sloane, Apr 12 2014


STATUS

approved



