A031443 -id:A031443 - cp's OEIS frontend

A014486 List of totally balanced sequences of 2n binary digits written in base 10. Binary expansion of each term contains n 0's and n 1's and reading from left to right (the most significant to the least significant bit), the number of 0's never exceeds the number of 1's.

0, 2, 10, 12, 42, 44, 50, 52, 56, 170, 172, 178, 180, 184, 202, 204, 210, 212, 216, 226, 228, 232, 240, 682, 684, 690, 692, 696, 714, 716, 722, 724, 728, 738, 740, 744, 752, 810, 812, 818, 820, 824, 842, 844, 850, 852, 856, 866, 868, 872, 880, 906, 908, 914

Offset: 0

Wouter Meeussen

The binary Dyck-Language (A063171) in decimal representation.
These encode width 2n mountain ranges, rooted planar trees of n+1 vertices and n edges, planar planted trees with n nodes, rooted plane binary trees with n+1 leaves (2n edges, 2n+1 vertices, n internal nodes, the root included), Dyck words, binary bracketings, parenthesizations, non-crossing handshakes and partitions and many other combinatorial structures in Catalan family, enumerated by A000108.
Is Sum_{k=1..n} a(k) / n^(5/2) bounded? - Benoit Cloitre, Aug 18 2002
This list is the intersection of A061854 and A031443. - Jason Kimberley, Jan 18 2013
The sequence does start at n = 0, since in the binary interpretation of the Dyck language (e.g., as parenthesizations where "1" stands for "(" and "0" stands for ")") having a(0) = 0 will do since it would stand for the empty string where the "0"s and "1"s are balanced (hence the parentheses are balanced). - Daniel Forgues, Feb 17 2013
It appears that for n>=1 this sequence can be obtained by concatenating the terms of the irregular array whose n-th row length is A000108(n) and that is defined recursively by B(n,0) = A020988(n) and B(n,k) = B(n, k-1) + D(n, k-1) where D(x,y) = (2^(2*(A089309(B(x,y))-1))-1)*(2/3) + 2^A007814(B(x,y)). - Raúl Mario Torres Silva and Michel Marcus, May 01 2020
This encoding is related to the ranking by standard ordered tree numbers in that (1) the binary encoding of trees ordered by standard ranking is given by A358505, while (2) the standard ranking of trees ordered by binary encoding is given by A358523. - Gus Wiseman, Nov 21 2022

			a(19) = 226_10 = 11100010_2 = A063171(19) as bracket expression: ( ( ( ) ) )( ) and as a binary tree, proceeding from left to right in depth-first fashion, with 1's in binary expansion standing for internal (branching) nodes and 0's for leaves:
  0   0
   \ /
    1   0 0  (0)
     \ /   \ /
      1     1
       \   /
         1
Note that in this coding scheme the last leaf of the binary trees (here in parentheses) is implicit. This tree can be also converted to a particular S-expression in languages like Lisp, Scheme and Prolog, if we interpret its internal nodes (1's) as cons cells with each leftward leaning branch being the "car" and the rightward leaning branch the "cdr" part of the pair, with the terminal nodes (0's) being ()'s (NILs). Thus we have (cons (cons (cons () ()) ()) (cons () ())) = '( ( ( () . () ) . () ) . ( () . () ) ) = (((())) ()) i.e., the same bracket expression as above, but surrounded by extra parentheses. This mapping is performed by the Scheme function A014486->parenthesization given below.
From _Gus Wiseman_, Nov 21 2022: (Start)
The terms and corresponding ordered rooted trees begin:
    0: o
    2: (o)
   10: (oo)
   12: ((o))
   42: (ooo)
   44: (o(o))
   50: ((o)o)
   52: ((oo))
   56: (((o)))
  170: (oooo)
  172: (oo(o))
  178: (o(o)o)
  180: (o(oo))
  184: (o((o)))
(End)

Donald E. Knuth, The Art of Computer Programming, Vol. 4A: Combinatorial Algorithms, Part 1, Addison-Wesley, 2011, Section 7.2.1.6, pp. 443 (Algorithm P).

Paolo Xausa, Table of n, a(n) for n = 0..23713 (terms 0..2500 from Franklin T. Adams-Watters).
Jason Bell, Thomas Finn Lidbetter, and Jeffrey Shallit, Additive Number Theory via Approximation by Regular Languages, arXiv:1804.07996 [cs.FL], 2018.
N. G. De Bruijn and B. J. M. Morselt, A note on plane trees, J. Combinatorial Theory 2 (1967), 27-34.
Gennady Eremin, Dynamics of balanced parentheses, lexicographic series and Dyck polynomials, arXiv:1909.07675 [math.CO], 2019.
R. K. Guy, The Second Strong Law of Small Numbers, Math. Mag, 63 (1990), no. 1, 3-20.
Antti Karttunen, Catalan ranking and unranking functions, OEIS Wiki.
Antti Karttunen, Illustration of 626 initial terms (up to size n=7) with various combinatorial interpretations of Catalan numbers encoded by this sequence.
Antti Karttunen, a089408.c - C program for computing this sequence and many of the related automorphisms.
Antti Karttunen, Some notes on Catalan's Triangle.
Dana G. Korssjoen, Biyao Li, Stefan Steinerberger, Raghavendra Tripathi, and Ruimin Zhang, Finding structure in sequences of real numbers via graph theory: a problem list, arXiv:2012.04625 [math.CO], 2020-2021.
D. L. Kreher and D. R. Stinson, Combinatorial Algorithms, Generation, Enumeration and Search, CRC Press, 1998.
Thomas Finn Lidbetter, Counting, Adding, and Regular Languages, Master's Thesis, University of Waterloo, Ontario, Canada, 2018.
R. J. Mathar, Topologically Distinct Sets of Non-intersecting Circles in the Plane, arXiv:1603.00077 [math.CO], 2016.
OEIS Wiki, Combinatorial interpretations of Catalan numbers
Frank Ruskey, Algorithmic Solution of Two Combinatorial Problems.
R. P. Stanley, Hipparchus, Plutarch, Schroeder and Hough, Am. Math. Monthly, Vol. 104, No. 4, p. 344, 1997.
R. P. Stanley, Exercises on Catalan and Related Numbers.
Paolo Xausa, A Mathematica implementation of Knuth's algorithms P and U.
Index entries for encodings of plane rooted trees (various subsets of this sequence).
Index entries for sequences related to parenthesizing
Index entries for signature-permutations induced by Catalan automorphisms (permutations of natural numbers induced by various bijective operations acting on these structures)
Index entries for the sequences induced by list functions of Lisp (sequences induced by various other operations on these codes or the corresponding structures).

Characteristic function: A080116. Inverse function: A080300.
The terms of binary width 2n are counted by A000108(n). Subset of A036990. Number of peaks in each mountain (number of leaves in rooted plane general trees): A057514. Number of trailing zeros in the binary expansion: A080237. First differences: A085192.
Cf. also A009766, A014137, A071156, A079436, A085184, A213704.
Cf. A020988, A089309, A007814.
Branches of the ordered tree are counted by A057515.
Edges of the ordered tree are counted by A072643.
The Matula-Goebel number of the ordered tree is A127301.
The standard ranking of the ordered tree is A358523.
The depth of the ordered tree is A358550.
Nodes of the ordered tree are counted by A358551.
Cf. A000081, A001263, A358505, A358524.

# Maple procedure CatalanUnrank is adapted from the algorithm 3.24 of the CAGES book and the Scheme function CatalanUnrank from Ruskey's thesis. See the a089408.c program for the corresponding C procedures.
CatalanSequences := proc(upto_n) local n,a,r; a := []; for n from 0 to upto_n do for r from 0 to (binomial(2*n,n)/(n+1))-1 do a := [op(a),CatalanUnrank(n,r)]; od; od; return a; end;
CatalanUnrank := proc(n,rr) local r,x,y,lo,m,a; r := (binomial(2*n,n)/(n+1))-(rr+1); y := 0; lo := 0; a := 0; for x from 1 to 2*n do m := Mn(n,x,y+1); if(r <= lo+m-1) then y := y+1; a := 2*a + 1; else lo := lo+m; y := y-1; a := 2*a; fi; od; return a; end;
Mn := (n,x,y) -> binomial(2*n-x,n-((x+y)/2)) - binomial(2*n-x,n-1-((x+y)/2));
# Alternative:
bin := n -> ListTools:-Reverse(convert(n, base, 2)):
isA014486 := proc(n): local B, s, b; s := 0;
    if n > 0 then
      for b in bin(n) do
          s := s + ifelse(b = 1, 1, -1);
           if 0 > s then return false fi;
      od fi;
  s = 0 end:
select(isA014486, [seq(0..240)]);  # Peter Luschny, Mar 13 2024

