A001998 -id:A001998 - cp's OEIS frontend

A001997 Number of different shapes formed by bending a piece of wire of length n in the plane.

1, 1, 2, 4, 10, 24, 66, 176, 493, 1362, 3821, 10660, 29864, 83329, 232702, 648182, 1804901, 5015725, 13931755, 38635673, 107090666, 296449133, 820271143, 2267225157, 6264244414, 17291930470

Offset: 0

N. J. A. Sloane

The wire is marked into n equal segments by n-1 marks, is bent at right angles at each of one or more of these points, making each segment parallel to one of two rectangular axes. (Stays in plane, bends are of 0 or +-90 degs.) May cross itself but is not self-coincident over a finite length.
A trail is a path which may cross itself but does not reuse an edge. This sequence counts undirected trails on the square lattice up to rotation and reflection. Directed trails are counted by A006817.
Much less is known about the three-dimensional problem.

			._. ._._._. Here are the
|_. . ._. . 4 solutions
._._| . |_. when n=3 (described by 00, RR, 0L, RL).
The 24 solutions for n=5 are 0000, 000R, 00R0, 00RR, 00RL, L00L, L00R, 0R0R, 0R0L, 0RR0, 0RL0, 0LRL, 0LRR, 0LLR, 0LLL, R0LR, R0LL, R0RL, R0RR, LRLR, LRLL, LRLR, LRRR, LLRR.

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

R. M. Foster, Solution to Problem E185, Amer. Math. Monthly, 44 (1937), 50-51.
R. M. Foster, Solution to Problem E185, Amer. Math. Monthly, 44 (1937), 50-51. [Annotated scanned copy]
Jessica Gonzalez, Illustration of a(4)=10
Eric Weisstein's World of Mathematics, Self-avoiding walk.
Index entries for sequences obtained by enumerating foldings

The total number of different shapes (including those shapes where the wire is self-coincident over a finite path) is given by A001998.

Cf. A006817.

More terms from David W. Wilson, Jul 18 2001

A182522 a(0) = 1; thereafter a(2n + 1) = 3^n, a(2n + 2) = 2 * 3^n.

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 18, 27, 54, 81, 162, 243, 486, 729, 1458, 2187, 4374, 6561, 13122, 19683, 39366, 59049, 118098, 177147, 354294, 531441, 1062882, 1594323, 3188646, 4782969, 9565938, 14348907, 28697814, 43046721, 86093442, 129140163, 258280326, 387420489

Offset: 0

Michael Somos, May 03 2012

Row sums of triangle in A123149. - Philippe Deléham, May 04 2012
This is simply the classic sequence A038754 prefixed by a 1. - N. J. A. Sloane, Nov 23 2017
Binomial transform is A057960.
Range of row n of the circular Pascal array of order 6. - Shaun V. Ault, May 30 2014
a(n) is also the number of achiral color patterns in a row or cycle of length n using three or fewer colors. Two color patterns are the same if we permute the colors, so ABCAB=BACBA. For a cycle, we can rotate the colors, so ABCAB=CABAB. A row is achiral if it is the same as some color permutation of its reverse. Thus the reversal of ABCAB is BACBA, which is equivalent to ABCAB when we permute A and B. A cycle is achiral if it is the same as some rotation of some color permutation of its reverse. Thus CABAB reversed is BABAC. We can permute A and B to get ABABC and then rotate to get CABAB, so CABAB is achiral. It is interesting that the number of achiral color patterns is the same for rows and cycles. - Robert A. Russell, Mar 10 2018
Also, the number of walks of length n on the graph 0--1--2--3--4 starting at vertex 0. - Sean A. Irvine, Jun 03 2025

			G.f. = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 9*x^5 + 18*x^6 + 27*x^7 + 54*x^8 + ...
From _Robert A. Russell_, Mar 10 2018: (Start)
For a(4) = 6, the achiral color patterns for rows are AAAA, AABB, ABAB, ABBA, ABBC, and ABCA.  Note that for cycles AABB=ABBA and ABBC=ABCA.  The achiral patterns for cycles are AAAA, AAAB, AABB, ABAB, ABAC, and ABBC.  Note that AAAB and ABAC are not achiral rows.
For a(5) = 9, the achiral color patterns (for both rows and cycles) are AAAAA, AABAA, ABABA, ABBBA, AABCC, ABACA, ABBBC, ABCAB, and ABCBA. (End)

