A055099 -id:A055099 - cp's OEIS frontend

A007481 Number of subsequences of [ 1,...,n ] in which each even number has an odd neighbor.

1, 2, 3, 7, 11, 25, 39, 89, 139, 317, 495, 1129, 1763, 4021, 6279, 14321, 22363, 51005, 79647, 181657, 283667, 646981, 1010295, 2304257, 3598219, 8206733, 12815247, 29228713, 45642179, 104099605, 162557031, 370756241, 578955451, 1320467933

Offset: 0

N. J. A. Sloane

A055099(n) = a(2*n+1) - a(2*n) = a(2*(n+1)) - a(2*n+1). - Reinhard Zumkeller, Oct 25 2015

			For n=2, there are the following three subsequences of [1,2] with the desired property: empty, [1], [1,2].
For n=3, there are the following seven subsequences of [1,2,3] with the desired property: empty, [1], [3], [1,2], [2,3], [1,3], [1,2,3].

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

T. D. Noe, Table of n, a(n) for n = 0..400
R. K. Guy and W. O. J. Moser, Numbers of subsequences without isolated odd members, Fibonacci Quarterly 34:2 (1996), pp. 152-155.
Index entries for linear recurrences with constant coefficients, signature (0, 3, 0, 2).

Cf. A007455, A007482, A007484, A055099.

a007481 n = a007481_list !! n
a007481_list = 1 : 2 : 3 : 7 : zipWith (+)
               (map (* 3) $ drop 2 a007481_list) (map (* 2) a007481_list)
-- Reinhard Zumkeller, Oct 25 2015

LinearRecurrence[{0,3,0,2},{1,2,3,7},40] (* Harvey P. Dale, Feb 29 2012 *)

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 2,0,3,0]^n*[1;2;3;7])[1,1] \\ Charles R Greathouse IV, Mar 02 2016

a(n) = 3*a(n-2) + 2*a(n-4).

G.f.: (x^3+2*x+1)/(-2*x^4-3*x^2+1). - Harvey P. Dale, Feb 29 2012

More terms from James Sellers, Dec 24 1999

A123620 Expansion of (1 + x + x^2) / (1 - 3x - 3x^2).

Original entry on oeis.org

1, 4, 16, 60, 228, 864, 3276, 12420, 47088, 178524, 676836, 2566080, 9728748, 36884484, 139839696, 530172540, 2010036708, 7620627744, 28891993356, 109537863300, 415289569968, 1574482299804, 5969315609316, 22631393727360, 85802128010028, 325300565212164

Offset: 0

N. J. A. Sloane, Nov 20 2006

From Johannes W. Meijer, Aug 14 2010: (Start)
A berserker sequence, see A180141. For the corner squares 16 A[5] vectors with decimal values between 3 and 384 lead to this sequence. These vectors lead for the side squares to A180142 and for the central square to A155116.
This sequence belongs to a family of sequences with GF(x) = (1+x+k*x^2)/(1-3*x+(k-4)*x^2). Berserker sequences that are members of this family are 4*A055099(n) (k=2; with leading 1 added), A123620 (k=1; this sequence), A000302 (k=0), 4*A179606 (k=-1; with leading 1 added) and A180141 (k=-2). Some other members of this family are 4*A003688 (k=3; with leading 1 added), 4*A003946 (k=4; with leading 1 added), 4*A002878 (k=5; with leading 1 added) and 4*A033484 (k=6; with leading 1 added).
(End)
a(n) is the number of length n sequences on an alphabet of 4 letters that do not contain more than 2 consecutive equal letters. For example, a(3)=60 because we count all 4^3=64 words except: aaa, bbb, ccc, ddd. - Geoffrey Critzer, Mar 12 2014

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, arXiv:math/0112281 [math.CO], 2001.
A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, Annals. Combin., 7 (2003), 1-14.
Martin Burtscher, Igor Szczyrba, Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 205
Index entries for linear recurrences with constant coefficients, signature (3,3).

Column 4 in A265584.

[1] cat [Round(((2^(1-n)*(-(3-Sqrt(21))^(1+n) + (3+Sqrt(21))^(1+n))))/(3*Sqrt(21))): n in [1..50]]; // G. C. Greubel, Oct 26 2017

nn=25;CoefficientList[Series[(1-z^(m+1))/(1-r z +(r-1)z^(m+1))/.{r->4,m->2},{z,0,nn}],z] (* Geoffrey Critzer, Mar 12 2014 *)
CoefficientList[Series[(1 + x + x^2)/(1 - 3 x - 3 x^2), {x, 0, 40}], x] (* Vincenzo Librandi, Mar 14 2014 *)
LinearRecurrence[{3,3},{1,4,16},30] (* Harvey P. Dale, Jul 14 2023 *)

