login
Number of binary strings of length n which have the same number of 00 and 01 substrings.
35

%I #59 May 02 2024 10:06:23

%S 1,2,2,3,6,9,15,30,54,97,189,360,675,1304,2522,4835,9358,18193,35269,

%T 68568,133737,260802,509132,995801,1948931,3816904,7483636,14683721,

%U 28827798,56637969,111347879,219019294,431043814,848764585,1672056525,3295390800,6497536449

%N Number of binary strings of length n which have the same number of 00 and 01 substrings.

%C A variation of problem 11424 in the American Mathematical Monthly. Terms were brute-force calculated using Maple 10.

%C Proposed Problem 11610 in the Dec 2011 A.M.M.

%C From _Gus Wiseman_, Jul 27 2021: (Start)

%C Also the antidiagonal sums of the matrices counting integer compositions by length and alternating sum (A345197). So a(n) is the number of integer compositions of n + 1 of length (n - s + 3)/2, where s is the alternating sum of the composition. For example, the a(0) = 1 through a(6) = 7 compositions are:

%C (1) (2) (3) (4) (5) (6) (7)

%C (11) (21) (31) (41) (51) (61)

%C (121) (122) (123) (124)

%C (221) (222) (223)

%C (1112) (321) (322)

%C (1211) (1122) (421)

%C (1221) (1132)

%C (2112) (1231)

%C (2211) (2122)

%C (2221)

%C (3112)

%C (3211)

%C (11131)

%C (12121)

%C (13111)

%C For a bijection with the main (binary string) interpretation, take the run-lengths of each binary string of length n + 1 that satisfies the condition and starts with 1.

%C (End)

%H Alois P. Heinz, <a href="/A163493/b163493.txt">Table of n, a(n) for n = 0..3328</a> (first 501 terms from R. H. Hardin)

%H Shalosh B. Ekhad and Doron Zeilberger, <a href="http://arxiv.org/abs/1112.6207">Automatic Solution of Richard Stanley's Amer. Math. Monthly Problem #11610 and ANY Problem of That Type</a>, arXiv preprint arXiv:1112.6207 [math.CO], 2011. See subpages for rigorous derivations of g.f., recurrence, asymptotics for this sequence. [From _N. J. A. Sloane_, Apr 07 2012]

%H R. Stanley, <a href="https://www.jstor.org/stable/10.4169/amer.math.monthly.118.10.936">Problem 11610</a>, Amer. Math. Monthly, 118 (2011), 937; 120 (2013), 943-944.

%F G.f.: 1/2/(1-x) + (1+2*x)/2/sqrt((1-x)*(1-2*x)*(1+x+2*x^2)). - _Richard Stanley_, corrected Apr 29 2011

%F G.f.: (1 + sqrt( 1 + 4*x / ((1 - x) * (1 - 2*x) * (1 + x + 2*x^2)))) / (2*(1 - x)). - _Michael Somos_, Jan 30 2012

%F a(n) = sum( binomial(2*k-1, k)*binomial(n-2*k,k) + binomial(2*k, k)*binomial(n-2*k-1, k), k=0..floor(n/3)). - _Joel B. Lewis_, May 21 2011

%F Conjecture: -n*a(n) +(2+n)*a(n-1) +(3n-12)*a(n-2) +(12-n)*a(n-3) +(2n-18)*a(n-4)+(56-12n)*a(n-5) +(8n-40)*a(n-6)=0. - _R. J. Mathar_, Nov 28 2011

%F G.f. y = A(x) satisfies x = (1 - x) * (1 - 2*x) * (1 + x + 2*x^2) * y * (y * (1 - x) - 1). - _Michael Somos_, Jan 30 2012

%F Sequence a(n) satisfies 0 = a(n) * (n^2-2*n) + a(n-1) * (-3*n^2+8*n-2) + a(n-2) * (3*n^2-10*n+2) + a(n-3) * (-5*n^2+18*n-6) + a(n-4) * (8*n^2-34*n+22) + a(n-5) * (-4*n^2+20*n-16) except if n=1 or n=2. - _Michael Somos_, Jan 30 2012

%F a(n) = (1 + 3*hypergeom([1/2, 1-3*n/8, (1-n)/3, (2-n)/3, -n/3],[1, (1-n)/2, 1-n/2, -3*n/8],-27))/2 for n > 0. - _Stefano Spezia_, Apr 26 2024

%F a(n) ~ 2^n / sqrt(Pi*n). - _Vaclav Kotesovec_, Apr 26 2024

%e 1 + 2*x + 2*x^2 + 3*x^3 + 6*x^4 + 9*x^5 + 15*x^6 + 30*x^7 + 54*x^8 + 97*x^9 + ...

%e From _Gus Wiseman_, Jul 27 2021: (Start)

