A217464 -id:A217464 - cp's OEIS frontend

A216604 G.f. satisfies: A(x) = (1 + x(1-x)A(x)) * (1 + x^2*A(x)).

1, 1, 1, 2, 3, 4, 7, 12, 19, 33, 59, 102, 181, 329, 593, 1076, 1979, 3643, 6723, 12494, 23289, 43498, 81557, 153356, 288925, 545687, 1032997, 1958978, 3721819, 7083716, 13503311, 25778612, 49283755, 94345179, 180830195, 347006694, 666636809, 1282024484, 2467964693

Offset: 0

Paul D. Hanna, Sep 10 2012

nonn

The radius of convergence of the g.f. A(x) equals 1/2, with A(1/2) = 4.
More generally, if A(x) = (1 + x*(t-x)*A(x)) * (1 + x^2*A(x)), |t|>0, then
A(x) = exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} binomial(n,k)^2 * x^k*(t-x)^(n-k) )
where the radius of convergence r of the g.f. A(x) satisfies
r = (1-r)^2/(t-r) = (1-t*r)/(2*(1-r)) with A(r) = 1/(r*(1-r)) = 2/(1-t*r).
Number of Motzkin excursions of length n that avoid the patterns UU, UD and DH. A Motzkin excursion is a lattice path with steps from the set {D=-1, H=0, U=1} that starts at (0,0), never goes below the x-axis, and terminates at the altitude 0. - Andrei Asinowski, Dec 20 2019

			G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 4*x^5 + 7*x^6 + 12*x^7 + 19*x^8 + ...
The logarithm of the g.f. begins:
log(A(x)) = ((1-x) + x)*x + ((1-x)^2 + 2^2*x*(1-x) + x^2)*x^2/2 +
((1-x)^3 + 3^2*x*(1-x)^2 + 3^2*x^2*(1-x) + x^3)*x^3/3 +
((1-x)^4 + 4^2*x*(1-x)^3 + 6^2*x^2*(1-x)^2 + 4^2*x^3*(1-x) + x^4)*x^4/4 +
((1-x)^5 + 5^2*x*(1-x)^4 + 10^2*x^2*(1-x)^3 + 10^2*x^3*(1-x)^2 + 5^2*x^4*(1-x) + x^5)*x^5/5 + ...
Explicitly,
log(A(x)) = x + x^2/2 + 4*x^3/3 + 5*x^4/4 + 6*x^5/5 + 16*x^6/6 + 29*x^7/7 + 45*x^8/8 + 94*x^9/9 + 186*x^10/10 + ... + A217464(n)*x^n/n + ...

G. C. Greubel, Table of n, a(n) for n = 0..1000
Andrei Asinowski, Cyril Banderier, and Valerie Roitner, Generating functions for lattice paths with several forbidden patterns, preprint, 2019.

Cf. A000108, A217464, A105633, A216434, A216454, A216447, A192415, A216616, A216617.

CoefficientList[Series[((1 - x) - Sqrt[(1 - x)^2 - 4*x^3*(1 - x)])/(2*x^3 *(1 - x)), {x,0,50}], x] (* G. C. Greubel, Jan 24 2017 *)

a(n):=sum(sum(binomial(n-2*q-2,n-r-q)*binomial(q+1,r-1)*binomial(q+1,r) ,r,0,q+1)/(q+1), q,0,n); /* Vladimir Kruchinin, Jan 22 2019 */
a(n):=sum((binomial(2*m,m)*binomial(n-2*m+1,n-3*m))/(n-2*m+1),m,0,n/3);
/*Vladimir Kruchinin, Jan 27 2022 */

{a(n)=polcoeff(exp(sum(m=1,n+1,x^m/m*sum(k=0,m,binomial(m,k)^2*x^k*(1-x)^(m-k) + x*O(x^n)))),n)}

{a(n)=polcoeff(2/(1-x+sqrt((1-x)^2-4*x^3*(1-x) +x*O(x^n))),n)}
for(n=0,40,print1(a(n),", "))

a(n) = sum(k=0, n\3, binomial(n-2*k, k)*binomial(2*k, k)/(k+1)); \\ Seiichi Manyama, Jan 22 2023

G.f.: exp( Sum_{n>=1} x^n/n * Sum_{k=0..n} binomial(n,k)^2 * x^k*(1-x)^(n-k) ).
G.f.: ((1-x) - sqrt( (1-x)^2 - 4*x^3*(1-x) )) / (2*x^3*(1-x)).
a(n) ~ 2^(n+2)/(sqrt(Pi)*n^(3/2)). - Vaclav Kotesovec, Sep 16 2013
a(n) = Sum_{q=0..n} 1/(q+1)*Sum_{r=0..q+1} C(n-2*q-2,n-r-q)*C(q+1,r-1)*C(q+1,r). - Vladimir Kruchinin, Jan 22 2019
a(n) = 1 + Sum_{k=0..n-3} a(k) * a(n-k-3). - Ilya Gutkovskiy, Jan 28 2021
a(n) = Sum_{m=0..n/3} C(2*m,m)*C(n-2*m+1,n-3*m)/(n-2*m+1). - Vladimir Kruchinin, Jan 27 2022

