login
This site is supported by donations to The OEIS Foundation.

 

Logo


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

Table of n, a(n) for n=1..56.

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

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

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.

License Agreements, Terms of Use, Privacy Policy. .

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