G. C. Greubel, Table of n, a(n) for n = 0..1000
Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, arXiv:1407.2197 [math.CO], 2014.
Shaun V. Ault and Charles Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics, Volume 332, October 2014, Pages 45-54.
Daniel Birmajer, Juan B. Gil, Jordan O. Tirrell, and Michael D. Weiner, Pattern-avoiding stabilized-interval-free permutations, arXiv:2306.03155 [math.CO], 2023.
Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015-2016.
Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.
Sean A. Irvine, Walks on Graphs.
Index entries for linear recurrences with constant coefficients, signature (0,3).

Cf. A038754 (essentially the same sequence).
Cf. A008277, A052551, A057427, A057960.
Cf. A123149, A140735, A293181, A304973.
Also row sums of triangle in A169623.
Column 3 of A305749.
Cf. A124302 (oriented), A001998 (unoriented), A107767 (chiral), for rows, varying offsets.
Cf. A002076 (oriented), A056353 (unoriented), A320743 (chiral), for cycles.

I:=[1,1,2]; [n le 3 select I[n] else 3*Self(n-2): n in [1..40]]; // Bruno Berselli, Mar 19 2013

Join[{1}, RecurrenceTable[{a[1]==1, a[2]==2, a[n]==3 a[n-2]}, a, {n, 40}]] (* Bruno Berselli, Mar 19 2013 *)
CoefficientList[Series[(1+x-x^2)/(1-3*x^2), {x,0,50}], x] (* G. C. Greubel, Apr 14 2017 *)
Table[If[EvenQ[n], StirlingS2[(n+6)/2,3] - 4 StirlingS2[(n+4)/2,3] + 5 StirlingS2[(n+2)/2,3] - 2 StirlingS2[n/2,3], StirlingS2[(n+5)/2,3] - 3 StirlingS2[(n+3)/2,3] + 2 StirlingS2[(n+1)/2,3]], {n,0,40}] (* Robert A. Russell, Oct 21 2018 *)
Join[{1},Table[If[EvenQ[n], 2 3^((n-2)/2), 3^((n-1)/2)],{n,40}]] (* Robert A. Russell, Oct 28 2018 *)

makelist(if n=0 then 1 else (1+mod(n-1,2))*3^floor((n-1)/2), n, 0, 40); /* Bruno Berselli, Mar 19 2013 */

{a(n) = if( n<1, n==0, n--; (n%2 + 1) * 3^(n \ 2))}

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

def A182522(n): return (3 -(3-2*sqrt(3))*((n+1)%2))*3^((n-3)/2) + int(n==0)/3
[A182522(n) for n in range(41)] # G. C. Greubel, Jul 17 2023

G.f.: (1 + x - x^2) / (1 - 3*x^2).
Expansion of 1 / (1 - x / (1 - x / (1 + x / (1 + x)))) in powers of x.
a(n+1) = A038754(n).
a(n) = Sum_{k=0..n} A123149(n,k). - Philippe Deléham, May 04 2012
a(n) = (3-(1+(-1)^n)*(3-2*sqrt(3))/2)*sqrt(3)^(n-3) for n>0, a(0)=1. - Bruno Berselli, Mar 19 2013
a(0) = 1, a(1) = 1, a(n) = a(n-1) + a(n-2) if n is odd, and a(n) = a(n-1) + a(n-2) + a(n-3) if n is even. - Jon Perry, Mar 19 2013
For odd n = 2m-1, a(2m-1) = T(m,1)+T(m,2)+T(m,3) for triangle T(m,k) of A140735; for even n = 2m, a(2m) = T(m,1)+T(m,2)+T(m,3) for triangle T(m,k) of A293181. - Robert A. Russell, Mar 10 2018
From Robert A. Russell, Oct 21 2018: (Start)
a(2m) = S2(m+3,3) - 4*S2(m+2,3) + 5*S2(m+1,3) - 2*S2(m,3).
a(2m-1) = S2(m+2,3) - 3*S2(m+1,3) + 2*S2(m,3), where S2(n,k) is the Stirling subset number A008277.
a(n) = 2*A001998(n-1) - A124302(n) = A124302(n) - 2*A107767(n-1) = A001998(n-1) - A107767(n-1).
a(n) = 2*A056353(n) - A002076(n) = A002076(n) - 2*A320743(n) = A056353(n) - A320743(n).
a(n) = A057427(n) + A052551(n-2) + A304973(n). (End)