my(x='x+O('x^50)); Vec((1+x+x^2)/(1-3*x-3*x^2)) \\ G. C. Greubel, Oct 16 2017

a(0)=1, a(1)=4, a(2)=16, a(n)=3*a(n-1)+3*a(n-2) for n>2. - Philippe Deléham, Sep 18 2009

a(n) = ((2^(1-n)*(-(3-sqrt(21))^(1+n) + (3+sqrt(21))^(1+n)))) / (3*sqrt(21)) for n>0. - Colin Barker, Oct 17 2017

A208343 Triangle of coefficients of polynomials v(n,x) jointly generated with A208342; see the Formula section.

Original entry on oeis.org

1, 0, 2, 0, 1, 3, 0, 1, 2, 5, 0, 1, 2, 5, 8, 0, 1, 2, 6, 10, 13, 0, 1, 2, 7, 13, 20, 21, 0, 1, 2, 8, 16, 29, 38, 34, 0, 1, 2, 9, 19, 39, 60, 71, 55, 0, 1, 2, 10, 22, 50, 86, 122, 130, 89, 0, 1, 2, 11, 25, 62, 116, 187, 241, 235, 144, 0, 1, 2, 12, 28, 75, 150, 267, 392, 468

Offset: 1

Clark Kimberling, Feb 25 2012

