A246596 - OEIS

%I #38 Mar 15 2020 05:06:27

%S 1,1,1,2,1,1,2,5,1,1,1,2,2,2,5,14,1,1,1,2,1,1,2,5,2,2,2,4,5,5,14,42,1,

%T 1,1,2,1,1,2,5,1,1,1,2,2,2,5,14,2,2,2,4,2,2,4,10,5,5,5,10,14,14,42,

%U 132,1,1,1,2,1,1,2,5,1,1,1,2,2,2,5,14,1,1,1,2,1,1,2,5

%N Run Length Transform of Catalan numbers A000108.

%C The Run Length Transform of a sequence {S(n), n>=0} is defined to be the sequence {T(n), n>=0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g. 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0)=1 (the empty product).

%H Chai Wah Wu, <a href="/A246596/b246596.txt">Table of n, a(n) for n = 0..8192</a>

%H <a href="/index/Ru#rlt">Index entries for sequences computed with run length transform</a>

%F a(n) = A069739(A005940(1+n)). - _Antti Karttunen_, May 29 2017

%e From _Omar E. Pol_, Feb 15 2015: (Start)

%e Written as an irregular triangle in which row lengths are the terms of A011782:

%e 1;

%e 1;

%e 1,2;

%e 1,1,2,5;

%e 1,1,1,2,2,2,5,14;

%e 1,1,1,2,1,1,2,5,2,2,2,4,5,5,14,42;

%e 1,1,1,2,1,1,2,5,1,1,1,2,2,2,5,14,2,2,2,4,2,2,4,10,5,5,5,10,14,14,42,132;

%e ...

%e Right border gives the Catalan numbers. This is simply a restatement of the theorem that this sequence is the Run Length Transform of A000108.

%e (End)

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

%p ans:=[];

%p for n from 0 to 100 do lis:=[]; t1:=convert(n, base, 2); L1:=nops(t1); out1:=1; c:=0;

%p for i from 1 to L1 do

%p if out1 = 1 and t1[i] = 1 then out1:=0; c:=c+1;

%p elif out1 = 0 and t1[i] = 1 then c:=c+1;

%p elif out1 = 1 and t1[i] = 0 then c:=c;

%p elif out1 = 0 and t1[i] = 0 then lis:=[c, op(lis)]; out1:=1; c:=0;

%p fi;

%p if i = L1 and c>0 then lis:=[c, op(lis)]; fi;

%p od:

%p a:=mul(Cat(i), i in lis);

%p ans:=[op(ans), a];

%p od:

%p ans;

%t f = CatalanNumber; Table[Times @@ (f[Length[#]]&) /@ Select[ Split[ IntegerDigits[n, 2]], #[[1]] == 1&], {n, 0, 87}] (* _Jean-François Alcover_, Jul 11 2017 *)

%o (Python)

%o from operator import mul

%o from functools import reduce

%o from gmpy2 import divexact

%o from re import split

%o def A246596(n):

%o     s, c = bin(n)[2:], [1, 1]

%o     for m in range(1, len(s)):

%o         c.append(divexact(c[-1]*(4*m+2),(m+2)))

%o     return reduce(mul,(c[len(d)] for d in split('0+',s))) if n > 0 else 1

%o # _Chai Wah Wu_, Sep 07 2014

%o (Sage) # uses[RLT from A246660]

%o A246596_list = lambda len: RLT(lambda n: binomial(2*n, n)/(n+1), len)

%o A246596_list(88) # _Peter Luschny_, Sep 07 2014

%o (Scheme) ; using MIT/GNU Scheme

%o (define (A246596 n) (fold-left (lambda (a r) (* a (A000108 r))) 1 (bisect (reverse (binexp->runcount1list n)) (- 1 (modulo n 2)))))

%o (define A000108 (EIGEN-CONVOLUTION 1 *))

%o ;; Note: EIGEN-CONVOLUTION can be found from my IntSeq-library and other functions are as in A227349. - _Antti Karttunen_, Sep 08 2014

%Y Cf. A000108.

%Y Cf. A003714 (gives the positions of ones).

%Y Run Length Transforms of other sequences: A005940, A069739, A071053, A227349, A246588, A246595, A246660, A246661, A246674.

%K nonn

%O 0,4

%A _N. J. A. Sloane_, Sep 06 2014