Edited by Bruno Berselli, Mar 19 2013

Definition simplified by N. J. A. Sloane, Nov 23 2017

A320750 Array read by antidiagonals: T(n,k) is the number of color patterns (set partitions) in an unoriented row of length n using k or fewer colors (subsets).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 4, 6, 1, 1, 2, 4, 10, 10, 1, 1, 2, 4, 11, 25, 20, 1, 1, 2, 4, 11, 31, 70, 36, 1, 1, 2, 4, 11, 32, 107, 196, 72, 1, 1, 2, 4, 11, 32, 116, 379, 574, 136, 1, 1, 2, 4, 11, 32, 117, 455, 1451, 1681, 272, 1

Offset: 1

Robert A. Russell, Oct 27 2018

Two color patterns are equivalent if the colors are permuted.
In an unoriented row, chiral pairs are counted as one.
T(n,k) = Pi_k(P_n) which is the number of non-equivalent partitions of the path on n vertices, with at most k parts. Two partitions P1 and P2 of a graph G are said to be equivalent if there is a nontrivial automorphism of G which maps P1 onto P2. - Mohammad Hadi Shekarriz, Aug 21 2019
From Allan Bickle, Apr 05 2022: (Start)
The columns count unlabeled k-paths with n+k+2 vertices. (A k-path with order n at least k+2 is a k-tree with exactly two k-leaves (vertices of degree k). It can be constructed from a clique with k+1 vertices by iteratively adding a new degree k vertex adjacent to an existing clique containing an existing k-leaf.)
Recurrences for the columns appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)

			Array begins with T(1,1):
  1   1     1     1      1      1      1      1      1      1      1 ...
  1   2     2     2      2      2      2      2      2      2      2 ...
  1   3     4     4      4      4      4      4      4      4      4 ...
  1   6    10    11     11     11     11     11     11     11     11 ...
  1  10    25    31     32     32     32     32     32     32     32 ...
  1  20    70   107    116    117    117    117    117    117    117 ...
  1  36   196   379    455    467    468    468    468    468    468 ...
  1  72   574  1451   1993   2135   2151   2152   2152   2152   2152 ...
  1 136  1681  5611   9134  10480  10722  10742  10743  10743  10743 ...
  1 272  5002 22187  43580  55091  58071  58461  58486  58487  58487 ...
  1 528 14884 87979 211659 301633 333774 339764 340359 340389 340390 ...
For T(4,3)=10, the patterns are AAAA, AABB, ABAB, ABBA, ABBC, ABCA, AAAB, AABA, AABC, ABAC, the last four being chiral with partners ABBB, ABAA, ABCC, and ABCB.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2.]

B. Ahmadi, F. Alinaghipour and M. H. Shekarriz, Number of Distinguishing Colorings and Partitions, arXiv:1910.12102 [math.CO], 2019.
Allan Bickle, How to Count k-Paths, J. Integer Sequences, 25 (2022) Article 22.5.6.
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
J. Eckhoff, Extremal interval graphs, J. Graph Theory 17 1 (1993), 117-127.
L. Markenzon, O. Vernet, and P. R. da Costa Pereira, A clique-difference encoding scheme for labelled k-path graphs, Discrete Appl. Math. 156 (2008), 3216-3222.

Columns 1-7 are A000012, A005418, A001998(n-1), A056323, A056324, A056325, A345207.
As k increases, columns converge to A103293(n+1).
Cf. transpose of A278984 (oriented), A320751 (chiral), A305749 (achiral).
Partial column sums of A284949.

Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2,k] + Ach[n-2,k-1] + Ach[n-2,k-2]] (* A304972 *)
Table[Sum[StirlingS2[n,j] + Ach[n,j], {j,k-n+1}]/2, {k,15}, {n,k}] // Flatten

