|
|
A246596
|
|
Run Length Transform of Catalan numbers A000108.
|
|
11
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
|
|
EXAMPLE
|
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
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
A246596_list = lambda len: RLT(lambda n: binomial(2*n, n)/(n+1), len)
(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. A003714 (gives the positions of ones).
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|