A277666 -id:A277666 - cp's OEIS frontend

A095263 a(n+3) = 3a(n+2) - 2a(n+1) + a(n).

1, 3, 7, 16, 37, 86, 200, 465, 1081, 2513, 5842, 13581, 31572, 73396, 170625, 396655, 922111, 2143648, 4983377, 11584946, 26931732, 62608681, 145547525, 338356945, 786584466, 1828587033, 4250949112, 9882257736, 22973462017, 53406819691

Offset: 1

Gary W. Adamson, May 31 2004

a(n+1) = number of n-tuples over {0,1,2} without consecutive digits. For the general case see A096261.
Diagonal sums of Riordan array (1/(1-x)^3, x/(1-x^3)), A127893. - Paul Barry, Jan 07 2008
The signed variant (-1)^(n+1)*a(n+1) is the bottom right entry of the n-th power of the matrix [[0,1,0],[0,0,1],[-1,-2,-3]]. - Roger L. Bagula, Jul 01 2007
a(n) is the number of generalized compositions of n+1 when there are i^2/2-i/2 different types of i, (i=1,2,...). - Milan Janjic, Sep 24 2010
Dedrickson (Section 4.1) gives a bijection between colored compositions of n, where each part k has one of binomial(k,2) colors, and 0,1,2 strings of length n-2 without sequential digits (i.e., avoiding 01 and 12). Cf. A052529. - Peter Bala, Sep 17 2013
Except for the initial 0, this is the p-INVERT of (1,1,1,1,1,...) for p(S) = 1 - S^2 - S^3; see A291000. - Clark Kimberling, Aug 24 2017
For n>1, a(n-1) is the number of ways to split [n] into an unspecified number of intervals and then choose 2 blocks (i.e., subintervals) from each interval.  For example, for n=6, a(5)=37 since the number of ways to split [6] into intervals and then select 2 blocks from each interval is C(6,2) + C(4,2)*C(2,2) + C(3,2)*C(3,2) + C(2,2)*C(4,2) + C(2,2)*C(2,2)*C(2,2). - Enrique Navarrete, May 20 2022

			a(9) = 1081 = 3*465 - 2*200 + 86.
M^9 * [1 0 0] = [a(7) a(8) a(9)] = [200 465 1081].
G.f. = x + 3*x^2 + 7*x^3 + 16*x^4 + 37*x^5 + 86*x^6 + 200*x^7 + ...

Vincenzo Librandi, Table of n, a(n) for n = 1..1000
C. R. Dedrickson III, Compositions, Bijections, and Enumerations Thesis, Jack N. Averitt College of Graduate Studies, Georgia Southern University, 2012.
Index entries for linear recurrences with constant coefficients, signature (3,-2,1).

Cf. A000931, A010912, A034943, A052529, A052530, A097550, A137531.
Cf. A052921 (first differences), A137229 (partial sums).
Column k=3 of A277666.

I:=[1,3,7]; [n le 3 select I[n] else 3*Self(n-1) -2*Self(n-2) +Self(n-3): n in [1..30]]; // G. C. Greubel, Apr 12 2021

A:= gfun:-rectoproc({a(n+3)=3*a(n+2)-2*a(n+1)+a(n),a(1)=1,a(2)=3,a(3)=7},a(n),remember):
seq(A(n),n=1..100); # Robert Israel, Sep 15 2014

a[1]=1; a[2]=3; a[3]=7; a[n_]:= a[n]= 3a[n-1] -2a[n-2] +a[n-3]; Table[a[n], {n, 22}] (* Or *)
a[n_]:= (MatrixPower[{{0,1,2,3}, {1,2,3,0}, {2,3,0,1}, {3,0,1,2}}, n].{{1}, {0}, {0}, {0}})[[2, 1]]; Table[ a[n], {n, 22}] (* Robert G. Wilson v, Jun 16 2004 *)
RecurrenceTable[{a[1]==1,a[2]==3,a[3]==7,a[n+3]==3a[n+2]-2a[n+1]+a[n]},a,{n,30}] (* Harvey P. Dale, Sep 17 2022 *)

