This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A010027 Triangle read by rows: T(n,k) is the number of permutations of [n] having k consecutive ascending pairs (0<=k<=n-1). 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(n-1)=d(n-1)+d(n), U(n,n-1)=d(n), where d(j)=A000166(j) (derangement numbers). (End) This is essentially the reversal of the exponential Riordan array [exp(-x)/(1-x)^2,x] (cf. A123513). - Paul Barry, Jun 17 2010 U(n-1, k-2) * n*(n-1)/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 A. N. Myers, Counting permutations by their rigid patterns, J. Combin. Theory, A 99 (2002), 345-357. [Emeric Deutsch, May 15 2010] FORMULA E.g.f.: exp(x*(y-1))/(1-x)^2. - Vladeta Jovovic, Jan 03 2003 From Emeric Deutsch, May 15 2010: (Start) U(n,k) = binomial(n-1,k-1)*(k-1)!*Sum((-1)^{k-j-1}*(j+1)/(k-j-1)!, j=0..k-1) (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 (* Jean-François Alcover, Jan 07 2014, after Emeric Deutsch *) CROSSREFS Diagonals, reading from the right-hand 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 back-to-back 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified November 21 03:20 EST 2018. Contains 317427 sequences. (Running on oeis4.)