A095263 -id:A095263 - cp's OEIS frontend

A190525 Number of n-step one-sided prudent walks, avoiding exactly two consecutive west steps (can have three or more west steps).

1, 3, 6, 15, 34, 80, 185, 431, 1001, 2328, 5411, 12580, 29244, 67985, 158045, 367411, 854126, 1985603, 4615966, 10730820, 24946129, 57992715, 134816705, 313410816, 728591751, 1693770328, 3937538296, 9153665985, 21279691689, 49469281395

Offset: 0

Shanzhen Gao, May 11 2011

The Ze2 sums, see A180662 for the definition of these sums, of the 'Races with Ties' triangle A035317 leads to this sequence with a(-1) = 1; the recurrence relation confirms this value. - Johannes W. Meijer, Jul 20 2011

Number of tilings of a 5 X 3n rectangle with 5 X 1 pentominoes. - M. Poyraz Torcuk, Dec 25 2021

			a(2) = 6 since there are 6 such walks: NN, NW, WN, EE, EN, NE.

G. C. Greubel, Table of n, a(n) for n = 0..1000
S. Gao and H. Niederhausen, Sequences Arising From Prudent Self-Avoiding Walks, 2010.
Index entries for linear recurrences with constant coefficients, signature (2,1,-1,1).

I:=[1,3,6,15]; [n le 4 select I[n] else 2*Self(n-1) +Self(n-2) -Self(n-3) +Self(n-4): n in [1..40]]; // G. C. Greubel, Apr 17 2021

A190525 := proc(n) option remember: if n=0 then 1 elif n=1 then 3 elif n=2 then 6 elif n=3 then 15 else 2*procname(n-1) + procname(n-2) - procname(n-3) + procname(n-4) fi: end: seq(A190525(n), n=0..29); # Johannes W. Meijer, Jul 20 2011

LinearRecurrence[{2,1,-1,1}, {1,3,6,15}, 40] (* G. C. Greubel, Apr 17 2021 *)

def A190525_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1+x-x^2+x^3)/(1-2*x-x^2+x^3-x^4) ).list()
A190525_list(40) # G. C. Greubel, Apr 17 2021

G.f.: (1+x-x^2+x^3)/(1-2*x-x^2+x^3-x^4).
From Johannes W. Meijer, Jul 20 2011: (Start)
a(n) = 2*a(n-1) + a(n-2) - a(n-3) + a(n-4) with a(0) = 1, a(1) = 3, a(2) = 6 and a(3) = 15.
a(n) = (9*A095263(n+1) - 8*A095263(n) + 5*A095263(n-1) - 2*(-1)^n)/7. (End)

A129080 Expansion of g.f. x(x^4 - 5x^3 + 10x^2 - 12x + 4)/((1-x)^2(1 - 3x + 2*x^2 - x^3)).

Original entry on oeis.org

4, 8, 14, 25, 48, 99, 215, 482, 1100, 2534, 5865, 13606, 31599, 73425, 170656, 396688, 922146, 2143685, 4983416, 11584987, 26931775, 62608726, 145547572, 338356994, 786584517, 1828587086, 4250949167, 9882257793, 22973462076, 53406819752, 124155792838

Offset: 1

Roger L. Bagula, May 11 2007

G. C. Greubel, Table of n, a(n) for n = 1..1000
Shigeki Akiyama, Pisot number system and its dual tiling, in: "Physics and Theoretical Computer Science", ed. by J. P. Gazeau et al., IOS Press (2007) 133-154.
Petr Ambroz, Christiane Frougny, Zuzana Masakova and Edita Pelantova, Palindromic complexity of infinite words associated with simple Parry numbers, arXiv:math/0603608 [math.CO], 2006.
Index entries for linear recurrences with constant coefficients, signature (5,-9,8,-4,1)

Cf. A095263.

b:= func< n | n lt 4 select 2^n -1 else 3*Self(n-1) -2*Self(n-2) +Self(n-3) >;
[2*n+1+b(n): n in [1..40]]; // G. C. Greubel, Apr 12 2021

m:=40; S:=series( x*(x^4-5*x^3+10*x^2-12*x+4)/((1-x)^2*(1-3*x+2*x^2-x^3)), x, m+1):
seq(coeff(S, x, j), j=1..m); # G. C. Greubel, Apr 12 2021

