A379151 - OEIS

A379151

The binary weights of the Catalan numbers (A000108).

1, 1, 1, 2, 3, 3, 2, 6, 6, 9, 6, 8, 8, 12, 9, 16, 13, 17, 12, 17, 13, 18, 15, 25, 20, 17, 20, 24, 28, 25, 26, 25, 25, 32, 27, 34, 29, 32, 33, 29, 35, 29, 31, 36, 35, 44, 44, 49, 40, 46, 48, 44, 38, 50, 43, 44, 46, 47, 55, 50, 52, 58, 59, 60, 65, 68, 56, 62, 68

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,4

LINKS

Amiram Eldar, Table of n, a(n) for n = 0..10000

Amiram Eldar, Plot of (1/n^2) * Sum_{k=1..n} a(k) for n = 2^(8..23).

Florian Luca and Igor E. Shparlinski, On the g-ary expansions of middle binomial coefficients and Catalan numbers, The Rocky Mountain Journal of Mathematics, Vol. 41, No. 4 (2011), pp. 1291-1301.

FORMULA

a(n) = A000120(A000108(n)).

Two formulas from Luca and Shparlinski (2011):

a(n) >= 3 for all but finitely many positive integers n.

a(n) >> eps(n) * sqrt(log(n)), for all n <= X with at most o(X) exceptions as X -> oo, where eps(n) is a function tending to zero as n -> oo.

Conjecture: Sum_{k=1..n} a(k) ~ n^2 / 2 (see the plot in the Links section).

EXAMPLE

a(10) = 6 because Catalan(10) = 16796 = 100000110011100_2, which has 6 one bits. - Vincenzo Librandi, Feb 05 2025

MATHEMATICA

a[n_] := DigitCount[CatalanNumber[n], 2, 1]; Array[a, 100, 0]

PROG

(PARI) a(n) = hammingweight(binomial(2*n, n)/(n+1));