|
| |
|
|
A010027
|
|
Triangle read by rows: T(n,k) is the number of permutations of [n] having k consecutive ascending pairs (0 <= k <= n-1).
|
|
20
|
|
|
|
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.
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
|
|
|
|
FORMULA
|
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
|
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
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
Original definition from David, Kendall and Barton restored by N. J. A. Sloane, Apr 12 2014
|
|
|
STATUS
|
approved
|
| |
|
|