(* b = A095263 *)
b[n_]:= b[n]= If[n<4, 2^n -1, 3*b[n-1] -2*b[n-2] +b[n-3]];
a[n_]:= a[n]= If[n==1, 4, a[n-1] +b[n] -b[n-1] +2];
Table[a[n], {n, 40}] (*modified by G. C. Greubel, Apr 12 2021 *)
LinearRecurrence[{5,-9,8,-4,1},{4,8,14,25,48},40] (* Harvey P. Dale, Feb 14 2015 *)

@CachedFunction
def b(n): return 2^n -1 if n < 4 else 3*b(n-1) -2*b(n-2) +b(n-3)
[2*n+1 +b(n) for n in (1..40)] # G. C. Greubel, Apr 12 2021

a(n) = a(n-1) + A095263(n) - A095263(n-1) + 2.
G.f.: x*(x^4 - 5*x^3 + 10*x^2 - 12*x + 4)/((1-x)^2*(1 - 3*x + 2*x^2 - x^3)). [Maksym Voznyy (voznyy(AT)mail.ru), Aug 14 2009; corrected by R. J. Mathar, Sep 16 2009]
a(n) = A095263(n) + 2*n + 1. - G. C. Greubel, Apr 12 2021

Edited by G. C. Greubel, Apr 12 2021

New name using Maksym Voznyy's g.f., Joerg Arndt, Apr 13 2021

A176482 Triangle, read by rows, defined by T(n, k) = b(n) - b(k) - b(n-k) + 1 (see formula section for recurrence for b(n)).

Original entry on oeis.org

1, 1, 1, 1, 3, 1, 1, 9, 9, 1, 1, 29, 35, 29, 1, 1, 94, 120, 120, 94, 1, 1, 304, 395, 415, 395, 304, 1, 1, 983, 1284, 1369, 1369, 1284, 983, 1, 1, 3179, 4159, 4454, 4519, 4454, 4159, 3179, 1, 1, 10281, 13457, 14431, 14706, 14706, 14431, 13457, 10281, 1

Offset: 0

Roger L. Bagula, Apr 18 2010

			Triangle begins as:
  1;
  1,     1;
  1,     3,     1;
  1,     9,     9,     1;
  1,    29,    35,    29,     1;
  1,    94,   120,   120,    94,     1;
  1,   304,   395,   415,   395,   304,     1;
  1,   983,  1284,  1369,  1369,  1284,   983,     1;
  1,  3179,  4159,  4454,  4519,  4454,  4159,  3179,     1;
  1, 10281, 13457, 14431, 14706, 14706, 14431, 13457, 10281,     1;
  1, 33249, 43527, 46697, 47651, 47861, 47651, 46697, 43527, 33249, 1;
...
T(4,3) = a(4) - a(3) - a(4 - 3) + 1 = 42 - 13 - 1 + 1 = 29. - _Indranil Ghosh_, Feb 18 2017

Indranil Ghosh, Rows 0..120, flattened
B. Adamczewski, Ch. Frougny, A. Siegel and W. Steiner, Rational numbers with purely periodic beta-expansion, Bull. Lond. Math. Soc. 42:3 (2010), pp. 538-552; also arXiv:0907.0206 [math.NT], 2009-2010.
Indranil Ghosh, Python Program to generate the b-file
Roger L. Bagula, Three methods to generate the sequence b(n)

Cf. A095263.

b[0]:=0; b[1]:=1; b[2]:=4; b[3]=13; b[n_]:= b[n]= 4*b[n-1] -3*b[n-2] + 2*b[n-3] -b[n-4]; T[n_, m_]:=b[n]-b[m]-b[n-m]+1; Table[T[n, m], {n,0,12}, {m,0,n}]//Flatten

{b(n) = if(n==0, 0, if(n==1, 1, if(n==2, 4, if(n==3, 13, 4*b(n-1) -3*b(n-2) + 2*b(n-3) -b(n-4)))))};
{T(n,k) = b(n) -b(k) -b(n-k) +1};
for(n=0,10, for(k=0,n, print1(T(n,k), ", "))) \\ G. C. Greubel, May 06 2019

Python
```
# see Indranil Ghosh link
```

