A126360 -id:A126360 - cp's OEIS frontend

A126501 Number of n-tuples of numbers [0..5] (leading zeros allowed) in which adjacent digits differ by 4 or less.

1, 6, 34, 194, 1106, 6306, 35954, 204994, 1168786, 6663906, 37994674, 216628994, 1235123666, 7042134306, 40151166194, 228924368194, 1305226505746, 7441830001506, 42430056030514, 241917600158594, 1379308224915026

Offset: 0

R. H. Hardin, Dec 28 2006

For n>=1, a(n) equals the numbers of words of length n-1 on alphabet {0,1,...,5} containing no subwords 00 and 11. - Milan Janjic, Jan 31 2015

See PARI script for proof of g.f. - Andrew Howroyd, Apr 15 2017

Index entries for linear recurrences with constant coefficients, signature (5, 4).

Cf. Base 6 differing by three or less A126474, two or less A126393, one or less A126360.

LinearRecurrence[{5, 4}, {1, 6}, 21] (* Jean-François Alcover, Oct 07 2017 *)

\\ Proof of generating function
TransferGf(m,u,t,v,z)=vector(m,i,u(i))*matsolve(matid(m)-z*matrix(m,m,i,j,t(i,j)),vectorv(m,i,v(i)));
RowGf(d,m,z)=1+z*TransferGf(m, i->1, (i,j)->abs(i-j)<=d, j->1, z);
print(RowGf(4,6,x)); \\ Andrew Howroyd, Apr 15 2017

[Empirical] a(base,n) = a(base-1,n)+9^(n-1) for base>=4n-3; a(base,n) = a(base-1,n)+9^(n-1)-2 when base=4n-4.
From Philippe Deléham, Mar 24 2012: (Start)
G.f.: (1+x)/(1-5*x-4*x^2).
a(n) = 5*a(n-1) + 4*a(n-2), a(0) = 1, a(1) = 6.
a(n) = Sum_{k, 0<=k<=n} A054458(n,k)*3^k. (End)
Conjecture: a(n) = (2^(-1-n)*((5-sqrt(41))^n*(-7+sqrt(41)) + (5+sqrt(41))^n*(7+sqrt(41)))) / sqrt(41). - Colin Barker, Jan 20 2017

A188866 T(n,k) is the number of n X k binary arrays without the pattern 0 1 diagonally, vertically or antidiagonally.

Original entry on oeis.org

2, 4, 3, 8, 7, 4, 16, 17, 10, 5, 32, 41, 26, 13, 6, 64, 99, 68, 35, 16, 7, 128, 239, 178, 95, 44, 19, 8, 256, 577, 466, 259, 122, 53, 22, 9, 512, 1393, 1220, 707, 340, 149, 62, 25, 10, 1024, 3363, 3194, 1931, 950, 421, 176, 71, 28, 11, 2048, 8119, 8362, 5275, 2658, 1193, 502, 203, 80, 31, 12

Offset: 1

R. H. Hardin, Apr 12 2011

Number of 0..n strings of length k and adjacent elements differing by one or less. (See link for bijection.) Equivalently, number of base (n+1) k digit numbers with adjacent digits differing by one or less. - Andrew Howroyd, Mar 30 2017
All rows are linear recurrences with constant coefficients. See PARI script to obtain generating functions. - Andrew Howroyd, Apr 15 2017
Equivalently, the number of walks of length k-1 on the path graph P_{n+1} with a loop added at each vertex. - Pontus von Brömssen, Sep 08 2021

			Table starts:
   2  4  8  16  32   64  128   256   512   1024   2048    4096    8192    16384
   3  7 17  41  99  239  577  1393  3363   8119  19601   47321  114243   275807
   4 10 26  68 178  466 1220  3194  8362  21892  57314  150050  392836  1028458
   5 13 35  95 259  707 1931  5275 14411  39371 107563  293867  802859  2193451
   6 16 44 122 340  950 2658  7442 20844  58392 163594  458356 1284250  3598338
   7 19 53 149 421 1193 3387  9627 27383  77923 221805  631469 1797957  5119593
   8 22 62 176 502 1436 4116 11814 33942  97582 280676  807574 2324116  6689624
   9 25 71 203 583 1679 4845 14001 40503 117263 339699  984515 2854281  8277153
  10 28 80 230 664 1922 5574 16188 47064 136946 398746 1161634 3385486  9869934
  11 31 89 257 745 2165 6303 18375 53625 156629 457795 1338779 3916897 11463989
