cp's OEIS Frontend

A184182 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} whose longest block is of length k (0<=k<=n).

%I A184182 #29 Aug 06 2024 14:36:21
%S A184182 1,0,1,0,1,1,0,3,2,1,0,11,10,2,1,0,53,53,11,2,1,0,309,334,63,11,2,1,0,
%T A184182 2119,2428,415,64,11,2,1,0,16687,20009,3121,425,64,11,2,1,0,148329,
%U A184182 184440,26402,3205,426,64,11,2,1,0,1468457,1881050,248429,27145,3215,426,64,11,2,1
%N A184182 Triangle read by rows: T(n,k) is the number of permutations of {1,2,...,n} whose longest block is of length k (0<=k<=n).
%C A184182 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. Its longest block has length 3.
%H A184182 Alois P. Heinz, <a href="/A184182/b184182.txt">Rows n = 0..140, flattened</a>
%F A184182 T(n,k) = Sum_{m=1..n} (b(n,m,k)-b(n,m,k-1))*(d(m)+d(m-1)), where b(n,m,k) = coefficient of t^n in (t+t^2+...+t^k)^m and d(j) = A000166(j) are the derangement numbers.
%F A184182 T(n,1) = A000255(n-1) for n>=1.
%F A184182 Sum_{k=1..n} T(n,k) = n! (row sums).
%e A184182 T(3,1) = 3 because we have 132, 213, and 321.
%e A184182 T(4,3) = 2 because we have 4123 and 2341.
%e A184182 Triangle starts:
%e A184182   1;
%e A184182   0,   1;
%e A184182   0,   1,   1;
%e A184182   0,   3,   2,  1;
%e A184182   0,  11,  10,  2,  1;
%e A184182   0,  53,  53, 11,  2, 1;
%e A184182   0, 309, 334, 63, 11, 2, 1;
%e A184182   ...
%p A184182 d[-1]:= 0: d[0] := 1: for n to 40 do d[n] := n*d[n-1]+(-1)^n end do: b := proc (n, m, k) options operator, arrow: coeff(add(t^j, j = 1 .. k)^m, t, n) end proc: T := proc (n, k) options operator, arrow: add(b(n, m, k)*(d[m]+d[m-1]), m = 0 .. n)-add(b(n, m, k-1)*(d[m]+d[m-1]), m = 1 .. n) end proc: for n from 0 to 11 do seq(T(n, k), k = 0 .. n) end do; # yields sequence in triangular form
%t A184182 b[n_, m_, k_] := Module[{t}, Coefficient[Total[t^Range[k]]^m, t, n]];
%t A184182 T[n_, k_] := If[n == 0, 1, Module[{d = Subfactorial}, Sum[(b[n, m, k] - b[n, m, k-1])*(d[m]+d[m-1]), {m, 1, n}]]];
%t A184182 Table[T[n, k], {n, 0, 10}, {k, 0, n}] // Flatten (* _Jean-François Alcover_, Aug 06 2024 *)
%Y A184182 Columns k=0..3 give A000007, A000255(n-1), A370390, A370392.
%Y A184182 Cf. A000166, A184180.
%Y A184182 Row sums are A000142.
%K A184182 nonn,tabl
%O A184182 0,8
%A A184182 _Emeric Deutsch_, Feb 13 2011
%E A184182 Row n=0 and column k=0 added by _Alois P. Heinz_, Feb 17 2024