def b(n):
    if (n==0): return 0
    elif (n==1): return 1
    elif (n==2): return 4
    elif (n==3): return 13
    else: return 4*b(n-1) -3*b(n-2) +2*b(n-3) -b(n-4)
def T(n, k): return b(n) - b(k) - b(n-k) + 1
[[T(n, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, May 06 2019

With b(n) = 4*b(n-1) - 3*b(n-2) + 2*b(n-3) - b(n-4), with b(0) = 0, b(1) = 1, b(2) = 4 and b(3) = 13, then the triangle is generated by T(n, k) = b(n) - b(k) - b(n-k) + 1.

Name and formula sections edited by Indranil Ghosh, Feb 18 2017

Edited by G. C. Greubel, May 06 2019

A176483 Triangle, read by rows, defined by T(n, k) = b(n) - b(k) - b(n-k) + 1, where b(n) = 5b(n-1) - 4b(n-2) + 3b(n-3) - 2b(n-4) - b(n-5) and b(0) = 0, b(1) = 1, b(2) = 5, b(3) = 21, b(4) = 88.

Original entry on oeis.org

1, 1, 1, 1, 4, 1, 1, 16, 16, 1, 1, 67, 79, 67, 1, 1, 281, 344, 344, 281, 1, 1, 1176, 1453, 1504, 1453, 1176, 1, 1, 4921, 6093, 6358, 6358, 6093, 4921, 1, 1, 20594, 25511, 26671, 26885, 26671, 25511, 20594, 1, 1, 86185, 106775, 111680, 112789, 112789, 111680, 106775, 86185, 1

Offset: 0

Roger L. Bagula, Apr 18 2010

Row sums are {1, 2, 6, 34, 215, 1252, 6764, 34746, 172439, 834860, 3967727, ...}.

			Triangle begins as:
  1;
  1,     1;
  1,     4,      1;
  1,    16,     16,      1;
  1,    67,     79,     67,      1;
  1,   281,    344,    344,    281,      1;
  1,  1176,   1453,   1504,   1453,   1176,      1;
  1,  4921,   6093,   6358,   6358,   6093,   4921,      1;
  1, 20594,  25511,  26671,  26885,  26671,  25511,  20594,     1;
  1, 86185, 106775, 111680, 112789, 112789, 111680, 106775, 86185, 1;
...
T(3,2) = b(3) - b(2) - b(3 - 2) + 1 = 21 - 5 - 1 + 1 = 16 [b(1) = 1, b(2) = 5, b(3) = 21]. - _Indranil Ghosh_, Feb 17 2017

Indranil Ghosh, Rows 0..120, flattened
Indranil Ghosh, Python Program to generate the b-file

Cf. A095263.

b[0]:=0; b[1]:=1; b[2]:=5; b[3]:=21; b[4]:=88;
b[n_]:= 5*b[n-1] -4*b[n-2] +3*b[n-3] -2*b[n-4] -b[n-5];
T[n_, m_]:= b[n] -b[m] -b[n-m] +1;
Table[T[n, m], {n,0,10}, {m,0,n}]//Flatten (* modified by G. C. Greubel, May 06 2019 *)

{b(n) = if(n==0, 0, if(n==1, 1, if(n==2, 5, if(n==3, 21, if(n==4, 88, 5*b(n-1) -4*b(n-2) +3*b(n-3) -2*b(n-4) -b(n-5))))))};
{T(n, k) = b(n) -b(k) -b(n-k) +1};
for(n=0,10, for(k=0,n, print1(T(n,k), ", "))) \\ G. C. Greubel, May 06 2019

def b(n):
    if (n==0): return 0
    elif (n==1): return 1
    elif (n==2): return 5
    elif (n==3): return 21
    elif (n==4): return 88
    else: return 5*b(n-1) -4*b(n-2) +3*b(n-3) -2*b(n-4) -b(n-5)
def T(n, k): return b(n) - b(k) - b(n-k) + 1
[[T(n, k) for k in (0..n)] for n in (0..12)] # G. C. Greubel, May 06 2019

Let b(n) = 5*b(n-1) - 4*b(n-2) + 3*b(n-3) - 2*b(n-4) - b(n-5), with b(0) = 0, b(1) = 1, b(2) = 5, b(3) = 21, b(4) = 88, then T(n, k) = b(n) - b(k) - b(n-k) + 1.

Edited by G. C. Greubel, May 06 2019

A253273 Triangle T(n,k) = Sum_{j=0..n-k+1} binomial(k+j,k-j+1)*binomial(n-k,j-1), read by rows.

Original entry on oeis.org

1, 1, 2, 1, 3, 3, 1, 4, 7, 4, 1, 5, 12, 14, 5, 1, 6, 18, 30, 25, 6, 1, 7, 25, 53, 66, 41, 7, 1, 8, 33, 84, 136, 132, 63, 8, 1, 9, 42, 124, 244, 315, 245, 92, 9, 1, 10, 52, 174, 400, 636, 673, 428, 129, 10, 1, 11, 63, 235, 615, 1152, 1522, 1346, 711, 175, 11

Offset: 0

Vladimir Kruchinin, May 01 2015

			The triangle begins as:
  1;
  1,  2;
  1,  3,  3;
  1,  4,  7,   4;
  1,  5, 12,  14,   5;
  1,  6, 18,  30,  25,   6;
  1,  7, 25,  53,  66,  41,   7;
  1,  8, 33,  84, 136, 132,  63,   8;
  1,  9, 42, 124, 244, 315, 245,  92,   9;
  1, 10, 52, 174, 400, 636, 673, 428, 129, 10;
  ...

G. C. Greubel, Rows n = 0..50 of the triangle, flattened

Cf. A095263.

T:= func< n,k | (&+[Binomial(k+j,k-j+1)*Binomial(n-k,j-1): j in [0..n-k+1]]) >;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Apr 17 2021

T[n_, k_]:= Sum[Binomial[k+j,k-j+1]*Binomial[n-k,j-1], {j,0,n-k+1}];
Table[T[n, k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Apr 17 2021 *)

T(n,m):=sum(binomial(m+k,m-k+1)*binomial(n-m,k-1),k,0,n-m+1);

def T(n,k): return sum(binomial(k+j,k-j+1)*binomial(n-k,j-1) for j in (0..n-k+1))
flatten([[T(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Apr 17 2021

T(n,k) = Sum_{j=0..n-k+1} binomial(k+j,k-j+1)*binomial(n-k,j-1).
Sum_{k=0..n} T(n,k) = A095263(n+1).
G.f.: 1/( (1-x)*(1+y^2) - (2-x)*y ).

A353232 a(n) is the number of ways to split [n] = {1,2,...,n} into two (possibly empty) complementary intervals {1,2,...,i} and {i+1,i+2,...,n} and then, if both intervals are nonempty, select 2 nonempty blocks/cells (i.e., subintervals) from each of them, or if one of the intervals is empty, select 2 nonempty blocks/cells from the nonempty interval.

Original entry on oeis.org

0, 2, 6, 13, 26, 51, 98, 182, 324, 552, 902, 1419, 2158, 3185, 4578, 6428, 8840, 11934, 15846, 20729, 26754, 34111, 43010, 53682, 66380, 81380, 98982, 119511, 143318, 170781, 202306, 238328, 279312, 325754, 378182, 437157, 503274, 577163, 659490, 750958

Offset: 1

Enrique Navarrete, May 01 2022

See A095263 for the number of ways to split [n] into an unspecified number of intervals and then choose 2 blocks (i.e., subintervals) from each interval.

			a(1)=0 since we can't choose 2 nonempty blocks/cells (i.e., subintervals) from an interval of one block.
a(2)=2 since we have 2 cases: first interval is empty, so we choose both blocks (i.e., subintervals) from the second interval in C(2,2) ways, and similarly for the case of the second interval being empty (note we can't consider the case where [2] splits into 2 intervals of one block each since we can't choose 2 nonempty blocks from a single block; i.e., C(1,2)*C(1,2)=0).
a(6)=51 since the following are the number of ways to split [6] into 2 intervals with k and (n-k) blocks (subintervals) each (written as k|(n-k) below) and to choose the blocks/cells:
   6|0 (second interval empty): C(6,2) = 15 from the first interval;
   0|6 (first interval empty): C(6,2) = 15 from the second interval;
   2|4:  C(2,2)*C(4,2) = 6;
   3|3:  C(3,2)*C(3,2) = 9;
   4|2:  C(4,2)*C(2,2) = 6.

Paolo Xausa, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Cf. A095263, A002378, A000389.

A353232[n_] := 2*Binomial[n, 2] + Binomial[n + 1, 5];
Array[A353232, 50] (* Paolo Xausa, May 27 2024 *)

a(n) = 2*binomial(n,2) + binomial(n+1,5); \\ Michel Marcus, Jul 06 2022

a(n) = 2*C(n,2) + C(n+1,5).
G.f.: x^2*(2 - 6*x + 7*x^2 - 2*x^3)/(1 - x)^6. - Stefano Spezia, May 02 2022
a(n) = n*(n-1)*(n^3 - 4*n^2 + n + 126)/120. - R. J. Mathar, Jul 05 2022

A176480 Triangle: let b(n) = 3b(n - 1) - 2b(n - 2) + b(n - 3), then T(n,m) = b(n) - b(m) - b(n - m) + 1.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 4, 1, 1, 9, 11, 9, 1, 1, 21, 28, 28, 21, 1, 1, 49, 68, 73, 68, 49, 1, 1, 114, 161, 178, 178, 161, 114, 1, 1, 265, 377, 422, 434, 422, 377, 265, 1, 1, 616, 879, 989, 1029, 1029, 989, 879, 616, 1, 1, 1432, 2046, 2307, 2412, 2440, 2412, 2307, 2046

Offset: 0

Roger L. Bagula, Apr 18 2010

			{1},
{1, 1},
{1, 2, 1},
{1, 4, 4, 1},
{1, 9, 11, 9, 1},
{1, 21, 28, 28, 21, 1},
{1, 49, 68, 73, 68, 49, 1},
{1, 114, 161, 178, 178, 161, 114, 1},
{1, 265, 377, 422, 434, 422, 377, 265, 1},
{1, 616, 879, 989, 1029, 1029, 989, 879, 616, 1},
{1, 1432, 2046, 2307, 2412, 2440, 2412, 2307, 2046, 1432, 1}

Cf. A095263

b[0] := 0; b[1] := 1; b[2] := 3;
b[n_] := b[n] = 3*b[n - 1] - 2*b[n - 2] + b[n - 3];
t[n_, m_] := t[n, m] = b[n] - b[m] - b[n - m] + 1;
Table[Table[t[n, m], {m, 0, n}], {n, 0, 10}];
Flatten[%]

cp's OEIS Frontend

A190525 Number of n-step one-sided prudent walks, avoiding exactly two consecutive west steps (can have three or more west steps).

Views

Author

Keywords

Comments

Examples

Links

Programs

Magma

Maple

Mathematica

Sage

Formula

A129080 Expansion of g.f. x*(x^4 - 5*x^3 + 10*x^2 - 12*x + 4)/((1-x)^2*(1 - 3*x + 2*x^2 - x^3)).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Sage

Formula

Extensions

A176482 Triangle, read by rows, defined by T(n, k) = b(n) - b(k) - b(n-k) + 1 (see formula section for recurrence for b(n)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Sage

Formula

Extensions

A176483 Triangle, read by rows, defined by T(n, k) = b(n) - b(k) - b(n-k) + 1, where b(n) = 5*b(n-1) - 4*b(n-2) + 3*b(n-3) - 2*b(n-4) - b(n-5) and b(0) = 0, b(1) = 1, b(2) = 5, b(3) = 21, b(4) = 88.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

Extensions

A253273 Triangle T(n,k) = Sum_{j=0..n-k+1} binomial(k+j,k-j+1)*binomial(n-k,j-1), read by rows.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

Sage

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A176480 Triangle: let b(n) = 3*b(n - 1) - 2*b(n - 2) + b(n - 3), then T(n,m) = b(n) - b(m) - b(n - m) + 1.

A129080 Expansion of g.f. x(x^4 - 5x^3 + 10x^2 - 12x + 4)/((1-x)^2(1 - 3x + 2*x^2 - x^3)).

A176483 Triangle, read by rows, defined by T(n, k) = b(n) - b(k) - b(n-k) + 1, where b(n) = 5b(n-1) - 4b(n-2) + 3b(n-3) - 2b(n-4) - b(n-5) and b(0) = 0, b(1) = 1, b(2) = 5, b(3) = 21, b(4) = 88.

A176480 Triangle: let b(n) = 3b(n - 1) - 2b(n - 2) + b(n - 3), then T(n,m) = b(n) - b(m) - b(n - m) + 1.