OFFSET
0,2
COMMENTS
A variation of problem 11424 in the American Mathematical Monthly. Terms were brute-force calculated using Maple 10.
Proposed Problem 11610 in the Dec 2011 A.M.M.
From Gus Wiseman, Jul 27 2021: (Start)
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:
(1) (2) (3) (4) (5) (6) (7)
(11) (21) (31) (41) (51) (61)
(121) (122) (123) (124)
(221) (222) (223)
(1112) (321) (322)
(1211) (1122) (421)
(1221) (1132)
(2112) (1231)
(2211) (2122)
(2221)
(3112)
(3211)
(11131)
(12121)
(13111)
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.
(End)
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..3328 (first 501 terms from R. H. Hardin)
Shalosh B. Ekhad and Doron Zeilberger, Automatic Solution of Richard Stanley's Amer. Math. Monthly Problem #11610 and ANY Problem of That Type, 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]
R. Stanley, Problem 11610, Amer. Math. Monthly, 118 (2011), 937; 120 (2013), 943-944.
FORMULA
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
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
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
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
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
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
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
a(n) ~ 2^n / sqrt(Pi*n). - Vaclav Kotesovec, Apr 26 2024
EXAMPLE
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 + ...
From Gus Wiseman, Jul 27 2021: (Start)
The a(0) = 1 though a(6) = 15 binary strings:
() (0) (1,0) (0,0,1) (0,0,1,0) (0,0,1,1,0) (0,0,0,1,0,1)
(1) (1,1) (1,1,0) (0,0,1,1) (0,0,1,1,1) (0,0,1,0,0,1)
(1,1,1) (0,1,0,0) (0,1,1,0,0) (0,0,1,1,1,0)
(1,0,0,1) (1,0,0,1,0) (0,0,1,1,1,1)
(1,1,1,0) (1,0,0,1,1) (0,1,0,0,0,1)
(1,1,1,1) (1,0,1,0,0) (0,1,1,1,0,0)
(1,1,0,0,1) (1,0,0,1,1,0)
(1,1,1,1,0) (1,0,0,1,1,1)
(1,1,1,1,1) (1,0,1,1,0,0)
(1,1,0,0,1,0)
(1,1,0,0,1,1)
(1,1,0,1,0,0)
(1,1,1,0,0,1)
(1,1,1,1,1,0)
(1,1,1,1,1,1)
(End)
MAPLE
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:
# second Maple program:
b:= proc(n, l, t) option remember; `if`(n-abs(t)<0, 0, `if`(n=0, 1,
add(b(n-1, i, t+`if`(l=0, (-1)^i, 0)), i=0..1)))
end:
a:= n-> b(n, 1, 0):
seq(a(n), n=0..36); # Alois P. Heinz, Mar 20 2024
MATHEMATICA
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}];
Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Nov 28 2017, after Joel B. Lewis *)
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 *)
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 *)
PROG
(Python)
from math import comb
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
CROSSREFS
Antidiagonal sums of the matrices A345197.
Row sums of A345907.
Taking diagonal instead of antidiagonal sums gives A345908.
A011782 counts compositions (or binary strings).
A097805 counts compositions by alternating (or reverse-alternating) sum.
Compositions of n, 2n, or 2n+1 with alternating/reverse-alternating sum k:
KEYWORD
nonn
AUTHOR
Christopher Carl Heckman, Jul 29 2009
STATUS
approved