A217615 G.f.: Sum_{n>=0} x^n * Sum_{k=0..n} binomial(n,k)^2 * x^k*(1-x)^(n-k).

Original entry on oeis.org

1, 1, 1, 3, 5, 7, 15, 29, 49, 95, 187, 345, 659, 1289, 2465, 4739, 9237, 17911, 34715, 67705, 132063, 257477, 503309, 984983, 1927895, 3778017, 7411237, 14544967, 28565661, 56144615, 110406527, 217225533, 427636561, 842256047, 1659600955, 3271579689, 6451913519

Offset: 0

Paul D. Hanna, Oct 09 2012

nonn

Radius of convergence of g.f. is r = 1/2.
More generally, given
A(x) = Sum_{n>=1} x^n * Sum_{k=0..n} binomial(n,k)^2 * x^k*(t-x)^(n-k),
then A(x) = 1/sqrt( (1 - t*x + 2*x^2)^2 - 4*x^2 )
and the radius of convergence r satisfies: (1-r)^2 = r*(t-r) for t > 0.
a(n) is the number of (2k-1)-element subsets of {1, 2, ..., n+1} whose k-th smallest (i.e., k-th largest) element equals 2k-1. - Darij Grinberg, Oct 09 2019

			G.f.: A(x) = 1 + x + x^2 + 3*x^3 + 5*x^4 + 7*x^5 + 15*x^6 + 29*x^7 + 49*x^8 + ...
where the g.f. equals the series:
A(x) = 1 +
  x*((1-x) + x) +
  x^2*((1-x)^2 + 2^2*x*(1-x) + x^2) +
  x^3*((1-x)^3 + 3^2*x*(1-x)^2 + 3^2*x^2*(1-x) + x^3) +
  x^4*((1-x)^4 + 4^2*x*(1-x)^3 + 6^2*x^2*(1-x)^2 + 4^2*x^3*(1-x) + x^4) +
  x^5*((1-x)^5 + 5^2*x*(1-x)^4 + 10^2*x^2*(1-x)^3 + 10^2*x^3*(1-x)^2 + 5^2*x^4*(1-x) + x^5) + ...

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A217616, A217617, A217461, A217464, A216604, A217661.

a := n -> `if`(n < 4, [1, 1, 1, 3][n+1], hypergeom([1/2, (1-n)/3, (2-n)/3, -n/3], [1, (1-n)/2, -n/2], -27)):
seq(simplify(a(n)), n=0..36); # Peter Luschny, Oct 09 2019

CoefficientList[Series[1/Sqrt[(1-x+2*x^2)^2-4*x^2], {x, 0, 20}], x] (* Vaclav Kotesovec, Sep 16 2013 *)

{a(n)=polcoeff(sum(m=0, n+1, x^m*sum(k=0, m, binomial(m, k)^2*x^k*(1-x)^(m-k) + x*O(x^n))), n)}
for(n=0,40,print1(a(n),", "))

a(n)={sum(k=0, n\2, binomial(2*k, k) * binomial(n-2*k, k))} \\ Andrew Howroyd, Oct 09 2019

G.f.: A(x) = 1 / sqrt( (1 - x + 2*x^2)^2 - 4*x^2 ).
G.f.: A(x) = 1 / sqrt( (1-x)*(1-2*x)*(1+x+2*x^2) ).
G.f. satisfies: A(x) = (1 + 2*x^2*Sum_{n>=0} A000108(n)*(-x*A(x))^(2*n)) / (1-x+2*x^2) where A000108(n) = binomial(2*n,n)/(n+1) forms the Catalan numbers.
a(n) ~ 2^n/sqrt(Pi*n). - Vaclav Kotesovec, Sep 16 2013
a(n) = Sum_{k=0..floor(n/2)} binomial(2*k, k) * binomial(n-2*k, k). - Darij Grinberg, Oct 09 2019
a(n) = hypergeom([1/2,(1-n)/3,(2-n)/3, -n/3], [1, (1-n)/2, -n/2], -27) for n >= 4. - Peter Luschny, Oct 09 2019

A371570 Number of binary necklaces of length n which have more 01 than 00 substrings.

Original entry on oeis.org