T(n,k) = Sum_{j=1..k} (S2(n,j) + Ach(n,j))/2, where S2 is the Stirling subset number A008277 and Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k) + Ach(n-2,k-1) + Ach(n-2,k-2)).
T(n,k) = (A278984(k,n) + A305749(n,k)) / 2 = A278984(k,n) - A320751(n,k) = A320751(n,k) + A305749(n,k).
T(n,k) = Sum_{j=1..k} A284949(n,j).

A056327 Number of reversible string structures with n beads using exactly three different colors.

Original entry on oeis.org

0, 0, 1, 4, 15, 50, 160, 502, 1545, 4730, 14356, 43474, 131145, 395150, 1188580, 3572902, 10732065, 32225810, 96733636, 290322394, 871200825, 2614097750, 7843255300, 23531775502, 70599259185, 211805902490

Offset: 1

Marks R. Nester

A string and its reverse are considered to be equivalent. Permuting the colors will not change the structure.

Number of set partitions for an unoriented row of n elements using exactly three different elements. An unoriented row is equivalent to its reverse. - Robert A. Russell, Oct 14 2018

			For a(4)=4, the color patterns are ABCA, ABBC, AABC, and ABAC. The first two are achiral. - _Robert A. Russell_, Oct 14 2018

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (6,-6,-24,49,6,-66,36).

Column 3 of A284949.
Cf. A056310.
Cf. A000392 (oriented), A320526 (chiral), A304973 (achiral).

I:=[0,0,1,4,15,50,160]; [n le 7 select I[n] else 6*Self(n-1) -6*Self(n-2) -24*Self(n-3) +49*Self(n-4) +6*Self(n-5) -66*Self(n-6) +36*Self(n-7): n in [1..40]]; // G. C. Greubel, Oct 16 2018

k=3; Table[(StirlingS2[n,k] + If[EvenQ[n], 2StirlingS2[n/2+1,3] - 2StirlingS2[n/2,3], StirlingS2[(n+3)/2,3] - StirlingS2[(n+1)/2,3]])/2, {n,30}] (* Robert A. Russell, Oct 15 2018 *)
Ach[n_, k_] := Ach[n, k] = If[n < 2, Boole[n == k && n >= 0], k Ach[n-2, k] + Ach[n-2, k-1] + Ach[n-2, k-2]]
k=3; Table[(StirlingS2[n, k] + Ach[n, k])/2, {n,30}] (* Robert A. Russell, Oct 15 2018 *)
LinearRecurrence[{6, -6, -24, 49, 6, -66, 36}, {0, 0, 1, 4, 15, 50, 160}, 30] (* Robert A. Russell, Oct 15 2018 *)

m=40; v=concat([0,0,1,4,15,50,160], vector(m-7)); for(n=8, m, v[n] = 6*v[n-1] -6*v[n-2] -24*v[n-3] +49*v[n-4] +6*v[n-5] -66*v[n-6] +36*v[n-7] ); v \\ G. C. Greubel, Oct 16 2018

a(n) = A001998(n-1) - A005418(n).
G.f.: x^3*(3*x^4 - 8*x^3 + 3*x^2 + 2*x - 1)/((x-1)*(2*x-1)*(3*x-1)*(2*x^2-1)*(3*x^2-1)). - Colin Barker, Sep 23 2012
From Robert A. Russell, Oct 14 2018: (Start)
a(n) = (S2(n,k) + A(n,k))/2, where k=3 is the number of colors (sets), S2 is the Stirling subset number A008277 and A(n,k) = [n>1] * (k*A(n-2,k) + A(n-2,k-1) + A(n-2,k-2)) + [n<2 & n==k & n>=0].
a(n) = (A000392(n) + A304973(n)) / 2 = A000392(n) - A320526(n) = A320526(n) + A304973(n). (End)

A005963 Number of restricted hexagonal polyominoes with n cells.

Original entry on oeis.org

0, 0, 1, 2, 10, 45, 210, 1002, 4883, 23797, 116518, 571471

