A126362 -id:A126362 - cp's OEIS frontend

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

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

A048489 a(n) = 7 * 2^n - 6.

Original entry on oeis.org

1, 8, 22, 50, 106, 218, 442, 890, 1786, 3578, 7162, 14330, 28666, 57338, 114682, 229370, 458746, 917498, 1835002, 3670010, 7340026, 14680058, 29360122, 58720250, 117440506, 234881018, 469762042, 939524090, 1879048186

Offset: 0

Clark Kimberling

Number of 3 X n 0-1 matrices avoiding simultaneously the right angled numbered polyomino patterns (ranpp) (00;1), (10;0) and (11;0). An occurrence of a ranpp (xy;z) in a matrix A=(a(i,j)) is a triple (a(i1,j1), a(i1,j2), a(i2,j1)) where i1Sergey Kitev, Nov 13 2004
Row sums of triangle A131115. - N. J. A. Sloane, Nov 10 2007
Equals binomial transform of [1, 7, 7, 7, ...]. - Gary W. Adamson, Apr 28 2008
Number of variations of a Componium barrel which produces n phrases. This sequence describes the variations produced by the Componium, a historical mechanical organ. Another way of describing it is: Number of base 8 n-digit numbers produced by repeating or advancing along this 14-step cycle: (0,1,2,3,4,5,6,7,6,5,4,3,2,1). Subset of A126362. - Jim Bumgardner, Dec 10 2013
a(n) = the sum of the terms in row(n) in a triangle with first column T(n,0)=
1+2*n and diagonal T(n,n)=1+4*n with T(i,j)=T(i-1,j-1) + T(i-1,j). - J. M. Bergot, May 11 2018

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Jim Bumgardner, Variations of the Componium, 2013
S. Kitaev, On multi-avoidance of right angled numbered polyomino patterns, Integers: Electronic Journal of Combinatorial Number Theory 4 (2004), A21, 20pp.
Index entries for linear recurrences with constant coefficients, signature (3,-2).

a(n)=T(6, n), array T given by A048483.
n-th difference of a(n), a(n-1), ..., a(0) is (7, 7, 7, ...).
Cf. A131115.

A048489:=n->7*2^n-6: seq(A048489(n), n=0..40); # Wesley Ivan Hurt, Apr 18 2017

CoefficientList[Series[(1 + 5 x)/((2 x - 1) (x - 1)), {x, 0, 28}], x] (* Michael De Vlieger, May 22 2018 *)
7*2^Range[0,30]-6 (* or *) LinearRecurrence[{3,-2},{1,8},30] (* Harvey P. Dale, May 19 2019 *)

a(n)=7<Charles R Greathouse IV, Dec 10 2013

a(n) = A000079(n)*7-6 = A005009(n)-6. - Omar E. Pol, Dec 21 2008
a(n) = 2*a(n-1)+6 with n>0, a(0)=1. - Vincenzo Librandi, Aug 06 2010
G.f.: ( 1+5*x ) / ( (2*x-1)*(x-1) ). - R. J. Mathar, Oct 21 2012
a(n) = A063757(2*n). - Philippe Deléham, Apr 13 2013

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

Original entry on oeis.org

1, 8, 34, 150, 668, 2986, 13362, 59816, 267802, 1199022, 5368412, 24036226, 107618586, 481846232, 2157395218, 9659418342, 43248619100, 193639305850, 866991400098, 3881825980040, 17380302665002, 77817738944382

Offset: 0

R. H. Hardin, Dec 28 2006

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

Cf. Base 8 differing by one or less A126362.

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

A126476 Number of base 8 n-digit numbers with adjacent digits differing by three or less.

Original entry on oeis.org

1, 8, 44, 252, 1446, 8300, 47642, 273466, 1569700, 9010108, 51718192, 296863410, 1704001644, 9781001986, 56143138234, 322262685896, 1849793972828, 10617852738356, 60946677537854, 349835093256180, 2008060117756986

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.

Cf. Base 8 differing by two or less A126395, one or less A126362.

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

A126503 Number of base 8 n-digit numbers with adjacent digits differing by four or less.

Original entry on oeis.org

1, 8, 52, 348, 2322, 15500, 103462, 690610, 4609826, 30770620, 205394096, 1371006978, 9151480836, 61086196378, 407750773322, 2721739165358, 18167627307952, 121269034961780, 809471627267722, 5403228578160660

Offset: 0

R. H. Hardin, Dec 28 2006

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

Cf. Base 8 differing by three or less A126476, two or less A126395, one or less A126362.

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

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

A126529 Number of base 8 n-digit numbers with adjacent digits differing by five or less.

Original entry on oeis.org

1, 8, 58, 426, 3124, 22914, 168066, 1232708, 9041498, 66316346, 486408084, 3567639634, 26167436306, 191929340708, 1407737135338, 10325278224266, 75732441613044, 555471977422754, 4074200053901346, 29882886543125508

Offset: 0

R. H. Hardin, Dec 28 2006

[Empirical] a(base,n)=a(base-1,n)+11^(n-1) for base>=5n-4; a(base,n)=a(base-1,n)+11^(n-1)-2 when base=5n-5.

Cf. Base 8 differing by four or less A126503, three or less A126476, two or less A126395, one or less A126362.

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

cp's OEIS Frontend

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

A048489 a(n) = 7 * 2^n - 6.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

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

Views

Author

Keywords

Comments

Crossrefs

Formula

A126476 Number of base 8 n-digit numbers with adjacent digits differing by three or less.

Views

Author

Keywords

Comments

Crossrefs

Formula

A126503 Number of base 8 n-digit numbers with adjacent digits differing by four or less.

Views

Author

Keywords

Comments

Crossrefs

Formula

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

A126529 Number of base 8 n-digit numbers with adjacent digits differing by five or less.

Views

Author

Keywords

Comments

Crossrefs

Formula