A124696 -id:A124696 - cp's OEIS frontend

A276562 Array read by antidiagonals: T(m,n) = number of m-ary words of length n with cyclically adjacent elements differing by 1 or less.

1, 1, 2, 1, 4, 3, 1, 8, 7, 4, 1, 16, 15, 10, 5, 1, 32, 35, 22, 13, 6, 1, 64, 83, 54, 29, 16, 7, 1, 128, 199, 134, 73, 36, 19, 8, 1, 256, 479, 340, 185, 92, 43, 22, 9, 1, 512, 1155, 872, 481, 236, 111, 50, 25, 10, 1, 1024, 2787, 2254, 1265, 622, 287, 130, 57, 28, 11

Offset: 1

Andrew Howroyd, Apr 15 2017

All rows are linear recurrences with constant coefficients. See PARI script to obtain generating functions.

			Array starts:
   1  1  1   1   1    1    1    1     1     1 ...
   2  4  8  16  32   64  128  256   512  1024 ...
   3  7 15  35  83  199  479 1155  2787  6727 ...
   4 10 22  54 134  340  872 2254  5854 15250 ...
   5 13 29  73 185  481 1265 3361  8993 24193 ...
   6 16 36  92 236  622 1658 4468 12132 33146 ...
   7 19 43 111 287  763 2051 5575 15271 42099 ...
   8 22 50 130 338  904 2444 6682 18410 51052 ...
   9 25 57 149 389 1045 2837 7789 21549 60005 ...
  10 28 64 168 440 1186 3230 8896 24688 68958 ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.

Rows 3-32 are A124696-A124719, A124726, A124783, A124784, A124799, A124803, A124804.

Cf. A188866, A220062, A285280, A285281, A208777, A208721.

T[m_, n_] := Sum[(1 + 2*Cos[j*Pi/(m+1)])^n, {j, 1, m}] // FullSimplify;
Table[T[m-n+1, n], {m, 1, 11}, {n, m, 1, -1}] // Flatten (* Jean-François Alcover, Jun 06 2017 *)

\\ from Knopfmacher et al.
ChebyshevU(n,x) = sum(i=0, n/2, 2*poltchebi(n-2*i,x)) + (n%2-1);
RowGf(k,x) = 1 + (k*x*(1+3*x) - 2*(k+1)*x*subst(ChebyshevU(k-1,z)/ChebyshevU(k,z),z,(1-x)/(2*x)))/((1+x)*(1-3*x));
a(m,n)=Vec(RowGf(m,x)+O(x^(n+1)))[n+1];
for(m=1, 10, print(RowGf(m,x)));
for(m=1, 10, for(n=1, 9, print1( a(m,n), ", ") ); print(); );

T(m, n) = Sum_{j=1..m} (1 + 2*cos(j*pi/(m+1)))^n. - Andrew Howroyd, Apr 15 2017

A208772 Number of n-bead necklaces labeled with numbers 1..3 not allowing reversal, with no adjacent beads differing by more than 1.

Original entry on oeis.org

3, 5, 7, 12, 19, 39, 71, 152, 315, 685, 1479, 3294, 7283, 16359, 36791, 83312, 189123, 431393, 986247, 2262308, 5200851, 11985863, 27676615, 64034954, 148406243, 344507805, 800902879, 1864502926, 4346071603, 10142619039, 23696518919, 55420734752, 129742923475, 304014655205, 712985901943, 1673486556648

Offset: 1

R. H. Hardin, Mar 01 2012

nonn

Allowing arbitrary differences between the first and last bead gives A215327. [Joerg Arndt, Aug 08 2012]

			All solutions for n=4:
..1....2....2....2....1....1....1....3....2....1....2....1
..2....2....3....2....1....2....1....3....3....2....2....1
..1....3....2....2....2....3....1....3....3....2....2....1
..2....3....3....3....2....2....1....3....3....2....2....2

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Arnold Knopfmacher, Toufik Mansour, Augustine Munagi, Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.

Column 3 of A208777.

Cf. A215335 (cyclically smooth Lyndon words with 3 colors).

sn[n_, k_] := 1/n*Sum[ Sum[ EulerPhi[j]*(1 + 2*Cos[i*Pi/(k + 1)])^(n/j), {j, Divisors[n]}], {i, 1, k}]; Table[sn[n, 3], {n, 1, 36}] // FullSimplify (* Jean-François Alcover, Oct 31 2017, after Joerg Arndt *)

