A126386 -id:A126386 - 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).

A128386 Expansion of c(3x^2)/(1-xc(3*x^2)), c(x) the g.f. of A000108.

Original entry on oeis.org

1, 1, 4, 7, 28, 58, 232, 523, 2092, 4966, 19864, 48838, 195352, 492724, 1970896, 5068915, 20275660, 52955950, 211823800, 560198962, 2240795848, 5987822380, 23951289520, 64563867454, 258255469816, 701383563388, 2805534253552

Offset: 0

Paul Barry, Feb 28 2007

Hankel transform is 3^C(n+1,2) = A047656(n+1).

Series reversion of x*(1+x)/(1+2*x+4*x^2).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Alin Bostan, Computer Algebra for Lattice Path Combinatorics, Slides, Séminaire de Combinatoire Ph. Flajolet, March 28 2013.
Alin Bostan, Andrew Elvey Price, Anthony John Guttmann, and Jean-Marie Maillard, Stieltjes moment sequences for pattern-avoiding permutations, arXiv:2001.00393 [math.CO], 2020.

Cf. A000108, A009766, A047656, A120730.

R:=PowerSeriesRing(Rationals(), 40); Coefficients(R!( (Sqrt(1-12*x^2)+2*x-1)/(2*x*(1-4*x)) )); // G. C. Greubel, Nov 07 2022

A120730[n_, k_]:= If[n>2*k, 0, Binomial[n,k]*(2*k-n+1)/(k+1)];
A126386[n_]:= Sum[3^k*A120730[n, n-k], {k,0,n}];
Table[A126386[n], {n,0,50}] (* G. C. Greubel, Nov 07 2022 *)

def A120730(n, k): return 0 if (n>2*k) else binomial(n, k)*(2*k-n+1)/(k+1)
def A126386(n): return sum(3^k*A120730(n,n-k) for k in range(n+1))
[A126386(n) for n in range(51)] # G. C. Greubel, Nov 07 2022

G.f.: (sqrt(1-12*x^2)+2*x-1)/(2*x*(1-4*x)).
a(n) = (1/(n+1))*Sum_{k=0..n+1} Sum_{j=0..k} C(n,k)*C(k,j)*C(2*n-2*k+j, n-2*k+j)*(-1)^(n+j)*2^(2*k-j).
a(n) = Sum_{k=0..floor(n/2)} C(n,n-k)*(n-2*k+1)*3^k/(n-k+1);
a(n) = Sum_{k=0..floor(n/2)} A009766(n-k,k)*3^k.
a(n) = Sum_{k=0..n} 3^k*A120730(n,n-k). - Philippe Deléham, Mar 03 2007
D-finite with recurrence (n+1)*a(n) - 4*(n+1)*a(n-1) + 12*(2-n)*a(n-2) + 48*(n-2)*a(n-3) = 0. - R. J. Mathar, Nov 14 2011

A128387 Expansion of c(5x^2)/(1-x*c(5x^2)), where c(x) is the g.f. of A000108.

Original entry on oeis.org

1, 1, 6, 11, 66, 146, 876, 2131, 12786, 32966, 197796, 530526, 3183156, 8786436, 52718616, 148733571, 892401426, 2561439806, 15368638836, 44731364266, 268388185596, 790211926076, 4741271556456, 14095578557486

Offset: 0

Paul Barry, Feb 28 2007

Hankel transform is 5^C(n+1,2).

Reversion of x*(1+x)/(1+2*x+6*x^2).

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

Cf. A000108, A009766, A120730, A126386.

R:=PowerSeriesRing(Rationals(), 50); Coefficients(R!( (Sqrt(1-20*x^2)+2*x-1)/(2*x*(1-6*x)) )); // G. C. Greubel, Nov 07 2022

A120730[n_, k_]:= If[n>2*k, 0, Binomial[n, k]*(2*k-n+1)/(k+1)];
A126387[n_]:= Sum[5^k*A120730[n, n-k], {k,0,n}];
Table[A126387[n], {n, 0, 50}] (* G. C. Greubel, Nov 07 2022 *)

def A120730(n, k): return 0 if (n>2*k) else binomial(n, k)*(2*k-n+1)/(k+1)
def A126387(n): return sum(5^k*A120730(n,n-k) for k in range(n+1))
[A126387(n) for n in range(51)] # G. C. Greubel, Nov 07 2022

G.f.: (sqrt(1-20*x^2) + 2*x - 1)/(2*x*(1-6*x)).
a(n) = (1/(n+1))*Sum_{k=0..n+1} Sum_{j=0..k} C(n,k)*C(k,j)*C(2*n-2*k+j, n-2*k+j)*(-1)^(n+j)*2^j*6^(k-j).
a(n) = Sum_{k=0..floor(n/2)} C(n,n-k)*(n-2*k+1)*5^k/(n-k+1).
a(n) = Sum_{k=0..floor(n/2)} A009766(n-k,k)*5^k.
a(n) = Sum_{k=0..n} 5^k*A120730(n,n-k). - Philippe Deléham, Mar 03 2007
(n+1)*a(n) = 6*(n+1)*a(n-1) + 20*(n-2)*a(n-2) - 120*(n-2)*a(n-3). - R. J. Mathar, Nov 14 2011

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

Original entry on oeis.org

1, 32, 154, 750, 3668, 17986, 88348, 434524, 2139230, 10540030, 51964360, 256332260, 1265027930, 6245522700, 30845183058, 152383470186, 753018119972, 3722010001906, 18401089523298, 90990129769076, 450009665618408

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 32 differing by one or less A126386.

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

Original entry on oeis.org

1, 32, 212, 1428, 9676, 65800, 448524, 3062596, 20939104, 143307908, 981612296, 6728277248, 46143758054, 316613006372, 2173302900418, 14923204166476, 102502175850752, 704231575697316, 4839430076086740, 33262613275263868

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 32 differing by two or less A126419, one or less A126386.

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

Original entry on oeis.org

1, 32, 268, 2292, 19748, 170904, 1483284, 12899556, 112350184, 979640156, 8549531716, 74665238648, 652426700120, 5703387501520, 49875030912772, 436266613941484, 3816936851122500, 33400491065984904, 292314430831005104

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 32 differing by three or less A126500, two or less A126419, one or less A126386.

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

Original entry on oeis.org

1, 32, 322, 3322, 34572, 361614, 3794396, 39900036, 420199296, 4429943806, 46737838878, 493369276732, 5210044608364, 55033710005144, 581433527148552, 6143714493591276, 64923869760680486, 686132382682831498

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 32 differing by four or less A126527, three or less A126500, two or less A126419, one or less A126386.

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

A128386 Expansion of c(3*x^2)/(1-x*c(3*x^2)), c(x) the g.f. of A000108.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A128387 Expansion of c(5x^2)/(1-x*c(5x^2)), where c(x) is the g.f. of A000108.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

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

Views

Author

Keywords

Comments

Crossrefs

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

Views

Author

Keywords

Comments

Crossrefs

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

Views

Author

Keywords

Comments

Crossrefs

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

Views

Author

Keywords

Comments

Crossrefs

A128386 Expansion of c(3x^2)/(1-xc(3*x^2)), c(x) the g.f. of A000108.