A006356 -id:A006356 - cp's OEIS frontend

A306334 a(n) is the number of different linear hydrocarbon molecules with n carbon atoms.

1, 3, 4, 10, 18, 42, 84, 192, 409, 926, 2030, 4577, 10171, 22889, 51176, 115070, 257987, 579868, 1301664, 2925209, 6569992, 14763529, 33166848, 74527233, 167446566, 376253517, 845401158, 1899609267, 4268309531, 9590827171, 21550227328, 48422972296, 108805058758

Offset: 1

Vincent Champain, Feb 08 2019

Linear hydrocarbons are molecules made of carbon (C) and hydrogen (H) atoms organized without cycles.
a(n) <= A002986(n) because molecules can be acyclic but not linear (i.e., including carbon atoms bonded with more than two other carbons).
From Petros Hadjicostas, Nov 16 2019: (Start)
We prove Vaclav Kotesovec's conjectures from the Formula section. Let M = [[0,0,1], [0,1,1], [1,1,1]], X(n) = M^(n-2), and Y(n) = M^(floor(n/2)-2) = X(floor(n/2)) (with negative powers indicating matrix inverses). Let also, t_1 = [1,1,1]^T, t_2 = [1,2,2]^T, and t_3 = [1,2,3]^T. In addition, define b(n) = (1/2)*(t_1^T X(n) t_1) and c(n) = (1/2)*(t_3^T Y(n) t_1) if n is even and = (1/2)*(t_2^T Y(n) t_1) if n is odd.
We have a(n) = b(n) + c(n) for n >= 1. Since the characteristic polynomial of Vaclav Kotesovec's recurrence is x^9 - 2*x^8 - 3*x^7 + 5*x^6 + x^5 + 2*x^3 - 3*x^2 - x + 1 = g(x)*g(x^2), where g(x) = x^3 - 2*x^2 - x + 1, to prove his first conjecture, it suffices to show that b(n) - 2*b(n-1) - b(n-2) + b(n-3) = 0 (whose characteristic polynomial is g(x)) and c(n) - 2*c(n-2) - c(n-4) + c(n-6) = 0 (whose characteristic polynomial is g(x^2)).
Note that 2*b(n) = A006356(n-1) for n >= 1. (See the comments by L. Edson Jeffery and R. J. Mathar in the documentation of that sequence.) Also, 2*c(2*n) = A006356(n) and 2*c(2*n-1) = A006054(n+1) for n >= 1.
Properties of the polynomial g(x) = x^3 - 2*x^2 - x + 1 and its roots were studied by Witula et al. (2006) (see Corollary 2.4). This means that a(n) can essentially be expressed in terms of exp(I*2*Pi/7), but we omit the discussion. See also the comments for sequence A006054.
The characteristic polynomial of matrix M is g(x). By the Cayley-Hamilton theorem, 0 = g(M) = M^3 - 2*M^2 - M + I_3, and thus, for n >= 5, X(n) - 2*X(n-1) - X(n-2) + X(n-3) = M^(n-2) - 2*M^(n-3) - M^(n-4) + M^(n-5) = 0. Pre-multiplying by (1/2)*t_1^T and post-multiplying by t_1, we get that b(n) - 2*b(n-1) - b(n-2) + b(n-3) = 0 for n >= 5.
Similarly, for n >= 10, Y(n) - 2*Y(n-2) - Y(n-4) + Y(n-6) = X(floor(n/2)) - 2*X(floor((n-2)/2)) - X(floor((n-4)/2)) + X(floor((n-6)/2)) = X(floor(n/2)) - 2*X(floor(n/2) - 1) - X(floor(n/2) - 2) + X(floor(n/2) - 3) = 0. Pre-multiplying by (1/2)*t_3^T (when n is even) or by (1/2)*t_2^T (when n is odd), and post-multiplying by t_1, we get c(n) - 2*c(n-2) - c(n-4) + c(n-6) = 0 for n >= 10.
Since the characteristic polynomial of Vaclav Kotesovec's recurrence is g(x)*g(x^2), which is a polynomial of degree 9, the denominator of the g.f. of the sequence (a(n): n >= 1) should be x^9*g(1/x)*g(1/x^2) = (1 - 2*x - x^2 + x^3)*(1 - 2*x^2 - x^4 + x^6), as Vaclav Kotesovec conjectured below. The numerator of Vaclav Kotesovec's g.f. can be easily derived using the initial conditions (from a(1) = 1 to a(9) = 409). (End)

			For n=1, there is one possibility: CH4.