Offset: 1

N. J. A. Sloane

nonn

A. T. Balaban, Enumeration of Cyclic Graphs, pp. 63-105 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976; see p. 75.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Equals A000228 - A002216.

Cf. A036359, A002216, A005963, A000228, A001998.

A036359 Number of branched catafusenes with n condensed hexagons.

Original entry on oeis.org

0, 0, 0, 1, 2, 12, 53, 250, 1115, 5012, 22032, 96746, 422732, 1848128, 8088090, 35498533, 156328706, 691192578, 3068780449, 13683070474, 61267204610, 275455737555, 1243320744572, 5633022679582, 25611815936218, 116840427373176, 534705818846660, 2454282243059471

Offset: 1

N. J. A. Sloane

nonn

F. Harary and R. C. Read, The Enumeration of Tree-like Polyhexes, Proc. Edinburgh Math. Soc., Series II, 17 (1970), pp. 1-13.
Alexandru T. Balaban, The Enumeration of Cyclic Graphs, pp. 63-105 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976; see p. 75.

Cf. A036359, A002216, A005963, A000228, A001998.

a(n) = A002216(n) - A001998(n-2) with A001998(-1)=1. - Sean A. Irvine, Oct 26 2020

More terms from Sean A. Irvine, Oct 26 2020

A001444 Bending a piece of wire of length n+1 (configurations that can only be brought into coincidence by turning the figure over are counted as different).

Original entry on oeis.org

1, 2, 6, 15, 45, 126, 378, 1107, 3321, 9882, 29646, 88695, 266085, 797526, 2392578, 7175547, 21526641, 64573362, 193720086, 581140575, 1743421725, 5230206126, 15690618378, 47071677987, 141215033961, 423644570442, 1270933711326, 3812799539655, 11438398618965

Offset: 0

Todd Simpson

The wire stays in the plane, there are n bends, each is R,L or O.

			There are 2 ways to bend a piece of wire of length 2 (bend it or not).
G.f. = 1 + 2*x + 6*x^2 + 15*x^3 + 45*x^4 + 126*x^5 + 378*x^6 + ...

Todd Andrew Simpson, "Combinatorial Proofs and Generalizations of Weyl's Denominator Formula", Ph. D. Dissertation, Penn State University, 1994.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for sequences obtained by enumerating foldings
Index entries for linear recurrences with constant coefficients, signature (3,3,-9).

Cf. A001997, A001998.

Cf. A000244.

a001444 n = div (3 ^ n + 3 ^ (div n 2)) 2
-- Reinhard Zumkeller, Jun 30 2013

Maple
```
f := n->(3^floor(n/2)+3^n)/2;
```

CoefficientList[Series[(1-x-3*x^2)/((1-3*x)*(1-3*x^2)),{x,0,30}],x] (* Vincenzo Librandi, Apr 15 2012 *)
LinearRecurrence[{3,3,-9},{1,2,6},40] (* Harvey P. Dale, Dec 30 2012 *)

a(n) = (3^n + 3^floor(n/2))/2.
G.f.: G(0) where G(k) = 1 + x*(3*3^k + 1)*(1 + 3*x*G(k+1))/(1 + 3^k). - Sergei N. Gladkovskii, Dec 13 2011 [Edited by Michael Somos, Sep 09 2013]
E.g.f. E(x) = (exp(3*x)+cosh(x*sqrt(3))+sinh(x*sqrt(3))/sqrt(3))/2 = G(0); G(k) = 1 + x*(3*3^k+1)/((2*k+1)*(1+3^k) - 3*x*(2*k+1)*(1+3^k)/(3*x + (2*k+2)/G(k+1))); (continued fraction). - Sergei N. Gladkovskii, Dec 13 2011
From Colin Barker, Apr 02 2012: (Start)
a(n) = 3*a(n-1) + 3*a(n-2) - 9*a(n-3).
G.f.: x*(1-x-3*x^2)/((1-3*x)*(1-3*x^2)). (End)

Interpretation in terms of bending wire from Colin Mallows.

A056328 Number of reversible string structures with n beads using exactly four different colors.

Original entry on oeis.org

0, 0, 0, 1, 6, 37, 183, 877, 3930, 17185, 73095, 306361, 1267266, 5198557, 21182343, 85910917, 347187210, 1399451545, 5629911015, 22616256721, 90754855026, 363890126677, 1458172596903, 5840531635357, 23385650196090

Offset: 1

Marks R. Nester

nonn

A string and its reverse are considered to be equivalent. Permuting the colors will not change the structure.

Number of set partitions for an unoriented row of n elements using exactly four different elements. An unoriented row is equivalent to its reverse. - Robert A. Russell, Oct 14 2018

			For a(5)=6, the color patterns are ABCDA, ABCBD, AABCD, ABACD, ABCAD, and ABBCD. The first two are achiral. - _Robert A. Russell_, Oct 14 2018

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]

Index entries for linear recurrences with constant coefficients, signature (8, -12, -44, 121, 12, -228, 144).

Column 4 of A284949.
Cf. A056311.
Cf. A000453 (oriented), A320527 (chiral), A304974 (achiral).

k=4; Table[(StirlingS2[n,k] + If[EvenQ[n], StirlingS2[n/2+2,4] - StirlingS2[n/2+1,4] - 2StirlingS2[n/2,4], 2StirlingS2[(n+3)/2,4] - 4StirlingS2[(n+1)/2,4]])/2, {n,30}] (* Robert A. Russell, Oct 14 2018 *)
Ach[n_, k_] := Ach[n, k] = If[n < 2, Boole[n == k && n >= 0], k Ach[n-2, k] + Ach[n-2, k-1] + Ach[n-2, k-2]]
k = 4; Table[(StirlingS2[n, k] + Ach[n, k])/2, {n, 1, 30}] (* Robert A. Russell, Oct 14 2018 *)
LinearRecurrence[{8, -12, -44, 121, 12, -228, 144}, {0, 0, 0, 1, 6, 37, 183}, 30] (* Robert A. Russell, Oct 14 2018 *)

a(n) = A056323(n) - A001998(n-1).
Empirical g.f.: -x^4*(3*x^3 + x^2 - 2*x + 1) / ((x-1)*(2*x-1)*(2*x+1)*(3*x-1)*(4*x-1)*(3*x^2-1)). - Colin Barker, Nov 25 2012
From Robert A. Russell, Oct 14 2018: (Start)
a(n) = (S2(n,k) + A(n,k))/2, where k=4 is the number of colors (sets), S2 is the Stirling subset number A008277 and A(n,k) = [n>1] * (k*A(n-2,k) + A(n-2,k-1) + A(n-2,k-2)) + [n<2 & n==k & n>=0].
a(n) = (A000453(n) + A304974(n)) / 2 = A000453(n) - A320527(n) = A320527(n) + A304974(n). (End)

A345207 Number of (unlabeled) 7-paths with n vertices.

Original entry on oeis.org

1, 1, 2, 4, 11, 32, 117, 468, 2151, 10722, 58071, 333774, 2018321, 12678506, 82035085, 542520052, 3646124339, 24791545874, 169986552195, 1172526610674, 8122332718341, 56435590886610, 392969320828713, 2740480494041976, 19132214719583207, 133671249471111626

Offset: 9

Allan Bickle, Jun 10 2021

A k-path with order n at least k+2 is a k-tree with exactly two k-leaves (vertices of degree k). It can be constructed from a clique with k+1 vertices by iteratively adding a new degree k vertex adjacent to an existing clique containing an existing k-leaf.
Also, the number of equivalence classes of strings of length n-9 using a maximum of seven different numbers that are equivalent when they can be made the same by permutation of their numbers and possible reversal of the string.
Recurrences appear in the papers by Bickle, Eckhoff, and Markenzon et al.

M. R. Nester (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2.]

Allan Bickle, How to Count k-Paths, J. Integer Sequences, 25 (2022) Article 22.5.6.
Allan Bickle, A Survey of Maximal k-degenerate Graphs and k-Trees, Theory and Applications of Graphs 0 1 (2024) Article 5.
J. Eckhoff, Extremal interval graphs, J. Graph Theory 17 1 (1993), 117-127.
L. Markenzon, O. Vernet, and P. R. da Costa Pereira, A clique-difference encoding scheme for labelled k-path graphs, Discrete Appl. Math. 156 (2008), 3216-3222.
Index entries for linear recurrences with constant coefficients, signature (20,-134,200,1502,-6120,-200,35440,-41269,-66380,141454,840,-135912,70560).

Column 7 of A320750.
The numbers of unlabeled k-paths for k = 2..6 are given in A005418, A001998, A056323, A056324, and A056325, respectively.
The sequences above converge to A103293(n+1).

LinearRecurrence[{20,-134,200,1502,-6120,-200,35440,-41269,-66380,141454,840,-135912,70560},{1,1,2,4,11,32,117,468,2151,10722,58071,333774,2018321,12678506},26] (* Stefano Spezia, Aug 01 2021 *)

a(n) = (7^(n-9) + 21*5^(n-9) + 70*4^(n-9) + 315*3^(n-9) + 924*2^(n-9) + 232*7^((n-9)/2) + 700*4^((n-9)/2) + 840*3^((n-9)/2) + 1008*2^((n-9)/2) + 2975)/10080 for n>9 odd;
a(n) = (7^(n-9) + 21*5^(n-9) + 70*4^(n-9) + 315*3^(n-9) + 924*2^(n-9) + 76*7^((n-8)/2) + 280*4^((n-8)/2) + 420*3^((n-8)/2) + 504*2^((n-8)/2) + 2975)/10080 for n even.
a(n) = 20*a(n-1) - 134*a(n-2) + 200*a(n-3) + 1502*a(n-4) - 6120*a(n-5) - 200*a(n-6) + 35440*a(n-7) - 41269*a(n-8) - 66380*a(n-9) + 141454*a(n-10) + 840*a(n-11) - 135912*a(n-12) + 70560*a(n-13) for n > 22. - Stefano Spezia, Aug 01 2021

Title changed by Allan Bickle, Apr 05 2022

A107767 a(n) = (1 + 3^n - 23^(n/2))/4 if n is even, (1 + 3^n - 43^((n-1)/2))/4 if n odd.

Original entry on oeis.org

0, 1, 4, 16, 52, 169, 520, 1600, 4840, 14641, 44044, 132496, 397852, 1194649, 3585040, 10758400, 32278480, 96845281, 290545684, 871666576, 2615029252, 7845176329, 23535617560, 70607118400, 211821620920, 635465659921

Offset: 1

Emeric Deutsch, Jun 12 2005

a(n-1) is the number of chiral pairs of color patterns (set partitions) for a row of length n using up to 3 colors (subsets). For n=4, a(n-1)=4, the chiral pairs are AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB. - Robert A. Russell, Oct 28 2018

Balaban, A. T., Brunvoll, J., Cyvin, B. N., & Cyvin, S. J. (1988). Enumeration of branched catacondensed benzenoid hydrocarbons and their numbers of Kekulé structures. Tetrahedron, 44(1), 221-228. See Eq. 5.

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
Gy. Tasi and F. Mizukami, Quantum algebraic-combinatoric study of the conformational properties of n-alkanes, J. Math. Chemistry, 25, 1999, 55-64 (see p. 60).
Index entries for linear recurrences with constant coefficients, signature (4,0,-12,9).

Cf. A167993 (first differences).
Column 3 of A320751, offset by 1.
Cf. A124302 (oriented), A001998 (unoriented), A182522 (achiral), varying offsets.

a:=[];; for n in [1..30] do if n mod 2 <> 0 then Add(a,(1+3^n-4*3^((n-1)/2))/4); else Add(a,(1+3^n-2*3^(n/2))/4); fi; od; a; # Muniru A Asiru, Oct 30 2018

I:=[0, 1, 4, 16]; [n le 4 select I[n] else 4*Self(n-1)-12*Self(n-3)+9*Self(n-4): n in [1..30]]; // Vincenzo Librandi, Jun 26 2012

a:=proc(n) if n mod 2 = 0 then (1+3^n-2*3^(n/2))/4 else (1+3^n-4*3^((n-1)/2))/4 fi end: seq(a(n),n=1..32);

CoefficientList[Series[-x/((x-1)*(3*x-1)*(3*x^2-1)),{x,0,40}],x] (* or *) LinearRecurrence[{4,0,-12,9},{0,1,4,16},50] (* Vincenzo Librandi, Jun 26 2012 *)
Ach[n_, k_] := Ach[n, k] = If[n<2, Boole[n==k && n>=0], k Ach[n-2,k] + Ach[n-2,k-1] + Ach[n-2,k-2]] (* A304972 *)
k=3; Table[Sum[StirlingS2[n,j]-Ach[n,j],{j,k}]/2,{n,2,40}] (* Robert A. Russell, Oct 28 2018 *)
CoefficientList[Series[(1/12 E^(-Sqrt[3] x) (-3 + 2 Sqrt[3] - (3 + 2 Sqrt[3]) E^(2 Sqrt[3] x) + 3 E^((3 + Sqrt[3]) x) + 3 E^(x + Sqrt[3] x)))/x, {x, 0, 20}], x]*Table[(k+1)!, {k, 0, 20}] (* Stefano Spezia, Oct 29 2018 *)

x='x+O('x^50); concat(0, Vec(x^2/((1-x)*(3*x-1)*(3*x^2-1)))) \\ Altug Alkan, Sep 23 2018

G.f.: -x^2 / ( (x-1)*(3*x-1)*(3*x^2-1) ). - R. J. Mathar, Dec 16 2010
a(n) = 4*a(n-1) - 12*a(n-3) + 9*a(n-4). - Vincenzo Librandi, Jun 26 2012
From Robert A. Russell, Oct 28 2018: (Start)
a(n-1) = Sum_{j=0..k} (S2(n,j) - Ach(n,j)) / 2, where k=3 is the maximum number of colors, S2 is the Stirling subset number A008277, and Ach(n,k) = [n>=0 & n<2 & n==k] + [n>1]*(k*Ach(n-2,k) + Ach(n-2,k-1) + Ach(n-2,k-2)).
a(n-1) = (A124302(n) - A182522(n))/2.
a(n-1) = A124302(n) - A001998(n-1).
a(n-1) = A001998(n-1) - A182522(n).
a(n-1) = A122746(n-2) + A320526(n). (End)
E.g.f.: (1/12)*exp(-sqrt(3)*x)*(-3 + 2*sqrt(3) - (3 + 2*sqrt(3))*exp(2*sqrt(3)*x) + 3*exp((3 + sqrt(3))*x) + 3*exp(x + sqrt(3)*x)). - Stefano Spezia, Oct 29 2018
From Bruno Berselli, Oct 31 2018: (Start)
a(n) = (1 + 3^n - 3^((n-1)/2)*(4 + (-2 + sqrt(3))*(1 + (-1)^n)))/4. Therefore:
a(2*k)   = (3^k - 1)^2/4;
a(2*k+1) = (3^k - 1)*(3^(k+1) - 1)/4. (End)

Entry revised by N. J. A. Sloane, Jul 29 2011

cp's OEIS Frontend

A001997 Number of different shapes formed by bending a piece of wire of length n in the plane.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Extensions

A182522 a(0) = 1; thereafter a(2*n + 1) = 3^n, a(2*n + 2) = 2 * 3^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

PARI

SageMath

Formula

Extensions

A320750 Array read by antidiagonals: T(n,k) is the number of color patterns (set partitions) in an unoriented row of length n using k or fewer colors (subsets).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A056327 Number of reversible string structures with n beads using exactly three different colors.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A005963 Number of restricted hexagonal polyominoes with n cells.

Views

Author

Keywords

References

Crossrefs

A036359 Number of branched catafusenes with n condensed hexagons.

Views

Author

Keywords

References

Crossrefs

Formula

Extensions

A001444 Bending a piece of wire of length n+1 (configurations that can only be brought into coincidence by turning the figure over are counted as different).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

A182522 a(0) = 1; thereafter a(2n + 1) = 3^n, a(2n + 2) = 2 * 3^n.

A107767 a(n) = (1 + 3^n - 23^(n/2))/4 if n is even, (1 + 3^n - 43^((n-1)/2))/4 if n odd.