A144899 -id:A144899 - cp's OEIS frontend

A077868 Expansion of 1/((1-x)*(1-x-x^3)).

1, 2, 3, 5, 8, 12, 18, 27, 40, 59, 87, 128, 188, 276, 405, 594, 871, 1277, 1872, 2744, 4022, 5895, 8640, 12663, 18559, 27200, 39864, 58424, 85625, 125490, 183915, 269541, 395032, 578948, 848490, 1243523, 1822472, 2670963, 3914487, 5736960, 8407924, 12322412

Offset: 0

N. J. A. Sloane, Nov 17 2002

Row sums of Riordan array (1/(1-x), x*(1+x^2)). - Paul Barry, Feb 16 2005

a(n) is the number of partitions of {1, ..., n+3} into two blocks in which only 1- or 3-strings of consecutive integers can appear in a block and there is at least one 3-string. E.g., a(3)=5 because the enumerated partitions of {1,2,3,4,5,6} are 1235/46, 1345/26, 15/2346, 13/2456, 123/456. - Augustine O. Munagi, Apr 11 2005

Chu, Hung Viet. "Various Sequences from Counting Subsets." Fib. Quart., 59:2 (May 2021), 150-157.

G. C. Greubel, Table of n, a(n) for n = 0..1000
Kassie Archer and Aaron Geary, Powers of permutations that avoid chains of patterns, arXiv:2312.14351 [math.CO], 2023. See p. 15.
Hung Viet Chu, Various sequences from counting subsets, arXiv:2005.10081 [math.CO], 2020-2021.
A. O. Munagi, Set Partitions with Successions and Separations, IJMMS 2005:3 (2005), 451-463.
Index entries for linear recurrences with constant coefficients, signature (2,-1,1,-1).

Cf. A000071, A077888, A077941, A105489.
Cf. A000930, A050228, A144898, A144899, A144900, A144901, A144902, A144903, A144904, A226405.
Cf. A078012, A099567, A135851.

A077868:= func< n | n eq 0 select 0 else (&+[Binomial(n-2*j+, j+1): j in [0..Floor((n+1)/3)]]) >;
[A077868(n): n in [0..40]]; // G. C. Greubel, Jul 27 2022

a:= n-> (Matrix(4, (i,j)-> if i=j-1 then 1 elif j=1 then [2,-1,1,-1][i] else 0 fi)^n)[1,1]: seq(a(n), n=0..41); # Alois P. Heinz, Sep 05 2008
g:=(1+z+z^2)/(1-z-z^3): gser:=series(g, z=0, 43): seq(coeff(gser, z, n)-1, n=1..42); # Zerinvary Lajos, Jan 09 2009

LinearRecurrence[{1,1,0,0,-1}, {1,2,3,5,8,12}, 42] (* or *)
CoefficientList[Series[1/((1-x)(1-x-x^3)), {x, 0, 41}], x] (* Michael De Vlieger, Jun 06 2018 *)

Vec(1/(1-x)/(1-x-x^3)+O(x^99)) \\ Charles R Greathouse IV, Sep 23 2012

{a = vector(50);
a[1] = 1; a[2] = 2; a[3] = 3;
for(n=4,50,
a[n] = 1 + a[n-1] + a[n-3];
); a} \\ Gerry Martens, Jun 03 2018

{a(n) = if( n<0, n=-4-n; polcoeff( -1 / (1 - x) / (1 + x^2 - x^3) + x * O(x^n), n), polcoeff( 1 / (1 - x) / (1 - x - x^3) + x * O(x^n), n))}; /* Michael Somos, Jun 17 2018 */