Some solutions for 5 X 3:
  1 1 1   1 1 1   1 1 1   1 1 1   0 0 0   1 1 1   1 1 1
  1 1 1   0 0 1   0 1 1   1 1 1   0 0 0   1 0 0   1 0 1
  0 0 0   0 0 0   0 0 1   1 1 1   0 0 0   0 0 0   0 0 0
  0 0 0   0 0 0   0 0 0   1 1 0   0 0 0   0 0 0   0 0 0
  0 0 0   0 0 0   0 0 0   0 0 0   0 0 0   0 0 0   0 0 0

R. H. Hardin, Table of n, a(n) for n = 1..1741
Andrew Howroyd, Bijection with 0..n strings of length k.
Arnold Knopfmacher, Toufik Mansour, Augustine Munagi and Helmut Prodinger, Smooth words and Chebyshev polynomials, arXiv:0809.0551v1 [math.CO], 2008.

Columns 2..8 are A016777, A017257(n-1), A188861-A188865.
Rows 2..31 are A001333(n+1), A126358, A057960(n+1), A126360, A002714, A126362-A126386.
Main diagonal is A188860.
Cf. A276562, A220062.

rows = 11; rowGf[n_, x_] = 1 + (x*(n - (3*n + 2)*x) + (2*x^2)*(1 + ChebyshevU[n-1, (1-x)/(2*x)])/ChebyshevU[n, (1-x)/(2*x)])/(1-3*x)^2;
row[n_] := rowGf[n+1, x] + O[x]^(rows+1) // CoefficientList[#, x]& // Rest; T = Array[row, rows]; Table[T[[n-k+1, k]], {n, 1, rows}, {k, n, 1, -1}] // Flatten (* Jean-François Alcover, Oct 07 2017, after Andrew Howroyd *)

