Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%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