[sum( binomial(n+k+1,3*k+2) for k in (0..(n-1)//2)) for n in (1..30)] # G. C. Greubel, Apr 12 2021

Let M = the 3 X 3 matrix [0 1 0 / 0 0 1 / 1 -2 3]; then M^n *[1 0 0] = [a(n-2) a(n-1) a(n)].
a(n)/a(n-1) tends to 2.3247179572..., an eigenvalue of M and a root of the characteristic polynomial. [Is that constant equal to 1 + A060006? - Michel Marcus, Oct 11 2014] [Yes, the limit is the root of the equation -1 + 2*x - 3*x^2 + x^3 = 0, after substitution x = y + 1 we have the equation for y: -1 - y + y^3 = 0, y = A060006. - Vaclav Kotesovec, Jan 27 2015]
Related to the Padovan sequence A000931 as follows : a(n)=A000931(3n+4). Also the binomial transform of A000931(n+4).
From Paul Barry, Jul 06 2004: (Start)
a(n) = Sum_{k=0..floor((n+1)/2)} binomial(n+k, n-2*k+1).
a(n) = Sum_{k=0..floor((n+1)/2)} binomial(n+k, 3*k-1). (End)
From Paul Barry, Jan 07 2008: (Start)
G.f.: x/(1 -3*x +2*x^2 -x^3).
a(n) = Sum_{k=0..floor(n/2)} binomial(n+k+2,3*k+2).
a(n) = Sum_{k=0..n} binomial(n,k) * Sum_{j=0..floor((k+4)/2)} binomial(j,k-2j+4). (End)
If p[i]=i(i-1)/2 and if A is Hessenberg matrix of order n defined by: A[i,j]=p[j-i+1], (i<=j), A[i,j]=-1, (i=j+1), and A[i,j]=0 otherwise. Then, for n>=2, a(n-1)=det A. - Milan Janjic, May 02 2010
a(n) = A000931(3*n + 4). - Michael Somos, Sep 18 2012

Edited by Paul Barry, Jul 06 2004

Corrected and extended by Robert G. Wilson v, Jun 05 2004

A096261 Number of n-tuples of 0,1,2,3,4,5,6,7,8,9 without consecutive digits.

Original entry on oeis.org

1, 10, 91, 828, 7534, 68552, 623756, 5675568, 51642104, 469892512, 4275561136, 38903414208, 353982925023, 3220897542254, 29307009588171, 266665052127080, 2426390512890816, 22077774624328776, 200886102122914612

Offset: 0

Seppo Mustonen, Aug 01 2004

Sketch of a proof for a general base b >= 2: Let a(n) be the number of n-tuples of 0, 1, ..., b-1 without consecutive digits and s(n,i) the number of them with i (i = 0, 1, ..., b-1) as the last digit. Then it is clear that s(n,i) = a(n-1) - s(n-1, i-1) since when extending a valid n-1-tuple with i those ending with i-1 are not valid as n-tuples.

Thus s(n,0) = a(n-1), s(n,1) = a(n-1) - s(n-1,0) = a(n-1) - a(n-2) and in general s(n,i) = a(n-1) - a(n-2) + a(n-3) - ... + (-1)^i*a(n-i-1), i = 0, 1, ..., b-1. Since a(n) = Sum_{j=0..b-1} s(n,j), we get the recursion formula a(n) = b*a(n-1) -( b-1)*a(n-2) + (b-2)*a(n-3) - ... + (-1)^(b-1)*a(n-b).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (10,-9,8,-7,6,-5,4,-3,2,-1).

Case b=3 is A095263.

Column k=10 of A277666.

R:=PowerSeriesRing(Integers(), 30);
Coefficients(R!( 1/(1-10*x+9*x^2-8*x^3+7*x^4-6*x^5+5*x^6-4*x^7+3*x^8-2*x^9+x^10) )); // G. C. Greubel, Apr 17 2021

A096261:=proc(n,b::nonnegint) local s,i; option remember; if n<0 then RETURN(0) fi; if n=0 then RETURN(1) fi; s:=0; for i from 1 to b do s:=s+(-1)^(i-1)*(b-i+1)*A096261(n-i,b); od; end; seq(A096261(i,10),i=0..20);

a[n_]:= a[n]= If[n<0, 0, If[n==0, 1, 10a[n-1] -9a[n-2] +8a[n-3] -7a[n-4] +6a[n-5] -5a[n-6] +4a[n-7] -3a[n-8] +2a[n-9] -a[n-10] ]]; Table[ a[n], {n,0,25}] (* Robert G. Wilson v, Aug 02 2004 *)
LinearRecurrence[{10,-9,8,-7,6,-5,4,-3,2,-1}, {1,10,91,828,7534,68552,623756, 5675568,51642104,469892512}, 30] (* Harvey P. Dale, Dec 16 2013 *)

def A096261_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( 1/(1-10*x+9*x^2-8*x^3+7*x^4-6*x^5+5*x^6-4*x^7+3*x^8-2*x^9+x^10) ).list()
A096261_list(30) # G. C. Greubel, Apr 17 2021

a(n) = 10*a(n-1) - 9*a(n-2) + 8*a(n-3) - 7*a(n-4) + 6*a(n-5) - 5*a(n-6) + 4*a(n-7) - 3*a(n-8) + 2*a(n-9) - 1*a(n-10), a(0)=1, a(n)=0, for n<0.

G.f.: 1/(1 - 10*x + 9*x^2 - 8*x^3 + 7*x^4 - 6*x^5 + 5*x^6 - 4*x^7 + 3*x^8 - 2*x^9 + x^10). - Colin Barker, Dec 06 2012

More terms from Robert G. Wilson v, Aug 02 2004

A277668 Number of n-length words over a 5-ary alphabet {a_1,a_2,...,a_5} avoiding consecutive letters a_i, a_{i+1}.

Original entry on oeis.org

1, 5, 21, 88, 369, 1547, 6486, 27194, 114017, 478042, 2004299, 8403476, 35233470, 147724276, 619367372, 2596837513, 10887827441, 45649674187, 191396563242, 802473294131, 3364550422879, 14106637106664, 59145260271900, 247979854176461, 1039711513563070

Offset: 0

Alois P. Heinz, Oct 26 2016

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-4,3,-2,1)

Column k=5 of A277666.

Cf. A284840.

a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>,
          <0|0|0|0|1>, <1|-2|3|-4|5>>^n)[5, 5]:
seq(a(n), n=0..30);

LinearRecurrence[{5,-4,3,-2,1},{1,5,21,88,369},30] (* Harvey P. Dale, Oct 08 2017 *)

G.f.: 1/(1 + Sum_{j=1..5} (6-j)*(-x)^j).

A277667 Number of n-length words over a quaternary alphabet {a_1,a_2,...,a_4} avoiding consecutive letters a_i, a_{i+1}.

Original entry on oeis.org

1, 4, 13, 42, 136, 440, 1423, 4602, 14883, 48132, 155660, 503408, 1628033, 5265096, 17027441, 55067134, 178088372, 575941872, 1862609199, 6023720790, 19480850935, 63001517896, 203748351160, 658926832032, 2130984459505, 6891652526348, 22287762039781

Offset: 0

Alois P. Heinz, Oct 26 2016

			a(3) = 42: 000, 002, 003, 020, 021, 022, 030, 031, 032, 033, 100, 102, 103, 110, 111, 113, 130, 131, 132, 133, 200, 202, 203, 210, 211, 213, 220, 221, 222, 300, 302, 303, 310, 311, 313, 320, 321, 322, 330, 331, 332, 333 (using alphabet {0, 1, 2, 3}).

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,-3,2,-1)

Column k=4 of A277666.

a:= n-> (<<0|1|0|0>, <0|0|1|0>, <0|0|0|1>, <-1|2|-3|4>>^n)[4, 4]:
seq(a(n), n=0..30);

G.f.: 1/(1 + Sum_{j=1..4} (5-j)*(-x)^j).

A277669 Number of n-length words over a 6-ary alphabet {a_1,a_2,...,a_6} avoiding consecutive letters a_i, a_{i+1}.

Original entry on oeis.org

1, 6, 31, 160, 826, 4264, 22012, 113632, 586599, 3028182, 15632291, 80698096, 416585304, 2150525528, 11101591924, 57309407232, 295846593873, 1527239790702, 7884023093755, 40699450421136, 210101523661770, 1084600646648368, 5599000626972168, 28903549078371648

Offset: 0

Alois P. Heinz, Oct 26 2016

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (6,-5,4,-3,2,-1)

Column k=6 of A277666.

a:= n-> (<<0|1|0|0|0|0>, <0|0|1|0|0|0>, <0|0|0|1|0|0>,
          <0|0|0|0|1|0>, <0|0|0|0|0|1>, <-1|2|-3|4|-5|6>>^n)[6$2]:
seq(a(n), n=0..30);

G.f.: 1/(1 + Sum_{j=1..6} (7-j)*(-x)^j).

A277670 Number of n-length words over a 7-ary alphabet {a_1,a_2,...,a_7} avoiding consecutive letters a_i, a_{i+1}.

Original entry on oeis.org

1, 7, 43, 264, 1621, 9953, 61112, 375231, 2303939, 14146313, 86859145, 533319959, 3274614074, 20106311704, 123453866991, 758013577995, 4654245334143, 28577324020619, 175466351588409, 1077373112945523, 6615130559166437, 40617267861064920, 249392273325801363

Offset: 0

Alois P. Heinz, Oct 26 2016

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (7,-6,5,-4,3,-2,1)

Column k=7 of A277666.

a:= proc(n) option remember; `if`(n<0, 0, `if`(n=0, 1,
      -add((-1)^j*(8-j)*a(n-j), j=1..7)))
    end:
seq(a(n), n=0..25);

G.f.: 1/(1 + Sum_{j=1..7} (8-j)*(-x)^j).

A277671 Number of n-length words over an 8-ary alphabet {a_1,a_2,...,a_8} avoiding consecutive letters a_i, a_{i+1}.

Original entry on oeis.org

1, 8, 57, 406, 2892, 20600, 146736, 1045216, 7445184, 53032832, 377758463, 2690813426, 19166948203, 136528196220, 972504760052, 6927254109472, 49343562590512, 351479407373632, 2503624937520704, 17833584831080448, 127030508108889857, 904851724611169300

Offset: 0

Alois P. Heinz, Oct 26 2016

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (8,-7,6,-5,4,-3,2,-1)

Column k=8 of A277666.

a:= proc(n) option remember; `if`(n<0, 0, `if`(n=0, 1,
      -add((-1)^j*(9-j)*a(n-j), j=1..8)))
    end:
seq(a(n), n=0..25);

LinearRecurrence[{8,-7,6,-5,4,-3,2,-1},{1,8,57,406,2892,20600,146736,1045216},30] (* Harvey P. Dale, May 15 2018 *)

G.f.: 1/(1 + Sum_{j=1..8} (9-j)*(-x)^j).

A277672 Number of n-length words over a 9-ary alphabet {a_1,a_2,...,a_9} avoiding consecutive letters a_i, a_{i+1}.

Original entry on oeis.org

1, 9, 73, 592, 4801, 38935, 315754, 2560693, 20766637, 168412696, 1365788605, 11076234500, 89825738954, 728466283251, 5907695633935, 47910065991605, 388539722685585, 3150968653039294, 25553638078006016, 207234184444162395, 1680622033979603605

Offset: 0

Alois P. Heinz, Oct 26 2016

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (9,-8,7,-6,5,-4,3,-2,1)

Column k=9 of A277666.

a:= proc(n) option remember; `if`(n<0, 0, `if`(n=0, 1,
      -add((-1)^j*(10-j)*a(n-j), j=1..9)))
    end:
seq(a(n), n=0..25);

LinearRecurrence[{9,-8,7,-6,5,-4,3,-2,1},{1,9,73,592,4801,38935,315754,2560693,20766637},30] (* Harvey P. Dale, Apr 03 2019 *)

G.f.: 1/(1 + Sum_{j=1..9} (10-j)*(-x)^j).

A277673 Number of n-length words over an n-ary alphabet {a_1,a_2,...,a_n} avoiding consecutive letters a_i, a_{i+1}.

Original entry on oeis.org

1, 1, 3, 16, 136, 1547, 22012, 375231, 7445184, 168412696, 4275561136, 120338946469, 3718175865856, 125094920949797, 4551798150123456, 178094082550301368, 7455514741874966528, 332495821030327545527, 15737024371475868676864, 787813565550480151088691

Offset: 0

Alois P. Heinz, Oct 26 2016

nonn

			a(3) = 16: 000, 002, 020, 021, 022, 100, 102, 110, 111, 200, 202, 210, 211, 220, 221, 222 (using ternary alphabet {0, 1, 2}).

Alois P. Heinz, Table of n, a(n) for n = 0..386

Main diagonal of A277666.

b:= proc(n, k) option remember; `if`(n<0, 0, `if`(n=0, 1,
      -add((-1)^j*(k+1-j)*b(n-j, k), j=1..k)))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..25);

b[n_, k_] := b[n, k] = If[n < 0, 0, If[n == 0, 1,
     -Sum[(-1)^j (k+1-j) b[n-j, k], {j, 1, k}]]];
a[n_] := b[n, n];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Nov 02 2021, after Alois P. Heinz *)

a(n) = [x^n] 1/(1+Sum_{j=1..n} (n+1-j)*(-x)^j).

cp's OEIS Frontend

A095263 a(n+3) = 3*a(n+2) - 2*a(n+1) + a(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

Extensions

A096261 Number of n-tuples of 0,1,2,3,4,5,6,7,8,9 without consecutive digits.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

Extensions

A277668 Number of n-length words over a 5-ary alphabet {a_1,a_2,...,a_5} avoiding consecutive letters a_i, a_{i+1}.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A277667 Number of n-length words over a quaternary alphabet {a_1,a_2,...,a_4} avoiding consecutive letters a_i, a_{i+1}.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Formula

A277669 Number of n-length words over a 6-ary alphabet {a_1,a_2,...,a_6} avoiding consecutive letters a_i, a_{i+1}.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A277670 Number of n-length words over a 7-ary alphabet {a_1,a_2,...,a_7} avoiding consecutive letters a_i, a_{i+1}.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Formula

A277671 Number of n-length words over an 8-ary alphabet {a_1,a_2,...,a_8} avoiding consecutive letters a_i, a_{i+1}.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A277672 Number of n-length words over a 9-ary alphabet {a_1,a_2,...,a_9} avoiding consecutive letters a_i, a_{i+1}.

Views

A095263 a(n+3) = 3a(n+2) - 2a(n+1) + a(n).