/* from the Knopfmacher et al. reference */
default(realprecision,99); /* using floats */
sn(n,k)=1/n*sum(i=1,k,sumdiv(n,j,eulerphi(j)*(1+2*cos(i*Pi/(k+1)))^(n/j)));
vector(66,n, round(sn(n,3)) )
/* Joerg Arndt, Aug 09 2012 */

a(n) = Sum_{ d | n } A215335(d). - Joerg Arndt, Aug 13 2012

a(n) = (1/n) * Sum_{d | n} totient(n/d) * A124696(n). - Andrew Howroyd, Mar 18 2017

A124697 Number of base 4 circular n-digit numbers with adjacent digits differing by 1 or less.

Original entry on oeis.org

1, 4, 10, 22, 54, 134, 340, 872, 2254, 5854, 15250, 39802, 104004, 271964, 711490, 1861862, 4873054, 12755614, 33391060, 87413152, 228841254, 599099054, 1568437210, 4106182322, 10750060804, 28143920884, 73681573690, 192900592822, 505019869254, 1322158472054

Offset: 0

R. H. Hardin, Dec 28 2006

[Empirical] a(base,n)=a(base-1,n)+A002426(n+1) for base>=1.int(n/2)+1

a(n) = T(n, 4) where T(n, k) = Sum_{j=1..k} (1+2*cos(j*Pi/(k+1)))^n. These are the number of smooth cyclic words of length n over the alphabet {1,2,3,4}. See theorem 3.3 in Knopfmacher and others, reference in A124696. - Peter Luschny, Aug 13 2012

Colin Barker, Table of n, a(n) for n = 0..1000
OEIS Wiki, Number of base k circular n-digit numbers with adjacent digits differing by d or less
Index entries for linear recurrences with constant coefficients, signature (4,-3,-2,1).

Cf. A000032, A005248, A056014.

LinearRecurrence[{4,-3,-2,1},{1,4,10,22,54},30] (* Harvey P. Dale, Oct 14 2016 *)

Vec(-(3*x^4-4*x^3-3*x^2+1)/((x^2-3*x+1)*(x^2+x-1)) + O(x^40)) \\ Colin Barker, Jul 19 2015

G.f.: A(x) = (3*x^4-4*x^3-3*x^2+1) / ((x^2-3*x+1)*(1-x-x^2)). - Colin Barker, Jul 19 2015
From Peter Bala, Nov 08 2022: (Start)
a(n) = Lucas(n) + Lucas(2*n) = A000032(n) + A005248(n) for n >= 1.
A(x) = 1 + x*B'(x)/B(x), where B(x) = 1/((1 - x - x^2)*(1 - 3*x + x^2)) = 1 + 4*x + 13*x^2 + 38*x^3 + ... has integral coefficients. See A056014.
It follows that the Gauss congruences hold: a(n*p^r) == a(n*p^(r-1)) (mod p^r) for all primes p and positive integers n and r. (End)

A124698 Number of base 5 circular n-digit numbers with adjacent digits differing by 1 or less.

Original entry on oeis.org

1, 5, 13, 29, 73, 185, 481, 1265, 3361, 8993, 24193, 65345, 177025, 480641, 1307137, 3559169, 9699841, 26452481, 72173569, 196989953, 537802753, 1468536833, 4010582017, 10954043393, 29920862209, 81733033985, 223274237953

Offset: 0

R. H. Hardin, Dec 28 2006

[Empirical] a(base,n)=a(base-1,n)+A002426(n+1) for base>=1.int(n/2)+1.

a(n) = T(n, 5) where T(n, k) = Sum_{j=1..k} (1+2*cos(j*Pi/(k+1)))^n. These are the number of smooth cyclic words of length n over the alphabet {1,2,..,5}. See theorem 3.3 in Knopfmacher and others, reference in A124696. - Peter Luschny, Aug 13 2012

OEIS Wiki, Number of base k circular n-digit numbers with adjacent digits differing by d or less

Conjectures from Colin Barker, Jun 04 2017: (Start)
G.f.: (1 - 6*x^2 - 4*x^3 + 12*x^4) / ((1 - x)*(1 - 2*x)*(1 - 2*x - 2*x^2)).
a(n) = 5*a(n-1) - 6*a(n-2) - 2*a(n-3) + 4*a(n-4) for n>4.
(End)

A124726 Number of base 27 circular n-digit numbers with adjacent digits differing by 1 or less.

Original entry on oeis.org

1, 27, 79, 183, 491, 1307, 3583, 9911, 27715, 78051, 221159, 629711, 1800371, 5165187, 14862871, 42878543, 123982195, 359207987, 1042568407, 3030781151, 8823230131, 25719643811, 75061264951, 219298798031, 641338650427

Offset: 0

R. H. Hardin, Dec 28 2006

[Empirical] a(base,n)=a(base-1,n)+A002426(n+1) for base>=1.int(n/2)+1

a(n) = T(n, 27) where T(n, k) = Sum_{j=1..k} (1+2*cos(j*Pi/(k+1)))^n. These are the number of smooth cyclic words of length n over the alphabet {1,2,..,27}. See theorem 3.3 in Knopfmacher and others, reference in A124696. - Peter Luschny, Aug 13 2012

OEIS Wiki, Number of base k circular n-digit numbers with adjacent digits differing by d or less

Edited by Charles R Greathouse IV, Aug 05 2010

A124699 Number of base 6 circular n-digit numbers with adjacent digits differing by 1 or less.

Original entry on oeis.org

1, 6, 16, 36, 92, 236, 622, 1658, 4468, 12132, 33146, 90998, 250802, 693426, 1922118, 5339006, 14854932, 41387764, 115438672, 322267784, 900314242, 2516648618, 7038066876, 19690060024, 55102545322, 154241612986

Offset: 0

R. H. Hardin, Dec 28 2006

[Empirical] a(base,n)=a(base-1,n)+A002426(n+1) for base>=1.int(n/2)+1

a(n) = T(n, 6) where T(n, k) = Sum_{j=1..k} (1+2*cos(j*Pi/(k+1)))^n. These are the number of smooth cyclic words of length n over the alphabet {1,2,..,6}. See theorem 3.3 in Knopfmacher and others, reference in A124696. - Peter Luschny, Aug 13 2012

OEIS Wiki, Number of base k circular n-digit numbers with adjacent digits differing by d or less

Conjectures from Colin Barker, Jun 04 2017: (Start)
G.f.: (1 - 10*x^2 + 27*x^4 - 8*x^5 - 5*x^6) / ((1 - 2*x - x^2 + x^3)*(1 - 4*x + 3*x^2 + x^3)).
a(n) = 6*a(n-1) - 10*a(n-2) + 9*a(n-4) - 2*a(n-5) - a(n-6) for n>6.
(End)

A124700 Number of base 7 circular n-digit numbers with adjacent digits differing by 1 or less.

Original entry on oeis.org

1, 7, 19, 43, 111, 287, 763, 2051, 5575, 15271, 42099, 116651, 324591, 906367, 2538331, 7126403, 20049671, 56509639, 159514963, 450865067, 1275778031, 3613401695, 10242581819, 29053799555, 82461727687, 234163952487

Offset: 0

R. H. Hardin, Dec 28 2006

[Empirical] a(base,n)=a(base-1,n)+A002426(n+1) for base>=1.int(n/2)+1.

a(n) = T(n, 7) where T(n, k) = Sum_{j=1..k} (1+2*cos(j*Pi/(k+1)))^n. These are the number of smooth cyclic words of length n over the alphabet {1,2,..,7}. See theorem 3.3 in Knopfmacher and others, reference in A124696. - Peter Luschny, Aug 13 2012

OEIS Wiki, Number of base k circular n-digit numbers with adjacent digits differing by d or less

G.f.: (1 - 2*x)*(1 + 2*x - 11*x^2 - 12*x^3 + 21*x^4 + 6*x^5 - 3*x^6) / ((1 - x)*(1 - 2*x - x^2)*(1 - 4*x + 2*x^2 + 4*x^3 - x^4)) (conjectured). - Colin Barker, Jun 03 2017

A124719 Number of base 26 circular n-digit numbers with adjacent digits differing by 1 or less.

Original entry on oeis.org

1, 26, 76, 176, 472, 1256, 3442, 9518, 26608, 74912, 212206, 604058, 1726582, 4952246, 14246644, 41090936, 118785568, 344073056, 998415598, 2901784298, 8445850762, 24614293082, 71820129424, 209785569908, 613390314046

Offset: 0

R. H. Hardin, Dec 28 2006

[Empirical] a(base,n)=a(base-1,n)+A002426(n+1) for base>=1.int(n/2)+1

a(n) = T(n, 26) where T(n, k) = Sum_{j=1..k} (1+2*cos(j*Pi/(k+1)))^n. These are the number of smooth cyclic words of length n over the alphabet {1,2,..,26}. See theorem 3.3 in Knopfmacher and others, reference in A124696. - Peter Luschny, Aug 13 2012

OEIS Wiki, Number of base k circular n-digit numbers with adjacent digits differing by d or less

A124783 Number of base 28 circular n-digit numbers with adjacent digits differing by 1 or less.

Original entry on oeis.org

1, 28, 82, 190, 510, 1358, 3724, 10304, 28822, 81190, 230112, 655364, 1874160, 5378128, 15479098, 44666150, 129178822, 374342918, 1086721216, 3159778004, 9200609500, 26824994540, 78302400478, 228812026154, 669286986808

Offset: 0

R. H. Hardin, Dec 28 2006

[Empirical] a(base,n)=a(base-1,n)+A002426(n+1) for base>=1.int(n/2)+1

a(n) = T(n, 28) where T(n, k) = Sum_{j=1..k} (1+2*cos(j*Pi/(k+1)))^n. These are the number of smooth cyclic words of length n over the alphabet {1,2,..,28}. See theorem 3.3 in Knopfmacher and others, reference in A124696. - Peter Luschny, Aug 13 2012

OEIS Wiki, Number of base k circular n-digit numbers with adjacent digits differing by d or less

A124784 Number of base 29 circular n-digit numbers with adjacent digits differing by 1 or less.

Original entry on oeis.org

1, 29, 85, 197, 529, 1409, 3865, 10697, 29929, 84329, 239065, 681017, 1947949, 5591069, 16095325, 46453757, 134375449, 389477849, 1130874025, 3288774857, 9577988869, 27930345269, 81543536005, 238325254277, 697235323189

Offset: 0

R. H. Hardin, Dec 28 2006

[Empirical] a(base,n)=a(base-1,n)+A002426(n+1) for base>=1.int(n/2)+1

a(n) = T(n, 29) where T(n, k) = Sum_{j=1..k} (1+2*cos(j*Pi/(k+1)))^n. These are the number of smooth cyclic words of length n over the alphabet {1,2,..,29}. See theorem 3.3 in Knopfmacher and others, reference in A124696. - Peter Luschny, Aug 13 2012

OEIS Wiki, Number of base k circular n-digit numbers with adjacent digits differing by d or less

cp's OEIS Frontend

A276562 Array read by antidiagonals: T(m,n) = number of m-ary words of length n with cyclically adjacent elements differing by 1 or less.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A208772 Number of n-bead necklaces labeled with numbers 1..3 not allowing reversal, with no adjacent beads differing by more than 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A124697 Number of base 4 circular n-digit numbers with adjacent digits differing by 1 or less.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A124698 Number of base 5 circular n-digit numbers with adjacent digits differing by 1 or less.

Views

Author

Keywords

Comments

Links

Formula

A124726 Number of base 27 circular n-digit numbers with adjacent digits differing by 1 or less.

Views

Author

Keywords

Comments

Links

Extensions

A124699 Number of base 6 circular n-digit numbers with adjacent digits differing by 1 or less.

Views

Author

Keywords

Comments

Links

Formula

A124700 Number of base 7 circular n-digit numbers with adjacent digits differing by 1 or less.

Views

Author

Keywords

Comments

Links

Formula

A124719 Number of base 26 circular n-digit numbers with adjacent digits differing by 1 or less.

Views

Author

Keywords

Comments

Links

A124783 Number of base 28 circular n-digit numbers with adjacent digits differing by 1 or less.

Views

Author

Keywords

Comments

Links

A124784 Number of base 29 circular n-digit numbers with adjacent digits differing by 1 or less.

Views

Author

Keywords