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
Alois P. Heinz, Rows n = 1..150, flattened
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_{j=0..k-1} (-1)^(k-j-1)*(j+1)/(k-j-1)! (1 <= k <= n).
U(n,k) = (k+1)!*binomial(n,k)*(1/n)*Sum_{i=0..k+1} (-1)^i/i!.
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.
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