def A077868(n): return sum(binomial(n-2*j+1, j+1) for j in (0..((n+1)//3)))
[A077868(n) for n in (0..40)] # G. C. Greubel, Jul 27 2022

Partial sums of A000930. a(n-1) = Sum_{k=0..floor(n/2)} binomial(n-2*k, k+1). - Paul Barry, Jul 07 2004
a(n-3) = Sum(binomial(n-r, r)), r=1, 2, ... which is the case t=3 and k=2 in the general case of t-strings and k blocks: a(n-3, k, t) = Sum(binomial(n-r*(t-1), r)*S2(n-r*(t-1)-1, k-1)), r=1, 2, ... - Augustine O. Munagi, Apr 11 2005
From Paul Weisenhorn, Oct 28 2011: (Start)
a(n) = a(n-1) + a(n-2) - a(n-5) for n > 4.
a(n) = a(n-2) + a(n-3) + a(n-4) + 2 for n > 3.
G.f.: 1/((1-x)*(1-x-x^3)). (End)
a(n) = 1 + a(n-1) + a(n-3), a(1)=1, a(2)=2, a(3)=3. - Gerry Martens, Jun 10 2018
a(n) = -A077888(-4-n) for all n in Z. - Michael Somos, Jun 17 2018
a(n) = A000930(n+3) - 1. - Greg Dresden, Jun 20 2021
a(n) = A099567(n+3, 4). - G. C. Greubel, Jul 27 2022

More terms from Augustine O. Munagi, Apr 11 2005

A099567 Riordan array (1/(1-x-x^3), 1/(1-x)).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 3, 3, 1, 3, 5, 6, 4, 1, 4, 8, 11, 10, 5, 1, 6, 12, 19, 21, 15, 6, 1, 9, 18, 31, 40, 36, 21, 7, 1, 13, 27, 49, 71, 76, 57, 28, 8, 1, 19, 40, 76, 120, 147, 133, 85, 36, 9, 1, 28, 59, 116, 196, 267, 280, 218, 121, 45, 10, 1, 41, 87, 175, 312, 463, 547, 498, 339, 166, 55, 11, 1

Offset: 0

Paul Barry, Oct 22 2004

Inverse matrix is A099569.

Subtriangle of the triangle in A144903. - Philippe Deléham, Dec 29 2013

			Rows begin:
   1;
   1,  1;
   1,  2,   1;
   2,  3,   3,   1;
   3,  5,   6,   4,   1;
   4,  8,  11,  10,   5,   1;
   6, 12,  19,  21,  15,   6,   1;
   9, 18,  31,  40,  36,  21,   7,   1;
  13, 27,  49,  71,  76,  57,  28,   8,   1;
  19, 40,  76, 120, 147, 133,  85,  36,   9,   1;
  28, 59, 116, 196, 267, 280, 218, 121,  45,  10,   1;

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

Cf. A000217, A050407, A099568 (row sums), A099569, A144903, A144904.

Columns: A000930, A077868, A050228, A226405, A144898, A144899, A144900, A144901, A144902.

T:= func< n,k | (&+[Binomial(n-2*j, k+j): j in [0..Floor(n/3)]]) >;
[[T(n,k): k in [0..n]]: n in [0..15]]; // G. C. Greubel, Jul 27 2022

T[n_, 0]:=T[n,0]=HypergeometricPFQ[{(1-n)/3,(2-n)/3,-n/3}, {(1-n)/2,-n/2}, -27/4];
T[n_, k_]:= T[n,k]= If[k==n, 1, T[n-1,k-1] +T[n-1,k]];
Table[T[n, k], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Apr 28 2017 *)

@CachedFunction
def A099567(n, k): return sum( binomial(n-2*j, k+j) for j in (0..(n//3)) )
flatten([[A099567(n,k) for k in (0..n)] for n in (0..15)]) # G. C. Greubel, Jul 27 2022

Number triangle T(n, k) = Sum_{j=0..floor(n/3)} binomial(n-2*j, k+j).
Columns have g.f. (1/(1-x-x^3))*(x/(1-x))^k.
Sum_{k=0..n} T(n, k) = A099568(n).
T(n,0) = A000930(n), T(n,n) = 1, T(n,k) = T(n-1,k-1) + T(n-1,k) for 0Philippe Deléham, Dec 29 2013
exp(x) * e.g.f. for row n = e.g.f. for diagonal n. For example, for n = 3 we have exp(x)*(2 + 3*x + 3*x^2/2! + x^3/3!) = 2 + 5*x + 11*x^2/2! + 21*x^3/3! + 36*x^4/4! + .... The same property holds more generally for Riordan arrays of the form ( f(x), x/(1 - x) ). - Peter Bala, Dec 21 2014
From G. C. Greubel, Jul 27 2022: (Start)
T(n, n-1) = n, for n >= 1.
T(n, n-2) = A000217(n-1), for n >= 2.
T(n, n-3) = A050407(n+1), for n >= 3.
T(2*n, n) = A144904(n+1), for n >= 1. (End)

A144903 Square array A(n,k), n>=0, k>=0, read by antidiagonals, where column k is the expansion of x/((1-x-x^3)*(1-x)^(k-1)).

Original entry on oeis.org

0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 1, 1, 0, 1, 3, 3, 2, 1, 0, 1, 4, 6, 5, 3, 1, 0, 1, 5, 10, 11, 8, 4, 2, 0, 1, 6, 15, 21, 19, 12, 6, 3, 0, 1, 7, 21, 36, 40, 31, 18, 9, 4, 0, 1, 8, 28, 57, 76, 71, 49, 27, 13, 6, 0, 1, 9, 36, 85, 133, 147, 120, 76, 40, 19, 9, 0, 1, 10, 45, 121, 218, 280, 267, 196, 116, 59, 28, 13

Offset: 0

Alois P. Heinz, Sep 24 2008

			Square array (A(n,k)) begins:
  0, 0,  0,  0,  0,   0,   0 ... A000004;
  1, 1,  1,  1,  1,   1,   1 ... A000012;
  0, 1,  2,  3,  4,   5,   6 ... A001477;
  0, 1,  3,  6, 10,  15,  21 ... A000217;
  1, 2,  5, 11, 21,  36,  57 ... A050407;
  1, 3,  8, 19, 40,  76, 133 ... ;
  1, 4, 12, 31, 71, 147, 200 ... A027658;
Antidiagonal triangle (T(n,k)) begins as:
  0;
  0,  1;
  0,  1,  0;
  0,  1,  1,  0;
  0,  1,  2,  1,  1;
  0,  1,  3,  3,  2,  1;
  0,  1,  4,  6,  5,  3,  1;
  0,  1,  5, 10, 11,  8,  4,  2;
  0,  1,  6, 15, 21, 19, 12,  6,  3;

Alois P. Heinz, Antidiagonals n = 0..140, flattened

Rows 0-4, 6 give: A000004, A000012, A001477, A000217, A050407(n+3), A027658.
Columns 0-9 give: A078012 and A135851(n+2), A078012(n+2) and A135851(n+4), A077868(n-1) for n>0, A050228(n-1) for n>0, A226405, A144898, A144899, A144900, A144901, A144902.
Main diagonal gives: A144904.
Cf. A000930.

A000930:= func< n | (&+[Binomial(n-2*j,j): j in [0..Floor(n/3)]]) >;
A144903:= func< n,k | k eq 0 select 0 else (&+[Binomial(n-k+j-2,j)*A000930(k-j-1) : j in [0..k-1]]) >;
[A144903(n,k): k in [0..n], n in [0..15]]; // G. C. Greubel, Aug 01 2022

A:= proc(n,k) coeftayl (x/ (1-x-x^3)/ (1-x)^(k-1), x=0, n) end:
seq(seq(A(n, d-n), n=0..d), d=0..13);

(* First program *)
a[n_, k_] := SeriesCoefficient[x/((1-x-x^3)*(1-x)^(k-1)), {x, 0, n}];
Table[a[n-k, k], {n,0,12}, {k,n,0,-1}]//Flatten (* Jean-François Alcover, Jan 15 2014 *)
(* Second Program *)
A000930[n_]:= A000930[n]= Sum[Binomial[n-2*j,j], {j,0,Floor[n/3]}];
T[n_, k_]:= T[n, k]= If[k==0, 0, Sum[Binomial[n-k+j-2,j]*A000930[k-j-1], {j,0,k- 1}]];
Table[T[n, k], {n,0,15}, {k,0,n}]//Flatten (* G. C. Greubel, Aug 01 2022 *)

def A000930(n): return sum(binomial(n-2*j,j) for j in (0..(n//3)))
def A144903(n,k):
    if (k==0): return 0
    else: return sum(binomial(n-k+j-2,j)*A000930(k-j-1) for j in (0..k-1))
flatten([[A144903(n,k) for k in (0..n)] for n in (0..15)]) # G. C. Greubel, Aug 01 2022

G.f. of column k: x/((1-x-x^3)*(1-x)^(k-1)).
A(n, n) = A144904(n).
From G. C. Greubel, Aug 01 2022: (Start)
A(n, k) = Sum_{j=0..n-1} binomial(k+j-2, j)*A000930(n-j-1), with A(0, k) = 0.
T(n, k) = Sum_{j=0..k-1} binomial(n-k-j-2, j)*A000930(k-j-1), with T(n, 0) = 0.
T(2*n, n) = A144904(n). (End)

A050228 a(n) is the number of subsequences {s(k)} of {1,2,3,...n} such that s(k+1)-s(k) is 1 or 3.

Original entry on oeis.org

1, 3, 6, 11, 19, 31, 49, 76, 116, 175, 262, 390, 578, 854, 1259, 1853, 2724, 4001, 5873, 8617, 12639, 18534, 27174, 39837, 58396, 85596, 125460, 183884, 269509, 394999, 578914, 848455, 1243487, 1822435, 2670925, 3914448, 5736920, 8407883

Offset: 1

John W. Layman, Dec 20 1999

The second differences c(n) of {a(n)} satisfy c(n)=c(n-1)+c(n-3) and give A000930 with the first 5 terms deleted.

Partial sums of A077868. - Paul Barry, Sep 16 2004

Chu, Hung Viet. "Various Sequences from Counting Subsets." Fib. Quart., 59:2 (May 2021), 150-157.

G. C. Greubel, Table of n, a(n) for n = 1..1000
Hung Viet Chu, Various sequences from counting subsets, arXiv:2005.10081 [math.CO], 2020-2021.
Z. Kasa, On scattered subword complexity, arXiv preprint arXiv:1104.4425 [cs.DM], 2011.
Index entries for linear recurrences with constant coefficients, signature (3,-3,2,-2,1).

Cf. A000930, A077868, A144898, A144899, A144900, A144901, A144902, A144903, A144904, A226405.

Cf. A078012, A099567, A135851.

A050228:= func< n | n eq 0 select 0 else (&+[Binomial(n-2*j+1, j+2): j in [0..Floor((n+1)/3)]]) >;
[A050228(n): n in [1..40]]; // G. C. Greubel, Jul 27 2022

with(combstruct): SubSetSeqU := [T, {T=Subst(U,U), S=Set(U, card>=3), U=Sequence(Z, card>=3)}, unlabeled]: seq(count(SubSetSeqU, size=n), n=9..46); # Zerinvary Lajos, Mar 18 2008

Rest[CoefficientList[Series[1/((1-x)^2*(1-x-x^3)), {x, 0, 50}], x]] (* G. C. Greubel, Apr 27 2017 *)
LinearRecurrence[{3,-3,2,-2,1},{1,3,6,11,19},50] (* Harvey P. Dale, Apr 21 2020 *)

my(x='x+O('x^50)); Vec(x/((1-x)^3-x^3*(1-x)^2)) \\ G. C. Greubel, Apr 27 2017

def A050228(n): return sum(binomial(n-2*j+1, j+2) for j in (0..((n+1)//3)))
[A050228(n) for n in (1..40)] # G. C. Greubel, Jul 27 2022

From Paul Barry, Sep 16 2004: (Start)
G.f.: x/((1-x)^3 - x^3(1-x)^2).
a(n) = 3*a(n-1) - 3*a(n-2) + 2*a(n-3) - 2*a(n-4) + a(n-5).
a(n-1) = Sum_{k=0..floor(n/3)} binomial(n-2*k, k+2). (End)
G.f. = 1/((1-x)^2*(1-x-x^3)). - N. J. A. Sloane, Jun 02 2021
a(n) = A000930(n+5) - n - 4. - Greg Dresden, Jun 20 2021
From G. C. Greubel, Jul 27 2022: (Start)
a(n) = Sum_{j=0..floor((n+1)/3)} binomial(n-2*j+1, j+2).
a(n) = A099567(n+1, 2). (End)

A144898 Expansion of x/((1-x-x^3)*(1-x)^4).

Original entry on oeis.org

0, 1, 5, 15, 36, 76, 147, 267, 463, 775, 1262, 2011, 3150, 4867, 7438, 11268, 16951, 25358, 37766, 56047, 82945, 122482, 180553, 265798, 390880, 574358, 843432, 1237966, 1816384, 2664311, 3907237, 5729077, 8399372, 12313154, 18049371, 26456513, 38778103

Offset: 0

Alois P. Heinz, Sep 24 2008

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (5,-10,11,-9,7,-4,1).

5th column of A144903.
Cf. A000930, A050228, A077868, A144899, A144900, A144901, A144902, A144903, A144904, A226405.
Cf. A078012, A099567, A135851.

A144898:= func< n | n eq 0 select 0 else (&+[Binomial(n-2*j+3, j+4): j in [0..Floor((n+3)/3)]]) >;
[A144898(n): n in [0..40]]; // G. C. Greubel, Jul 27 2022

a:= n-> (Matrix(7, (i, j)-> if i=j-1 then 1 elif j=1 then [5, -10, 11, -9, 7, -4, 1][i] else 0 fi)^n)[1, 2]: seq(a(n), n=0..40);

CoefficientList[Series[ x/((1-x-x^3)(1-x)^4), {x, 0, 40}], x] (* Vincenzo Librandi, Jun 06 2013 *)

def A144898(n): return sum(binomial(n-2*j+3, j+4) for j in (0..((n+3)//3)))
[A144898(n) for n in (0..40)] # G. C. Greubel, Jul 27 2022

G.f.: x/((1-x-x^3)*(1-x)^4).
From G. C. Greubel, Jul 27 2022: (Start)
a(n) = Sum_{j=0..floor((n+3)/3)} binomial(n-2*j+3, j+4).
a(n) = A099567(n+3, 4). (End)

A226405 Expansion of x/((1-x-x^3)*(1-x)^3).

Original entry on oeis.org

0, 1, 4, 10, 21, 40, 71, 120, 196, 312, 487, 749, 1139, 1717, 2571, 3830, 5683, 8407, 12408, 18281, 26898, 39537, 58071, 85245, 125082, 183478, 269074, 394534, 578418, 847927, 1242926, 1821840, 2670295, 3913782, 5736217, 8407142, 12321590, 18058510, 26466393

Offset: 0

Alois P. Heinz, Jun 06 2013

From Bruno Berselli, Jun 07 2013: (Start)
A050228(n)  = a(n)   -a(n-1), n>0.
A077868(n-1)= a(n) -2*a(n-1)   +a(n-2), n>1.
A000217(n)  = a(n)   -a(n-1)             -a(n-3), n>2.
A000930(n-1)= a(n) -3*a(n-1) +3*a(n-2)   -a(n-3), n>2.
n           = a(n) -2*a(n-1)   +a(n-2)   -a(n-3)   +a(n-4), n>3.
1           = a(n) -3*a(n-1) +3*a(n-2) -2*a(n-3) +2*a(n-4)   -a(n-5), n>4.
0           = a(n) -4*a(n-1) +6*a(n-2) -5*a(n-3) +4*a(n-4) -3*a(n-5) +a(n-6), n>5.
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,-6,5,-4,3,-1).

4th column of A144903.
Cf. A000217, A078012, A099567, A135851.
Cf. A000930, A050228, A077868, A144898, A144899, A144900, A144901, A144902, A144903, A144904, A226405.

A226405:= func< n | n eq 0 select 0 else (&+[Binomial(n-2*j+2, j+3): j in [0..Floor((n+2)/3)]]) >;
[A226405(n): n in [0..40]]; // G. C. Greubel, Jul 27 2022

a:= n-> (Matrix(6, (i, j)-> if i=j-1 then 1 elif j=1 then [4, -6, 5, -4, 3, -1][i] else 0 fi)^n)[1, 2]: seq(a(n), n=0..40);

LinearRecurrence[{4,-6,5,-4,3,-1}, {0,1,4,10,21,40}, 40]  (* Bruno Berselli, Jun 07 2013 *)
CoefficientList[Series[x/((1-x-x^3)*(1-x)^3), {x, 0, 50}], x] (* G. C. Greubel, Apr 28 2017 *)

my(x='x+O('x^50)); Vec(x/((1-x-x^3)*(1-x)^3)) \\ G. C. Greubel, Apr 28 2017

def A226405(n): return sum(binomial(n-2*j+2, j+3) for j in (0..((n+2)//3)))
[A226405(n) for n in (0..40)] # G. C. Greubel, Jul 27 2022

G.f.: x/((1-x-x^3)*(1-x)^3).
From G. C. Greubel, Jul 27 2022: (Start)
a(n) = Sum_{j=0..floor((n+2)/3)} binomial(n-2*j+2, j+3).
a(n) = A099567(n+2, 3). (End)

cp's OEIS Frontend

A077868 Expansion of 1/((1-x)*(1-x-x^3)).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

PARI

SageMath

Formula

Extensions

A099567 Riordan array (1/(1-x-x^3), 1/(1-x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Mathematica

SageMath

Formula

A144903 Square array A(n,k), n>=0, k>=0, read by antidiagonals, where column k is the expansion of x/((1-x-x^3)*(1-x)^(k-1)).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A050228 a(n) is the number of subsequences {s(k)} of {1,2,3,...n} such that s(k+1)-s(k) is 1 or 3.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

SageMath

Formula

A144898 Expansion of x/((1-x-x^3)*(1-x)^4).

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

A226405 Expansion of x/((1-x-x^3)*(1-x)^3).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs