A028859 -id:A028859 - cp's OEIS frontend

A207543 Triangle read by rows, expansion of (1+yx)/(1-2y*x+y(y-1)x^2).

1, 0, 3, 0, 1, 5, 0, 0, 5, 7, 0, 0, 1, 14, 9, 0, 0, 0, 7, 30, 11, 0, 0, 0, 1, 27, 55, 13, 0, 0, 0, 0, 9, 77, 91, 15, 0, 0, 0, 0, 1, 44, 182, 140, 17, 0, 0, 0, 0, 0, 11, 156, 378, 204, 19, 0, 0, 0, 0, 0, 1, 65, 450, 714, 285, 21, 0

Offset: 0

Philippe Deléham, Feb 24 2012

Previous name was: "A scaled version of triangle A082985."

Triangle, read by rows, given by (0, 1/3, -1/3, 0, 0, 0, 0, 0, 0, 0, ...) DELTA (3, -4/3, 1/3, 0, 0, 0, 0, 0, 0, 0, ...) where DELTA is the operator defined in A084938.

			Triangle begins :
1
0, 3
0, 1, 5
0, 0, 5, 7
0, 0, 1, 14, 9
0, 0, 0, 7, 30, 11
0, 0, 0, 1, 27, 55, 13
0, 0, 0, 0, 9, 77, 91, 15
0, 0, 0, 0, 1, 44, 182, 140, 17
0, 0, 0, 0, 0, 11, 156, 378, 204, 19
0, 0, 0, 0, 0, 1, 65, 450, 714, 285, 21
0, 0, 0, 0, 0, 0, 13, 275, 1122, 1254, 385, 23

R. Zielinski, Induction and Analogy in a Problem of Finite Sums arXiv:1608.04006 [math.GM], 2016.

Cf. A082985 which is another version of this triangle.

Cf. Diagonals : A005408, A000330, A005585, A050486, A054333, A057788. Cf. A119900.

s := (1+y*x)/(1-2*y*x+y*(y-1)*x^2): t := series(s,x,12):
seq(print(seq(coeff(coeff(t,x,n),y,m),m=0..n)),n=0..11); # Peter Luschny, Aug 17 2016

T(n,k) = 2*T(n-1,k-1) + T(n-2,k-1) - T(n-2,k-2), T(0,0) = 1, T(1,0) = 0, T(1,1) = 3.
G.f.: (1+y*x)/(1-2*y*x+y*(y-1)*x^2).
Sum_{i, i>=0} T(n+i,n) = A000204(2*n+1).
Sum_{k, 0<=k<=n} T(n,k)*x^k = A078069(n), A000007(n), A003945(n), A111566(n) for x = -1, 0, 1, 2 respectively.
Sum_{k, 0<=k<=n} T(n,k)*x^(n-k) = A090131(n), A005408(n), A003945(n), A078057(n), A028859(n), A000244(n), A063782(n), A180168(n) for x = -1, 0, 1, 2, 3, 4, 5, 6 respectively.
From Peter Bala, Aug 17 2016: (Start)
Let S(k,n) = Sum_{i = 1..n} i^k. Calculations in Zielinski 2016 suggest the following identity holds involving the p-th row elements of this triangle:
Sum_{k = 0..p} T(p,k)*S(2*k,n) = 1/2*(2*n + 1)*(n*(n + 1))^p.
For example, for row 6 we find S(6,n) + 27*S(8,n) + 55*S(10,n) + 13*S(12,n) = 1/2*(2*n + 1)*(n*(n + 1))^6.
There appears to be a similar result for the odd power sums S(2*k + 1,n) involving A119900. (End)

New name using a formula of the author from Peter Luschny, Aug 17 2016

A334966 Numbers k such that the k-th composition in standard order (row k of A066099) has weakly decreasing non-adjacent parts.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 27, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 45, 47, 48, 49, 51, 55, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 79, 80, 81, 82, 83, 85, 86, 87

Offset: 1

Gus Wiseman, May 18 2020

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

The complement starts: 14, 26, 28, 29, 30, 44, 46, 50, ...

			The sequence together with the corresponding compositions begins:
   0: ()           17: (4,1)          37: (3,2,1)
   1: (1)          18: (3,2)          38: (3,1,2)
   2: (2)          19: (3,1,1)        39: (3,1,1,1)
   3: (1,1)        20: (2,3)          40: (2,4)
   4: (3)          21: (2,2,1)        41: (2,3,1)
   5: (2,1)        22: (2,1,2)        42: (2,2,2)
   6: (1,2)        23: (2,1,1,1)      43: (2,2,1,1)
   7: (1,1,1)      24: (1,4)          45: (2,1,2,1)
   8: (4)          25: (1,3,1)        47: (2,1,1,1,1)
   9: (3,1)        27: (1,2,1,1)      48: (1,5)
  10: (2,2)        31: (1,1,1,1,1)    49: (1,4,1)
  11: (2,1,1)      32: (6)            51: (1,3,1,1)
  12: (1,3)        33: (5,1)          55: (1,2,1,1,1)
  13: (1,2,1)      34: (4,2)          63: (1,1,1,1,1,1)
  15: (1,1,1,1)    35: (4,1,1)        64: (7)
  16: (5)          36: (3,3)          65: (6,1)
For example, (2,3,1,2) is such a composition because the non-adjacent pairs are (2,1), (2,2), (3,2), all of which are weakly decreasing, so 166 is in the sequence

The case of normal sequences appears to be A028859.
Strict compositions are A032020.
A version for ordered set partitions is A332872.
These compositions are enumerated by A333148.
The strict case is enumerated by A333150.
Cf. A072706, A072707, A227038, A332834, A333193.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],!MatchQ[stc[#],{_,x_,,y_,_}/;y>x]&]

A005666 Minimal number of moves for the cyclic variant of the Towers of Hanoi for 3 pegs and n disks, with the final peg two steps away.

Original entry on oeis.org

0, 2, 7, 21, 59, 163, 447, 1223, 3343, 9135, 24959, 68191, 186303, 508991, 1390591, 3799167, 10379519, 28357375, 77473791, 211662335, 578272255, 1579869183, 4316282879, 11792304127, 32217174015, 88018956287, 240472260607, 656982433791, 1794909388799

Offset: 0

N. J. A. Sloane

Original name was: Tower of Hanoi with 3 pegs and cyclic moves only (counterclockwise). - Jianing Song, Nov 01 2024

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 18.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

J.-P. Allouche, Note on the cyclic towers of Hanoi, Theoret. Comput. Sci., 123 (1994), 3-7.
M. D. Atkinson, The Cyclic Towers of Hanoi, Info. Proc. Letters, 13 (1981), 118-119.
R. K. Guy, Letter to N. J. A. Sloane, 1976
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
D. G. Poole, The towers and triangles of Professor Claus (or, Pascal knows Hanoi), Math. Mag., 67 (1994), 323-344.
Amir Sapir, The Tower of Hanoi with Forbidden Moves, The Computer J. 47 (1) (2004) 20, case (ii), cyclic.
Index entries for sequences related to Towers of Hanoi
Index entries for linear recurrences with constant coefficients, signature (3,0,-2).

Cf. A005665, A052945 (first differences).

Cf. A338024, A292764, A338089 (4 pegs).

[Floor((1/(4*Sqrt(3)))*((1+Sqrt(3))^(n+2)-(1-Sqrt(3))^(n+2))-1): n in [0..30]]; // Vincenzo Librandi, Sep 03 2015

CoefficientList[Series[z (2 + z)/(z - 1)/(2 z^2 + 2 z - 1), {z, 0, 22}], z] (* Michael De Vlieger, Sep 02 2015 *)
LinearRecurrence[{3,0,-2},{0,2,7},30] (* Harvey P. Dale, Jul 28 2025 *)

a(n) = (1/(4*s3))*((1+s3)^(n+2)-(1-s3)^(n+2))-1 where s3 = sqrt(3).
a(n) = A028859(n) - 1.
G.f.: x*(2+x) / ( (x-1)*(2*x^2+2*x-1) ). - Simon Plouffe in his 1992 dissertation
From Paul Zimmermann, Feb 07 2018: (Start)
a(n) = 2*a(n-1)+2*a(n-2)+3 (same recurrence as A005665).
a(n) = 2*a(n-1)+c(n-1)+2 where c(n) = 2*a(n-1)+1 stands for A005665. (End)
E.g.f.: exp(x)*(3*cosh(sqrt(3)*x) + 2*sqrt(3)*sinh(sqrt(3)*x) - 3)/3. - Stefano Spezia, Apr 11 2025

Name clarified by Paul Zimmermann, Feb 09 2018

New name based on the name of A338024, A292764, and A338089 by Jianing Song, Nov 01 2024

A103279 Array read by antidiagonals, generated by the matrix M = [1,1,1;1,N,1;1,1,1].

Original entry on oeis.org

1, 1, 3, 1, 3, 8, 1, 3, 9, 22, 1, 3, 10, 27, 60, 1, 3, 11, 34, 81, 164, 1, 3, 12, 43, 116, 243, 448, 1, 3, 13, 54, 171, 396, 729, 1224, 1, 3, 14, 67, 252, 683, 1352, 2187, 3344, 1, 3, 15, 82, 365, 1188, 2731, 4616, 6561, 9136, 1, 3, 16, 99, 516, 2019, 5616, 10923, 15760

Offset: 0

Lambert Klasen (lambert.klasen(AT)gmx.net), Jan 27 2005

Consider the matrix M = [1,1,1;1,N,1;1,1,1]; Characteristic polynomial of M is x^3 + (-N - 2)*x^2 + (2*N - 2)*x.
Now (M^n)[1,1] is equivalent to the recursion a(1) = 1, a(2) = 3, a(n) = (N+2)a(n-1)+(2N-2)a(n-2). (This also holds for negative N and fractional N.)
a(n+1)/a(n) converges to the upper root of the characteristic polynomial ((N + 2) + sqrt((N - 2)^2 + 8))/2 for n to infinity.
Columns of array follow the polynomials:
1,
3,
N + 8,
N^2 + 4*N + 22,
N^3 + 4*N^2 + 16*N + 60,
N^4 + 4*N^3 + 18*N^2 + 56*N + 164,
N^5 + 4*N^4 + 20*N^3 + 68*N^2 + 188*N + 448,
N^6 + 4*N^5 + 22*N^4 + 80*N^3 + 248*N^2 + 608*N + 1224,
N^7 + 4*N^6 + 24*N^5 + 92*N^4 + 312*N^3 + 864*N^2 + 1920*N + 3344,
N^8 + 4*N^7 + 26*N^6 + 104*N^5 + 380*N^4 + 1152*N^3 + 2928*N^2 + 5952*N + 9136,
etc.

			Array begins:
1,3,8,22,60,164,448,1224,3344,9136,...
1,3,9,27,81,243,729,2187,6561,19683,...
1,3,10,34,116,396,1352,4616,15760,53808,...
1,3,11,43,171,683,2731,10923,43691,174763,...
1,3,12,54,252,1188,5616,26568,125712,594864,...
...

Cf. A103280 (for (M^n)[1, 2]), A028859 (for N=0), A000244 (for N=1), A007052 (for N=2), A007583 (for N=3), A083881 (for N=4), A026581 (for N=-1), A026532 (for N=-2), A026568.

T11(N, n) = if(n==1,1,if(n==2,3,(N+2)*r1(N,n-1)-(2*N-2)*r1(N,n-2))) for(k=0,10,print1(k,": ");for(i=1,10,print1(T11(k,i),","));print())

T(N, 1)=1, T(N, 2)=3, T(N, n)=(N+2)*T(N, n-1)-(2*N-2)*T(N, n-2).

A118357 Triangle read by rows: T(n,k) is the number of ternary sequences of length n containing k subsequences 00 (n>=0, 0<=k<=max(0,n-1)).

Original entry on oeis.org

1, 3, 8, 1, 22, 4, 1, 60, 16, 4, 1, 164, 56, 18, 4, 1, 448, 188, 68, 20, 4, 1, 1224, 608, 248, 80, 22, 4, 1, 3344, 1920, 864, 312, 92, 24, 4, 1, 9136, 5952, 2928, 1152, 380, 104, 26, 4, 1, 24960, 18192, 9696, 4128, 1472, 452, 116, 28, 4, 1, 68192, 54976, 31536, 14400

Offset: 0

Emeric Deutsch, May 24 2006

Sum of entries in row n is 3^n (A000244). T(n,0) = A028859(n). T(n,1) = A073388(n-2). Sum(k*T(n,k),k=0..n-1) = (n-1)*3^(n-2) (A027471).

			T(4,2) = 4 because we have 0001, 0002, 1000 and 2000.
Triangle starts:
1;
3;
8,1;
22,4,1;
60,16,4,1;

Alois P. Heinz, n = 0..141, flattened

Cf. A000244, A028859, A073388, A027471.

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

nn=15;a=1/(1-2x);b=x/(1-y x)+1;f[list_]:=Select[list,#>0&];Map[f,CoefficientList[Series[a b/(1-2x^2/((1-y x)(1-2x))),{x,0,nn}],{x,y}]]//Grid  (* Geoffrey Critzer, Nov 19 2012 *)

G.f.: G-1, where G = G(t,z) = [1+(1-t)z]/[1-(2+t)z-2(1-t)z^2]. G.f. of column k is z^(k+1)*(1-2z)^(k-1)/(1-2z-2z^2)^(k+1) (k>=1).

A209239 Number of length n words on {0,1,2} with no four consecutive 0's.

Original entry on oeis.org

1, 3, 9, 27, 80, 238, 708, 2106, 6264, 18632, 55420, 164844, 490320, 1458432, 4338032, 12903256, 38380080, 114159600, 339561936, 1010009744, 3004222720, 8935908000, 26579404800, 79059090528, 235157252096, 699463310848

Offset: 0

Geoffrey Critzer, Jan 13 2013

R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Wesley, 1996, page 377.

D. Birmajer, J. B. Gil, and M. D. Weiner, On the Enumeration of Restricted Words over a Finite Alphabet, J. Int. Seq. 19 (2016) # 16.1.3, Example 7.
Milan Janjic, On Linear Recurrence Equations Arising from Compositions of Positive Integers, J. Int. Seq. 18 (2015) # 15.4.7.
Index entries for linear recurrences with constant coefficients, signature (2,2,2,2).

Cf. A000079, A028859, A119826.

nn=25; CoefficientList[Series[(1-x^4)/(1-3x+2x^5), {x,0,nn}], x]
LinearRecurrence[{2,2,2,2},{1,3,9,27},40] (* Harvey P. Dale, Sep 13 2018 *)

O.g.f.: (1 - x^4)/(1 - 3*x+ 2*x^5) = (1+x)*(1+x^2)/(1-2*x-2*x^2-2*x^3-2*x^4).
a(n) = A160175(n) + A160175(n-1) + A160175(n-2) + A160175(n-3). - R. J. Mathar, Aug 04 2019
a(n) = 2*(a(n-1) + a(n-2) + a(n-3) + a(n-4)) for n>=4, with a(0) = 1, a(1) = 3, a(2) = 9, a(3) = 27. - Taras Goy, Aug 04 2019

A209241 3^n times the expected value of the longest run of 0's in all length n words on {0,1,2}.

Original entry on oeis.org

0, 1, 6, 25, 92, 317, 1054, 3425, 10964, 34729, 109162, 341125, 1061132, 3288713, 10161666, 31318201, 96312696, 295632805, 905955146, 2772234385, 8472129040, 25861509393, 78861419302, 240252829461, 731313754312, 2224352781697

Offset: 0

Geoffrey Critzer, Jan 13 2013

nonn

a(n) is also the sum of length n words on {0,1,2} that have no runs of 0's of length >= i for i >= 1. In other words, A000079 + A028859 + A119826 + A209239 + ...

			a(2) = 6 because for such length 2 words: 00, 01, 02, 10, 11, 12, 20, 21, 22 we have respectively longest zero runs of length 2 + 1 + 1 + 1 + 0 + 0 + 1 + 0 + 0 = 6.

R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison and Wesley, 1996, Chapter 7.

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A119706.

nn=25; CoefficientList[Series[Sum[1/(1-3x)-(1-x^k)/(1-3x+2x^(k+1)), {k,1,nn}], {x,0,nn}], x]

O.g.f.: Sum_{k=1..n} 1/(1-3x)-(1-x^k)/(1-3x+2x^(k+1)).

a(n) = Sum_{k=1..n} A209240(n,k)*k.

A350336 Number of n X n ternary matrices with no two adjacent 0's.

Original entry on oeis.org

1, 3, 56, 7504, 6832640, 42780151808, 1836366011301888, 540795841280638713856, 1092417949346109029345132544, 15137179876232766647722798101823488, 1438787206346713875314130065804001328234496, 938091111277955250977701268973340995182098116509696

Offset: 0

Robert P. P. McKone, Jan 03 2022

A two-dimensional generalization of A028859.

2^(n^2) < a(n) < 3^(n^2).

			a(1) is trivial because all 3 1 X 1 matrices have no 2 adjacent 0's, whereas for a(2) the 56 matrices are:
  {
    {{0, 1}, {1, 0}}, {{0, 1}, {1, 1}},
    {{0, 1}, {1, 2}}, {{0, 1}, {2, 0}},
    {{0, 1}, {2, 1}}, {{0, 1}, {2, 2}},
    {{0, 2}, {1, 0}}, {{0, 2}, {1, 1}},
    {{0, 2}, {1, 2}}, {{0, 2}, {2, 0}},
    {{0, 2}, {2, 1}}, {{0, 2}, {2, 2}},
    {{1, 0}, {0, 1}}, {{1, 0}, {0, 2}},
    {{1, 0}, {1, 1}}, {{1, 0}, {1, 2}},
    {{1, 0}, {2, 1}}, {{1, 0}, {2, 2}},
    {{1, 1}, {0, 1}}, {{1, 1}, {0, 2}},
    {{1, 1}, {1, 0}}, {{1, 1}, {1, 1}},
    {{1, 1}, {1, 2}}, {{1, 1}, {2, 0}},
    {{1, 1}, {2, 1}}, {{1, 1}, {2, 2}},
    {{1, 2}, {0, 1}}, {{1, 2}, {0, 2}},
    {{1, 2}, {1, 0}}, {{1, 2}, {1, 1}},
    {{1, 2}, {1, 2}}, {{1, 2}, {2, 0}},
    {{1, 2}, {2, 1}}, {{1, 2}, {2, 2}},
    {{2, 0}, {0, 1}}, {{2, 0}, {0, 2}},
    {{2, 0}, {1, 1}}, {{2, 0}, {1, 2}},
    {{2, 0}, {2, 1}}, {{2, 0}, {2, 2}},
    {{2, 1}, {0, 1}}, {{2, 1}, {0, 2}},
    {{2, 1}, {1, 0}}, {{2, 1}, {1, 1}},
    {{2, 1}, {1, 2}}, {{2, 1}, {2, 0}},
    {{2, 1}, {2, 1}}, {{2, 1}, {2, 2}},
    {{2, 2}, {0, 1}}, {{2, 2}, {0, 2}},
    {{2, 2}, {1, 0}}, {{2, 2}, {1, 1}},
    {{2, 2}, {1, 2}}, {{2, 2}, {2, 0}},
    {{2, 2}, {2, 1}}, {{2, 2}, {2, 2}}
  }

Andrew Howroyd, Table of n, a(n) for n = 0..30

Cf. A006506 for binary version.

Cf. A028859 for one-dimensional version.

t[m_] := t[m] = Map[ArrayReshape[#, {m, m}] &, Tuples[{0, 1, 2}, m^2]];a[m_] := a[m] = Count[Table[AnyTrue[Flatten[{Table[Equal[0, t[m][[n, a, b]], t[m][[n, a, b + 1]]], {a, 1, m}, {b, 1, m - 1}], Table[Equal[0, t[m][[n, a, b]], t[m][[n, a + 1, b]]], {a, 1, m - 1}, {b, 1, m}]}], TrueQ], {n, 1, 3^(m^2)}], False]; Table[a[n], {n, 1, 3}]

Terms a(5)-a(11) from Andrew Howroyd, Jan 04 2022

cp's OEIS Frontend

A207543 Triangle read by rows, expansion of (1+y*x)/(1-2*y*x+y*(y-1)*x^2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A334966 Numbers k such that the k-th composition in standard order (row k of A066099) has weakly decreasing non-adjacent parts.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A005666 Minimal number of moves for the cyclic variant of the Towers of Hanoi for 3 pegs and n disks, with the final peg two steps away.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A103279 Array read by antidiagonals, generated by the matrix M = [1,1,1;1,N,1;1,1,1].

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

PARI

Formula

A118357 Triangle read by rows: T(n,k) is the number of ternary sequences of length n containing k subsequences 00 (n>=0, 0<=k<=max(0,n-1)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A209239 Number of length n words on {0,1,2} with no four consecutive 0's.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Mathematica

Formula

A209241 3^n times the expected value of the longest run of 0's in all length n words on {0,1,2}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

A350336 Number of n X n ternary matrices with no two adjacent 0's.

A207543 Triangle read by rows, expansion of (1+yx)/(1-2y*x+y(y-1)x^2).