%e The a(0) = 1 though a(6) = 15 binary strings:

%e () (0) (1,0) (0,0,1) (0,0,1,0) (0,0,1,1,0) (0,0,0,1,0,1)

%e (1) (1,1) (1,1,0) (0,0,1,1) (0,0,1,1,1) (0,0,1,0,0,1)

%e (1,1,1) (0,1,0,0) (0,1,1,0,0) (0,0,1,1,1,0)

%e (1,0,0,1) (1,0,0,1,0) (0,0,1,1,1,1)

%e (1,1,1,0) (1,0,0,1,1) (0,1,0,0,0,1)

%e (1,1,1,1) (1,0,1,0,0) (0,1,1,1,0,0)

%e (1,1,0,0,1) (1,0,0,1,1,0)

%e (1,1,1,1,0) (1,0,0,1,1,1)

%e (1,1,1,1,1) (1,0,1,1,0,0)

%e (1,1,0,0,1,0)

%e (1,1,0,0,1,1)

%e (1,1,0,1,0,0)

%e (1,1,1,0,0,1)

%e (1,1,1,1,1,0)

%e (1,1,1,1,1,1)

%e (End)

%p with(combinat): count := proc(n) local S, matches, A, k, i; S := subsets(\{seq(i, i=1..n)\}): matches := 0: while not S[finished] do A := S[nextvalue](): k := 0: for i from 1 to n-1 do: if not (i in A) and not (i+1 in A) then k := k + 1: fi: if not (i in A) and (i+1 in A) then k := k - 1: fi: od: if (k = 0) then matches := matches + 1: fi: end do; return(matches); end proc:

%p # second Maple program:

%p b:= proc(n, l, t) option remember; `if`(n-abs(t)<0, 0, `if`(n=0, 1,

%p add(b(n-1, i, t+`if`(l=0, (-1)^i, 0)), i=0..1)))

%p end:

%p a:= n-> b(n, 1, 0):

%p seq(a(n), n=0..36); # _Alois P. Heinz_, Mar 20 2024

%t a[0] = 1; a[n_] := Sum[Binomial[2*k - 1, k]*Binomial[n - 2*k, k] + Binomial[2*k, k]*Binomial[n - 2*k - 1, k], {k, 0, n/3}];

%t Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Nov 28 2017, after _Joel B. Lewis_ *)

%t Table[Length[Select[Tuples[{0,1},n],Count[Partition[#,2,1],{0,0}]==Count[Partition[#,2,1],{0,1}]&]],{n,0,10}] (* _Gus Wiseman_, Jul 27 2021 *)

%t a[0]:=1; a[n_]:=(1 + 3*HypergeometricPFQ[{1/2, 1-3*n/8, (1-n)/3, (2-n)/3, -n/3},{1, (1-n)/2, 1-n/2, -3*n/8}, -27])/2; Array[a,37,0] (* _Stefano Spezia_, Apr 26 2024 *)

%o (Python)

%o from math import comb

%o def A163493(n): return 2+sum((x:=comb((k:=m<<1)-1,m)*comb(n-k,m))+(x*(n-3*m)<<1)//(n-k) for m in range(1,n//3+1)) if n else 1 # _Chai Wah Wu_, May 01 2024

%Y Antidiagonal sums of the matrices A345197.

%Y Row sums of A345907.

%Y Taking diagonal instead of antidiagonal sums gives A345908.

%Y A011782 counts compositions (or binary strings).

%Y A097805 counts compositions by alternating (or reverse-alternating) sum.

%Y A103919 counts partitions by sum and alternating sum (reverse: A344612).

%Y A316524 gives the alternating sum of prime indices (reverse: A344616).

%Y Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:

%Y - k = 0: counted by A088218, ranked by A344619/A344619.

%Y - k = 1: counted by A000984, ranked by A345909/A345911.

%Y - k = -1: counted by A001791, ranked by A345910/A345912.

%Y - k = 2: counted by A088218, ranked by A345925/A345922.

%Y - k = -2: counted by A002054, ranked by A345924/A345923.

%Y - k >= 0: counted by A116406, ranked by A345913/A345914.

%Y - k <= 0: counted by A058622(n-1), ranked by A345915/A345916.

%Y - k > 0: counted by A027306, ranked by A345917/A345918.

%Y - k < 0: counted by A294175, ranked by A345919/A345920.

%Y - k != 0: counted by A058622, ranked by A345921/A345921.

%Y - k even: counted by A081294, ranked by A053754/A053754.

%Y - k odd: counted by A000302, ranked by A053738/A053738.

%Y Cf. A000041, A000070, A000096, A000097, A000124, A000346, A007318, A008549, A025047, A131577, A238279.

%K nonn

%O 0,2

%A _Christopher Carl Heckman_, Jul 29 2009