\\ from Knopfmacher et al.
RowGf(k, x='x) = my(z=(1-x)/(2*x)); 1 + (x*(k-(3*k+2)*x) + (2*x^2)*(1+polchebyshev(k-1, 2, z))/polchebyshev(k, 2, z))/(1-3*x)^2;
T(n,k) = {polcoef(RowGf(n+1) + O(x*x^k),k)}
for(n=1, 10, print(Vec(RowGf(n+1) + O(x^11)))) \\ Andrew Howroyd, Apr 15 2017 [updated Mar 13 2021]

Empirical: T(n,1) = n + 1.
Empirical: T(n,2) = 3*n + 1.
Empirical: T(n,3) = 9*n - 1.
Empirical: T(n,4) = 27*n - 13 for n > 1.
Empirical: T(n,5) = 81*n - 65 for n > 2.
Empirical: T(n,6) = 243*n - 265 for n > 3.
Empirical: T(n,7) = 729*n - 987 for n > 4.
Empirical: T(n,8) = 2187*n - 3495 for n > 5.
Empirical: T(1,k) = 2*T(1,k-1).
Empirical: T(2,k) = 2*T(2,k-1) + T(2,k-2).
Empirical: T(3,k) = 3*T(3,k-1) - T(3,k-2).
Empirical: T(4,k) = 3*T(4,k-1) - 2*T(4,k-3).
Empirical: T(5,k) = 4*T(5,k-1) - 3*T(5,k-2) -   T(5,k-3).
Empirical: T(6,k) = 4*T(6,k-1) - 2*T(6,k-2) - 4*T(6,k-3) +   T(6,k-4).
Empirical: T(7,k) = 5*T(7,k-1) - 6*T(7,k-2) -   T(7,k-3) + 2*T(7,k-4).
Empirical: T(8,k) = 5*T(8,k-1) - 5*T(8,k-2) - 5*T(8,k-3) + 5*T(8,k-4) + T(8,k-5).

A126393 Number of base 6 n-digit numbers with adjacent digits differing by two or less.

Original entry on oeis.org

1, 6, 24, 100, 418, 1748, 7310, 30570, 127842, 534628, 2235784, 9349922, 39100844, 163517514, 683820978, 2859700582, 11959105792, 50012302772, 209148616298, 874647662172, 3657726962214, 15296406894730, 63968706878962

Offset: 0

R. H. Hardin, Dec 28 2006

a(base,n) = a(base-1,n) + 5^(n-1) for base >= 2*n - 1.

a(base,n) = a(base-1,n) + 5^(n-1) - 2 when base = 2*(n-1).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Sergey Kitaev and Jeffrey Remmel, (a,b)-rectangle patterns in permutations and words, arXiv:1304.4286 [math.CO], 2013.
Index entries for linear recurrences with constant coefficients, signature (4,1,-1).

Cf. Base 6 differing by one or less A126360.

Cf. A364705.

I:=[1,6,24,100]; [n le 4 select I[n] else 4*Self(n-1) +Self(n-2) -Self(n-3): n in [1..41]]; // G. C. Greubel, Aug 08 2023

LinearRecurrence[{4,1,-1}, {1,6,24,100}, 41] (* G. C. Greubel, Aug 08 2023 *)

@CachedFunction
def a(n): # A126393
    if (n<4): return (1,6,24,100)[n]
    else: return 4*a(n-1) +a(n-2) -a(n-3)
[a(n) for n in range(41)] # G. C. Greubel, Aug 08 2023

G.f.: 1 + 2*x*(3-x^2)/(1-4*x-x^2+x^3). - R. J. Mathar, Jun 06 2013

a(n) = [n=0] + 6*A364705(n) - 2*A364705(n-2). - G. C. Greubel, Aug 08 2023

A126474 Number of arrays in [1..6]^n with adjacent elements differing by three or less.

Original entry on oeis.org

1, 6, 30, 154, 788, 4034, 20650, 105708, 541122, 2770018, 14179796, 72586754, 371573530, 1902094812, 9736874082, 49843318162, 255149275268, 1306115946338, 6686042370634, 34226029248972, 175203956722818

Offset: 0

R. H. Hardin, Dec 27 2006

[Empirical] a(base,n)=a(base-1,n)+7^(n-1) for base>=3n-2; a(base,n)=a(base-1,n)+7^(n-1)-2 when base=3n-3

Original name: Number of base 6 n-digit numbers with adjacent digits differing by three or less.

			For n=2 the a(2)=30 solutions are [1, 1], [1, 2], [1, 3], [1, 4], [2, 1], [2, 2], [2, 3], [2, 4], [2, 5], [3, 1], [3, 2], [3, 3], [3, 4], [3, 5], [3, 6], [4, 1], [4, 2], [4, 3], [4, 4], [4, 5], [4, 6], [5, 2], [5, 3], [5, 4], [5, 5], [5, 6], [6, 3], [6, 4], [6, 5], [6, 6]. - _Robert Israel_, Jan 23 2018

Robert Israel, Table of n, a(n) for n = 0..1408

Cf. Base 6 differing by two or less A126393, one or less A126360.

f:= gfun:-rectoproc({a(n) = 5*a(n-1) + a(n-2) - 2*a(n-3),a(0)=1,a(1)=6,a(2)=30},a(n),remember):
map(f, [$0..30]); # Robert Israel, Jan 23 2018

Conjectures from Colin Barker, Jan 20 2017: (Start)
a(n) = 5*a(n-1) + a(n-2) - 2*a(n-3) for n>2.
G.f.: (1 + x - x^2) / (1 - 5*x - x^2 + 2*x^3).
(End)
From Robert Israel, Jan 23 2018: (Start)
a(n) = e^T M^(n-1) e where e = [1,1,1,1,1,1]^T and M is the 6 X 6 matrix with entries M(i,j) = 1 if |i-j|<=3, 0 otherwise.
The fact that (M^3-5*M^2-M+2I) e = 0 implies Colin Barker's recursion, and the G.f. follows. (End)

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

Original entry on oeis.org

6, 11, 16, 30, 48, 100, 182, 404, 850, 1996, 4614, 11391, 28002, 71236, 181710, 471437, 1227712, 3226816, 8509930, 22564205, 60002088, 160113626, 428273964, 1148410792, 3085474406, 8305718893, 22394409228, 60474491712, 163531569910, 442782412569

Offset: 1

R. H. Hardin, Mar 01 2012

nonn

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

Andrew Howroyd, Table of n, a(n) for n = 1..100

Column 6 of A208721.

Cf. A208775, A126360.

a(2n+1) = (1/2) * (A208775(2n+1) + A126360(n+1)). - Andrew Howroyd, Mar 03 2017

a(2n) = (1/2) * A208775(2n) + (1/4) * (A126360(n) + A126360(n+1)). - Andrew Howroyd, Mar 03 2017

a(26)-a(30) from Andrew Howroyd, Mar 03 2017

A296449 Triangle I(m,n) read by rows: number of perfect lattice paths on the m*n board.

Original entry on oeis.org

1, 2, 4, 3, 7, 17, 4, 10, 26, 68, 5, 13, 35, 95, 259, 6, 16, 44, 122, 340, 950, 7, 19, 53, 149, 421, 1193, 3387, 8, 22, 62, 176, 502, 1436, 4116, 11814, 9, 25, 71, 203, 583, 1679, 4845, 14001, 40503, 10, 28, 80, 230, 664, 1922, 5574, 16188, 47064, 136946, 11, 31, 89, 257, 745, 2165, 6303, 18375, 53625, 156629, 457795

Offset: 1

R. J. Mathar, Dec 13 2017

			Triangle begins:
   1;
   2,  4;
   3,  7, 17;
   4, 10, 26,  68;
   5, 13, 35,  95, 259;
   6, 16, 44, 122, 340,  950;
   7, 19, 53, 149, 421, 1193, 3387;
   8, 22, 62, 176, 502, 1436, 4116, 11814;
   9, 25, 71, 203, 583, 1679, 4845, 14001, 40503;
  10, 28, 80, 230, 664, 1922, 5574, 16188, 47064, 136946;

D. Yaqubi, M. Farrokhi D. G., and H. Ghasemian Zoeram, Lattice paths inside a table, I, arXiv:1612.08697 [math.CO], 2016-2017, array I(m,n).

Cf. A081113 (diagonal), A000079 (2nd row), A001333 (3rd row), A126358, A057960, A126360, A002714, A126362, A188866.

Inm := proc(n,m)
    if m >= n then
        (n+2)*3^(n-2)+(m-n)*add(A005773(i)*A005773(n-i),i=0..n-1)
            +2*add((n-k-2)*3^(n-k-3)*A001006(k),k=0..n-3) ;
    else
        0 ;
    end if;
end proc:
for m from 1 to 13 do
for n from 1 to m do
    printf("%a,",Inm(n,m)) ;
end do:
printf("\n") ;
end do:
# Second program:
A296449row := proc(n) local gf, ser;
gf := n -> 1 + (x*(n - (3*n + 2)*x) + (2*x^2)*(1 +
ChebyshevU(n - 1, (1 - x)/(2*x))) / ChebyshevU(n, (1 - x)/(2*x)))/(1 - 3*x)^2;
ser := n -> series(expand(gf(n)), x, n + 1);
seq(coeff(ser(n), x, k), k = 1..n) end:
for n from 0 to 11 do A296449row(n) od; # Peter Luschny, Sep 07 2021

(* b = A005773 *) b[0] = 1; b[n_] := Sum[k/n*Sum[Binomial[n, j] * Binomial[j, 2*j - n - k], {j, 0, n}], {k, 1, n}];
(* c = A001006 *) c[0] = 1; c[n_] := c[n] = c[n-1] + Sum[c[k] * c[n-2-k], {k, 0, n-2}];
Inm[n_, m_] := If[m >= n, (n + 2)*3^(n - 2) + (m - n)*Sum[b[i]*b[n - i], {i, 0, n - 1}] + 2*Sum[(n - k - 2)*3^(n - k - 3)*c[k], {k, 0, n-3}], 0];
Table[Inm[n, m], {m, 1, 13}, {n, 1, m}] // Flatten (* Jean-François Alcover, Jan 23 2018, adapted from first Maple program. *)

I(m,n) = (n+2)*3^(n-2) + (m-n)*Sum_{i=0..n-1} A005773(i)*A005773(n-i) + 2*Sum_{k=0..n-3} (n-k-2)*3^(n-k-3)*A001006(k). [Yaqubi Corr. 2.10]

I(m,n) = A188866(m-1,n) for m > 1. - Pontus von Brömssen, Sep 06 2021

cp's OEIS Frontend

A126501 Number of n-tuples of numbers [0..5] (leading zeros allowed) in which adjacent digits differ by 4 or less.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A188866 T(n,k) is the number of n X k binary arrays without the pattern 0 1 diagonally, vertically or antidiagonally.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A126393 Number of base 6 n-digit numbers with adjacent digits differing by two or less.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A126474 Number of arrays in [1..6]^n with adjacent elements differing by three or less.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions

A296449 Triangle I(m,n) read by rows: number of perfect lattice paths on the m*n board.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A354548 Number of edges in the graph of continuous discrete sections for a trivial bundle in a total space of the fiber bundle of size n.

Views

Author

Keywords

Comments

Links

Crossrefs