A052536 -id:A052536 - cp's OEIS frontend

A076264 Number of ternary (0,1,2) sequences without a consecutive '012'.

1, 3, 9, 26, 75, 216, 622, 1791, 5157, 14849, 42756, 123111, 354484, 1020696, 2938977, 8462447, 24366645, 70160958, 202020427, 581694636, 1674922950, 4822748423, 13886550633, 39984728949, 115131438424, 331507764639

Offset: 0

John L. Drost, Nov 05 2002

A transform of A000244 under the mapping g(x)->(1/(1+x^3))g(x/(1+x^3)). - Paul Barry, Oct 20 2004
b(n) := (-1)^n*a(n) appears in the formula for the nonpositive powers of rho(9) := 2*cos(Pi/9), when written in the power basis of the algebraic number field Q(rho(9)) of degree 3. See A187360 for the minimal polynomial C(9, x) of rho(9), and a link to the Q(2*cos(pi/n)) paper. 1/rho(9) = -3*1 + 0*rho(9) + 1*rho(9)^2 (see A230079, row n=5). 1/rho(9)^n = b(n)*1 + b(n-2)*rho(9) + b(n-1)*rho(9)^2, n >= 0, with b(-1) = 0 = b(-2). - Wolfdieter Lang, Nov 04 2013
The limit b(n+1)/b(n) = -a(n+1)/a(n) for n -> infinity is -tau(9) := -(1 + rho(9)) = 1/(2*cos(Pi*5/9)), approximately -2.445622407. tau(9) is known to be the length ratio (longest diagonal)/side in the regular 9-gon. This limit follows from the b(n)-recurrence and the solutions of X^3 + 3*X^2 - 1 = 0, which are given by the inverse of the known solutions of the minimal polynomial C(9, x) of rho(9) (see A187360). The other two X solutions are 1/rho(9) = -3 + rho(9)^2, approximately 0.5320888860 and 1/(2*cos(Pi*7/9)) = 1 + rho(9) - rho(9)^2, approximately -0.6527036445, and they are therefore irrelevant for this sequence. - Wolfdieter Lang, Nov 08 2013
a(n) is also the number of ternary (0,1,2) sequences of length n without a consecutive '110' because the patterns A=012 and B=110 have the same autocorrelation, i.e., AA=100=BB, in the sense of Guibas and Odlysko (1981). (A cyclic version of this sequence can be found in sequence A274018.) - Petros Hadjicostas, Sep 12 2017

			1/rho(9)^3 = -26*1 - 3*rho(9) + 9*rho(9)^2, (approximately 0.15064426) with rho(9) given in the Nov 04 2013 comment above. - _Wolfdieter Lang_, Nov 04 2013
G.f. = 1 + 3*x + 9*x^2 + 26*x^3 + 75*x^4 + 216*x^5 + 622*x^6 + 1791*x^7 + ...

A. Tucker, Applied Combinatorics, 4th ed. p. 277

Harvey P. Dale, Table of n, a(n) for n = 0..1000
Taras Goy and Mark Shattuck, Toeplitz-Hessenberg determinant formulas for the sequence F_n-1, Online J. Anal. Comb. (2025) Vol. 19, Paper 1, 1-26. See p. 12.
Leo J. Guibas and Andrew M. Odlyzko, String overlaps, pattern matching, and nontransitive games, J. Combin. Theory Ser. A 30 (1981), 183-208. [Comment: The authors use generating functions in terms of z^{-1}. To get the g.f. of the sequence, as shown below in the FORMULA section, let x=z^{-1} and perform simple algebra. There are some minor typos in Theorem 2.1, p. 191, that can be easily corrected by looking at the proof. - _Petros Hadjicostas_, Sep 12 2017]
Yun-Tak Oh, Hosho Katsura, Hyun-Yong Lee, and Jung Hoon Han, Proposal of a spin-one chain model with competing dimer and trimer interactions, arXiv:1709.01344 [cond-mat.str-el], 2017.
Index entries for linear recurrences with constant coefficients, signature (3,0,-1).

The g.f. corresponds to row 3 of triangle A225682.

List([0..25],n->Sum([0..Int(n/3)],k->Binomial(n-2*k,k)*(-1)^k*3^(n-3*k))); # Muniru A Asiru, Feb 20 2018

LinearRecurrence[{3,0,-1},{1,3,9},30] (* Harvey P. Dale, Feb 28 2016 *)

{a(n) = if( n<0, 0, polcoeff( 1 / (1 - 3*x + x^3) + x * O(x^n), n))};

a(n) is asymptotic to g*c^n where c = cos(Pi/18)/cos(7*Pi/18) and g is the largest real root of 81*x^3 - 81*x^2 - 9*x + 1 = 0. - Benoit Cloitre, Nov 06 2002
G.f.: 1/(1 - 3x + x^3).
a(n) = 3*a(n-1) - a(n-3), n > 0.
a(n) = Sum_{k=0..floor(n/3)} binomial(n-2k, k)(-1)^k*3^(n-3k). - Paul Barry, Oct 20 2004
a(n) = middle term in M^(n+1) * [1 0 0], where M = the 3 X 3 matrix [2 1 1 / 1 1 0 / 1 0 0]. Right term = A052536(n), left term = A052536(n+1). - Gary W. Adamson, Sep 05 2005

A122100 a(n) = 3*a(n-1) - a(n-3) for n>2, with a(0)=1, a(1)=-1, a(2)=0.

Original entry on oeis.org

1, -1, 0, -1, -2, -6, -17, -49, -141, -406, -1169, -3366, -9692, -27907, -80355, -231373, -666212, -1918281, -5523470, -15904198, -45794313, -131859469, -379674209, -1093228314, -3147825473, -9063802210, -26098178316, -75146709475, -216376326215, -623030800329, -1793945691512

Offset: 0

Philippe Deléham, Oct 18 2006

G. C. Greubel, Table of n, a(n) for n = 0..1000
Paul Barry, Centered polygon numbers, heptagons and nonagons, and the Robbins numbers, arXiv:2104.01644 [math.CO], 2021.
Kai Wang, Fibonacci Numbers And Trigonometric Functions Outline, (2019).
Index entries for linear recurrences with constant coefficients, signature (3,0,-1).

Cf. A052536, A122099.

a:=[1,-1,0];; for n in [4..40] do a[n]:=3*a[n-1]-a[n-3]; od; a; # G. C. Greubel, Oct 02 2019

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1-4*x+3*x^2)/(1-3*x+x^3) )); // G. C. Greubel, Oct 02 2019

seq(coeff(series((1-4*x+3*x^2)/(1-3*x+x^3), x, n+1), x, n), n = 0 .. 40); # G. C. Greubel, Oct 02 2019

LinearRecurrence[{3,0,-1},{1,-1,0},40] (* Harvey P. Dale, Nov 14 2014 *)

Vec((1-4*x+3*x^2)/(1-3*x+x^3)+O(x^40)) \\ Charles R Greathouse IV, Jan 17 2012

def A122100_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-4*x+3*x^2)/(1-3*x+x^3)).list()
A122100_list(40) # G. C. Greubel, Oct 02 2019

G.f.: (1-4*x+3*x^2)/(1-3*x+x^3).

A366671 Smallest prime dividing 8^n + 1.

Original entry on oeis.org

2, 3, 5, 3, 17, 3, 5, 3, 97, 3, 5, 3, 17, 3, 5, 3, 193, 3, 5, 3, 17, 3, 5, 3, 97, 3, 5, 3, 17, 3, 5, 3, 641, 3, 5, 3, 17, 3, 5, 3, 97, 3, 5, 3, 17, 3, 5, 3, 193, 3, 5, 3, 17, 3, 5, 3, 97, 3, 5, 3, 17, 3, 5, 3, 769, 3, 5, 3, 17, 3, 5, 3, 97, 3, 5, 3, 17, 3, 5

Offset: 0

Sean A. Irvine, Oct 15 2023

nonn

a(n) = 3 if n is odd. a(n) = 5 if n == 2 (mod 4). - Robert Israel, Nov 20 2023

Max Alekseyev, Table of n, a(n) for n = 0..16383

Cf. A002586, A366609, A052536, A366655, A274905, A366670, A038371, A366719.

P1000:= mul(ithprime(i),i= 4..1000):
f:= proc(n) local t;
  if n::odd then return 3 elif n mod 4 = 2 then return 5 fi;
  t:= igcd(8^n+1,P1000);
  if t <> 1 then min(numtheory:-factorset(t)) else min(numtheory:-factorset(8^n+1)) fi
end proc:
map(f, [$0..100]); # Robert Israel, Nov 20 2023

Table[FactorInteger[8^n + 1][[1,1]], {n, 0, 78}] (* Paul F. Marrero Romero, Oct 20 2023 *)

from sympy import primefactors
def A366671(n): return min(primefactors((1<<3*n)+1)) # Chai Wah Wu, Oct 16 2023

a(n) = A020639(A062395(n)). - Paul F. Marrero Romero, Oct 20 2023

a(n) = A002586(3*n) for n >= 1. - Robert Israel, Nov 20 2023

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

Original entry on oeis.org

1, 1, 4, 11, 32, 92, 265, 763, 2197, 6326, 18215, 52448, 151018, 434839, 1252069, 3605189, 10380728, 29890115, 86065156, 247814740, 713554105, 2054597159, 5915976737, 17034376106, 49048531159, 141229616740, 406654474114

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

(1, 4, 11, 32, ...) = INVERT transform of (1, 3, 4, 5, 6, 7, ...).

G. C. Greubel, Table of n, a(n) for n = 0..1000
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 481
Index entries for linear recurrences with constant coefficients, signature (3,0,-1).

Cf. A215448. First differences of A052536.

a:=[1,1,4];; for n in [4..40] do a[n]:=3*a[n-1]-a[n-3]; od; a; # G. C. Greubel, May 08 2019

R:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1-x)^2/(1-3*x+x^3) )); // G. C. Greubel, May 08 2019

spec := [S,{S=Sequence(Prod(Z,Union(Z,Sequence(Z)),Sequence(Z)))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..20);

LinearRecurrence[{3,0,-1}, {1,1,4}, 40] (* G. C. Greubel, May 08 2019 *)

my(x='x+O('x^40)); Vec((1-x)^2/(1-3*x+x^3)) \\ G. C. Greubel, May 08 2019

TOP = 33
a = [1]*TOP
a[2]=4
for n in range(3,TOP):
    print(a[n-3], end=',')
    a[n] = 3*a[n-1] - a[n-3]
# Alex Ratushnyak, Aug 10 2012

((1-x)^2/(1-3*x+x^3)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, May 08 2019

G.f.: (1-x)^2/(1-3*x+x^3).
a(n) = 3*a(n-1) - a(n-3), with a(0)=a(1)=1, a(2)=4.
a(n) = Sum_{alpha = RootOf(1-3*x+x^3)} (-1/9 * (-1+2*alpha^2-2*alpha) * alpha^(-1-n)).
a(n) = A076264(n) - 2*A076264(n-1) + A076264(n-2). - R. J. Mathar, Nov 28 2011

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

Original entry on oeis.org

1, 3, 6, 18, 51, 147, 423, 1218, 3507, 10098, 29076, 83721, 241065, 694119, 1998636, 5754843, 16570410, 47712594, 137382939, 395578407, 1139022627, 3279684942, 9443476419, 27191406630, 78294534948, 225440128425, 649128978645, 1869092400987, 5381837074536

Offset: 0

N. J. A. Sloane, Nov 20 2006

nonn

A. Burstein and T. Mansour, Words restricted by 3-letter ..., Annals. Combin., 7 (2003), 1-14.

G. C. Greubel, 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.
Index entries for linear recurrences with constant coefficients, signature (3,0,-1).

Cf. A052536.

a:=[3,6,18];; for n in [4..30] do a[n]:=3*a[n-1]-a[n-3]; od; Concatenation([1], a); # G. C. Greubel, Aug 07 2019

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-3*x^2+x^3)/(1-3*x+x^3) )); // G. C. Greubel, Aug 07 2019

seq(coeff(series((1-3*x^2+x^3)/(1-3*x+x^3), x, n+1), x, n), n = 0..40); # G. C. Greubel, Aug 07 2019

Join[{1}, LinearRecurrence[{3, 0, -1}, {3, 6, 18}, 28]] (* Jean-François Alcover, Oct 08 2018 *)
CoefficientList[Series[(1-3x^2+x^3)/(1-3x+x^3),{x,0,40}],x] (* Harvey P. Dale, Jan 16 2022 *)

my(x='x+O('x^30)); Vec((1-3*x^2+x^3)/(1-3*x+x^3)) \\ G. C. Greubel, Aug 07 2019

((1-3*x^2+x^3)/(1-3*x+x^3)).series(x, 30).coefficients(x, sparse=False) # G. C. Greubel, Aug 07 2019

a(n) = 3*A052536(n-1), n>0. - R. J. Mathar, Sep 27 2014

A215448 a(0)=1, a(1)=0, a(n) = a(n-1) + a(n-2) + Sum_{i=0...n-1} a(i).

Original entry on oeis.org

1, 0, 2, 5, 15, 43, 124, 357, 1028, 2960, 8523, 24541, 70663, 203466, 585857, 1686908, 4857258, 13985917, 40270843, 115955271, 333879896, 961368845, 2768151264, 7970573896, 22950352843, 66082907265, 190278147899, 547884090854, 1577569365297, 4542429947992

Offset: 0

Alex Ratushnyak, Aug 10 2012

For the general recurrence X(n) = 3*X(n-1) - X(n-3) we get Sum_{k=3..n} X(k) = 3*Sum_{k=2..n-1} X(k) - Sum_{k=0..n-3} X(k), which implies the following summation formula: X(n) - X(n-1) - X(n-2) - X(2) + X(1) + X(0) = Sum_{k=2..n-1} X(k). Similarly from the formula X(n) + X(n-3) = 3*X(n-1) we deduce the following relations: Sum_{k=0..2*n-1} X(3*k) = 3*Sum_{k=0..n-1} X(6*k+2), Sum_{k=0..2*n-1} X(3*k+1) = 3*Sum_{k=1..n} X(6*k), and Sum_{k=0..2*n-1} X(3*k+2) = 3*Sum_{k=1..n} X(6*k-2). Lastly from the formula X(n)-X(n-1)=(X(n-1)-X(n-3))+X(n-1) we obtain the relations: Sum_{k=2..2*n+1} (-1)^(k-1)*X(k) = X(2*n) - X(0) + Sum_{k=1..n} X(2*k) and Sum_{k=3..2n} (-1)^k*X(k) = X(2*n-1) - X(1) + Sum_{k=2..n} X(2*k-1). - Roman Witula, Aug 27 2012

Index entries for linear recurrences with constant coefficients, signature (3,0,-1).

Cf. A052536: same formula, seed {0, 1}, first term removed.
Cf. A122100: same formula, seed {0,-1}, first two terms removed.
Cf. A052545: same formula, seed {1, 1}.

LinearRecurrence[{3,0,-1},{1,0,2},30] (* Harvey P. Dale, Jan 26 2017 *)

a = [1]*33
a[1]=0
sum = a[0]+a[1]
for n in range(2,33):
    print(a[n-2], end=', ')
    a[n] = a[n-1] + a[n-2] + sum
    sum += a[n]

a(0)=1, a(1)=0, for n>=2, a(n) = a(n-1) + a(n-2) + (a(0)+...+a(n-1)).
Conjecture: a(n) = +3*a(n-1) -a(n-3) = A076264(n) -3 *A076264(n-1) +2*A076264(n-2). G.f. (2*x-1)*(x-1) / ( 1-3*x+x^3 ). - R. J. Mathar, Aug 11 2012
Proof of the above conjecture: we have a(n) - a(n-1) = a(n-1) + a(n-2) + (a(0) + ... + a(n-1)) - a(n-2) - a(n-3) - (a(0) + ... + a(n-2)), which after simple algebra implies a(n) - a(n-1) = 2*a(n-1) - a(n-3), so the Mathar's formula holds true (see also Witula's comment above). - Roman Witula, Aug 27 2012

A052693 Expansion of e.g.f. (1-x)/(1-3*x+x^3).

Original entry on oeis.org

1, 2, 12, 102, 1176, 16920, 292320, 5891760, 135717120, 3517032960, 101268921600, 3207514464000, 110828037196800, 4148515981209600, 167232459621427200, 7222900141416960000, 332760193091149824000

Offset: 0

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

G. C. Greubel, Table of n, a(n) for n = 0..375
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 642

Cf. A000142, A052536.

R:=PowerSeriesRing(Rationals(), 40); Coefficients(R!(Laplace( (1-x)/(1-3*x+x^3) ))); // G. C. Greubel, Jun 01 2022

spec := [S,{S=Sequence(Union(Z,Prod(Z,Union(Z,Sequence(Z)))))},labeled]: seq(combstruct[count](spec,size=n), n=0..20);

With[{nn=20},CoefficientList[Series[(1-x)/(1-3x+x^3),{x,0,nn}],x]Range[0,nn]!] (* Harvey P. Dale, Dec 17 2012 *)

@CachedFunction
def A052536(n):
    if (n<3): return factorial(n+1)
    else: return 3*A052536(n-1) - A052536(n-3)
def A052693(n): return factorial(n)*A052536(n)
[A052693(n) for n in (0..40)] # G. C. Greubel, Jun 01 2022