For n=2, there are 3 solutions: CHCH, CH3CH3, CH2CH2.
For n=3, there are 4 solutions: CHCCH3, CH2CCH2, CH3CHCH2, CH3CH2CH3.
For n=6, there are 42 solutions: CH3CH2CHCHCCH, CH3CH2CHCHCH2CH3, CH2CHCCCHCH2, CH2CHCHCHCH2CH3, CH2CHCHCHCCH, CH2CCCCHCH3, CHCCCCHCH2, CH3CHCHCHCHCH3, CHCCHCHCCH, CH2CCCCCH2, CH3CCCH2CH2CH3, CH3CCCCCH3, CH3CH2CH2CH2CH2CH3, CH2CHCHCHCHCH2, CH2CCHCH2CHCH2, CH3CHCCCHCH3, CHCCH2CH2CH2CH3, CHCCH2CH2CCH, CH3CCCH2CHCH2, CH2CCCHCH2CH3, CH2CCCHCCH, CHCCH2CCCH3, CHCCH2CHCCH2, CH3CH2CH2CH2CHCH2, CH2CHCHCCHCH3, CH3CH2CCCH2CH3, CH2CHCH2CH2CHCH2, CH2CHCHCCCH2, CH3CHCCHCH2CH3, CH3CH2CH2CHCHCH3, CH3CHCCHCCH, CHCCH2CH2CHCH2, CH3CHCHCCCH3, CH2CCHCCCH3, CH3CHCHCHCCH2, CHCCCCH2CH3, CH2CHCH2CHCHCH3, CH2CCHCHCCH2, CHCCCCCH, CH2CCHCH2CH2CH3, CH3CH2CCCHCH2, CHCCH2CHCHCH3.

Vincent Champain, Table of n, a(n) for n = 1..1000
L. Edson Jeffery, Danzer matrices (unit-primitive matrices). [It contains a discussion of a generalization of the matrix M that appears in the formula for a(n). See basis D_7.]
Wikipedia, Cayley-Hamilton theorem.
R. Witula, D. Slota, and A. Warzynski, Quasi-Fibonacci Numbers of the Seventh Order, J. Integer Seq. 9 (2006), Article 06.4.3. [See Corollary 2.4 and the discussion about the polynomial p_7(x) and its roots. This essentially proves that a(n) can be expressed in terms of exp(I*2*Pi/7).]
Index entries for linear recurrences with constant coefficients, signature (2,3,-5,-1,0,-2,3,1,-1).

Other hydrocarbon related sequences: A002986, A018190, A129012.

Cf. A006054, A006356.

with(LinearAlgebra):
M := Matrix([[0, 0, 1], [0, 1, 1], [1, 1, 1]]):
X := proc(n) MatrixPower(M, n - 2): end proc:
Y := proc(n) MatrixPower(M, floor(1/2*n) - 2): end proc:
a := proc(n) `if`(n < 4, [1,3,4][n], 1/2*(add(add(X(n)[i, j], i = 1..3), j = 1..3) + add(add(Y(n)[i, j]*min(j, 3 - (n mod 2)), i = 1..3), j = 1..3))):
     end proc:
seq(a(n), n=1..40); # Petros Hadjicostas, Nov 17 2019

M = {{0, 0, 1}, {0, 1, 1}, {1, 1, 1}};
X[n_] := MatrixPower[M, n - 2];
Y[n_] := MatrixPower[M, Floor[1/2*n] - 2];
a[n_] := If[n < 4, {1, 3, 4}[[n]], 1/2*(Sum[Sum[X[n][[i, j]], {i, 1, 3}], {j, 1, 3}] + Sum[Sum[Y[n][[i, j]]*Min[j, 3 - Mod[n, 2]], {i, 1, 3}], {j, 1, 3}])];
Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Aug 16 2023, after Petros Hadjicostas *)

