cp's OEIS Frontend

A001100 Triangle read by rows: T(n,k) = number of permutations of length n with exactly k rising or falling successions, for n >= 1, 0 <= k <= n-1.

%I A001100 #35 May 21 2025 22:03:08
%S A001100 1,0,2,0,4,2,2,10,10,2,14,40,48,16,2,90,230,256,120,22,2,646,1580,
%T A001100 1670,888,226,28,2,5242,12434,12846,7198,2198,366,34,2,47622,110320,
%U A001100 112820,64968,22120,4448,540,40,2,479306,1090270,1108612,650644,236968,54304,7900,748,46,2
%N A001100 Triangle read by rows: T(n,k) = number of permutations of length n with exactly k rising or falling successions, for n >= 1, 0 <= k <= n-1.
%C A001100 Number of permutations of 12...n such that exactly k of the following occur: 12, 23, ..., (n-1)n, 21, 32, ..., n(n-1).
%D A001100 F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 263.
%D A001100 J. Riordan, A recurrence for permutations without rising or falling successions. Ann. Math. Statist. 36 (1965), 708-710.
%D A001100 David Sankoff and Lani Haque, Power Boosts for Cluster Tests, in Comparative Genomics, Lecture Notes in Computer Science, Volume 3678/2005, Springer-Verlag.
%H A001100 Alois P. Heinz, <a href="/A001100/b001100.txt">Rows n = 1..141, flattened</a>
%H A001100 D. P. Robbins, <a href="http://www.jstor.org/stable/2321990">The probability that neighbors remain neighbors after random rearrangements</a>, Amer. Math. Monthly 87 (1980), 122-124.
%F A001100 Let T{n, k} = number of permutations of 12...n with exactly k rising or falling successions. Let S[n](t) = Sum_{k >= 0} T{n, k}*t^k. Then S[0] = 1; S[1] = 1; S[2] = 2*t; S[3] = 4*t+2*t^2; for n >= 4, S[n] = (n+1-t)*S[n-1] - (1-t)*(n-2+3*t)*S[n-2] - (1-t)^2*(n-5+t)*S[n-3] + (1-t)^3*(n-3)*S[n-4].
%F A001100 T(n, 0) =  n! + Sum_{i=1..m-1} (-1)^i*(n-i)!*Sum_{j=1..i} 2^j*binomial(i-1, j-1)*binomial(n-i, j), and T(n, k) = Sum_{i=1..m-1} (-1)^(i-k)*binomial(i, k)*(n-i)!*Sum_{j=1..i} 2^j*binomial(i-1, j-1)*binomial(n-i, j), for k >= 1,  and n >= 1. See the D. P.Robbins link for A(n, k) = T(n, k), and his comment concerning the case k = i = 0 . - _Wolfdieter Lang_, May 17 2025
%e A001100 Triangle T(n,k) begins (n >= 1, k = 0..n-1):
%e A001100     1;
%e A001100     0,    2;
%e A001100     0,    4,    2;
%e A001100     2,   10,   10,   2;
%e A001100    14,   40,   48,  16,   2;
%e A001100    90,  230,  256, 120,  22,  2;
%e A001100   646, 1580, 1670, 888, 226, 28, 2;
%e A001100   ...
%p A001100 S:= proc(n) option remember; `if`(n<4, [1, 1, 2*t, 4*t+2*t^2]
%p A001100        [n+1], expand((n+1-t)*S(n-1) -(1-t)*(n-2+3*t)*S(n-2)
%p A001100        -(1-t)^2*(n-5+t)*S(n-3) +(1-t)^3*(n-3)*S(n-4)))
%p A001100     end:
%p A001100 T:= (n, k)-> coeff(S(n), t, k):
%p A001100 seq(seq(T(n, k), k=0..n-1), n=1..10);  # _Alois P. Heinz_, Jan 11 2013
%t A001100 s[n_] := s[n] = If[n < 4, {1, 1, 2*t, 4*t + 2*t^2}[[n + 1]], Expand[(n + 1 - t)*s[n - 1] - (1 - t)*(n - 2 + 3*t)*s[n - 2] - (1 - t)^2*(n - 5 + t)*s[n - 3] + (1 - t)^3*(n - 3)* s[n - 4]]]; t[n_, k_] := Ceiling[Coefficient[s[n], t, k]]; Flatten[ Table[ Table[t[n, k], {k, 0, n - 1}], {n, 1, 10}]] (* _Jean-François Alcover_, Jan 25 2013, translated from _Alois P. Heinz_'s Maple program *)
%Y A001100 Columns give A002464, A086852, A086853, A086854, A086955.
%Y A001100 Triangle in A086856 multiplied by 2. Cf. A010028.
%Y A001100 Cf. A322294, A322295, A322296.
%K A001100 tabl,nonn
%O A001100 1,3
%A A001100 _N. J. A. Sloane_, Aug 19 2003