A177790 -id:A177790 - cp's OEIS frontend

A003440 Number of binary vectors with restricted repetitions.

1, 1, 3, 7, 17, 42, 104, 259, 648, 1627, 4098, 10350, 26202, 66471, 168939, 430071, 1096451, 2799072, 7154189, 18305485, 46885179, 120195301, 308393558, 791882862, 2034836222, 5232250537, 13462265079, 34657740889, 89272680921, 230069128392

Offset: 0

N. J. A. Sloane

nonn

The sum of squared terms in row n of A104402 = 2*a(n) for n>0. - Paul D. Hanna, Mar 06 2005
From Jean-Pierre Levrel, Nov 26 2014: (Start)
The title "Binary Sequences with Restricted Repetitions," given the A003440 series, does not specify the type of restrictions used. After reading the article by K. A. Post, "Binary Sequences with Restricted Repetitions," it appears that the A003440 series corresponds to the following cases:
- Number of repetitions limited to two,
- Each sequence must begin with a zero.
It is important to consider these two hypotheses to interpret the series. I also think that the second constraint is not useful and could usefully be deleted. In this case, the series should be doubled from the second term and would become 1, 2, 6, 14, 34, 84, ..., i.e., A177790.
(End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Jean-Luc Baril and José L. Ramírez, Fibonacci and Catalan paths in a wall, 2023.
K. A. Post, Binary Sequences with Restricted Repetitions, Report 74-WSK-02, Math. Dept., Tech. Univ. Eindhoven, May. 1974.

Cf. A078678, A104402, A177790.

Flatten[{1,Table[Sum[(Binomial[k,n-k]+Binomial[k+1,n-k-1])^2/2,{k,0,n}],{n,1,20}]}] (* Vaclav Kotesovec, Feb 12 2014 *)
a[r_, s_] /; r<0 || s<0 = 0; a[r_ /; 0 <= r <= 2, 0] = 1; a[r_ /; r>2, 0] = 0; a[0, s_ /; s >= 1] = 0; a[r_, s_] := a[r, s] = a[r-2, s-2] + a[r-2, s-1] + a[r-1, s-2] + a[r-1, s-1]; a[n_] := a[n, n]; Table[a[n], {n, 0, 29}] (* Jean-François Alcover, Jan 19 2015, after given recurrence *)

{a(n)=polcoeff(((1-x)^2*sqrt((1+x+x^2)/(1-3*x+x^2))+x^2-1)/(2*x^2)+x*O(x^n),n)} \\ Paul D. Hanna, Mar 06 2005

{a(n)=if(n==0,1,sum(k=0,n,(binomial(k,n-k)+binomial(k+1,n-k-1))^2)/2)} \\ Paul D. Hanna, Mar 06 2005

G.f.: {(1-x)^2 * sqrt[(1+x+x^2)/(1-3x+x^2)] + x^2 - 1}/(2x^2) (conjectured). - Ralf Stephan, Mar 28 2004
a(n) = Sum_{k=0..n} (C(k, n-k) + C(k+1, n-k-1))^2/2 for n>0, with a(0)=1. - Paul D. Hanna, Mar 06 2005
Conjecture: (n+2)*a(n) +3*(-n-1)*a(n-1) +(n-2)*a(n-2) +(-n+1)*a(n-3) +3*(n-4)*a(n-4) +(-n+5)*a(n-5)=0. - R. J. Mathar, Jun 07 2013
Recurrence: (n-2)*(n-1)*(n+2)*a(n) = 2*(n-2)*n*(n+1)*a(n-1) + (n-1)*(n^2 - 2*n - 4)*a(n-2) + 2*(n-3)*(n-2)*n*a(n-3) - (n-4)*(n-1)*n*a(n-4). - Vaclav Kotesovec, Feb 12 2014
a(n) ~ sqrt(6+14/sqrt(5)) * (3+sqrt(5))^n / (sqrt(Pi*n) * 2^(n+1)). - Vaclav Kotesovec, Feb 12 2014
Equivalently, a(n) ~ phi^(2*n + 2) / (5^(1/4) * sqrt(Pi*n)), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Dec 08 2021

Typo in second formula corrected by Vaclav Kotesovec, Feb 12 2014

More terms from Vincenzo Librandi, Feb 13 2014

A247150 Number of paths from (0,0,0) to (n,n,n) avoiding 3 or more consecutive right steps, 3 or more consecutive up steps, and 3 or more consecutive away steps.

Original entry on oeis.org

1, 6, 90, 1314, 21084, 353772, 6128208, 108606408, 1958248980, 35787633828, 661145207064, 12322983505860, 231395387482470, 4372431546366636, 83068148270734740, 1585548331063624992, 30388252830928088010, 584527926996090202428, 11279880522021539956860

Offset: 0

Jean-Pierre Levrel, Nov 21 2014

nonn

This is a generalization of A177790 from 2D to 3D.

a(n) is also the number of ternary vectors (symbols 0, 1, and 2, for example) that can be composed with 3n elements (same number of each of the symbols) where each symbol cannot be repeated more than twice consecutively. For example, 0,2,1,0,2,2,1,0,1 is allowed, but 0,2,1,1,1,2,2,0,0 is prohibited because the symbol 1 is repeated 3 times.

			For n=1 the 6 paths are (000>001>011>111), (000>001>101>111), (000>010>011>111), (000>010>110>111), (000>100>101>111), (000>100>110>111).

Alois P. Heinz, Table of n, a(n) for n = 0..250
M. Erickson, S. Fernando, K. Tran, Enumerating rook and queen paths, Bulletin of the Institute for Combinatorics and Its Applications, Volume 60 (2010), 37-48.

Cf. A177790.

f:= proc(p,q,r) option remember;
  if p`))) fi;
  if r < 0 then return 0 fi;
   procname(p-1,q-1,r)+procname(p-1,q-2,r)+procname(p-2,q-1,r)+procname(p-2,q-2,r)+2*procname(p-1,q-1,r-1)+procname(p,q-2,r-1)+2*procname(p-1,q-2,r-1)+procname(p-1,q,r-1)+2*procname(p-2,q-1,r-1)+procname(p-2,q,r-1)+2*procname(p-2,q-2,r-1)+procname(p,q-1,r-1)+2*procname(p-2,q-2,r-2)+procname(p,q-1,r-2)+2*procname(p-1,q-1,r-2)+procname(p,q-2,r-2)+2*procname(p-1,q-2,r-2)+procname(p-1,q,r-2)+2*procname(p-2,q-1,r-2)+procname(p-2,q,r-2)
end proc:
f(0,0,0) := 1: f(1,0,0) := 1:
f(1,1,0) := 2: f(1,1,1) := 6:
f(2,0,0) := 1: f(2,1,0) := 3:
f(2,1,1) := 12: f(2,2,0) := 6:
f(2,2,1) := 30: f(2,2,2) := 90:
seq(f(n,n,n), n=0..30); # Robert Israel, Nov 26 2014
# second Maple program:
b:= proc(i, j, k, t) option remember; `if`(max(i, j, k)=0, 1,
      `if`(j>0, b(j-1, `if`(i0, b(k-1, `if`(i0 and t>0, b(i-1, j, k, t-1), 0))
    end:
a:= n-> b(n$3, 2):
seq(a(n), n=0..30);  # Alois P. Heinz, Nov 26 2014

(* Very slow *) a[0] = 1; a[n_] := SeriesCoefficient[((1+x+x^2)*(1+y+y^2)*(1+z+z^2)/(1-x*y*(1+x)*(1+y) - x*z*(1+x)*(1+ z) - y*z*(1+y)*(1+z) - 2*x*y*z*(1+x)*(1+y)*(1+z))), {x, 0, n}, {y, 0, n}, {z, 0, n}]; Table[Print[an = a[n]]; an, {n, 0, 10}] (* Jean-François Alcover, Nov 26 2014 *)
b[i_, j_, k_, t_] := b[i, j, k, t] = If[Max[i, j, k] == 0, 1, If[j>0, If[i0, If[i0 && t>0, b[i-1, j, k, t-1], 0]]; a[n_] := b[n, n, n, 2]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Nov 27 2014, after Alois P. Heinz *)

a(n) = [x^n y^n z^n] ((1+x+x^2)*(1+y+y^2)*(1+z+z^2)/(1-x*y*(1+x)*(1+y)-x*z*(1+x)*(1+z)-y*z*(1+y)*(1+z)-2*x*y*z*(1+x)*(1+y)*(1+z))).
Recurrence (20 terms):
a(p,q,r) = a(p-1,q-1,r) +a(p-1,q-2,r) +a(p-2,q-1,r) +a(p-2,q-2,r) +2*a(p-1,q-1,r-1) +a(p,q-2,r-1) +2*a(p-1,q-2,r-1) +a(p-1,q,r-1) +2*a(p-2,q-1,r-1) +a(p-2,q,r-1) +2*a(p-2,q-2,r-1) +a(p,q-1,r-1) +2*a(p-2,q-2,r-2) +a(p,q-1,r-2) +2*a(p-1,q-1,r-2) +a(p,q-2,r-2) +2*a(p-1,q-2,r-2) +a(p-1,q,r-2) +2*a(p-2,q-1,r-2) +a(p-2,q,r-2), for (p,q,r) > 2.
a(p,q,r) = 0 when p or q or r is negative.
Initial conditions: a(0,0,0) = 1, a(1,0,0) = 1, a(1,1,0) = 2, a(1,1,1) = 6, a(2,0,0) = 1, a(2,1,0) = 3, a(2,1,1) = 12, a(2,2,0) = 6, a(2,2,1) = 30, a(2,2,2) = 90.
Symmetry: a(p,q,r) = a(p,r,q) = a(q,p,r) = a(q,r,p) = a(r,p,q) = a(r,q,p).

cp's OEIS Frontend

A003440 Number of binary vectors with restricted repetitions.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI