A182522 -id:A182522 - cp's OEIS frontend

A001998 Bending a piece of wire of length n+1; walks of length n+1 on a tetrahedron; also non-branched catafusenes with n+2 condensed hexagons.

1, 2, 4, 10, 25, 70, 196, 574, 1681, 5002, 14884, 44530, 133225, 399310, 1196836, 3589414, 10764961, 32291602, 96864964, 290585050, 871725625, 2615147350, 7845353476, 23535971854, 70607649841, 211822683802, 635467254244, 1906400965570, 5719200505225, 17157599124190

Offset: 0

N. J. A. Sloane

The wire stays in the plane, there are n bends, each is R,L or O; turning the wire over does not count as a new figure.
Equivalently, walks of n+1 steps on a tetrahedron, visiting n+2 vertices, with n "corners"; the symmetry group is S4, reversing a walk does not count as different. Simply interpret R,L,O as instructions to turn R, turn L, or retrace the last step. Walks are not self-avoiding.
Also, it appears that a(n) gives the number of equivalence classes of n-tuples of 0, 1 and 2, where two n-tuples are equivalent if one can be obtained from the other by a sequence of operations R and C, where R denotes reversal and C denotes taking the 2's complement (C(x)=2-x). This has been verified up to a(19)=290585050. Example: for n=3 there are ten equivalence classes {000, 222}, {001, 100, 122, 221}, {002, 022, 200, 220}, {010, 212}, {011, 110, 112, 211}, {012, 210}, {020, 202}, {021, 102, 120, 201}, {101, 121}, {111}, so a(3)=10. - John W. Layman, Oct 13 2009
There exists a bijection between chains of n+2 hexagons and the above described equivalence classes of n-tuples of 0,1, and 2. Namely, for a given chain of n+2 hexagons we take the sequence of the numbers of vertices of degree 2 (0, 1, or 2) between the consecutive contact vertices on one side of the chain; switching to the other side we obtain the 2's complement of this sequence; reversing the order of the hexagons, we obtain the reverse sequence. The inverse mapping is straightforward. For example, to a linear chain of 7 hexagons there corresponds the 5-tuple 11111. - Emeric Deutsch, Apr 22 2013
If we treat two wire bends (or walks, or tuples) related by turning over (or reversing) as different in any of the above-given interpretations of this sequence, we get A007051 (or A124302). Also, a(n-1) is the sum of first 3 terms in n-th row of A284949, see crossrefs therein. - Andrey Zabolotskiy, Sep 29 2017
a(n-1) is the number of color patterns (set partitions) in an unoriented row of length n using 3 or fewer colors (subsets). - Robert A. Russell, Oct 28 2018
From Allan Bickle, Jun 02 2022: (Start)
a(n) is the number of (unlabeled) 3-paths with n+6 vertices. (A 3-path with order n at least 5 can be constructed from a 4-clique by iteratively adding a new 3-leaf (vertex of degree 3) adjacent to an existing 3-clique containing an existing 3-leaf.)
Recurrences appear in the papers by Bickle, Eckhoff, and Markenzon et al. (End)
a(n) is also the number of distinct planar embeddings of the (n+1)-alkane graph (up to at least n=9, and likely for all n). - Eric W. Weisstein, May 21 2024

			There are 2 ways to bend a piece of wire of length 2 (bend it or not).
For n=4 and a(n-1)=10, the 6 achiral patterns are AAAA, AABB, ABAB, ABBA, ABCA, and ABBC.  The 4 chiral pairs are AAAB-ABBB, AABA-ABAA, AABC-ABCC, and ABAC-ABCB. - _Robert A. Russell_, Oct 28 2018

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.
S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, Enumeration of tree-like octagonal systems: catapolyoctagons, ACH Models in Chem. 134 (1997), 55-70.
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.]
R. C. Read, The Enumeration of Acyclic Chemical Compounds, pp. 25-61 of A. T. Balaban, ed., Chemical Applications of Graph Theory, Ac. Press, 1976. [I think this reference does not mention this sequence. - N. J. A. Sloane, Aug 10 2006]
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).

Indranil Ghosh, Table of n, a(n) for n = 0..2092 (terms 0..500 from T. D. Noe)
A. T. Balaban, J. Brunvoll, B. N. Cyvin, and S. J. Cyvin, Enumeration of branched catacondensed benzenoid hydrocarbons and their numbers of Kekulé structures, Tetrahedron 44(1) (1988), 221-228. See Eq. (6), p. 223.
A. T. Balaban and F. Harary, Chemical graphs V: enumeration and proposed nomenclature of benzenoid cata-condensed polycyclic aromatic hydrocarbons, Tetrahedron 24 (1968), 2505-2516.
Christian Barrientos and Sarah Minion, On the Graceful Cartesian Product of Alpha-Trees, Theory and Applications of Graphs, Vol. 4: Iss. 1, Article 3, 2017. (It mentions this sequence on p. 7.)
L. W. Beineke and R. E. Pippert, On the enumeration of planar trees of hexagons, Glasgow Math. J., 15 (1974), 131-147.
L. W. Beineke and R. E. Pippert, On the enumeration of planar trees of hexagons, Glasgow Math. J., 15 (1974), 131-147 [annotated scanned copy].
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.
S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, Isomer enumeration of some polygonal systems representing polycyclic conjugated hydrocarbons, Journal of Molecular structure 376 (Issues 1-3) (1996), 495-505. See Table 2 on p. 501.
S. J. Cyvin, B. N. Cyvin, and J. Brunvoll, Unbranched catacondensed polygonal systems containing hexagons and tetragons, Croatica Chem. Acta, 69 (1996), 757-774.
J. Eckhoff, Extremal interval graphs, J. Graph Theory 17 1 (1993), 117-127.
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].
F. Harary and R. W. Robinson, Tapeworms, Unpublished manuscript, circa 1973. (Annotated scanned copy)
Thomas M. Liggett and Wenpin Tang, One-dependent hard-core processes and colorings of the star graph, arXiv:1804.06877 [math.PR], 2018.
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.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
Gyula Tasi and Fujio Mizukami, Quantum algebraic-combinatoric study of the conformational properties of n-alkanes, J. Math. Chemistry, 25, 1999, 55-64 (see p. 60).
Eric Weisstein's World of Mathematics, Alkane Graph.
Eric Weisstein's World of Mathematics, Planar Embedding.
Index entries for sequences obtained by enumerating foldings
Index entries for linear recurrences with constant coefficients, signature (4,0,-12,9).

Cf. A036359, A002216, A005963, A000228, A001997, A001444, A038766, A007051.
Column 3 of A320750, offset by one. Column k = 0 of A323942, offset by two.
Cf. A124302 (oriented), A107767 (chiral), A182522 (achiral), with varying offsets.
Column 3 of A320750.
The numbers of unlabeled k-paths for k = 2..7 are given in A005418, A001998, A056323, A056324, A056325, and A345207, respectively.
The sequences above converge to A103293(n+1).

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

A001998 := proc(n) if n = 0 then 1 elif n mod 2 = 1 then (1/4)*(3^n+4*3^((n-1)/2)+1) else (1/4)*(3^n+2*3^(n/2)+1); fi; end;
A001998:=(-1+3*z+2*z**2-8*z**3+3*z**4)/(z-1)/(3*z-1)/(3*z**2-1); # conjectured by Simon Plouffe in his 1992 dissertation; gives sequence with an extra leading 1

a[n_?OddQ] := (1/4)*(3^n + 4*3^((n - 1)/2) + 1); a[n_?EvenQ] := (1/4)*(3^n + 2*3^(n/2) + 1); Table[a[n], {n, 0, 27}] (* Jean-François Alcover, Jan 25 2013, from formula *)
LinearRecurrence[{4,0,-12,9},{1,2,4,10},30] (* Harvey P. Dale, Apr 10 2013 *)
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,40}] (* Robert A. Russell, Oct 28 2018 *)

Vec((1-2*x-4*x^2+6*x^3)/((1-x)*(1-3*x)*(1-3*x^2)) + O(x^50)) \\ Colin Barker, May 15 2016

a(n) = if n mod 2 = 0 then ((3^((n-2)/2)+1)/2)^2 else 3^((n-3)/2)+(1/4)*(3^(n-2)+1).
G.f.: (1-2*x-4*x^2+6*x^3) / ((1-x)*(1-3*x)*(1-3*x^2)). - Corrected by Colin Barker, May 15 2016
a(n) = 4*a(n-1)-12*a(n-3)+9*a(n-4), with a(0)=1, a(1)=2, a(2)=4, a(3)=10. - Harvey P. Dale, Apr 10 2013
a(n) = (1+3^n+3^(1/2*(-1+n))*(2-2*(-1)^n+sqrt(3)+(-1)^n*sqrt(3)))/4. - Colin Barker, May 15 2016
E.g.f.: (2*sqrt(3)*sinh(sqrt(3)*x) + 3*exp(2*x)*cosh(x) + 3*cosh(sqrt(3)*x))/6. - Ilya Gutkovskiy, May 15 2016
From Robert A. Russell, Oct 28 2018: (Start)
a(n-1) = (A124302(n) + A182522(n)) / 2 = A124302(n) - A107767(n-1) = A107767(n-1) + A182522(n).
a(n-1) = Sum_{j=1..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) = A057427(n) + A056326(n) + A056327(n). (End)
a(2*n) = A007051(n)^2; a(2*n+1) = A007051(n)*A007051(n+1). - Todd Simpson, Mar 25 2024

Offset and Maple code corrected by Colin Mallows, Nov 12 1999

Term added by Robert A. Russell, Oct 30 2018

A002076 Number of equivalence classes of base-3 necklaces of length n, where necklaces are considered equivalent under both rotations and permutations of the symbols.

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 26, 53, 146, 369, 1002, 2685, 7434, 20441, 57046, 159451, 448686, 1266081, 3588002, 10195277, 29058526, 83018783, 237740670, 682196949, 1961331314, 5648590737, 16294052602, 47071590147, 136171497650, 394427456121, 1143839943618, 3320824711205

Offset: 0

N. J. A. Sloane

Number of set partitions of an oriented cycle of length n with 3 or fewer subsets. - Robert A. Russell, Nov 05 2018

			E.g., a(2) = 2 as there are two equivalence classes of the 9 strings {00,01,02,10,11,12,20,21,22}: {00,11,22} form one equivalence class and {01,02,10,12,20,21} form the other. To see that (for example) 01 and 02 are equivalent, rotate 01 to 10 and then subtract 1 mod 3 from each element in 10 to get 02.
For a(6)=26, there are 18 achiral patterns (AAAAAA, AAAAAB, AAAABB, AAABAB, AAABBB, AABAAB, AABABB, ABABAB, AAAABC, AAABAC, AAABCB, AABAAC, AABBCC, AABCBC, AABCCB, ABABAC, ABACBC, ABCABC) and 8 chiral patterns in four pairs (AAABBC-AAABCC, AABABC-AABCAC, AABACB-AABCAB, AABACC-AABBAC). - _Robert A. Russell_, Nov 05 2018

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).

Vincenzo Librandi, Table of n, a(n) for n = 0..500
N. J. Fine, Classes of periodic sequences, Illinois J. Math., 2 (1958), 285-302.
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
Marko Riedel, Necklaces with swappable colors by Power Group Enumeration
Marko Riedel, Maple code for any necklace size, any number of swappable colors, by Power Group Enumeration.
N. J. A. Sloane, Maple code for this and related sequences
Index entries for sequences related to necklaces

Cf. A000013, A000048, A002075.

Cf. A056353 (unoriented), A320743 (chiral), A182522 (achiral).

Adn[d_, n_] := Module[{ c, t1, t2}, t2 = 0; For[c = 1, c <= d, c++, If[Mod[d, c] == 0 , t2 = t2 + (x^c/c)*(E^(c*z) - 1)]]; t1 = E^t2; t1 = Series[t1, {z, 0, n+1}]; Coefficient[t1, z, n]*n!]; Pn[n_] := Module[{ d, e, t1}, t1 = 0; For[d = 1, d <= n, d++, If[Mod[n, d] == 0, t1 = t1 + EulerPhi[d]*Adn[d, n/d]/n]]; t1/(1 - x)]; Pnq[n_, q_] := Module[{t1}, t1 = Series[Pn[n], {x, 0, q+1}] ; Coefficient[t1, x, q]]; a[n_] := Pnq[n, 3]; Print[1]; Table[Print[an = a[n]]; an, {n, 1, 28}] (* Jean-François Alcover, Oct 04 2013, after N. J. A. Sloane's Maple code *)
(* This Mathematica program uses Gilbert and Riordan's recurrence formula, which they recommend for calculations: *)
Adn[d_, n_] := Adn[d, n] = If[1==n, DivisorSum[d, x^# &],
  Expand[Adn[d, 1] Adn[d, n-1] + D[Adn[d, n-1], x] x]];
Join[{1},Table[SeriesCoefficient[DivisorSum[n, EulerPhi[#] Adn[#, n/#] &] /(n (1 - x)), {x, 0, 3}], {n,40}]]  (* Robert A. Russell, Feb 24 2018 *)
From Robert A. Russell, May 29 2018: (Start)
Join[{1},Table[(1/n) DivisorSum[n, EulerPhi[#] Which[Divisible[#, 6], 3 StirlingS2[n/#+2, 3] - 9 StirlingS2[n/#+1, 3] + 6 StirlingS2[n/#, 3], Divisible[#, 3], 2 StirlingS2[n/#+2, 3] - 7 StirlingS2[n/#+1, 3] + 6 StirlingS2[n/#, 3], Divisible[#, 2], 2 StirlingS2[n/#+2, 3] - 6 StirlingS2[n/#+1, 3] + 4 StirlingS2[n/#, 3], True, StirlingS2[n/#+2, 3] - 4 StirlingS2[n/#+1, 3] + 4 StirlingS2[n/#, 3]] &], {n,40}]] (* or *)
mx = 40; CoefficientList[Series[1 - Sum[(EulerPhi[d] / d) Which[
  Divisible[d, 6], Log[1 - 3x^d], Divisible[d, 3], (Log[1 - 3x^d] +
  Log[1 - x^d]) / 2, Divisible[d, 2], 2 Log[1 - 3x^d] / 3, True, (Log[1 - 3x^d] + 3 Log[1 - x^d]) / 6], {d, 1, mx}], {x, 0, mx}], x]
(End)
(* Adnk(n,d,k) is coefficient of x^k in A(d,n)(x) from Gilbert & Riordan *)
Adnk[d_,n_,k_] := Adnk[d,n,k] = If[n>0 && k>0, Adnk[d,n-1,k]k + DivisorSum[d,Adnk[d,n-1,k-#]&], Boole[n==0 && k==0]]
k=3; Join[{1},Table[Sum[DivisorSum[n,EulerPhi[#] Adnk[#,n/#,j] &],{j,k}]/n,{n,40}]] (* Robert A. Russell, Nov 05 2018 *)

Reference gives formula.
From Robert A. Russell, May 29 2018: (Start)
For n>0, a(n) = (1/n) * Sum_{d|n} phi(d) * ([d==0 mod 6] * (3*S2(n/d+2, 3) - 9*S2(n/d+1, 3) + 6*S2(n/d, 3)) + [d==3 mod 6] * (2*S2(n/d+2, 3) - 7*S2(n/d+1, 3) + 6*S2(n/d, 3)) + [d==2 mod 6 | d==4 mod 6] * (2*S2(n/d+2, 3) - 6*S2(n/d+1, 3) + 4*S2(n/d, 3)) + [d==1 mod 6 | d=5 mod 6] * (S2(n/d+2, 3) - 4*S2(n/d+1, 3) + 4*S2(n/d, 3))), where S2(n,k) is the Stirling subset number, A008277.
G.f.: 1 - Sum_{d>0} (phi(d) / d) * ([d==0 mod 6] * log(1-3x^d) +
  [d==3 mod 6] * (log(1-3x^d) + log(1-x^d)) / 2 +
  [d==2 mod 6 | d==4 mod 6] * 2*log(1-3x^d) / 3 +
  [d==1 mod 6 | d=5 mod 6] * (log(1-3x^d) + 3*log(1-x^d)) / 6).
(End)

Better description and more terms from Mark Weston (mweston(AT)uvic.ca), Oct 06 2001

a(0)=1 prepended by Robert A. Russell, Nov 05 2018

A169623 Generalized Pascal triangle read by rows: T(n,0) = T(0,n) = 1 for n >= 0, T(n,k) = 0 for k < 0 or k > n; otherwise T(n,k) = T(n-2,k-2) + T(n-2,k-1) + T(n-2,k) for 1 <= k <= n-1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 5, 5, 3, 1, 1, 3, 6, 7, 6, 3, 1, 1, 4, 9, 13, 13, 9, 4, 1, 1, 4, 10, 16, 19, 16, 10, 4, 1, 1, 5, 14, 26, 35, 35, 26, 14, 5, 1, 1, 5, 15, 30, 45, 51, 45, 30, 15, 5, 1, 1, 6, 20, 45, 75, 96, 96, 75, 45, 20, 6, 1

Offset: 0

Roger L. Bagula and Gary W. Adamson, Dec 03 2009

The borders are all 1's, with zero entries outside. To get an internal entry, use the rule that D = A+B+C here:
         A   B   C
       *   *   *   *
     *   *   D   *   *
That is, add the three terms directly above you, two rows back.
This is the triangle er(n,k) defined in the Ehrenborg and Readdy link. See Proposition 2.4 and Table 1. - Michel Marcus, Sep 14 2016
If the offset is changed from 0 to 1, this is also the table U(n,k) of the coefficients [x^k] p_n(x) of the polynomials p_n(x) = (x + 1)*p_{n-1}(x) (if n even), p_n = (x^2 + x + 1)^floor(n/2) if n odd.
May be split into two triangles by taking the even-numbered and odd-numbered rows separately: the even-numbered rows give A027907.
From Peter Bala, Aug 19 2021: (Start)
Let M denote the lower unit triangular array A070909. For k = 0,1,2,..., define M(k) to be the lower unit triangular block array
  /I_k 0\
  \ 0  M/
  having the k x k identity matrix I_k as the upper left block; in particular, M(0) = M. Then the present triangle equals the infinite matrix product M(0)*M(1)*M(2)*... (which is clearly well-defined). See the Example section below. The proof uses the hockey-stick identities from the Formula section. (End)

			Triangle begins:
                    1
                  1   1
                1   1   1
              1   2   2   1
            1   2   3   2   1
          1   3   5   5   3   1
        1   3   6   7   6   3   1
      1   4   9  13  13   9   4   1
    1   4  10  16  19  16  10   4   1
  ...
As a square array read by antidiagonals:
  1, 1, 1,  1,  1,  1,  1,  1,  1,  1,  1,  1, 1, 1, 1, 1, ...
  1, 1, 2,  2,  3,  3,  4,  4,  5,  5,  6,  6, 7, 7, 8, 8, ...
  1, 2, 3,  5,  6,  9, 10, 14, 15, 20, 21, 27, ...
  1, 2, 5,  7, 13, 16, 26, 30, 45, ...
  1, 3, 6, 13, 19, 35, 45, 75, ...
  1, 3, 9, 16, 35, 51, 96, ...
  ...
From _Peter Bala_, Aug 19 2021: (Start)
With the arrays M(k) as defined in the Comments section, the infinite product M(0)*M(1)*M(2)*... begins
  /1        \/1        \/1       \ /1       \        /1         \
  |1 1      ||0 1      ||0 1      ||0 1      |       |1 1       |
  |1 0 1    ||0 1 1    ||0 0 1    ||0 0 1    |...  = |1 1 1     |
  |1 0 1 1  ||0 1 0 1  ||0 0 1 1  ||0 0 0 1  |       |1 2 2 1   |
  |1 0 1 0 1||0 1 0 1 1||0 0 1 0 1||0 0 0 1 1|       |1 2 3 2 1 |
  |...      ||...       |...      ||...      |       |...       |
(End)

Rémy Sigrist, Rows 0..199, flattened
Paul Barry, Jacobsthal Decompositions of Pascal's Triangle, Ternary Trees, and Alternating Sign Matrices, Journal of Integer Sequences, 19, 2016, #16.3.5.
Richard Ehrenborg and Margaret A. Readdy, The Gaussian coefficient revisited, arXiv:1609.03216 [math.CO], 2016.
Richard L. Ollerton and Anthony G. Shannon, Some properties of generalized Pascal squares and triangles, Fib. Q., 36 (No. 2, 1998), 98-109. See Table 10.
Wikipedia, Hockey-stick identity.

A123149 is essentially the same triangle, except for a diagonal of zeros.
Row sums are in A182522 (essentially A038754).
Cf. A027907, A070909.
See A295555 for the next triangle in the series A007318, A169623 (this sequence).

T:=proc(n,k) option remember;
if n >= 0 and k = 0 then 1
elif n >= 0 and k = n then 1
elif (k < 0 or k > n) then 0
else T(n-2,k-2)+T(n-2,k-1)+T(n-2,k);
fi;
end;
for n from 0 to 14 do lprint([seq(T(n,k),k=0..n)]); od: # N. J. A. Sloane, Nov 23 2017

p[x, 1] := 1;
p[x_, n_] := p[x, n] = If[Mod[n, 2] == 0, (x + 1)*p[x, n - 1], (x^2 + x + 1)^Floor[n/2]]
a = Table[CoefficientList[p[x, n], x], {n, 1, 12}]
Flatten[a] (* This is for the same sequence but with offset 1 *)

From Peter Bala, Aug 19 2021: (Start)
T(2*n,k) = T(2*n-1,k-1) + T(2*n-2,k).
T(2*n,k) = T(2*n-1,k) + T(2*n-2,k-2).
T(2*n+1,k) = T(2*n,k) + T(2*n,k-1).
Hockey stick identities (relate row k entries to entries in row k-1):
T(2*n,k) = T(2*n-1,k-1) + T(2*n-3,k-1) + T(2*n-5,k-1) + ....
T(2*n+1,k) = T(2*n,k-1) + ( T(2*n-1,k-1) + T(2*n-3,k-1) + T(2*n-5,k-1) + ... ). (End)

Keyword:tabl added, notation standardized, formula added by the Assoc. Editors of the OEIS, Feb 02 2010

Entry revised by N. J. A. Sloane, Nov 23 2017

A305749 T(n,k) is the number of achiral color patterns (set partitions) in a row or loop of length n with k or fewer colors (sets).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 3, 4, 1, 1, 2, 3, 6, 4, 1, 1, 2, 3, 7, 9, 8, 1, 1, 2, 3, 7, 11, 18, 8, 1, 1, 2, 3, 7, 12, 27, 27, 16, 1, 1, 2, 3, 7, 12, 30, 43, 54, 16, 1, 1, 2, 3, 7, 12, 31, 55, 107, 81, 32, 1, 1, 2, 3, 7, 12, 31, 58, 141, 171, 162, 32, 1, 1, 2, 3, 7, 12, 31, 59, 159, 266, 427, 243, 64, 1, 1, 2, 3, 7, 12, 31, 59, 163, 312, 688, 683, 486, 64, 1

Offset: 1

Robert A. Russell, Jun 09 2018

An equivalent color pattern is obtained when we permute the colors. Thus all permutations of ABC are equivalent, as are AAABB and BBBAA. A color pattern is achiral if it is equivalent to its reversal. Rotations of the colors of a loop are equivalent, so for loops AAABCB = BAAABC = CBAAAB.

			The array begins at T(1,1):
1  1   1    1    1     1     1     1     1     1     1     1     1 ...
1  2   2    2    2     2     2     2     2     2     2     2     2 ...
1  2   3    3    3     3     3     3     3     3     3     3     3 ...
1  4   6    7    7     7     7     7     7     7     7     7     7 ...
1  4   9   11   12    12    12    12    12    12    12    12    12 ...
1  8  18   27   30    31    31    31    31    31    31    31    31 ...
1  8  27   43   55    58    59    59    59    59    59    59    59 ...
1 16  54  107  141   159   163   164   164   164   164   164   164 ...
1 16  81  171  266   312   334   338   339   339   339   339   339 ...
1 32 162  427  688   883   963   993   998   999   999   999   999 ...
1 32 243  683 1313  1774  2069  2169  2204  2209  2210  2210  2210 ...
1 64 486 1707 3407  5103  6119  6634  6789  6834  6840  6841  6841 ...
1 64 729 2731 6532 10368 13524 15080 15790 15975 16026 16032 16033 ...
a(n) are the terms of this array read by antidiagonals.
For T(4,3)=6, the achiral pattern rows are AAAA, AABB, ABAB, ABBA, ABBC, and ABCA. The achiral pattern loops are AAAA, AAAB, AABB, ABAB, AABC, and ABAC.

Columns 1-6 are A057427, A016116, A182522, A305750, A305751, and A305752.

Columns converge to the right to A080107.

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[Ach[n, j], {j, 1, k - n + 1}], {k, 1, 15}, {n, 1, k}] // Flatten

T(n,k) = Sum_{j=0..k} Ach(n,j), where Ach(n,k) = [n>1] * (k*T(n-2,k) + T(n-2,k-1) + T(n-2,k-2)) + [0 <= n <= 1 & n==k].

T(n,k) = Sum_{j=1..k} A304972(n,j).

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

A216238 Square array T, read by antidiagonals: T(n,k) = 0 if n-k>=1 or if k-n>=5, T(0,0) = T(0,1) = T(0,2) = T(0,3) = T(0,4) = 1, T(n,k) = T(n-1,k) + T(n,k-1).

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 2, 0, 0, 0, 4, 5, 0, 0, 0, 0, 4, 9, 5, 0, 0, 0, 0, 0, 13, 14, 0, 0, 0, 0, 0, 0, 13, 27, 14, 0, 0, 0, 0, 0, 0, 0, 40, 41, 0, 0, 0, 0, 0, 0, 0, 0, 40, 81, 41, 0, 0, 0, 0, 0, 0, 0, 0, 0, 121, 122, 0, 0, 0, 0, 0, 0

Offset: 0

Philippe Deléham, Mar 14 2013

Hexagon arithmetic of E. Lucas.

			Square array begins:
1, 1, 1, 1,  1,  0,   0,   0,   0,    0,    0, ... row n=0
0, 1, 2, 3,  4,  4,   0,   0,   0,    0,    0, ... row n=1
0, 0, 2, 5,  9, 13,  13,   0,   0,    0,    0, ... row n=2
0, 0, 0, 5, 14, 27,  40,  40,   0,    0,    0, ... row n=3
0, 0, 0, 0, 14, 41,  81, 121, 121,    0,    0, ... row n=4
0, 0, 0, 0,  0, 41, 122, 243, 364,  364,    0, ... row n=5
0, 0, 0, 0,  0,  0, 122, 365, 729, 1093, 1093, ... row n=6
...

E. Lucas, Théorie des nombres, Albert Blanchard, Paris, 1958, Tome1, p.89

E. Lucas, Théorie des nombres, Tome 1, Jacques Gabay, Paris, 1991, p.89

Cf. A000244, A003462, A124302, A182522.

Similar sequences: A216201, A216210, A216216, A216218, A216219, A216220, A216226, A216228, A216229, A216230, A216232, A216235, A216236.

T(n,n) = A124302(n).
T(n,n+1) = A124302(n+1).
T(n,n+2) = 3^n = A000244(n).
T(n,n+3) = T(n,n+4) = A003462(n+1).
Sum_{k, 0<=k<=n} T(n-k,k) = A182522(n).

A320743 Number of chiral pairs of color patterns (set partitions) in a cycle of length n using 3 or fewer colors (subsets).

Original entry on oeis.org

0, 0, 0, 0, 0, 4, 13, 46, 144, 420, 1221, 3474, 9856, 27794, 78632, 222156, 629760, 1787440, 5087797, 14509580, 41479867, 118811286, 341009901, 980488510, 2824029648, 8146494860, 23534997912, 68084154502, 197211336576, 571915188840, 1660405181149, 4825559508106, 14038010213051, 40875403561680, 119122661856133, 347441159864556, 1014152747485696

Offset: 1

Robert A. Russell, Oct 21 2018

Two color patterns are equivalent if the colors are permuted.
Adnk[d,n,k] in Mathematica program is coefficient of x^k in A(d,n)(x) in Gilbert and Riordan reference.
There are nonrecursive formulas, generating functions, and computer programs for A002076 and A182522, which can be used in conjunction with the first formula.

			For a(6)=4, the chiral pairs are AAABBC-AAABCC, AABABC-AABCAC, AABACB-AABCAB, and AABACC-AABBAC.

Andrew Howroyd, Table of n, a(n) for n = 1..200
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Column 3 of A320742.

Cf. A002076 (oriented), A056353 (unoriented), A182522 (achiral).

Adnk[d_,n_,k_] := Adnk[d,n,k] = If[n>0 && k>0, Adnk[d,n-1,k]k + DivisorSum[d, Adnk[d,n-1,k-#]&], Boole[n == 0 && k == 0]]
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[(DivisorSum[n,EulerPhi[#] Adnk[#,n/#,j]&]/n - Ach[n,j])/2, {j, k}], {n,40}]

a(n) = (A002076(n) - A182522(n)) / 2 = A002076(n) - A056353(n) = A056353(n) - A182522(n).
a(n) = Sum_{j=1..k} -Ach(n,j)/2 + (1/2n)*Sum_{d|n} phi(d)*A(d,n/d,j), where k=3 is the maximum number of colors, 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)), and A(d,n,k) = [n==0 & k==0] + [n>0 & k>0]*(k*A(d,n-1,k) + Sum_{j|d} A(d,n-1,k-j)).
a(n) = A059053(n) + A320643(n).

A123149 Triangle T(n,k), 0<=k<=n, read by rows given by [1, 0, -1, 0, 0, 0, 0, 0, ...] DELTA [0, 1, 0, -1, 0, 0, 0, 0, ...] where DELTA is the operator defined in A084938.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 2, 1, 0, 1, 2, 3, 2, 1, 0, 1, 3, 5, 5, 3, 1, 0, 1, 3, 6, 7, 6, 3, 1, 0, 1, 4, 9, 13, 13, 9, 4, 1, 0, 1, 4, 10, 16, 19, 16, 10, 4, 1, 0, 1, 5, 14, 26, 35, 35, 26, 14, 5, 1, 0, 1, 5, 15, 30, 45, 51, 45, 30, 15, 5, 1, 0, 1, 6, 20, 45, 75, 96, 96, 75, 45, 20, 6, 1, 0

Offset: 0

Philippe Deléham, Nov 05 2006

A169623 is a very similar triangle except it does not have the outer diagonal of 0's. - N. J. A. Sloane, Nov 23 2017

			Triangle begins:
  1;
  1,  0;
  1,  1,  0;
  1,  1,  1,  0;
  1,  2,  2,  1,  0;
  1,  2,  3,  2,  1,  0;
  1,  3,  5,  5,  3,  1,  0;
  1,  3,  6,  7,  6,  3,  1,  0;
  1,  4,  9, 13, 13,  9,  4,  1,  0;

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A002426, A005773, A013979, A027907, A038754, A084938, A135528, A169623, A182522 (row sums).

function T(n,k) // T = A123149
  if k lt 0 or k gt n then return 0;
  elif k eq 0 or k eq n-1 then return 1;
  elif k eq n then return 0;
  else return T(n-2,k) +T(n-2,k-1) +T(n-2,k-2);
  end if;
end function;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jul 17 2023

T[n_, k_]:= T[n, k]= If[k<0 || k>n, 0, If[k==0 || k==n-1, 1, If[k==n, 0, T[n-2,k] +T[n-2,k-1] +T[n-2,k-2] ]]];
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Jul 17 2023 *)

def T(n,k): # T = A123149
    if (k<0 or k>n): return 0
    elif (k==0 or k==n-1): return 1
    elif (k==n): return 0
    else: return T(n-2,k) +T(n-2,k-1) +T(n-2,k-2)
flatten([[T(n,k) for k in range(n+1)] for n in range(13)]) # G. C. Greubel, Jul 17 2023

T(n,k) = T(n-1,k-1) + T(n-1,k) if n even, T(n,k) = T(n-1,k-1) + T(n-2,k) if n odd, T(0,0) = 1, T(1,0) = 1, T(1,1) = 0, T(n,k) = 0 if k < 0 or if k > n.
T(n,k) = T(n,n-k-1).
Sum_{k=0..n} T(n,k) = A038754(n-1), for n>=1.
T(2*n,n) = A005773(n).
T(2*n+1,n) = A002426(n).
From Philippe Deléham, May 04 2012: (Start)
G.f.: (1+x-y^2*x^2)/(1-x^2-y*x^2-y^2*x^2).
T(n,k) = T(n-2,k) + T(n-2,k-1) + T(n-2,k-2), T(0,0) = T(1,0) = T(2,0) = T(2,1) = 1, T(1,1) = T(2,2) = 0 and T(n,k) = 0 if k < 0 or if k > n.
Sum_{k=0..n} T(n,k) = A182522(n). (End)
From G. C. Greubel, Jul 17 2023: (Start)
Sum_{k=0..n} (-1)^k*T(n,k) = A135528(n).
Sum_{k=0..floor(n/2)} T(n-k,k) = [n==0] + A013979(n+1). (End)

cp's OEIS Frontend

A001998 Bending a piece of wire of length n+1; walks of length n+1 on a tetrahedron; also non-branched catafusenes with n+2 condensed hexagons.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

Formula

Extensions

A002076 Number of equivalence classes of base-3 necklaces of length n, where necklaces are considered equivalent under both rotations and permutations of the symbols.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A169623 Generalized Pascal triangle read by rows: T(n,0) = T(0,n) = 1 for n >= 0, T(n,k) = 0 for k < 0 or k > n; otherwise T(n,k) = T(n-2,k-2) + T(n-2,k-1) + T(n-2,k) for 1 <= k <= n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A305749 T(n,k) is the number of achiral color patterns (set partitions) in a row or loop of length n with k or fewer colors (sets).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Formula

Extensions

A216238 Square array T, read by antidiagonals: T(n,k) = 0 if n-k>=1 or if k-n>=5, T(0,0) = T(0,1) = T(0,2) = T(0,3) = T(0,4) = 1, T(n,k) = T(n-1,k) + T(n,k-1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A320743 Number of chiral pairs of color patterns (set partitions) in a cycle of length n using 3 or fewer colors (subsets).

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.