A246596 Run Length Transform of Catalan numbers A000108.

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, 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, 1, 1, 1, 2, 1, 1, 2, 5, 1, 1, 1, 2, 2, 2, 5, 14, 1, 1, 1, 2, 1, 1, 2, 5

Offset

0,4

Comments

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).

Links

Chai Wah Wu, Table of n, a(n) for n = 0..8192

Index entries for sequences computed with run length transform

Formula

a(n) = A069739(A005940(1+n)). - Antti Karttunen, May 29 2017

Example

From Omar E. Pol, Feb 15 2015: (Start)
Written as an irregular triangle in which row lengths are the terms of A011782:
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,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;
...
Right border gives the Catalan numbers. This is simply a restatement of the theorem that this sequence is the Run Length Transform of A000108.
(End)

Maple

Cat:=n->binomial(2*n, n)/(n+1);
ans:=[];
for n from 0 to 100 do lis:=[]; t1:=convert(n, base, 2); L1:=nops(t1); out1:=1; c:=0;
for i from 1 to L1 do
if out1 = 1 and t1[i] = 1 then out1:=0; c:=c+1;
elif out1 = 0 and t1[i] = 1 then c:=c+1;
elif out1 = 1 and t1[i] = 0 then c:=c;
elif out1 = 0 and t1[i] = 0 then lis:=[c, op(lis)]; out1:=1; c:=0;
fi;
if i = L1 and c>0 then lis:=[c, op(lis)]; fi;
od:
a:=mul(Cat(i), i in lis);
ans:=[op(ans), a];
od:
ans;

Mathematica

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

Prog

(Python)
from operator import mul
from functools import reduce
from gmpy2 import divexact
from re import split
def A246596(n):
    s, c = bin(n)[2:], [1, 1]
    for m in range(1, len(s)):
        c.append(divexact(c[-1]*(4*m+2), (m+2)))
    return reduce(mul, (c[len(d)] for d in split('0+', s))) if n > 0 else 1
# Chai Wah Wu, Sep 07 2014
(Sage) # uses[RLT from A246660]
A246596_list = lambda len: RLT(lambda n: binomial(2*n, n)/(n+1), len)
A246596_list(88) # Peter Luschny, Sep 07 2014
(Scheme) ; using MIT/GNU Scheme
(define (A246596 n) (fold-left (lambda (a r) (* a (A000108 r))) 1 (bisect (reverse (binexp->runcount1list n)) (- 1 (modulo n 2)))))
(define A000108 (EIGEN-CONVOLUTION 1 *))
;; Note: EIGEN-CONVOLUTION can be found from my IntSeq-library and other functions are as in A227349. - Antti Karttunen, Sep 08 2014

Crossrefs

Cf. A000108.

Cf. A003714 (gives the positions of ones).

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

Sequence in context: A326566 A213953 A000361 * A135723 A377442 A125311

Adjacent sequences: A246593 A246594 A246595 * A246597 A246598 A246599

Keyword

nonn

Author

N. J. A. Sloane, Sep 06 2014

Status

approved