cp's OEIS Frontend

A242783 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down; triangle T(n,k), n>=0, read by rows.

%I A242783 #33 Sep 13 2020 14:40:38
%S A242783 1,1,2,5,1,21,3,70,50,450,270,4326,602,99,12,1,34944,5376,209863,
%T A242783 139714,13303,1573632,1366016,530432,158720,21824925,15302031,2715243,
%U A242783 74601,302273664,161855232,14872704,2854894485,2600075865,712988175,59062275
%N A242783 Number T(n,k) of permutations of [n] with exactly k (possibly overlapping) occurrences of the consecutive step pattern given by the binary expansion of n, where 1=up and 0=down; triangle T(n,k), n>=0, read by rows.
%C A242783 Sum_{k>0} k*T(n,k) = A249249(n).
%H A242783 Alois P. Heinz, <a href="/A242783/b242783.txt">Rows n = 0..130, flattened</a>
%e A242783 T(7,3) = 12 because 12 permutations of {1,2,3,4,5,6,7} have exactly 3 (possibly overlapping) occurrences of the consecutive step pattern up, up, up given by the binary expansion of 7 = 111_2: (1,2,3,4,5,7,6), (1,2,3,4,6,7,5), (1,2,3,5,6,7,4), (1,2,4,5,6,7,3), (1,3,4,5,6,7,2), (2,1,3,4,5,6,7), (2,3,4,5,6,7,1), (3,1,2,4,5,6,7), (4,1,2,3,5,6,7), (5,1,2,3,4,6,7), (6,1,2,3,4,5,7), (7,1,2,3,4,5,6).
%e A242783 Triangle T(n,k) begins:
%e A242783 : n\k :       0        1       2       3  4  ...
%e A242783 +-----+------------------------------------
%e A242783 :  0  :       1;
%e A242783 :  1  :       1;                             [row  1 of A008292]
%e A242783 :  2  :       2;                             [row  2 of A008303]
%e A242783 :  3  :       5,       1;                    [row  3 of A162975]
%e A242783 :  4  :      21,       3;                    [row  4 of A242819]
%e A242783 :  5  :      70,      50;                    [row  5 of A227884]
%e A242783 :  6  :     450,     270;                    [row  6 of A242819]
%e A242783 :  7  :    4326,     602,     99,     12, 1; [row  7 of A220183]
%e A242783 :  8  :   34944,    5376;                    [row  8 of A242820]
%e A242783 :  9  :  209863,  139714,  13303;            [row  9 of A230695]
%e A242783 : 10  : 1573632, 1366016, 530432, 158720;    [row 10 of A230797]
%p A242783 T:= proc(n) option remember; local b, k, r, h;
%p A242783       k:= iquo(n,2,'r'); h:= 2^ilog2(n);
%p A242783       b:= proc(u, o, t) option remember; `if`(u+o=0, 1, expand(
%p A242783       add(b(u-j, o+j-1, irem(2*t,   h))*`if`(r=0 and t=k, x, 1), j=1..u)+
%p A242783       add(b(u+j-1, o-j, irem(2*t+1, h))*`if`(r=1 and t=k, x, 1), j=1..o)))
%p A242783       end: forget(b);
%p A242783       (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 0, 0))
%p A242783     end:
%p A242783 seq(T(n), n=0..15);
%t A242783 T[n_] := T[n] = Module[{b, k, r, h}, {k, r} = QuotientRemainder[n, 2]; h = 2^Floor[Log[2, n]]; b[u_, o_, t_] := b[u, o, t] = If[u + o == 0, 1, Expand[ Sum[b[u - j, o + j - 1, Mod[2*t, h]]*If[r == 0 && t == k, x, 1], {j, 1, u}] + Sum[b[u + j - 1, o - j, Mod[2*t + 1, h]]*If[r == 1 && t == k, x, 1], {j, 1, o}]]]; Function[p, Table[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][b[n, 0, 0]]]; Table[T[n], {n, 0, 15}] // Flatten (* _Jean-François Alcover_, Feb 20 2016, after _Alois P. Heinz_ *)
%Y A242783 Column k=0-10 give: A242785, A246221, A246222, A246223, A246224, A246225, A246226, A246227, A246228, A246229, A243105.
%Y A242783 Row sums give A000142.
%Y A242783 Cf. A242784, A249249, A295987, A335308.
%K A242783 nonn,tabf,look
%O A242783 0,3
%A A242783 _Alois P. Heinz_, May 22 2014