cat[ n_ ] := (2 n)!/n!/(n+1)!; b2d[li_List] := Fold[2#1+#2&, 0, li]
d2b[n_Integer] := IntegerDigits[n, 2]
tree[n_] := Join[Table[1, {i, 1, n}], Table[0, {i, 1, n}]]
nexttree[t_] := Flatten[Reverse[t]/. {a___, 0, 0, 1, b___}:> Reverse[{Sort[{a, 0}]//Reverse, 1, 0, b}]]
wood[ n_ /; n<8 ] := NestList[ nexttree, tree[ n ], cat[ n ]-1 ]
Table[ Reverse[ b2d/@wood[ j ] ], {j, 0, 6} ]//Flatten
(* Alternative code *)
tbQ[n_]:=Module[{idn2=IntegerDigits[n,2]},Count[idn2,1]==Length[idn2]/2&&Min[Accumulate[idn2/.{0->-1}]]>=0]; Join[{0},Select[Range[900],tbQ]] (* Harvey P. Dale, Jul 04 2013 *)
balancedQ[0] = True; balancedQ[n_] := Module[{s = 0}, Do[s += If[b == 1, 1, -1]; If[s < 0, Return[False]], {b, IntegerDigits[n, 2]}]; Return[s == 0] ]; A014486 = FromDigits /@ IntegerDigits[Select[Range[0, 1000], balancedQ ]] (* Jean-François Alcover, Mar 05 2016 *)
A014486Q[0] = True; A014486Q[n_] := Catch[Fold[If[# < 0, Throw[False], If[#2 == 0, # - 1, # + 1]] &, 0, IntegerDigits[n, 2]] == 0]; Select[Range[0, 880], A014486Q] (* JungHwan Min, Dec 11 2016 *)
(* Uses Algorithm P from Knuth's TAOCP section 7.2.1.6 - see References and Links. *)
alist[n_] := Block[{a = Flatten[Table[{1, 0}, n]], m = 2*n - 1, j, k},
    FromDigits[#, 2]& /@ Reap[
    While[True,
        Sow[a]; a[[m]] = 0;
        If[a[[m - 1]] == 0,
            a[[--m]] = 1, j = m - 1; k = 2*n - 1;
            While[j > 1 && a[[j]] == 1, a[[j--]] = 0; a[[k]] = 1; k -= 2];
            If[j == 1, Break[]];
            a[[j]] = 1; m = 2*n - 1]
    ]][[2, 1]]];
Join[{{0}, {2}}, Array[alist, 4, 2]] (* Paolo Xausa, Mar 16 2024 *)

isA014486(n)=my(v=binary(n),t=0);for(i=1,#v,t+=if(v[i],1,-1);if(t<0,return(0))); t==0 \\ Charles R Greathouse IV, Jun 10 2011

a_rows(N) = my(a=Vec([[0]], N)); for(r=1, N-1, my(b=a[r], c=List()); foreach(b, t, my(v=if(t, valuation(t, 2), 0)); for(i=0, v, listput(~c, (t<<2)+(2<Ruud H.G. van Tol, May 16 2024

from itertools import count, islice
from sympy.utilities.iterables import multiset_permutations
def A014486_gen(): # generator of terms
    yield 0
    for l in count(1):
        for s in multiset_permutations('0'*l+'1'*(l-1)):
            c, m = 0, (l<<1)-1
            for i in range(m):
                if s[i] == '1':
                    c += 2
                if cA014486_list = list(islice(A014486_gen(),30)) # Chai Wah Wu, Nov 28 2023

def is_A014486(n) :
    B = bin(n)[2::] if n != 0 else 0
    s = 0
    for b in B :
        s += 1 if b=='1' else -1
        if 0 > s : return False
    return 0 == s
def A014486_list(n): return [k for k in (1..n) if is_A014486(k) ]
A014486_list(888) # Peter Luschny, Aug 10 2012

Additional comments from Antti Karttunen, Aug 11 2000 and May 25 2004

Added a(0)=0 (which had been removed in June 2011), Joerg Arndt, Feb 27 2013

A053754 If k is in the sequence then 2k and 2k+1 are not (and 0 is in the sequence); when written in binary k has an even number of bits (0 has 0 digits).

Original entry on oeis.org

0, 2, 3, 8, 9, 10, 11, 12, 13, 14, 15, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148

Offset: 1

Henry Bottomley, Apr 06 2000

Runs of successive terms with same number of bits have length twice powers of 4 (A081294). [Clarified by Michel Marcus, Oct 21 2020]
The sequence A081294 counts compositions of even numbers - Gus Wiseman, Aug 12 2021
A031443 is a subsequence; A179888 is the intersection of this sequence and A032925. - Reinhard Zumkeller, Jul 31 2010
The lower and upper asymptotic densities of this sequence are 1/3 and 2/3, respectively. - Amiram Eldar, Feb 01 2021
From Gus Wiseman, Aug 10 2021: (Start)
Also numbers k such that the k-th composition in standard order (row k of A066099) has even sum. The terms and corresponding compositions begin:
  0: ()   2: (2)      8: (4)
          3: (1,1)    9: (3,1)
                     10: (2,2)
                     11: (2,1,1)
                     12: (1,3)
                     13: (1,2,1)
                     14: (1,1,2)
                     15: (1,1,1,1)
The following pertain to compositions in standard order: A000120, A029837, A070939, A066099, A124767.
(End)

Reinhard Zumkeller, Table of n, a(n) for n = 1..10001

Cf. A031443, A032925, A179888.
Positions of even terms in A029837 with offset 0.
The complement (the odd version) is A053738, counted by A000302.
The version for Heinz numbers of partitions is A300061, counted by A058696.
Cf. A000120, A001969, A008549, A070939, A080791, A114121.

a053754 n = a053754_list !! (n-1)
a053754_list = 0 : filter (even . a070939) [1..]
-- Reinhard Zumkeller, Apr 18 2015

Select[Range[0, 150], EvenQ @ IntegerLength[#, 2] &] (* Amiram Eldar, Feb 01 2021 *)

lista(nn) = {my(va = vector(nn)); for (n=2, nn, my(k=va[n-1]+1); while (#select(x->(x==k\2), va), k++); va[n] = k;); va;} \\ Michel Marcus, Oct 20 2020

PARI
```
a(n) = n-1 + (1<Kevin Ryde, Apr 30 2021
```

Offset corrected by Reinhard Zumkeller, Jul 30 2010

A037861 (Number of 0's) - (number of 1's) in the base-2 representation of n.

Original entry on oeis.org

1, -1, 0, -2, 1, -1, -1, -3, 2, 0, 0, -2, 0, -2, -2, -4, 3, 1, 1, -1, 1, -1, -1, -3, 1, -1, -1, -3, -1, -3, -3, -5, 4, 2, 2, 0, 2, 0, 0, -2, 2, 0, 0, -2, 0, -2, -2, -4, 2, 0, 0, -2, 0, -2, -2, -4, 0, -2, -2, -4, -2, -4, -4, -6, 5, 3, 3, 1, 3, 1, 1, -1, 3

Offset: 0

Clark Kimberling

-Sum_{n>=1} a(n)/((2*n)*(2*n+1)) = the "alternating Euler constant" log(4/Pi) = 0.24156... - (see A094640 and Sondow 2005, 2010).

a(A072600(n)) < 0; a(A072601(n)) <= 0; a(A031443(n)) = 0; a(A072602(n)) >= 0; a(A072603(n)) > 0; a(A031444(n)) = 1; a(A031448(n)) = -1; abs(a(A089648(n))) <= 1. - Reinhard Zumkeller, Feb 07 2015

Reinhard Zumkeller, Table of n, a(n) for n = 0..10000
Jonathan Sondow, Double integrals for Euler's constant and ln(4/Pi) and an analog of Hadjicostas's formula, arXiv:math/0211148 [math.CA], 2002-2004; Amer. Math. Monthly 112 (2005), 61-65.
Jonathan Sondow, New Vacca-Type Rational Series for Euler's Constant and Its "Alternating" Analog ln(4/Pi), arXiv:math/0508042 [math.NT], 2005; Additive Number Theory, Festschrift In Honor of the Sixtieth Birthday of Melvyn B. Nathanson (D. Chudnovsky and G. Chudnovsky, eds.), Springer, 2010, pp. 331-340.
Ralf Stephan, Divide-and-conquer generating functions. I. Elementary sequences, arXiv:math/0307027 [math.CO], 2003.
Ralf Stephan, Some divide-and-conquer sequences with (relatively) simple ordinary generating functions, 2004.
Ralf Stephan, Table of generating functions (ps file).
Ralf Stephan, Table of generating functions (pdf file).
Index entries for sequences related to binary expansion of n

Cf. A031443 for n when a(n)=0, A053738 for n when a(n) odd, A053754 for n when a(n) even, A030300 for a(n+1) mod 2.
Cf. A066879, A094640, A110625, A145037.
Cf. A072600, A072601, A072602, A072603, A031444, A031448, A089648.
See A268289 for a recurrence based on this sequence.

a037861 n = a023416 n - a000120 n  -- Reinhard Zumkeller, Aug 01 2013

A037861:= proc(n) local L;
     L:= convert(n,base,2);
     numboccur(0,L) - numboccur(1,L)
end proc:
map(A037861, [$0..100]); # Robert Israel, Mar 08 2016

Table[Count[ IntegerDigits[n, 2], 0] - Count[IntegerDigits[n, 2], 1], {n, 0, 75}]

a(n) = if (n==0, 1, 1 + logint(n, 2) - 2*hammingweight(n)); \\ Michel Marcus, May 15 2020 and Jun 16 2020

def A037861(n):
    return 2*format(n,'b').count('0')-len(format(n,'b')) # Chai Wah Wu, Mar 07 2016

From Henry Bottomley, Oct 27 2000: (Start)
a(n) = A023416(n) - A000120(n) = A029837(n) - 2*A000120(n) = 2*A023416(n) - A029837(n).
a(2*n) = a(n) + 1; a(2*n + 1) = a(2*n) - 2 = a(n) - 1. (End)
G.f. satisfies A(x) = (1 + x)*A(x^2) - x*(2 + x)/(1 + x). - Franklin T. Adams-Watters, Dec 26 2006
a(n) = b(n) for n > 0 with b(0) = 0 and b(n) = b(floor(n/2)) + (-1)^(n mod 2). - Reinhard Zumkeller, Dec 31 2007
G.f.: 1 + (1/(1 - x))*Sum_{k>=0} x^(2^k)*(x^(2^k) - 1)/(1 + x^(2^k)). - Ilya Gutkovskiy, Apr 07 2018

A079309 a(n) = C(1,1) + C(3,2) + C(5,3) + ... + C(2*n-1,n).

Original entry on oeis.org

1, 4, 14, 49, 175, 637, 2353, 8788, 33098, 125476, 478192, 1830270, 7030570, 27088870, 104647630, 405187825, 1571990935, 6109558585, 23782190485, 92705454895, 361834392115, 1413883873975, 5530599237775, 21654401079325, 84859704298201, 332818970772253

Offset: 1

Miklos Kristof, Feb 10 2003

a(n) is the sum of pyramid weights of all Dyck paths of length 2n (for pyramid weight see Denise and Simion). Equivalently, a(n) is the sum of the total lengths of end branches of an ordered tree, summation being over all ordered trees with n edges. For example, the five ordered trees with 3 edges have total lengths of endbranches 3,2,3,3 and 3. - Emeric Deutsch, May 30 2003
a(n) is the number of Motzkin paths of length 2n with exactly one level segment. (A level segment is a maximal sequence of contiguous flatsteps.) Example: for n=2, the paths counted are FFFF, FFUD, UDFF, UFFD. The formula for a(n) below counts these paths by length of the level segment. - David Callan, Jul 15 2004
The inverse Catalan transform yields A024495, shifted once left. - R. J. Mathar, Jul 07 2009
From Paul Barry, Mar 29 2010: (Start)
Hankel transform is A138341.
The aerated sequence 0, 0, 1, 0, 4, 0, 14, 0, 49, ... has e.g.f. int(cosh(x-t)*Bessel_I(1,2t), t = 0..x). (End)
a(n) is the number of terms of A031443 not exceeding 4^n. - Vladimir Shevelev, Oct 01 2010
Also the number of nonempty subsets of {1..2n} with median n, bisection of A361801. The version containing n is A001700 (bisected). Replacing 2n with 2n+1 and n with n+1 gives A006134. For mean instead of median we have A212352. - Gus Wiseman, Apr 16 2023

			a(4) = C(1,1) + C(3,2) + C(5,3) + C(7,4) = 1 + 3 + 10 + 35 = 49.
G.f. = x + 4*x^2 + 14*x^3 + 49*x^4 + 175*x^5 + 637*x^6 + 2353*x^7 + ...
From _Gus Wiseman_, Apr 16 2023: (Start)
The a(1) = 1 through a(3) = 14 subsets of {1..2n} with median n:
  {1}  {2}      {3}
       {1,3}    {1,5}
       {1,2,3}  {2,4}
       {1,2,4}  {1,3,4}
                {1,3,5}
                {1,3,6}
                {2,3,4}
                {2,3,5}
                {2,3,6}
                {1,2,4,5}
                {1,2,4,6}
                {1,2,3,4,5}
                {1,2,3,4,6}
                {1,2,3,5,6}
(End)

Vincenzo Librandi and Robert Israel, Table of n, a(n) for n = 1..1500 (terms 1..200 from Vincenzo Librandi).
A. Denise and R. Simion, Two combinatorial statistics on Dyck paths, Discrete Math., 137, 1995, 155-176.
Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
R. Witula, Ramanujan type trigonometric formulas, Demonstratio Mathematica, Vol. XLV, No. 4 (2012), 789-796. - From _N. J. A. Sloane_, Jan 01 2013

Cf. A001700, A024495, A066796, A138341.
Equals A024718(n) - 1.
This is the even (or odd) bisection of A361801.
A007318 counts subsets by length, A327481 by mean, A013580 by median.
A359893 and A359901 count partitions by median.
Cf. A000975, A057552, A231147, A361654, A361864, A362046.

a := n -> add(binomial(2*j, j)/2, j=1..n): seq(a(n), n=1..24); # Zerinvary Lajos, Oct 25 2006
a := n -> add(abs(binomial(-j, -2*j)), j=1..n): seq(a(n), n=1..24); # Zerinvary Lajos, Oct 03 2007
f:= gfun:-rectoproc({n*a(n) +(-5*n+2)*a(n-1) +2*(2*n-1)*a(n-2)=0,a(1)=1,a(2)=4},a(n),remember):
map(f, [$1..100]); # Robert Israel, Jun 24 2015

Rest[CoefficientList[Series[(1/Sqrt[1-4*x]-1)/(1-x)/2, {x, 0, 20}], x]] (* Vaclav Kotesovec, Feb 13 2014 *)
Accumulate[Table[Binomial[2n-1,n],{n,30}]] (* Harvey P. Dale, Jan 06 2021 *)

{a(n) = sum(k=1, n, binomial(2*k - 1, k))}; /* Michael Somos, Feb 14 2006 */

my(x='x+O('x^40)); Vec((1/sqrt(1-4*x)-1)/(1-x)/2) \\ Altug Alkan, Dec 24 2015

a(n) = (1/2)*(C(2, 1) + C(4, 2) + C(6, 3) + ... + C(2*n, n)) = A066796(n)/2. - Vladeta Jovovic, Feb 12 2003
G.f.: (1/sqrt(1 - 4*x) - 1)/(1 - x)/2. - Vladeta Jovovic, Feb 12 2003
Given g.f. A(x), then x * A(x - x^2) is g.f. of A024495. - Michael Somos, Feb 14 2006
a(n) = A066796(n)/2. - Zerinvary Lajos, Oct 25 2006
a(n) = Sum_{0 <= i <= j <= n} binomial(i+j, i). - Benoit Cloitre, Nov 25 2006
D-finite with recurrence n*a(n) + (-5*n+2)*a(n-1) + 2*(2*n-1)*a(n-2) = 0. - R. J. Mathar, Nov 30 2012
a(n) ~ 2^(2*n+1) / (3*sqrt(Pi*n)). - Vaclav Kotesovec, Feb 13 2014
a(n) = Sum_{k=0..n-1} A001700(k). - Doug Bell, Jun 23 2015
a(n) = -binomial(2*n+1, n)*hypergeom([1, n+3/2], [n+2], 4) - (i/sqrt(3) + 1)/2. - Peter Luschny, May 18 2018
From Gus Wiseman, Apr 18 2023: (Start)
a(n) = A024718(n) - 1.
a(n) = A231147(2n+1,n).
a(n) = A361801(2n) = A361801(2n+1). (End)
a(n) = Sum_{k=0..floor(n/2)} (-1)^k*binomial(2*n+2-k, n-2*k). - Michael Weselcouch, Jun 17 2025
a(n) = binomial(2*(1+n), n)*hypergeom([1, (1-n)/2, -n/2], [-2*(1+n), 3+n], 4). - Stefano Spezia, Jun 18 2025

More terms from Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), Feb 11 2003

A345910 Numbers k such that the k-th composition in standard order (row k of A066099) has alternating sum -1.

Original entry on oeis.org

6, 20, 25, 27, 30, 72, 81, 83, 86, 92, 98, 101, 103, 106, 109, 111, 116, 121, 123, 126, 272, 289, 291, 294, 300, 312, 322, 325, 327, 330, 333, 335, 340, 345, 347, 350, 360, 369, 371, 374, 380, 388, 393, 395, 398, 402, 405, 407, 410, 413, 415, 420, 425, 427

Offset: 1

Gus Wiseman, Jul 01 2021

nonn

The alternating sum of a sequence (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i.

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The sequence of terms together with the corresponding compositions begins:
      6: (1,2)
     20: (2,3)
     25: (1,3,1)
     27: (1,2,1,1)
     30: (1,1,1,2)
     72: (3,4)
     81: (2,4,1)
     83: (2,3,1,1)
     86: (2,2,1,2)
     92: (2,1,1,3)
     98: (1,4,2)
    101: (1,3,2,1)
    103: (1,3,1,1,1)
    106: (1,2,2,2)
    109: (1,2,1,2,1)

These compositions are counted by A001791.
A version using runs of binary digits is A031444.
These are the positions of -1's in A124754.
The opposite (positive 1) version is A345909.
The reverse version is A345912.
The version for alternating sum of prime indices is A345959.
Standard compositions: A000120, A066099, A070939, A124754, A228351, A344618.
A000041 counts partitions of 2n with alternating sum 0, ranked by A000290.
A000070 counts partitions of 2n+1 with alternating sum 1, ranked by A001105.
A011782 counts compositions.
A097805 counts compositions by sum and alternating sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A316524 gives the alternating sum of prime indices (reverse: A344616).
A345197 counts compositions by sum, length, and alternating sum.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218, ranked by A344619/A344619.
- k = 1:  counted by A000984, ranked by A345909/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2:  counted by A088218, ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k <= 0: counted by A058622(n-1), ranked by A345915/A345916.
- k > 0:  counted by A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k != 0: counted by A058622, ranked by A345921/A345921.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000097, A000346, A008549, A025047, A027187, A031443, A031448, A114121, A119899, A126869, A238279, A344617.

stc[n_]:=Differences[Prepend[Join@@Position[ Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];
Select[Range[0,100],ats[stc[#]]==-1&]

A345909 Numbers k such that the k-th composition in standard order (row k of A066099) has alternating sum 1.

Original entry on oeis.org

1, 5, 7, 18, 21, 23, 26, 29, 31, 68, 73, 75, 78, 82, 85, 87, 90, 93, 95, 100, 105, 107, 110, 114, 117, 119, 122, 125, 127, 264, 273, 275, 278, 284, 290, 293, 295, 298, 301, 303, 308, 313, 315, 318, 324, 329, 331, 334, 338, 341, 343, 346, 349, 351, 356, 361

Offset: 1

Gus Wiseman, Jun 30 2021

nonn

The alternating sum of a composition (y_1,...,y_k) is Sum_i (-1)^(i-1) y_i.

			The sequence of terms together with the corresponding compositions begins:
      1: (1)             87: (2,2,1,1,1)
      5: (2,1)           90: (2,1,2,2)
      7: (1,1,1)         93: (2,1,1,2,1)
     18: (3,2)           95: (2,1,1,1,1,1)
     21: (2,2,1)        100: (1,3,3)
     23: (2,1,1,1)      105: (1,2,3,1)
     26: (1,2,2)        107: (1,2,2,1,1)
     29: (1,1,2,1)      110: (1,2,1,1,2)
     31: (1,1,1,1,1)    114: (1,1,3,2)
     68: (4,3)          117: (1,1,2,2,1)
     73: (3,3,1)        119: (1,1,2,1,1,1)
     75: (3,2,1,1)      122: (1,1,1,2,2)
     78: (3,1,1,2)      125: (1,1,1,1,2,1)
     82: (2,3,2)        127: (1,1,1,1,1,1,1)
     85: (2,2,2,1)      264: (5,4)

These compositions are counted by A000984 (bisection of A126869).
The version for prime indices is A001105.
A version using runs of binary digits is A031448.
These are the positions of 1's in A124754.
The opposite (negative 1) version is A345910.
The reverse version is A345911.
The version for Heinz numbers of partitions is A345958.
Standard compositions: A000120, A066099, A070939, A124754, A228351, A344618.
A000070 counts partitions with alternating sum 1 (ranked by A345957).
A000097 counts partitions with alternating sum 2 (ranked by A345960).
A011782 counts compositions.
A097805 counts compositions by sum and alternating sum.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A316524 gives the alternating sum of prime indices (reverse: A344616).
A344610 counts partitions by sum and positive reverse-alternating sum.
A344611 counts partitions of 2n with reverse-alternating sum >= 0.
A345197 counts compositions by sum, length, and alternating sum.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
- k = 0:  counted by A088218, ranked by A344619/A344619.
- k = 1:  counted by A000984, ranked by A345909 (this sequence)/A345911.
- k = -1: counted by A001791, ranked by A345910/A345912.
- k = 2:  counted by A088218, ranked by A345925/A345922.
- k = -2: counted by A002054, ranked by A345924/A345923.
- k >= 0: counted by A116406, ranked by A345913/A345914.
- k <= 0: counted by A058622(n-1), ranked by A345915/A345916.
- k > 0:  counted by A027306, ranked by A345917/A345918.
- k < 0:  counted by A294175, ranked by A345919/A345920.
- k != 0: counted by A058622, ranked by A345921/A345921.
- k even: counted by A081294, ranked by A053754/A053754.
- k odd:  counted by A000302, ranked by A053738/A053738.
Cf. A000346, A008549, A025047, A031443, A031444, A034871, A114121, A238279, A304620, A344651.

stc[n_]:=Differences[Prepend[Join@@Position[ Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];
Select[Range[0,100],ats[stc[#]]==1&]

A145037 Number of 1's minus number of 0's in the binary representation of n.

Original entry on oeis.org

0, 1, 0, 2, -1, 1, 1, 3, -2, 0, 0, 2, 0, 2, 2, 4, -3, -1, -1, 1, -1, 1, 1, 3, -1, 1, 1, 3, 1, 3, 3, 5, -4, -2, -2, 0, -2, 0, 0, 2, -2, 0, 0, 2, 0, 2, 2, 4, -2, 0, 0, 2, 0, 2, 2, 4, 0, 2, 2, 4, 2, 4, 4, 6, -5, -3, -3, -1, -3, -1, -1, 1, -3, -1, -1, 1, -1, 1, 1, 3, -3, -1, -1, 1, -1, 1, 1, 3, -1, 1, 1

Offset: 0

Reikku Kulon, Sep 30 2008

Column 2 of A144912 (which begins at n = 2).

Zeros in that column correspond to A031443.

			From _Michel Marcus_, Feb 12 2022: (Start)
Viewed as an irregular triangle:
   0;
   1;
   0,  2;
  -1,  1,  1, 3;
  -2,  0,  0, 2,  0, 2, 2, 4;
  -3, -1, -1, 1, -1, 1, 1, 3, -1, 1, 1, 3, 1, 3, 3, 5;
  ... (End)

Table of n, a(n) for n = 0..2^14

Cf. A037861 (negated), A031443 (indices of 0's), A144912, A000120.
Cf. A269735 (first differences), A268289 (partial sums).
Column k=1 of A360099.

a145037 0 = 0
a145037 n = a145037 n' + 2*m - 1 where (n', m) = divMod n 2
-- Reinhard Zumkeller, Jun 16 2011

a:= n-> add(2*i-1, i=Bits[Split](n)):
seq(a(n), n=0..90);  # Alois P. Heinz, Jan 18 2022

Join[{0}, Table[Count[#, 1] - Count[#, 0] &[IntegerDigits[n, 2]], {n, 1, 90}]] (* Robert P. P. McKone, Feb 12 2022 *)

A145037(n)=hammingweight(n)*2-logint(n<<1+!n,2) \\ M. F. Hasler, Mar 08 2018

result = [0]
for n in range (1, 2**14 + 1):
    result.append(bin(n)[2:].count("1") - bin(n)[2:].count("0"))
print(result[0:129]) # Karl-Heinz Hofmann, Jan 18 2022

def a(n): return (n.bit_count()<<1) - n.bit_length()
print([a(n) for n in range(1, 2**14+1)]) # Michael S. Branicky, May 14 2024
(C#)
int A145037(int n)  {
    int result = 0;
    while(n > 0)  {
        result += 2 * (n % 2) - 1;
        n /= 2;
    }
    return result;
} \\ Frank Hollstein, Dec 08 2022

a(n) = -A037861(n) for n >= 1.
a(n) = Sum_{i=1..k} (2*b[i] - 1) where b is the binary expansion of n and k is the number of bits in this binary expansion. - Michel Marcus, Jun 28 2021
From Aayush Soni Feb 12 2022: (Start)
Upper bound: a(n) <= floor(log_2(n+1)).
Lower bound: For n > 0, a(n) >= 1 - floor(log_2(n)).
If n is even, a(2^n) to a(2^(n+1)-1) inclusive are all odd and vice versa. (End)

Renamed (using a Mar 08 2018 comment from M. F. Hasler) and edited by Jon E. Schoenfield, Jun 29 2021

A372433 Binary weight (number of ones in binary expansion) of the n-th squarefree number.

Original entry on oeis.org

1, 1, 2, 2, 2, 3, 2, 3, 3, 3, 4, 2, 3, 3, 3, 4, 3, 4, 4, 5, 2, 2, 3, 3, 3, 4, 3, 3, 4, 4, 5, 4, 4, 5, 4, 4, 5, 5, 5, 2, 2, 3, 3, 3, 4, 3, 3, 4, 4, 5, 3, 4, 4, 4, 5, 4, 5, 5, 5, 6, 3, 4, 4, 5, 4, 4, 5, 5, 5, 6, 4, 4, 5, 5, 6, 5, 6, 7, 2, 2, 3, 3, 3, 3, 3, 4, 4

Offset: 1

Gus Wiseman, May 04 2024

Harvey P. Dale, Table of n, a(n) for n = 1..1000
MathOverflow, Are there primes of every Hamming weight?
Wikipedia, Hamming weight.

Restriction of A000120 to A005117.
For prime instead of squarefree we have A014499, zeros A035103.
Counting zeros instead of ones gives A372472, cf. A023416, A372473.
For binary length instead of weight we have A372475.
A003714 lists numbers with no successive binary indices.
A030190 gives binary expansion, reversed A030308.
A048793 lists positions of ones in reversed binary expansion, sum A029931.
A145037 counts ones minus zeros in binary expansion, cf. A031443, A031444, A031448, A097110.
A371571 lists positions of zeros in binary expansion, sum A359359.
A371572 lists positions of ones in binary expansion, sum A230877.
A372515 lists positions of zeros in reversed binary expansion, sum A359400.
A372516 counts ones minus zeros in binary expansion of primes, cf. A177718, A177796, A372538, A372539.
Cf. A039004, A049093, A049094, A059015, A069010, A070939, A073642, A211997, A368494, A372474.

DigitCount[Select[Range[100],SquareFreeQ],2,1]
Total[IntegerDigits[#,2]]&/@Select[Range[200],SquareFreeQ] (* Harvey P. Dale, Feb 14 2025 *)

from math import isqrt
from sympy import mobius
def A372433(n):
    def f(x): return n+x-sum(mobius(k)*(x//k**2) for k in range(1, isqrt(x)+1))
    m, k = n, f(n)
    while m != k:
        m, k = k, f(k)
    return int(m).bit_count() # Chai Wah Wu, Aug 02 2024

a(n) = A000120(A005117(n)).

a(n) + A372472(n) = A372475(n) = A070939(A005117(n)).

A039004 Numbers whose base-4 representation has the same number of 1's and 2's.

Original entry on oeis.org

0, 3, 6, 9, 12, 15, 18, 24, 27, 30, 33, 36, 39, 45, 48, 51, 54, 57, 60, 63, 66, 72, 75, 78, 90, 96, 99, 102, 105, 108, 111, 114, 120, 123, 126, 129, 132, 135, 141, 144, 147, 150, 153, 156, 159, 165, 177, 180, 183, 189, 192, 195, 198, 201, 204, 207, 210, 216, 219

Offset: 1

Olivier Gérard

Numbers such that sum (-1)^k*b(k) = 0 where b(k)=k-th binary digit of n (see A065359). - Benoit Cloitre, Nov 18 2003
Conjecture: a(C(2n,n)-1) = 4^n - 1. (A000984 is C(2n,n)). - Gerald McGarvey, Nov 18 2007
From Russell Jay Hendel, Jun 23 2015: (Start)
We prove the McGarvey conjecture (A) a(e(n,n)-1) = 4^n-1, with e(n,m) = A034870(n,m) = binomial(2n,m), the even rows of Pascal's triangle. By the comment from Hendel in A034870, we have the function s(n,k) = #{n-digit, base-4 numbers with n-k more 1-digits than 2-digits}. As shown in A034870, (B) #s(n,k)= e(n,k) with # indicating cardinality, that is, e(n,k) = binomial(2n,k) gives the number of n-digit, base-4 numbers with n-k more 1-digits than 2-digits.
We now show that (B) implies (A). By definition, s(n,n) contains the e(n,n) = binomial(2n,n) numbers with an equal number of 1-digits and 2-digits. The biggest n-digit, base-4 number is 333...3 (n copies of 3). Since 333...33 has zero 1-digits and zero 2-digits it follows that 333...333 is a member of s(n,n) and hence it is the biggest member of s(n,n). But 333...333 (n copies of 3) in base 4 has value 4^n-1. Since A039004 starts with index 0 (that is, 0 is the 0th member of A039004), it immediately follows that 4^n-1 is the (e(n,n)-1)st member of A039004, proving the McGarvey conjecture. (End)
Also numbers whose alternating sum of binary expansion is 0, i.e., positions of zeros in A345927. These are numbers whose binary expansion has the same number of 1's at even positions as at odd positions. - Gus Wiseman, Jul 28 2021

Alois P. Heinz, Table of n, a(n) for n = 1..10000

Cf. A139370, A139371, A139372, A139373.
Cf. A139351, A139352, A139353, A139354, A139355.
A subset of A001969 (evil numbers).
A base-2 version is A031443 (digitally balanced numbers).
Positions of 0's in A065359 and A345927.
Positions of first appearances are A086893.
The version for standard compositions is A344619.
A000120 and A080791 count binary digits, with difference A145037.
A003714 lists numbers with no successive binary indices.
A011782 counts compositions.
A030190 gives the binary expansion of each nonnegative integer.
A070939 gives the length of an integer's binary expansion.
A097805 counts compositions by alternating (or reverse-alternating) sum.
A101211 lists run-lengths in binary expansion:
- row-lengths: A069010
- reverse: A227736
- ones only: A245563
A138364 counts compositions with alternating sum 0:
- bisection: A001700/A088218
- complement: A058622
A328594 lists numbers whose binary expansion is aperiodic.
A345197 counts compositions by length and alternating sum.
Cf. A000302, A000346, A003242, A029837, A053738, A053754, A071321, A103919, A191232, A328596.

Fortran
```
c See link in A139351.
```

N:= 1000: # to get all terms up to N, which should be divisible by 4
B:= Array(0..N-1):
d:= ceil(log[4](N));
S:= Array(0..N-1,[seq(op([0,1,-1,0]),i=1..N/4)]):
for i from 1 to d do
  B:= B + S;
  S:= Array(0..N-1,i-> S[floor(i/4)]);
od:
select(t -> B[t]=0, [$0..N-1]); # Robert Israel, Jun 24 2015

ats[y_]:=Sum[(-1)^(i-1)*y[[i]],{i,Length[y]}];
Select[Range[0,100],ats[IntegerDigits[#,2]]==0&] (* Gus Wiseman, Jul 28 2021 *)

for(n=0,219,if(sum(i=1,length(binary(n)),(-1)^i*component(binary(n),i))==0,print1(n,",")))

Conjecture: there is a constant c around 5 such that a(n) is asymptotic to c*n. - Benoit Cloitre, Nov 24 2002

That conjecture is false. The number of members of the sequence from 0 to 4^d-1 is binomial(2d,d) which by Stirling's formula is asymptotic to 4^d/sqrt(Pi*d). If Cloitre's conjecture were true we would have 4^d-1 asymptotic to c*4^d/sqrt(Pi*d), a contradiction. - Robert Israel, Jun 24 2015

A049363 a(1) = 1; for n > 1, smallest digitally balanced number in base n.

Original entry on oeis.org

1, 2, 11, 75, 694, 8345, 123717, 2177399, 44317196, 1023456789, 26432593615, 754777787027, 23609224079778, 802772380556705, 29480883458974409, 1162849439785405935, 49030176097150555672, 2200618769387072998445, 104753196945250864004691, 5271200265927977839335179

Offset: 1

Harvey P. Dale

A037968(a(n)) = n and A037968(m) < n for m < a(n). - Reinhard Zumkeller, Oct 27 2003

Also smallest pandigital number in base n. - Franklin T. Adams-Watters, Nov 15 2006

			a(6) = 102345_6 = 1*6^5 + 2*6^3 + 3*6^2 + 4*6^1 + 5*6^0 = 8345.

Reinhard Zumkeller, Table of n, a(n) for n = 1..250
Eric Weisstein's World of Mathematics, Pandigital Number
Wikipedia, Pandigital number
Chai Wah Wu, Pandigital and penholodigital numbers, arXiv:2403.20304 [math.GM], 2024. See p. 1.

Column k=1 of A061845 and A378000 (for n>1).

Cf. A031443, A049354, A049355, A023811.

a049363 n = foldl (\v d -> n * v + d) 0 (1 : 0 : [2..n-1])
-- Reinhard Zumkeller, Apr 04 2012

a:= n-> n^(n-1)+add((n-i)*n^(i-1), i=1..n-2):
seq(a(n), n=1..23);  # Alois P. Heinz, May 02 2020

Table[FromDigits[Join[{1,0},Range[2,n-1]],n],{n,20}] (* Harvey P. Dale, Oct 12 2012 *)

A049363(n)=n^(n-1)+sum(i=1,n-2,n^(i-1)*(n-i))  \\ M. F. Hasler, Jan 10 2012

A049363(n)=if(n>1,(n^n-n)/(n-1)^2+n^(n-2)*(n-1)-1,1)  \\ M. F. Hasler, Jan 12 2012

def A049363(n): return (n**n-n)//(n-1)**2+n**(n-2)*(n-1)-1 if n>1 else 1 # Chai Wah Wu, Mar 13 2024

a(n) = (102345....n-1) in base n. - Ulrich Schimke (ulrschimke(AT)aol.com)
For n > 1, a(n) = (n^n-n)/(n-1)^2 + n^(n-2)*(n-1) - 1 = A023811(n) + A053506(n). - Franklin T. Adams-Watters, Nov 15 2006
a(n) = n^(n-1) + Sum_{m=2..n-1} m * n^(n - 1 - m). - Alexander R. Povolotsky, Sep 18 2022

More terms from Ulrich Schimke (ulrschimke(AT)aol.com)

cp's OEIS Frontend

A014486 List of totally balanced sequences of 2n binary digits written in base 10. Binary expansion of each term contains n 0's and n 1's and reading from left to right (the most significant to the least significant bit), the number of 0's never exceeds the number of 1's.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

SageMath

Extensions

A053754 If k is in the sequence then 2*k and 2*k+1 are not (and 0 is in the sequence); when written in binary k has an even number of bits (0 has 0 digits).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

PARI

Extensions

A037861 (Number of 0's) - (number of 1's) in the base-2 representation of n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A079309 a(n) = C(1,1) + C(3,2) + C(5,3) + ... + C(2*n-1,n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A345910 Numbers k such that the k-th composition in standard order (row k of A066099) has alternating sum -1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A345909 Numbers k such that the k-th composition in standard order (row k of A066099) has alternating sum 1.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A145037 Number of 1's minus number of 0's in the binary representation of n.

Views

A053754 If k is in the sequence then 2k and 2k+1 are not (and 0 is in the sequence); when written in binary k has an even number of bits (0 has 0 digits).