from numpy import array as npa
from numpy.linalg import matrix_power as npow
def F(n):
     if n<4: return([0,1,3,4][n])
     m=npa([[0,0,1],[0,1,1],[1,1,1]],dtype=object)
     m2=npow(m,n//2-2)
     return((sum(sum(npow(m,n-2)))+sum(sum(m2[j]*min(j+1,3-(n&1)) for j in range(3))))//2)

a(n) = (1/2) * (Sum_{i,j = 1..3} X_{ij} + Sum_{i,j = 1..3} Y_{ij} * min(j, 3 - (n&1))), where M = [[0,0,1], [0,1,1], [1,1,1]], X = [X_{ij}: i,j = 1..3] = M^(n-2), and Y = [Y_{ij}: i,j = 1..3] = M^(floor(n/2)-2)) for n >= 1 (with negative powers indicating matrix inverses). [Edited by Petros Hadjicostas, Nov 16 2019]
Conjectures from Vaclav Kotesovec, Feb 12 2019: (Start)
a(n) = 2*a(n-1) + 3*a(n-2) - 5*a(n-3) - a(n-4) - 2*a(n-6) + 3*a(n-7) + a(n-8) - a(n-9), for n >= 10.
G.f.: (1 - x - 2*x^2 - x^4 + 2*x^5 + x^6 - x^7) / ((1 - 2*x - x^2 + x^3)*(1 - 2*x^2 - x^4 + x^6)) - 1. (End) [These conjectures are true. See my comments above. - Petros Hadjicostas, Nov 17 2019]
From Petros Hadjicostas, Nov 17 2019: (Start)
a(2*n) = (1/2)*(A006356(2*n-1) + A006356(n)).
a(2*n-1) = (1/2)*(A006356(2*n-2) + A006054(n+1)). (End)

A030113 Number of distributive lattices; also number of paths with n turns when light is reflected from 9 glass plates.

Original entry on oeis.org

1, 9, 45, 285, 1695, 10317, 62349, 377739, 2286648, 13846117, 83833256, 507596153, 3073376281, 18608642427, 112671254094, 682200039446, 4130572919575, 25009722123505, 151428434581516, 916866281219258

Offset: 0

Jacques Haubrich (jhaubrich(AT)freeler.nl)

Let M(9) be the 9 X 9 matrix (0,0,0,1)/(0,0,1,1)/(0,0,1,1)/(1,1,1,1) and let v(9) be the vector (1,1,1,1,1,1,1,1,1); then v(9)*M(9)^n = (x,y,z,t,u,v, w,m,a(n)) - Benoit Cloitre, Sep 29 2002

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124.
J. Haubrich, Multinacci Rijen [Multinacci sequences], Euclides (Netherlands), Vol. 74, Issue 4, 1998, pp. 131-133.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
Index entries for linear recurrences with constant coefficients, signature (5,10,-20,-15,21,7,-8,-1,1).

See also A006356-A006359, A025030, A030112-A030116.

CoefficientList[Series[-(x^8 - x^7 -7 x^6 + 6 x^5 + 15 x^4 - 10 x^3 - 10 x^2 + 4 x + 1)/(x^9 - x^8 - 8 x^7 + 7 x^6 + 21 x^5 - 15 x^4 - 20 x^3 + 10 x^2 + 5 x - 1), {x, 0, 30}], x] (* Vincenzo Librandi, Oct 19 2013 *)
LinearRecurrence[{5,10,-20,-15,21,7,-8,-1,1},{1,9,45,285,1695,10317,62349,377739,2286648},30] (* Harvey P. Dale, Dec 13 2015 *)

k=9; M(k)=matrix(k,k,i,j,if(1-sign(i+j-k),0,1)); v(k)=vector(k,i,1); a(n)=vecmax(v(k)*M(k)^n)

G.f.: -(x^8 -x^7 -7*x^6 +6*x^5 +15*x^4 -10*x^3 -10*x^2 +4*x +1)/(x^9 -x^8 -8*x^7 +7*x^6 +21*x^5 -15*x^4 -20*x^3 +10*x^2 +5*x -1). [Colin Barker, Nov 09 2012]

More terms from Benoit Cloitre, Sep 29 2002

A030115 Number of distributive lattices; also number of paths with n turns when light is reflected from 11 glass plates.

Original entry on oeis.org

1, 11, 66, 506, 3641, 26818, 196119, 1437799, 10532302, 77173602, 565424068, 4142793511, 30353430420, 222394369223, 1629443428021, 11938642758854, 87472304803355, 640893994357062, 4695716053827835, 34404674660198306

Offset: 0

Jacques Haubrich (jhaubrich(AT)freeler.nl)

Let M(11) be the 11 X 11 matrix (0,0,0,1)/(0,0,1,1)/(0,1,1,1)/(1,1,1,1) and let v(11) be the vector (1,1,1,1,1,1,1,1,1); then v(11)*M(11)^n = (x,y,z,t,u,v, w,m,n,o,a(n)) - Benoit Cloitre, Sep 29 2002

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124.
J. Haubrich, Multinacci Rijen [Multinacci sequences], Euclides (Netherlands), Vol. 74, Issue 4, 1998, pp. 131-133.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
Index entries for linear recurrences with constant coefficients, signature (6,15,-35,-35,56,28,-36,-9,10,1,-1).

See also A006356-A006359, A025030, A030112-A030116.

CoefficientList[Series[-(x - 1) (x^3 - x^2 - 2 x + 1) (x^6 + x^5 - 6 x^4 - 6 x^3 + 8 x^2 + 8 x + 1)/(x^11 -x^10 - 10 x^9 + 9 x^8 + 36 x^7 - 28 x^6 - 56 x^5 + 35 x^4 + 35 x^3 - 15 x^2 - 6 x + 1), {x, 0, 30}], x] (* Vincenzo Librandi, Oct 19 2013 *)

k=11; M(k)=matrix(k,k,i,j,if(1-sign(i+j-k),0,1)); v(k)=vector(k,i,1); a(n)=vecmax(v(k)*M(k)^n)

G.f.: -(x -1)*(x^3 -x^2 -2*x +1)*(x^6 +x^5 -6*x^4 -6*x^3 +8*x^2 +8*x +1)/(x^11 -x^10 -10*x^9 +9*x^8 +36*x^7 -28*x^6 -56*x^5 +35*x^4 +35*x^3 -15*x^2 -6*x +1). [Colin Barker, Nov 09 2012]

More terms from Benoit Cloitre, Sep 29 2002

A180262 Triangle by rows, generated from a triangle with (1,2,1,1,1,...) in every column.

Original entry on oeis.org

1, 2, 1, 1, 2, 3, 1, 1, 6, 6, 1, 1, 3, 12, 14, 1, 1, 3, 6, 28, 31, 1, 1, 3, 6, 14, 62, 70, 1, 1, 3, 6, 14, 31, 140, 157, 1, 1, 3, 6, 14, 31, 70, 314, 353, 1, 1, 3, 6, 14, 31, 70, 157, 706, 793, 1, 1, 3, 6, 14, 31, 70, 157, 353, 1586, 1782

Offset: 0

Gary W. Adamson, Aug 21 2010

Row sums = A006356: (1, 3, 6, 14, 31, 70, 157, 353,...).

Sum of n-th row terms = rightmost term of next row.

			First few rows of the triangle:
  1;
  2, 1;
  1, 2, 3;
  1, 1, 6,  6;
  1, 1, 3, 12, 14;
  1, 1, 3,  6, 28, 31;
  1, 1, 3,  6, 14, 62,  70;
  1, 1, 3,  6, 14, 31, 140, 157;
  1, 1, 3,  6, 14, 31,  70, 314, 353;
  1, 1, 3,  6, 14, 31,  70, 157, 706,  793;
  1, 1, 3,  6, 14, 31,  70, 157, 353, 1586, 1782;
  1, 1, 3,  6, 14, 31,  70, 157, 353,  793, 3564, 4004;
  1, 1, 3,  6, 14, 31,  70, 157, 353,  793, 1782, 8008,  8997;
  1, 1, 3,  6, 14, 31,  70, 157, 353,  793, 1782, 4004, 17994, 20216;
  ...
Example: row 3 of the triangle = (1, 1, 6, 6) = termwise products of (1, 1, 2, 1) and (1, 1, 3, 6).

Cf. A006356.

Let M be an infinite Toeplitz lower triangular matrix with (1,2,1,1,1,..) in every column. A180262 = M * a diagonalized variant of A006356 such that the main diagonal = A006356 prefaced with a 1: (1, 1, 3, 6, 14, 31,...) and the rest zeros.

A030114 Number of distributive lattices; also number of paths with n turns when light is reflected from 10 glass plates.

Original entry on oeis.org

1, 10, 55, 385, 2530, 17017, 113641, 760804, 5089282, 34053437, 227837533, 1524414737, 10199443436, 68241935348, 456589252304, 3054922560820, 20439707165252, 136756870048981, 915005341022187, 6122067418010887, 40961191948244094, 274060890253820561

Offset: 0

Jacques Haubrich (jhaubrich(AT)freeler.nl)

Let M(10) be the 10 X 10 matrix (0,0,0,1)/(0,0,1,1)/(0,1,1,1)/(1,1,1,1) and let v(10) be the vector (1,1,1,1,1,1,1,1,1); then v(10)*M(10)^n = (x,y,z,t,u,v, w,m,a(n)) - Benoit Cloitre, Sep 29 2002

J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124.
J. Haubrich, Multinacci Rijen [Multinacci sequences], Euclides (Netherlands), Vol. 74, Issue 4, 1998, pp. 131-133.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
J. Berman and P. Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, 121 (1976), 103-124. [Annotated scanned copy]
G. Kreweras, Les préordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
Index entries for linear recurrences with constant coefficients, signature (5,15,-20,-35,21,28,-8,-9,1,1).

See also A006356-A006359, A025030, A030112-A030116.

CoefficientList[Series[-(x^9 + x^8 - 8 x^7 - 7 x^6 + 21 x^5 + 15 x^4 - 20 x^3 - 10 x^2 + 5 x + 1)/((x + 1) (x^3 + x^2 - 2 x - 1) (x^6 - x^5 - 6 x^4 + 6 x^3 8 x^2 - 8 x + 1)), {x, 0, 40}], x] (* Vincenzo Librandi, Oct 19 2013 *)

k=10; M(k)=matrix(k,k,i,j,if(1-sign(i+j-k),0,1)); v(k)=vector(k,i,1); a(n)=vecmax(v(k)*M(k)^n)

G.f.: 1/(-x-1/(-x-1/(-x-1/(-x-1/(-x-1/(-x-1/(-x-1/(-x-1/(-x-1/(-x-1)))))))))) = -(x^9 +x^8 -8*x^7 -7*x^6 +21*x^5 +15*x^4 -20*x^3 -10*x^2 +5*x +1)/((x +1)*(x^3 +x^2 -2*x -1)*(x^6 -x^5 -6*x^4 +6*x^3 +8*x^2 -8*x +1)). [Colin Barker, Nov 09 2012]

More terms from Benoit Cloitre, Sep 29 2002

a(20)-a(21) from Vincenzo Librandi, Oct 19 2013

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

Original entry on oeis.org

2, 2, 4, 7, 15, 32, 71, 158, 354, 794, 1783, 4005, 8998, 20217, 45426, 102070, 229348, 515339, 1157955, 2601900, 5846415, 13136774, 29518062, 66326482, 149034251, 334876921, 752461610, 1690765889, 3799116466, 8536537210, 19181424996

Offset: 0

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

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

Cf. A006356.

a:=[2,2,4,7];; for n in [5..40] do a[n]:=3*a[n-1]-a[n-2]-2*a[n-3] +a[n-4]; od; a; # G. C. Greubel, Oct 21 2019

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

spec:= [S,{S=Union(Sequence(Prod(Union(Sequence(Z),Z),Z)),Sequence(Z))}, unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
seq(coeff(series((2-4*x+x^3)/((1-x)*(1-2*x-x^2+x^3)), x, n+1), x, n), n = 0..40); # G. C. Greubel, Oct 21 2019

LinearRecurrence[{3,-1,-2,1}, {2,2,4,7}, 40] (* G. C. Greubel, Oct 21 2019 *)
CoefficientList[Series[(2-4x+x^3)/((1-x)(1-2x-x^2+x^3)),{x,0,50}],x] (* Harvey P. Dale, Jul 30 2024 *)

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

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

G.f.: (2 -4*x +x^3)/((1-x)*(1 -2*x -x^2 +x^3)).
a(n) = 2*a(n-1) + a(n-2) - a(n-3) - 1.
a(n) = A006356(n-1) + 1, n>0.
a(n) = 1 + Sum_{alpha=RootOf(1-2*z-z^2+z^3)} (1/7)*(1 + 2*alpha - alpha^2)*alpha^(-1-n).

More terms from James Sellers, Jun 05 2000

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

Original entry on oeis.org

0, 2, 2, 6, 12, 28, 62, 140, 314, 706, 1586, 3564, 8008, 17994, 40432, 90850, 204138, 458694, 1030676, 2315908, 5203798, 11692828, 26273546, 59036122, 132652962, 298068500, 669753840, 1504923218, 3381531776, 7598232930, 17073074418

Offset: 0

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

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1071
Sergey Kitaev, Jeffrey Remmel, (a,b)-rectangle patterns in permutations and words, arXiv:1304.4286 [math.CO], 2013.
Index entries for linear recurrences with constant coefficients, signature (2,1,-1).

Equals 2 * A006356(n-2), n>1.

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

concat(0, Vec(-2*x*(-1+x)/(x^3-x^2-2*x+1) + O(x^40))) \\ Michel Marcus, Mar 19 2015

G.f.: -2*x*(-1+x)/(x^3-x^2-2*x+1)
Recurrence: {a(0)=0, a(1)=2, a(2)=2, a(n)-a(n+1)-2*a(n+2)+a(n+3)=0}
Sum(2/7*(-_alpha+_alpha^2+1)*_alpha^(-1-n), _alpha=RootOf(_Z^3-_Z^2-2*_Z+1))

More terms from James Sellers, Jun 05 2000

A121469 Triangle read by rows: T(n,k) is the number of directed column-convex polyominoes of area n having k 1-cell columns (0<=k<=n).

Original entry on oeis.org

1, 0, 1, 1, 0, 1, 1, 3, 0, 1, 3, 4, 5, 0, 1, 6, 13, 7, 7, 0, 1, 14, 28, 27, 10, 9, 0, 1, 31, 70, 62, 45, 13, 11, 0, 1, 70, 164, 171, 108, 67, 16, 13, 0, 1, 157, 392, 429, 325, 166, 93, 19, 15, 0, 1, 353, 926, 1101, 862, 540, 236, 123, 22, 17, 0, 1, 793, 2189, 2766, 2355, 1499, 824

Offset: 0

Emeric Deutsch, Aug 03 2006

Also number of nondecreasing Dyck paths of semilength n and such that there are k ascents of length 1. A nondecreasing Dyck path is a Dyck path for which the sequence of the altitudes of the valleys is nondecreasing. Example: T(4,2)=5 because we have (U)D(U)DUUDD, (U)DUUDD(U)D, (U)DUUD(U)DD, UUDD(U)D(U)D and UUD(U)D(U)DD, where U=(1,1) and D=(1,-1); the ascents of length one are shown between parentheses (also the Dyck path UUDUDDUD has two ascents but it is not nondecreasing because the valleys have altitudes 1 and 0). Row sums are the odd-subscripted Fibonacci numbers (A001519). T(n,0)=A006356(n-3). Sum(k*T(n,k),k=0..n)=A094864(n-1).

			T(3,1)=3 because we have the three directed column-convex polyominoes: [(0,2),(0,1)], [(0,2),(1,2)] and [(0,1),(0,2)] (here the j-th pair within the square brackets gives the lower and upper levels of the j-th column of that particular polyomino).
Triangle starts:
  1;
  0,1;
  1,0,1;
  1,3,0,1;
  3,4,5,0,1;
  6,13,7,7,0,1;

E. Barcucci, A. Del Lungo, S. Fezzi and R. Pinzani, Nondecreasing Dyck paths and q-Fibonacci numbers, Discrete Math., 170, 1997, 211-217.
E. Barcucci, R. Pinzani and R. Sprugnoli, Directed column-convex polyominoes by recurrence relations, Lecture Notes in Computer Science, No. 668, Springer, Berlin (1993), pp. 282-298.
Emeric Deutsch and H. Prodinger, A bijection between directed column-convex polyominoes and ordered trees of height at most three, Theoretical Comp. Science, 307, 2003, 319-325.

Cf. A001519 (row sums), A006356, A094864.

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

G.f.: G(t,z) = (1-2*z)/(1-(t+2)*z+(2*t-1)*z^2-(t-1)*z^3).

A190360 Number of one-sided n-step prudent walks, avoiding 4 or more consecutive east steps.

Original entry on oeis.org

1, 3, 7, 17, 40, 96, 229, 547, 1306, 3119, 7448, 17786, 42473, 101426, 242206, 578390, 1381200, 3298317, 7876408, 18808927, 44915872, 107259471, 256136497, 611656057, 1460639684, 3488019553, 8329419319, 19890721694, 47499206650

Offset: 0

Shanzhen Gao, May 09 2011

a(n,k) is the number of one-sided n-step prudent walks, avoiding k or more consecutive east steps; k=4 in this sequence.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Shanzhen Gao and Keh-Hsun Chen, Tackling Sequences From Prudent Self-Avoiding Walks, FCS'14, The 2014 International Conference on Foundations of Computer Science.
S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.
Index entries for linear recurrences with constant coefficients, signature (2, 1, 0, 0, -1).

Cf. A006356 = a(n,2), A033303 = a(n,3).

b:= proc(n, i) option remember; `if`(n<0, 0,
      `if`(n=0, 1, b(n-1,0) +`if`(i<=0, b(n-1,-1), 0)+
      `if`(i>=0 and i<3, b(n-1,i+1), 0)))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..30);  # Alois P. Heinz, Jun 04 2011

(1+t-t^k)/(1-2*t-t^2+t^(k+1)) /. k -> 4 + O[t]^25 // CoefficientList[#, t]& (* Jean-François Alcover, Oct 24 2016 *)

G.f.: (1+t-t^k)/(1-2*t-t^2+t^(k+1)), (k=4 in this sequence).

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

Original entry on oeis.org

1, -1, -1, -3, -6, -14, -31, -70, -157, -353, -793, -1782, -4004, -8997, -20216, -45425, -102069, -229347, -515338, -1157954, -2601899, -5846414, -13136773, -29518061, -66326481, -149034250, -334876920, -752461609, -1690765888, -3799116465, -8536537209

Offset: 0

Philippe Deléham, Nov 11 2011

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

Cf. A006356, A077998, A180262.

RecurrenceTable[{a[1]==-1, a[2]== -1, a[3]== -3, a[n]== 2*a[n-1]  + a[n-2] - a[n-3]}, a, {n,30}] (* G. C. Greubel, Aug 13 2015 *)
CoefficientList[Series[(1-3x+x^3)/(1-2x-x^2+x^3),{x,0,30}],x] (* or *) LinearRecurrence[{2,1,-1},{1,-1,-1,-3},40] (* Harvey P. Dale, May 31 2021 *)

Vec((1-3*x+x^3)/(1-2*x-x^2+x^3) + O(x^40)) \\ Michel Marcus, Aug 13 2015

a(n) = 2*a(n-1) + a(n-2) - a(n-3) with a(0)=1, a(1)=-1, a(2)=-1, a(3)=-3.

a(n+1) = - A077998(n). - G. C. Greubel, Aug 14 2015

cp's OEIS Frontend

A306334 a(n) is the number of different linear hydrocarbon molecules with n carbon atoms.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

A030113 Number of distributive lattices; also number of paths with n turns when light is reflected from 9 glass plates.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A030115 Number of distributive lattices; also number of paths with n turns when light is reflected from 11 glass plates.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A180262 Triangle by rows, generated from a triangle with (1,2,1,1,1,...) in every column.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A030114 Number of distributive lattices; also number of paths with n turns when light is reflected from 10 glass plates.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

Extensions

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

Views

Author

Keywords

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

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