0, 0, 2, 3, 6, 15, 29, 56, 118, 237, 467, 946, 1905, 3796, 7618, 15303, 30614, 61319, 122951, 246202, 492971, 987542, 1977560, 3959289, 7927969, 15873190, 31776708, 63614397, 127346134, 254908115, 510233309, 1021273672, 2044071894, 4091064805, 8187770675

Offset: 0

Robert P. P. McKone, Mar 28 2024

nonn

A necklace may also be referred to as circular or cyclic strings.

			a(3) = 3: 011, 101, 110.
a(4) = 6: 0101, 0111, 1010, 1011, 1101, 1110.
a(5) = 15: 00101, 01001, 01010, 01011, 01101, 01111, 10010, 10100, 10101, 10110, 10111, 11010, 11011, 11101, 11110.

Cf. A217464 (necklaces with equal 00 and 01), A371668 (necklaces with more 00 than 01).
Cf. A126869 (necklaces with equal 00 and 11, for n>=1), A058622 (necklaces with more 00 than 11).
Cf. A163493 (strings with equal 00 and 01), A371358 (strings with more 00 than 01), A371564 (strings with more 01 than 00).

tup[n_] := Tuples[{0, 1}, n];
tupToNec[n_] := Map[Append[#, #[[1]]] &, tup[n]];
cou[lst_List] := Count[lst, {0, 1}] > Count[lst, {0, 0}];
par[lst_List] := Partition[lst, 2, 1];
a[0] = 0;
a[n_] := Map[cou, Map[par, tupToNec[n]]] // Boole // Total;
Monitor[Table[a[n], {n, 0, 18}], {n, Table[a[m], {m, 0, n - 1}]}]

a(n) = 2^n - A217464(n) - A371668(n).

a(n) = -(((n-3)*(n-2) - 8*(n-5)^2*(n-2)*a(n-5) + 4*(n*((3n-34)*n+117)-114)*a(n-4) + 2*(((32-3n)*n-95)*n+62)*a(n-3) + (((5n-52)*n+157)*n-114)*a(n-2) + (((39-4n)*n-103)*n+58)*a(n-1))/((n-6)*(n-3)*n)) for n>=7.

A371668 Number of binary necklaces of length n which have more 00 than 01 substrings.

Original entry on oeis.org

0, 1, 1, 1, 5, 11, 19, 43, 93, 181, 371, 771, 1547, 3121, 6357, 12821, 25805, 52123, 105031, 211243, 425215, 855457, 1719257, 3455153, 6942387, 13942111, 27993317, 56197117, 112785797, 226311535, 454043339, 910778203, 1826666093, 3663122277, 7344953123

Offset: 0

Robert P. P. McKone, Apr 02 2024

nonn

			a(3) = 1: 000.
a(4) = 5: 0000, 0001, 0010, 0100, 1000.
a(5) = 11: 00000, 00001, 00010, 00011, 00100, 00110, 01000, 01100, 10000, 10001, 11000.

Cf. A217464 (necklaces with equal 00 and 01), A371570 (necklaces with more 01 than 00).
Cf. A126869 (necklaces with equal 00 and 11, for n>=1), A058622 (necklaces with more 00 than 11).
Cf. A163493 (strings with equal 00 and 01), A371358 (strings with more 00 than 01), A371564 (strings with more 01 than 00).

tup[n_] := Tuples[{0, 1}, n];
tupToNec[n_] := Map[Append[#, #[[1]]] &, tup[n]];
cou[lst_List] := Count[lst, {0, 0}] > Count[lst, {0, 1}];
par[lst_List] := Partition[lst, 2, 1];
a[0] = 0;
a[n_] := a[n] = Map[cou, Map[par, tupToNec[n]]] // Boole // Total;
Monitor[Table[a[n], {n, 0, 18}], {n, Table[a[m], {m, 0, n - 1}]}]

a(n) = 2^n - A217464(n) - A371570(n).

a(n) = (8*(n-7)*a(n-7) + 4*(29-5*n)*a(n-6) + (26*n-110)*a(n-5) + (77-23*n)*a(n-4) + (15*n-46)*a(n-3) + (22-10*n)*a(n-2) + 5*(n-1)*a(n-1))/n for n>=7.

cp's OEIS Frontend

A216604 G.f. satisfies: A(x) = (1 + x*(1-x)*A(x)) * (1 + x^2*A(x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

PARI

PARI

Formula

A217615 G.f.: Sum_{n>=0} x^n * Sum_{k=0..n} binomial(n,k)^2 * x^k*(1-x)^(n-k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A371570 Number of binary necklaces of length n which have more 01 than 00 substrings.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A371668 Number of binary necklaces of length n which have more 00 than 01 substrings.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

Formula

A216604 G.f. satisfies: A(x) = (1 + x(1-x)A(x)) * (1 + x^2*A(x)).