login
Triangle T(n,k) (listed in order T(1,0), T(2,0), T(2,1), T(3,0), T(3,1), T(3,2), T(4,0), etc.) giving the number of 2^k-cycles that occur in the n-th sub-permutation of A069767/A069768 (i.e., in the range [A014137(n-1)..A014138(n-1)] inclusive).
7

%I #5 Jul 29 2017 23:39:23

%S 1,0,1,1,0,1,0,1,1,1,0,1,2,2,1,0,0,3,5,3,1,1,0,3,10,9,4,1,0,1,3,17,24,

%T 14,5,1,0,1,3,28,57,44,20,6,1,0,0,5,41,128,128,71,27,7,1,0,1,4,60,271,

%U 354,234,106,35,8,1,0,0,5,81,549,937,738,384,150,44,9,1,0,0,5,106,1061

%N Triangle T(n,k) (listed in order T(1,0), T(2,0), T(2,1), T(3,0), T(3,1), T(3,2), T(4,0), etc.) giving the number of 2^k-cycles that occur in the n-th sub-permutation of A069767/A069768 (i.e., in the range [A014137(n-1)..A014138(n-1)] inclusive).

%e If we take the fifth such sub-permutation, i.e., the subsequence A069767[23..64]: [45,46,48,49,50,54,55,57,58,59,61,62,63,64,44,47,53,56,60,43,52,40,31,32,41,34,35,36,42,51,39,30,33,38,29,26,27,37,28,25,24,23], subtract 22 from each term and convert the resulting permutation of [1..42] to disjoint cycle notation, we get:

%e (17,31),(20,21,30,29),(3,26,12,40),(6,32,8,35,7,33,11,39),(15,22,18,34,16,25,19,38),(1,23,9,36,4,27,13,41,2,24,10,37,5,28,14,42)

%e which implies that T(5,0) = 0 (no fixed elements), T(5,1) = 1 (one transposition), T(5,2) = 2 (two 4-cycles), T(5,3) = 2 (two 8-cycles), T(5,4) = 1 (and one 16-cycle). It is guaranteed that only cycles whose length is a power of 2 occur in A069767/A069768.

%p A074079bi := (n,k) -> A073346bi(n,k)/(2^k);

%p A074080 := n -> A074079bi(A003056(n)+1, A002262(n));

%p A003056 := n -> floor(sqrt(2*(1+n))-(1/2));

%p A002262 := n -> n - binomial(floor((1/2)+sqrt(2*(1+n))),2);

%Y Upper triangular region of the square array A074079 (actually, only the area above its main diagonal, excluding also the leftmost column). T(n, k) = A073430(n, k)/(2^k) [with the rightmost edge of A073430 discarded]. Row sums: A073431. A000108(n) = Sum_{i=0..n-1} 2^i * T(n, i). Cf. A073346, A003056, A002262.

%K nonn,tabl

%O 0,13

%A _Antti Karttunen_, Aug 19 2002