cp's OEIS Frontend

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

%I A010027 #46 Dec 13 2024 21:10:33
%S A010027 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,
%T A010027 1854,2119,1,7,63,385,1855,6489,14833,16687,1,8,84,616,3710,17304,
%U A010027 59332,133496,148329,1,9,108,924,6678,38934,177996,600732,1334961,1468457,1
%N A010027 Triangle read by rows: T(n,k) is the number of permutations of [n] having k consecutive ascending pairs (0 <= k <= n-1).
%C A010027 A "consecutive ascending pair" in a permutation p_1, p_2, ..., p_n is a pair p_i, p_{i+1} = p_i + 1.
%C A010027 From _Emeric Deutsch_, May 15 2010: (Start)
%C A010027 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.
%C A010027 When seen as coefficients of polynomials with decreasing exponents: evaluations are A001339 (x=2), A081923 (x=3), A081924 (x=4), A087981 (x=-1).
%C A010027 The sum of the entries in row n is n!.
%C A010027 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)
%C A010027 This is essentially the reversal of the exponential Riordan array [exp(-x)/(1-x)^2,x] (cf. A123513). - _Paul Barry_, Jun 17 2010
%C A010027 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
%D A010027 F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.
%H A010027 Alois P. Heinz, <a href="/A010027/b010027.txt">Rows n = 1..150, flattened</a>
%H A010027 A. N. Myers, <a href="http://dx.doi.org/10.1006/jcta.2002.3279">Counting permutations by their rigid patterns</a>, J. Combin. Theory, A 99 (2002), 345-357. [_Emeric Deutsch_, May 15 2010]
%F A010027 E.g.f.: exp(x*(y-1))/(1-x)^2. - _Vladeta Jovovic_, Jan 03 2003
%F A010027 From _Emeric Deutsch_, May 15 2010: (Start)
%F A010027 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).
%F A010027 U(n,k) = (k+1)!*binomial(n,k)*(1/n)*Sum_{i=0..k+1} (-1)^i/i!.
%F A010027 U(n,k) = (1/n)*binomial(n,k)*d(k+1), where d(j)=A000166(j) (derangement numbers). (End)
%e A010027 Triangle starts:
%e A010027   1;
%e A010027   1, 1;
%e A010027   1, 2,   3;
%e A010027   1, 3,   9,  11;
%e A010027   1, 4,  18,  44,   53;
%e A010027   1, 5,  30, 110,  265,   309;
%e A010027   1, 6,  45, 220,  795,  1854,   2119;
%e A010027   1, 7,  63, 385, 1855,  6489,  14833,  16687;
%e A010027   1, 8,  84, 616, 3710, 17304,  59332, 133496,  148329;
%e A010027   1, 9, 108, 924, 6678, 38934, 177996, 600732, 1334961, 1468457;
%e A010027   ...
%e A010027 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
%e A010027 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
%p A010027 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
%t A010027 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_ *)
%t A010027 T[0,0]:=0; T[1,1]:=1; T[n_,n_]:=T[n,n]=(n-1)T[n-1,n-1]+(n-2)T[n-2,n-2]; T[n_,k_]:=T[n,k]=T[n-1,k] (n-1)/(n-k); Flatten@Table[T[n,k],{n,1,10},{k,1,n}] (* _Oliver Seipel_, Dec 01 2024 *)
%Y A010027 Diagonals, reading from the right-hand edge: A000255, A000166, A000274, A000313, A001260, A001261. A045943 is another diagonal.
%Y A010027 Cf. A123513 (mirror image).
%Y A010027 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.
%K A010027 tabl,nonn
%O A010027 1,5
%A A010027 _N. J. A. Sloane_
%E A010027 More terms from _Vladeta Jovovic_, Jan 03 2003
%E A010027 Original definition from David, Kendall and Barton restored by _N. J. A. Sloane_, Apr 12 2014