E.g.f.: (1-x)/(1-3*x+x^3).
Recurrence: a(0)=1, a(1)=2, a(2)=12 a(n+3) = 3*(n+3)*a(n+2) - (n+1)*(n+2)*(n+3)*a(n).
a(n) = (n!/9)*Sum_{alpha=RootOf(1 -3*Z +Z^3)} (2 - alpha + alpha^2)*alpha^(-1-n).
a(n) = n! * A052536(n). - G. C. Greubel, Jun 01 2022

A105478 Triangle read by rows: T(n,k) is the number of compositions of n into k parts when parts 1 and 2 are of two kinds.

Original entry on oeis.org

2, 2, 4, 1, 8, 8, 1, 8, 24, 16, 1, 8, 36, 64, 32, 1, 9, 44, 128, 160, 64, 1, 10, 54, 192, 400, 384, 128, 1, 11, 66, 264, 720, 1152, 896, 256, 1, 12, 79, 352, 1120, 2432, 3136, 2048, 512, 1, 13, 93, 456, 1632, 4272, 7616, 8192, 4608, 1024, 1, 14, 108, 576, 2280, 6816

Offset: 1

Emeric Deutsch, Apr 10 2005

			T(4,2)=8 because we have (1,3),(1',3),(3,1),(3,1'),(2,2),(2,2'),(2',2) and (2',2').
Triangle begins:
2;
2,4;
1,8,8;
1,8,24,16;
1,8,36,64,32;

Row sums yield A052536.

G:=t*z*(2-z^2)/(1-z-2*t*z+t*z^3): Gser:=simplify(series(G,z=0,14)): for n from 1 to 12 do P[n]:=expand(coeff(Gser,z^n)) od: for n from 1 to 12 do seq(coeff(P[n],t^k),k=1..n) od; # yields sequence in triangular form

t[1, 1] = t[2, 1] = 2; t[3, 2] = 8; t[, 1] = 1; t[n, n_] := 2^n; t[n_, k_] /; 1 <= k <= n := t[n, k] = t[n-1, k] + 2*t[n-1, k-1] - t[n-3, k-1]; t[n_, k_] = 0; Table[t[n, k], {n, 1, 11}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 12 2013 *)

G.f.=tz(2-z^2)/(1-z-2tz+tz^3). T(n, k)=T(n-1, k)+2T(n-1, k-1)-T(n-3, k-1).

A362379 Convolution triangle of A052547(n).

Original entry on oeis.org

1, 0, 1, 2, 0, 1, 1, 4, 0, 1, 5, 2, 6, 0, 1, 5, 14, 3, 8, 0, 1, 14, 14, 27, 4, 10, 0, 1, 19, 49, 27, 44, 5, 12, 0, 1, 42, 68, 113, 44, 65, 6, 14, 0, 1, 66, 175, 159, 214, 65, 90, 7, 16, 0, 1, 131, 286, 465, 304, 360, 90, 119, 8, 18, 0, 1

Offset: 0

Philippe Deléham, Apr 20 2023

			Triangle begins, for n>=0, 0<=k<=n :
   1 ;
   0,  1 ;
   2,  0,   1 ;
   1,  4,   0,  1 ;
   5,  2,   6,  0,  1 ;
   5, 14,   3,  8,  0,  1 ;
  14, 14,  27,  4, 10,  0,  1 ;
  19, 49,  27, 44,  5, 12,  0, 1 ;
  42, 68, 113, 44, 65,  6, 14, 0, 1 ;
  ...

Cf. A052547, A077998 (row sums), A052964 (diagonal sums).

T(n,k) = T(n-1,k) + T(n-1,k-1) + 2*T(n-2,k) - T(n-2,k-1) - T(n-3,k) ; T(0,0) = T(1,1) = T(2,2) = 1, T(1,0) = T(2,1) = 0, T(2,0) = 2, T(n,k) = 0 if k<0 or if k>n .
Sum_{k = 0..n} T(n,k)*x^k = A052547(n), A077998(n), A052536(n), A052941(n) for x = 0, 1, 2, 3 respectively.
Sum_{k = 0..n} T(n,k)*2^(n-k) = A139818(n+1) = A001045(n+1)^2.

cp's OEIS Frontend

A076264 Number of ternary (0,1,2) sequences without a consecutive '012'.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Mathematica

PARI

Formula

A122100 a(n) = 3*a(n-1) - a(n-3) for n>2, with a(0)=1, a(1)=-1, a(2)=0.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A366671 Smallest prime dividing 8^n + 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Python

Sage

Formula

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

Views

Author

Keywords

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A215448 a(0)=1, a(1)=0, a(n) = a(n-1) + a(n-2) + Sum_{i=0...n-1} a(i).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

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