u(n,n) = A000045(n+1) (Fibonacci numbers).
n-th row sum:  2^(n-1)
As triangle T(n,k) with 0 <= k <= n, it is (0, 1/2, 1/2, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (2, -1/2, -1/2, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Feb 26 2012

			First five rows:
  1;
  0, 2;
  0, 1, 3;
  0, 1, 2, 5;
  0, 1, 2, 5, 8;
First five polynomials v(n,x):
  1
     2x
      x + 3x^2
      x + 2x^2 + 5x^3
      x + 2x^2 + 5x^3 + 8x^4.

Cf. A208343.

Cf. A084938, A000045, A000079.

u[1, x_] := 1; v[1, x_] := 1; z = 13;
u[n_, x_] := u[n - 1, x] + x*v[n - 1, x];
v[n_, x_] := x*u[n - 1, x] + x*v[n - 1, x];
Table[Expand[u[n, x]], {n, 1, z/2}]
Table[Expand[v[n, x]], {n, 1, z/2}]
cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
TableForm[cu]
Flatten[%]  (* A208342 *)
Table[Expand[v[n, x]], {n, 1, z}]
cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
TableForm[cv]
Flatten[%]  (* A208343 *)

u(n,x) = u(n-1,x) + x*v(n-1,x),
v(n,x) = x*u(n-1,x) + x*v(n-1,x),
where u(1,x)=1, v(1,x)=1.
From Philippe Deléham, Feb 26 2012: (Start)
As triangle T(n,k) with 0 <= k <= n:
T(n,k) = T(n-1,k) + T(n-1,k-1) + T(n-2,k-2) - T(n-2,k-1), T(0,0) = 1, T(1,0) = 0, T(1,1) = 2, T(n,k) = 0 if k > n or if k < 0.
G.f.: (1-(1-y)*x)/(1-(1+y)*x+y*(1-y)*x^2).
Sum_{k=0..n} T(n,k)*x^k = (-1)*A091003(n+1), A152166(n), A000007(n), A000079(n), A055099(n), A152224(n) for x = -2, -1, 0, 1, 2, 3 respectively.
Sum_{k=0..n} T(n,k)*x^(n-k) = A087205(n), A140165(n+1), A016116(n+1), A000045(n+2), A000079(n), A122367(n), A006012(n), A052961(n), A154626(n) for x = -3, -2, -1, 0, 1, 2, 3, 4 respectively. (End)
T(n,k) = A208748(n,k)/2^k. - Philippe Deléham, Mar 05 2012

A254601 Numbers of n-length words on alphabet {0,1,...,6} with no subwords ii, where i is from {0,1,2}.

Original entry on oeis.org

1, 7, 46, 304, 2008, 13264, 87616, 578752, 3822976, 25252864, 166809088, 1101865984, 7278432256, 48078057472, 317582073856, 2097804673024, 13857156333568, 91534156693504, 604633565495296, 3993938019745792, 26382162380455936, 174268726361718784

Offset: 0

Milan Janjic, Feb 02 2015

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (6,4).

Cf. A055099, A126473, A126501, A126528, A135032, A190976 (shifted bin. trans).

[n le 1 select 7^n else 6*Self(n)+4*Self(n-1): n in [0..25]]; // Bruno Berselli, Feb 03 2015

RecurrenceTable[{a[0] == 1, a[1] == 7, a[n] == 6 a[n - 1] + 4 a[n - 2]}, a[n], {n, 0, 25}]
LinearRecurrence[{6,4},{1,7},30] (* Harvey P. Dale, Oct 10 2017 *)

Vec((1 + x)/(1 - 6*x - 4*x^2) + O(x^30)) \\ Colin Barker, Jan 22 2017

G.f.: (1 + x)/(1 - 6*x - 4*x^2).
a(n) =  6*a(n-1) + 4*a(n-2) with n>1, a(0) = 1, a(1) = 7.
a(n) = ((3-r)^n*(-4+r) + (3+r)^n*(4+r)) / (2*r), where r=sqrt(13). - Colin Barker, Jan 22 2017
a(n) = A135032(n-1)+A135032(n). - R. J. Mathar, Apr 07 2022

A254658 Numbers of words on alphabet {0,1,...,7} with no subwords ii, where i is from {0,1,2,3}.

Original entry on oeis.org

1, 8, 60, 452, 3404, 25636, 193068, 1454020, 10950412, 82468964, 621084396, 4677466628, 35226603980, 265296094372, 1997979076524, 15047037913156, 113321181698188, 853436423539940, 6427339691572332, 48405123535166084, 364545223512451916, 2745437058727827748

Offset: 0

Milan Janjic, Feb 04 2015

a(n) equals the number of octonary sequences of length n such that no two consecutive terms differ by 6. - David Nacin, May 31 2017

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (7,4).

Cf. A015561, A055099, A126473, A126501, A126528, A254598, A254602.

[n le 1 select 8^n else 7*Self(n)+4*Self(n-1): n in [0..20]];

RecurrenceTable[{a[0] == 1, a[1] == 8, a[n] == 7 a[n - 1] + 4 a[n - 2]}, a[n], {n, 0, 20}]
LinearRecurrence[{7,4},{1,8},30] (* Harvey P. Dale, Jan 21 2023 *)

Vec((1 + x) / (1 - 7*x -4*x^2) + O(x^30)) \\ Colin Barker, Jan 21 2017

G.f.: (1 + x)/(1 - 7*x -4*x^2).
a(n) = 7*a(n-1) + 4*a(n-2) with n>1, a(0) = 1, a(1) = 8.
a(n) = (2^(-1-n)*((7-sqrt(65))^n*(-9+sqrt(65)) + (7+sqrt(65))^n*(9+sqrt(65)))) / sqrt(65). - Colin Barker, Jan 21 2017

A254663 Numbers of n-length words on alphabet {0,1,...,7} with no subwords ii, where i is from {0,1,...,5}.

Original entry on oeis.org

1, 8, 58, 422, 3070, 22334, 162478, 1182014, 8599054, 62557406, 455099950, 3310814462, 24085901134, 175222936862, 1274732360302, 9273572395838, 67464471491470, 490798445231966, 3570518059606702, 25975223307710846, 188967599273189326, 1374723641527746974

Offset: 0

Milan Janjic, Feb 04 2015

a(n) equals the number of octonary sequences of length n such that no two consecutive terms differ by 5. - David Nacin, May 31 2017

Colin Barker, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (7,2).

Cf. A015555, A055099, A126473, A126501, A126528, A254598, A254602.

[n le 1 select 8^n else 7*Self(n)+2*Self(n-1): n in [0..20]];

RecurrenceTable[{a[0] == 1, a[1] == 8, a[n] == 7 a[n - 1] + 2 a[n - 2]}, a[n], {n, 0, 20}]
LinearRecurrence[{7,2},{1,8},30] (* Harvey P. Dale, Nov 28 2023 *)

Vec((1 + x)/(1 - 7*x - 2*x^2) + O(x^30)) \\ Colin Barker, Jan 22 2017

G.f.: (1 + x)/(1 - 7*x - 2*x^2).
a(n) = 7*a(n-1) + 2*a(n-2) with n>1, a(0) = 1, a(1) = 8.
a(n) = 2^(-1-n)*((7-r)^n*(-9+r) + (7+r)^n*(9+r)) / r, where r=sqrt(57). - Colin Barker, Jan 22 2017

A254664 Numbers of words on alphabet {0,1,...,8} with no subwords ii, where i is from {0,1,...,5}.

Original entry on oeis.org

1, 9, 75, 627, 5241, 43809, 366195, 3060987, 25586481, 213874809, 1787757915, 14943687747, 124912775721, 1044133269009, 8727804479235, 72954835640907, 609822098564961, 5097441295442409, 42608996659234155, 356164297160200467

Offset: 0

Milan Janjic, Feb 04 2015

a(n) is the number of nonary sequences of length n such that no two consecutive terms have distance 6. - David Nacin, May 31 2017

Index entries for linear recurrences with constant coefficients, signature (8,3).

Cf. A015574, A055099, A126473, A126501, A126528, A254598, A254602.

[n le 1 select 9^n else 8*Self(n)+3*Self(n-1): n in [0..20]];

RecurrenceTable[{a[0] == 1, a[1] == 9, a[n] == 8 a[n - 1] + 3 a[n - 2]}, a[n], {n, 0, 20}]
LinearRecurrence[{8,3},{1,9},20] (* Harvey P. Dale, Feb 16 2024 *)

G.f.: (1 + x)/(1 - 8*x -3*x^2).
a(n) = 8*a(n-1) + 3*a(n-2) with n>1, a(0) = 1, a(1) = 9.
a(n) = ((1+t)*(4-t)^(n+1)+(-1+t)*(4+t)^(n+1))/(6*t), where t=sqrt(19). [Bruno Berselli, Feb 04 2015]

A133129 Number of black/white colorings of a 3 X n rectangle which have no monochromatic 2 by 2 subsquares.

Original entry on oeis.org

1, 8, 50, 322, 2066, 13262, 85126, 546410, 3507314, 22512862, 144506294, 927561722, 5953863490, 38216853518, 245307588134, 1574588362378, 10107019231634, 64875265300670, 416423472774166, 2672952594083738, 17157235452223586, 110129423550044398

Offset: 0

Victor S. Miller, Sep 19 2007

nonn

			a(2) = 50 because if the middle row is not monochromatic, the top and bottom rows are unconstrained, contributing 2*4*4. if the middle row is monochromatic, the top and bottom rows can each take on only 3 values contributing 2*3*3.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (6, 3, -2).

Cf. A055099, A133357.

Column k=3 of A181245.

G.f.: 1+x*(8+2*x-2*x^2)/(1-6*x-3*x^2+2*x^3). - Colin Barker, Jan 04 2012

More terms from Colin Barker, Jan 03 2012

a(0)=1 prepended and g.f. adapted by Alois P. Heinz, Feb 19 2015

A208762 Triangle of coefficients of polynomials v(n,x) jointly generated with A208761; see the Formula section.

Original entry on oeis.org

1, 2, 2, 3, 7, 4, 4, 17, 21, 8, 5, 34, 68, 55, 16, 6, 60, 174, 225, 137, 32, 7, 97, 384, 705, 674, 327, 64, 8, 147, 763, 1863, 2489, 1883, 761, 128, 9, 212, 1400, 4362, 7640, 8012, 5016, 1735, 256, 10, 294, 2412, 9318, 20542, 27996, 24144, 12885, 3897

Offset: 1

Clark Kimberling, Mar 03 2012

Alternating row sums: 1,0,0,0,0,0,0,0,0,...  For a discussion and guide to related arrays, see A208510.
As triangle T(n,k) with 0<=k<=n, it is (2, -1/2, 1/2, 0 0 0 0 0 0 0 ...) DELTA (2, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938. - Philippe Deléham, Mar 04 2012
Row sums are in A055099. - Philippe Deléham, Mar 04 2012

			First five rows:
1
2...2
3...7....4
4...17...21...8
5...34...68...55...16
First five polynomials v(n,x):
1
2 + 2x
3 + 7x + 4x^2
4 + 17x + 22x^2 + 8x^3
5 + 34x + 68x^2 + 55x^3 + 16x^4

Cf. A208761, A208510.

u[1, x_] := 1; v[1, x_] := 1; z = 16;
u[n_, x_] := u[n - 1, x] + 2 x*v[n - 1, x];
v[n_, x_] := (x + 1)*u[n - 1, x] + (x + 1) v[n - 1, x];
Table[Expand[u[n, x]], {n, 1, z/2}]
Table[Expand[v[n, x]], {n, 1, z/2}]
cu = Table[CoefficientList[u[n, x], x], {n, 1, z}];
TableForm[cu]
Flatten[%]    (* A208761 *)
Table[Expand[v[n, x]], {n, 1, z}]
cv = Table[CoefficientList[v[n, x], x], {n, 1, z}];
TableForm[cv]
Flatten[%]    (* A208762 *)

u(n,x)=u(n-1,x)+2x*v(n-1,x),
v(n,x)=(x+1)*u(n-1,x)+(x+1)*v(n-1,x),
where u(1,x)=1, v(1,x)=1.
As triangle T(n,k) with 0<=k<=n : T(n,k) = 2*T(n-1,k) + T(n-1,k-1) - T(n-2,k) + T(n-2,k-1) + 2*T(n-2,k-2), T(0,0) = 1, T(1,0) = T(1,1) = 2 and T(n,k) = 0 if k>n or if k<0. - Philippe Deléham, Mar 04 2012
G.f.: (-1-x*y)*x*y/(-1+x*y+x^2*y+2*x^2*y^2+2*x-x^2). - R. J. Mathar, Aug 12 2015

A285266 Array read by antidiagonals: T(m,n) = number of m-ary words of length n with adjacent elements differing by 2 or less.

Original entry on oeis.org

1, 3, 1, 9, 4, 1, 27, 14, 5, 1, 81, 50, 19, 6, 1, 243, 178, 75, 24, 7, 1, 729, 634, 295, 100, 29, 8, 1, 2187, 2258, 1161, 418, 125, 34, 9, 1, 6561, 8042, 4569, 1748, 543, 150, 39, 10, 1, 19683, 28642, 17981, 7310, 2363, 668, 175, 44, 11, 1

Offset: 3

Andrew Howroyd, Apr 15 2017

All rows are linear recurrences with constant coefficients. See PARI script to obtain generating functions.

			Array starts (m>=3, n>=0):
1  3  9  27  81  243   729  2187   6561 ...
1  4 14  50 178  634  2258  8042  28642 ...
1  5 19  75 295 1161  4569 17981  70763 ...
1  6 24 100 418 1748  7310 30570 127842 ...
1  7 29 125 543 2363 10287 44787 194995 ...
1  8 34 150 668 2986 13362 59816 267802 ...
1  9 39 175 793 3611 16475 75229 343633 ...
1 10 44 200 918 4236 19598 90790 420870 ...

Andrew Howroyd, Table of n, a(n) for n = 3..1277

Rows 4-32 are A055099, A126392-A126419.

Cf. A285280, A188866, A285267.

diff = 2; m0 = 3; mmax = 12;
TransferGf[m_, u_, t_, v_, z_] := Array[u, m].LinearSolve[IdentityMatrix[m] - z*Array[t, {m, m}], Array[v, m]]
RowGf[d_, m_, z_] := 1+z*TransferGf[m, 1&, Boole[Abs[#1-#2] <= d]&, 1&, z];
row[m_] := row[m] = CoefficientList[RowGf[diff, m, x] + O[x]^mmax, x];
T[m_ /; m >= m0, n_ /; n >= 0] := row[m][[n + 1]];
Table[T[m - n , n], {m, m0, mmax}, {n, m - m0, 0, -1}] // Flatten (* Jean-François Alcover, Jun 17 2017, adapted from PARI *)

TransferGf(m,u,t,v,z)=vector(m,i,u(i))*matsolve(matid(m)-z*matrix(m,m,i,j,t(i,j)),vectorv(m,i,v(i)));
RowGf(d,m,z)=1+z*TransferGf(m, i->1, (i,j)->abs(i-j)<=d, j->1, z);
for(m=3, 10, print(RowGf(2,m,x)));
for(m=3, 10, v=Vec(RowGf(2,m,x) + O(x^9)); for(n=1, length(v), print1( v[n], ", ") ); print(); );

cp's OEIS Frontend

A007481 Number of subsequences of [ 1,...,n ] in which each even number has an odd neighbor.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Formula

Extensions

A123620 Expansion of (1 + x + x^2) / (1 - 3*x - 3*x^2).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A208343 Triangle of coefficients of polynomials v(n,x) jointly generated with A208342; see the Formula section.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A254601 Numbers of n-length words on alphabet {0,1,...,6} with no subwords ii, where i is from {0,1,2}.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A254658 Numbers of words on alphabet {0,1,...,7} with no subwords ii, where i is from {0,1,2,3}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A254663 Numbers of n-length words on alphabet {0,1,...,7} with no subwords ii, where i is from {0,1,...,5}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A254664 Numbers of words on alphabet {0,1,...,8} with no subwords ii, where i is from {0,1,...,5}.

Views

Author

Keywords

Comments

Links

Crossrefs

A123620 Expansion of (1 + x + x^2) / (1 - 3x - 3x^2).