A072881 -id:A072881 - cp's OEIS frontend

A048736 Dana Scott's sequence: a(n) = (a(n-2) + a(n-1) * a(n-3)) / a(n-4), a(0) = a(1) = a(2) = a(3) = 1.

1, 1, 1, 1, 2, 3, 5, 13, 22, 41, 111, 191, 361, 982, 1693, 3205, 8723, 15042, 28481, 77521, 133681, 253121, 688962, 1188083, 2249605, 6123133, 10559062, 19993321, 54419231, 93843471, 177690281, 483649942, 834032173, 1579219205, 4298430243, 7412446082, 14035282561, 38202222241, 65877982561

Offset: 0

David Johnson-Davies

The recursion has the Laurent property. If a(0), a(1), a(2), a(3) are variables, then a(n) is a Laurent polynomial (a rational function with a monic monomial denominator). - Michael Somos, Feb 05 2012

A generalization is if the recursion is modified to a(n) = (a(n-2) + a(n-1) * b*a(n-3)) / a(n-4) where b is a constant, and with arbitrary nonzero initial values, (a(0), a(1), a(2), a(3)), then a(n) = c*(a(n-3) - a(n-6)) + a(n-9) for all n in Z where c is another constant. - Michael Somos, Oct 28 2021

			G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 13*x^6 + 22*x^7 + 41*x^8 + 111*x^9 + ...

Seiichi Manyama, Table of n, a(n) for n = 0..3165 (first 501 terms from T. D. Noe)
Joshua Alman, Cesar Cuenca, and Jiaoyang Huang, Laurent phenomenon sequences, Journal of Algebraic Combinatorics 43(3) (2015), 589-633.
Hal Canary, The Dana Scott Recurrence [From _Jaume Oliver Lafont_, Sep 25 2009]
S. Fomin and A. Zelevinsky, The Laurent phenomenon, arXiv:math/0104241 [math.CO], 2001.
S. Fomin and A. Zelevinsky, The Laurent Phenomenon, Advances in Applied Mathematics, 28 (2002), 119-144.
David Gale, The strange and surprising saga of the Somos sequences, Math. Intelligencer 13(1) (1991), pp. 40-42.
D. Gale, Tracking the Automatic Ant And Other Mathematical Explorations, A Collection of Mathematical Entertainments Columns from The Mathematical Intelligencer, Springer, 1998, p. 4.
Matthew Christopher Russell, Using experimental mathematics to conjecture and prove theorems in the theory of partitions and commutative and non-commutative recurrences, PhD Dissertation, Mathematics Department, Rutgers University, May 2016.
Eric Weisstein's World of Mathematics, Laurent Polynomial
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (0,0,10,0,0,-10,0,0,1)

Cf. A006720, A006721, A006722, A006723, A092420, A072881.
Cf. A192241, A192242 (primes and where they occur).
Cf. A276531.

a048736 n = a048736_list !! n
a048736_list = 1 : 1 : 1 : 1 :
   zipWith div
     (zipWith (+)
       (zipWith (*) (drop 3 a048736_list)
                    (drop 1 a048736_list))
       (drop 2 a048736_list))
     a048736_list
-- Reinhard Zumkeller, Jun 26 2011

I:=[1,1,1,1]; [n le 4 select I[n] else (Self(n-2) + Self(n-1)*Self(n-3)) / Self(n-4): n in [1..30]]; // G. C. Greubel, Feb 20 2018

P:=proc(q) local n,v; v:=[1,1,1,1]; for n from 1 to q do
v:=[op(v),(v[-2]+v[-1]*v[-3])/v[-4]] od: op(v); end: P(35); # Paolo P. Lava, Aug 24 2025

RecurrenceTable[{a[0] == a[1] == a[2] == a[3] == 1, a[n] == (a[n - 2] + a[n - 1]a[n - 3])/a[n - 4]}, a[n], {n, 40}] (* or *) LinearRecurrence[{0, 0, 10, 0, 0, -10, 0, 0, 1}, {1, 1, 1, 1, 2, 3, 5, 13, 22}, 41] (* Harvey P. Dale, Oct 22 2011 *)

Vec((1+x+x^2-9*x^3-8*x^4-7*x^5+5*x^6+3*x^7+2*x^8) / (1-10*x^3+10*x^6-x^9)+O(x^99)) \\ Charles R Greathouse IV, Jul 01 2011

a(n) = 9*a(n-3) - a(n-6) - 3 - ( ceiling(n/3) - floor(n/3) ), with a(0) = a(1) = a(2) = a(3) = 1, a(4) = 2, a(5) = 3. - Michael Somos
From Jaume Oliver Lafont, Sep 17 2009: (Start)
a(n) = 10*a(n-3) - 10*a(n-6) + a(n-9).
G.f.: (1 + x + x^2 - 9*x^3 - 8*x^4 - 7*x^5 + 5*x^6 + 3*x^7 + 2*x^8)/(1 - 10*x^3 + 10*x^6 - x^9). (End)
a(n) = a(3-n) for all n in Z. - Michael Somos, Feb 05 2012

More terms from Michael Somos

A133848 a(n)a(n-11) = a(n-1)a(n-10)+a(n-5)+a(n-6) with initial terms a(1)=...=a(11)=1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5, 7, 9, 11, 15, 23, 35, 51, 71, 239, 411, 587, 767, 951, 1325, 2075, 3201, 4703, 6581, 22185, 38165, 54521, 71253, 88361, 123141, 192889, 297605, 437289, 611941, 2062927, 3548881, 5069803, 6625693, 8216551, 11450719

Offset: 1

Emilie Hogan, Sep 26 2007

Seiichi Manyama, Table of n, a(n) for n = 1..5091
P. Heideman and E. Hogan, A New Family of Somos-Like Recurrences, arXiv:0709.2529 [math.CO], 2007-2009.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,0,0,94,0,0,0,0,0,0,0,0,0,-94,0,0,0,0,0,0,0,0,0,1).

Cf. A072881, A092264, A133846, A133847, A133854.

a := proc(n) option remember; if n<=11 then RETURN(1); else RETURN((a(n-1)*a(n-10)+a(n-5)+a(n-6))/a(n-11)); fi; end;

Rest@ CoefficientList[Series[x (1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7 + x^8 + x^9 - 93 x^10 - 91 x^11 - 89 x^12 - 87 x^13 - 85 x^14 - 83 x^15 - 79 x^16 - 71 x^17 - 59 x^18 - 43 x^19 + 71 x^20 + 51 x^21 + 35 x^22 + 23 x^23 + 15 x^24 + 11 x^25 + 9 x^26 + 7 x^27 + 5 x^28 + 3 x^29)/((1 - x) (1 + x) (1 - x + x^2 - x^3 + x^4) (1 + x + x^2 + x^3 + x^4) (1 - 93 x^10 + x^20)), {x, 0, 47}], x] (* Michael De Vlieger, Jul 18 2016 *)

a(k=11, n) = {K = (k-1)/2; vds = vector(n); for (i=1, 2*K+1, vds[i] = 1;); for (i=2*K+2, n, vds[i] = (vds[i-1]*vds[i-2*K]+vds[i-K]+vds[i-K-1])/vds[i-2*K-1];); for (i=1, n, print1(vds[i], ","););} \\ Michel Marcus, Nov 01 2012

Vec(x*(1 +x +x^2 +x^3 +x^4 +x^5 +x^6 +x^7 +x^8 +x^9 -93*x^10 -91*x^11 -89*x^12 -87*x^13 -85*x^14 -83*x^15 -79*x^16 -71*x^17 -59*x^18 -43*x^19 +71*x^20 +51*x^21 +35*x^22 +23*x^23 +15*x^24 +11*x^25 +9*x^26 +7*x^27 +5*x^28 +3*x^29) / ((1 -x)*(1 +x)*(1 -x +x^2 -x^3 +x^4)*(1 +x +x^2 +x^3 +x^4)*(1 -93*x^10 +x^20)) + O(x^60)) \\ Colin Barker, Jul 18 2016

Sequence also generated by the linear recurrence 94*(u(n-10)-u(n-20))+u(n-30) with the initial 30 terms given by the quadratic recurrence.

G.f.: x*(1 +x +x^2 +x^3 +x^4 +x^5 +x^6 +x^7 +x^8 +x^9 -93*x^10 -91*x^11 -89*x^12 -87*x^13 -85*x^14 -83*x^15 -79*x^16 -71*x^17 -59*x^18 -43*x^19 +71*x^20 +51*x^21 +35*x^22 +23*x^23 +15*x^24 +11*x^25 +9*x^26 +7*x^27 +5*x^28 +3*x^29) / ((1 -x)*(1 +x)*(1 -x +x^2 -x^3 +x^4)*(1 +x +x^2 +x^3 +x^4)*(1 -93*x^10 +x^20)). - Colin Barker, Jul 18 2016

A092264 a(n)a(n-5) = a(n-1)a(n-4)+a(n-2)+a(n-3), with initial terms a(1) = ... = a(5) = 1.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 5, 9, 17, 65, 117, 227, 449, 1737, 3137, 6105, 12097, 46819, 84565, 164593, 326161, 1262361, 2280101, 4437891, 8794241, 34036913, 61478145, 119658449, 237118337, 917734275, 1657629797, 3226340217, 6393400849

Offset: 1

Paul Heideman (ppheideman(AT)wisc.edu), Feb 19 2004

Seiichi Manyama, Table of n, a(n) for n = 1..2801
P. Heideman and E. Hogan, A new family of Somos-like recurrences, The Electronic Journal of Combinatorics, Volume 15 (2008), #R54.
Index entries for linear recurrences with constant coefficients, signature (0, 0, 0, 28, 0, 0, 0, -28, 0, 0, 0, 1).

Cf. A072881, A133846, A133847, A133848, A133854.

R := proc(n) option remember; if n<5 then 1 else RETURN((R(n-1)*R(n-4)+R(n-2)+R(n-3))/R(n-5)); fi; end;

RecurrenceTable[{a[1]==a[2]==a[3]==a[4]==a[5]==1,a[n]==(a[n-1]a[n-4]+a[n-2]+a[n-3])/a[n-5]},a,{n,40}] (* or *) LinearRecurrence[ {0,0,0,28,0,0,0,-28,0,0,0,1},{1,1,1,1,1,3,5,9,17,65,117,227},40] (* Harvey P. Dale, Aug 08 2013 *)

a(k=5, n) = {K = (k-1)/2; vds = vector(n); for (i=1, 2*K+1, vds[i] = 1;); for (i=2*K+2, n, vds[i] = (vds[i-1]*vds[i-2*K]+vds[i-K]+vds[i-K-1])/vds[i-2*K-1];); for (i=1, n, print1(vds[i], ","););} \\ Michel Marcus, Nov 01 2012

Vec(x*(1 +x +x^2 +x^3 -27*x^4 -25*x^5 -23*x^6 -19*x^7 +17*x^8 +9*x^9 +5*x^10 +3*x^11) / ((1 -x)*(1 +x)*(1 +x^2)*(1 +5*x^2 -x^4)*(1 -5*x^2 -x^4)) + O(x^50)) \\ Colin Barker, Jul 18 2016

a(1)=1, a(2)=1, a(3)=1, a(4)=1, a(5)=1, a(6)=3, a(7)=5, a(8)=9, a(9)=17, a(10)=65, a(11)=117, a(12)=227, a(n)=28*a(n-4)-28*a(n-8)+a(n-12). - Harvey P. Dale, Aug 08 2013

G.f.: x*(1 +x +x^2 +x^3 -27*x^4 -25*x^5 -23*x^6 -19*x^7 +17*x^8 +9*x^9 +5*x^10 +3*x^11) / ((1 -x)*(1 +x)*(1 +x^2)*(1 +5*x^2 -x^4)*(1 -5*x^2 -x^4)). - Colin Barker, Jul 18 2016

A133846 a(n)*a(n-7) = a(n-1)a(n-6)+a(n-3)+a(n-4) with initial terms a(1)=...=a(7)=1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 3, 5, 7, 11, 19, 31, 111, 195, 283, 465, 831, 1381, 4969, 8741, 12697, 20885, 37353, 62101, 223471, 393121, 571051, 939331, 1680031, 2793151, 10051203, 17681675, 25684567, 42248981, 75564019, 125629681, 452080641, 795282225

Offset: 1

Emilie Hogan, Sep 26 2007

Harvey P. Dale, Table of n, a(n) for n = 1..1000
P. Heideman and E. Hogan, A New Family of Somos-Like Recurrences, arXiv:0709.2529 [math.CO], 2007-2009.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,46,0,0,0,0,0,-46,0,0,0,0,0,1).

Cf. A072881, A092264, A133847, A133848, A133854.

a := proc(n) option remember; if n<=7 then RETURN(1); else RETURN((a(n-1)*a(n-6)+a(n-3)+a(n-4))/a(n-7)); fi; end;

nxt[{a_,b_,c_,d_,e_,f_,g_}]:={b,c,d,e,f,g,(g*b+e+d)/a}; Transpose[ NestList[ nxt,{1,1,1,1,1,1,1},40]][[1]] (* or *) LinearRecurrence[ {0,0,0,0,0,46,0,0,0,0,0,-46,0,0,0,0,0,1},{1,1,1,1,1,1,1,3,5,7,11,19,31,111,195,283,465,831},40] (* Harvey P. Dale, Aug 21 2014 *)

a(k=7, n) = {K = (k-1)/2; vds = vector(n); for (i=1, 2*K+1, vds[i] = 1;); for (i=2*K+2, n, vds[i] = (vds[i-1]*vds[i-2*K]+vds[i-K]+vds[i-K-1])/vds[i-2*K-1];); for (i=1, n, print1(vds[i], ","););} \\ Michel Marcus, Nov 01 2012

Vec(x*(1 +x +x^2 +x^3 +x^4 +x^5 -45*x^6 -43*x^7 -41*x^8 -39*x^9 -35*x^10 -27*x^11 +31*x^12 +19*x^13 +11*x^14 +7*x^15 +5*x^16 +3*x^17) / ((1 -x)*(1 +x)*(1 -x +x^2)*(1 +x +x^2)*(1 -45*x^6 +x^12)) + O(x^50)) \\ Colin Barker, Jul 18 2016

G.f.: x*(1 +x +x^2 +x^3 +x^4 +x^5 -45*x^6 -43*x^7 -41*x^8 -39*x^9 -35*x^10 -27*x^11 +31*x^12 +19*x^13 +11*x^14 +7*x^15 +5*x^16 +3*x^17) / ((1 -x)*(1 +x)*(1 -x +x^2)*(1 +x +x^2)*(1 -45*x^6 +x^12)). - Colin Barker, Jul 18 2016

A133847 a(n)a(n-9) = a(n-1)a(n-8)+a(n-4)+a(n-5) with initial terms a(1)=...=a(9)=1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5, 7, 9, 13, 21, 33, 49, 169, 293, 421, 553, 823, 1365, 2179, 3265, 11289, 19585, 28153, 36993, 55081, 91393, 145929, 218689, 756163, 1311861, 1885783, 2477929, 3689557, 6121925, 9775033, 14648881, 50651601, 87875061

Offset: 1

Emilie Hogan, Sep 26 2007

Seiichi Manyama, Table of n, a(n) for n = 1..4390
P. Heideman and E. Hogan, A New Family of Somos-Like Recurrences, arXiv:0709.2529 [math.CO], 2007-2009.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,68,0,0,0,0,0,0,0,-68,0,0,0,0,0,0,0,1).

Cf. A072881, A092264, A133846, A133848, A133854.

a := proc(n) option remember; if n<=9 then RETURN(1); else RETURN((a(n-1)*a(n-8)+a(n-4)+a(n-5))/a(n-9)); fi; end;

RecurrenceTable[{a[1]==a[2]==a[3]==a[4]==a[5]==a[6]==a[7]==a[8]==a[9]==1,a[n]==(a[n-1]a[n-8]+a[n-4]+a[n-5])/a[n-9]},a,{n,50}] (* or *) LinearRecurrence[{0,0,0,0,0,0,0,68,0,0,0,0,0,0,0,-68,0,0,0,0,0,0,0,1},{1,1,1,1,1,1,1,1,1,3,5,7,9,13,21,33,49,169,293,421,553,823,1365,2179},50] (* Harvey P. Dale, Jan 14 2016 *)

a(k=9, n) = {K = (k-1)/2; vds = vector(n); for (i=1, 2*K+1, vds[i] = 1;); for (i=2*K+2, n, vds[i] = (vds[i-1]*vds[i-2*K]+vds[i-K]+vds[i-K-1])/vds[i-2*K-1];); for (i=1, n, print1(vds[i], ","););} \\ Michel Marcus, Nov 01 2012

Vec(x*(1 +x +x^2 +x^3 +x^4 +x^5 +x^6 +x^7 -67*x^8 -65*x^9 -63*x^10 -61*x^11 -59*x^12 -55*x^13 -47*x^14 -35*x^15 +49*x^16 +33*x^17 +21*x^18 +13*x^19 +9*x^20 +7*x^21 +5*x^22 +3*x^23) / ((1 -x)*(1 +x)*(1 +x^2)*(1 +x^4)*(1 -67*x^8 +x^16)) + O(x^50)) \\ Colin Barker, Jul 18 2016

Sequence also generated by the linear recurrence 68*(u(n-8)-u(n-16))+u(n-24) with the initial 24 terms given by the quadratic recurrence.

G.f.: x*(1 +x +x^2 +x^3 +x^4 +x^5 +x^6 +x^7 -67*x^8 -65*x^9 -63*x^10 -61*x^11 -59*x^12 -55*x^13 -47*x^14 -35*x^15 +49*x^16 +33*x^17 +21*x^18 +13*x^19 +9*x^20 +7*x^21 +5*x^22 +3*x^23) / ((1 -x)*(1 +x)*(1 +x^2)*(1 +x^4)*(1 -67*x^8 +x^16)). - Colin Barker, Jul 18 2016

A133854 a(n)a(n-13) = a(n-1)a(n-12)+a(n-6)+a(n-7) with initial terms a(1)=...=a(13)=1.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 5, 7, 9, 11, 13, 17, 25, 37, 53, 73, 97, 321, 549, 781, 1017, 1257, 1501, 1995, 2985, 4471, 6453, 8931, 11905, 39433, 67457, 95977, 124993, 154505, 184513, 245273, 367041, 549817, 793601, 1098393, 1464193, 4849891

Offset: 1

Emilie Hogan, Sep 26 2007

Seiichi Manyama, Table of n, a(n) for n = 1..5754
P. Heideman and E. Hogan, A New Family of Somos-Like Recurrences, arXiv:0709.2529 [math.CO], 2007-2009.
Index entries for linear recurrences with constant coefficients, signature (0,0,0,0,0,0,0,0,0,0,0,124,0,0,0,0,0,0,0,0,0,0,0,-124,0,0,0,0,0,0,0,0,0,0,0,1).

Cf. A072881, A092264, A133846, A133847, A133848.

a := proc(n) option remember; if n<=13 then RETURN(1); else RETURN((a(n-1)*a(n-12)+a(n-6)+a(n-7))/a(n-13)); fi; end;

RecurrenceTable[{a[1]==a[2]==a[3]==a[4]==a[5]==a[6]==a[7]== a[8]== a[9]== a[10]== a[11]== a[12]==a[13]==1,a[n]==(a[n-1]a[n-12]+a[n-6]+ a[n-7])/ a[n-13]},a,{n,50}] (* Harvey P. Dale, Nov 24 2015 *)

a(k=13, n) = {K = (k-1)/2; vds = vector(n); for (i=1, 2*K+1, vds[i] = 1;); for (i=2*K+2, n, vds[i] = (vds[i-1]*vds[i-2*K]+vds[i-K]+vds[i-K-1])/vds[i-2*K-1];); for (i=1, n, print1(vds[i], ","););} \\ Michel Marcus, Nov 01 2012

Vec(x*(1 +x +x^2 +x^3 +x^4 +x^5 +x^6 +x^7 +x^8 +x^9 +x^10 +x^11 -123*x^12 -121*x^13 -119*x^14 -117*x^15 -115*x^16 -113*x^17 -111*x^18 -107*x^19 -99*x^20 -87*x^21 -71*x^22 -51*x^23 +97*x^24 +73*x^25 +53*x^26 +37*x^27 +25*x^28 +17*x^29 +13*x^30 +11*x^31 +9*x^32 +7*x^33 +5*x^34 +3*x^35) / ((1 -x)*(1 +x)*(1 -x +x^2)*(1 +x^2)*(1 +x +x^2)*(1 -x^2 +x^4)*(1 +11*x^6 -x^12)*(1 -11*x^6 -x^12)) + O(x^60)) \\ Colin Barker, Jul 18 2016

Sequence also generated by the linear recurrence 124*(u(n-12)-u(n-24))+u(n-36) with the initial 36 terms given by the quadratic recurrence.

G.f.: x*(1 +x +x^2 +x^3 +x^4 +x^5 +x^6 +x^7 +x^8 +x^9 +x^10 +x^11 -123*x^12 -121*x^13 -119*x^14 -117*x^15 -115*x^16 -113*x^17 -111*x^18 -107*x^19 -99*x^20 -87*x^21 -71*x^22 -51*x^23 +97*x^24 +73*x^25 +53*x^26 +37*x^27 +25*x^28 +17*x^29 +13*x^30 +11*x^31 +9*x^32 +7*x^33 +5*x^34 +3*x^35) / ((1 -x)*(1 +x)*(1 -x +x^2)*(1 +x^2)*(1 +x +x^2)*(1 -x^2 +x^4)*(1 +11*x^6 -x^12)*(1 -11*x^6 -x^12)). - Colin Barker, Jul 18 2016

A276123 a(0) = a(1) = a(2) = 1; for n > 2, a(n) = (a(n-1) + 1)*(a(n-2) + 1) / a(n-3).

Original entry on oeis.org

1, 1, 1, 4, 10, 55, 154, 868, 2449, 13825, 39025, 220324, 621946, 3511351, 9912106, 55961284, 157971745, 891869185, 2517635809, 14213945668, 40124201194, 226531261495, 639469583290, 3610286238244, 10191389131441, 57538048550401, 162422756519761

Offset: 0

Bruno Langlois, Aug 21 2016

Colin Barker, Table of n, a(n) for n = 0..1000
Matthew Christopher Russell, Using experimental mathematics to conjecture and prove theorems in the theory of partitions and commutative and non-commutative recurrences", PhD Dissertation, Mathematics Department, Rutgers University, May 2016.
Index entries for linear recurrences with constant coefficients, signature (0,17,0,-17,0,1).

Cf. A072881, A076839, A276175.

I:=[1,1,1,4,10,55]; [n le 6 select I[n] else 17*Self(n-2)-17*Self(n-4)+Self(n-6): n in [1..30]]; // Vincenzo Librandi, Aug 27 2016

LinearRecurrence[{0, 17, 0, -17, 0, 1}, {1, 1, 1, 4, 10, 55}, 40] (* Vincenzo Librandi, Aug 27 2016 *)
nxt[{a_,b_,c_}]:={b,c,((c+1)(b+1))/a}; NestList[nxt,{1,1,1},30][[All,1]] (* Harvey P. Dale, Oct 01 2021 *)

Vec((1+x-16*x^2-13*x^3+10*x^4+4*x^5)/((1-x)*(1+x)*(1-16*x^2+x^4)) + O(x^30)) \\ Colin Barker, Aug 21 2016

a(n) = (9-3*(-1)^n)/2*a(n-1) - a(n-2) - 1.
From Colin Barker, Aug 21 2016: (Start)
a(n) = 17*a(n-2) - 17*a(n-4) + a(n-6) for n > 5.
G.f.: (1 + x - 16*x^2 - 13*x^3 + 10*x^4 + 4*x^5) / ((1-x)*(1+x)*(1 - 16*x^2 + x^4)). (End)
a(2n+1) = A073352(n). a(2n) = A048907(n). - R. J. Mathar, Jul 04 2024

More terms from Colin Barker, Aug 21 2016

A127743 Triangular array where T(n,k) is the number of set partitions of n with k atomic parts.

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 6, 5, 3, 1, 22, 16, 9, 4, 1, 92, 60, 31, 14, 5, 1, 426, 252, 120, 52, 20, 6, 1, 2146, 1160, 510, 209, 80, 27, 7, 1, 11624, 5776, 2348, 904, 335, 116, 35, 8, 1, 67146, 30832, 11610, 4184, 1481, 507, 161, 44, 9, 1

Offset: 1

Alford Arnold, Feb 24 2007

Triangular array distributing the Bell numbers (A000110). The value associated with each partition is the product of A074664(k) for each part of size k, times the number of compositions associated with the partition (A048996 & A072881). The value for T(n,k) is the total of these values for each partition of n into k parts.
Calculating the appropriate weights can be done by "working backward". Suppose for example we know the weights for 1 through 6 and desire the weight for the partitions of seven: Substitute the weights for each partition value and multiply. For example, 7 = 4+3 so f([4,3]) = 6*2 = 12; adjusting for the number of permutations of [4,3] we now have 2*12 = 24. Continuing in this manner for each partition of seven and summing to 451 we now know all of the values except that associated with the partition [7] which must be 877 - 451 = 426.
From Mike Zabrocki: (Start)
Every set partition can be uniquely split into "atomic" set partitions or is itself already atomic.
  {{1},{2},{3}} = {{1}}|{{1}}|{{1}}
  {{1},{23}} = {{1}}|{{12}}
  {{12},{3}} = {{12}}|{{1}}
  {{13},{2}} is already atomic
  {{123}} is already atomic
where this operation | is defined as {A1,...,Ar}|{B1,...,Bs} = {A1,...,Ar,B1+n,...,Bs+n}
where Bi+n = {bi1+n,bi2+n,...,bik+n} if Bi = {bi1,bi2,...,bik} and n = |A1|+|A2|+...+|Ar|. (End)
Subtriangle (n >= 1 and 1 <= k <= n) of triangle given by [0,1,1,2,1,3,1,4,1,5,1,6,...] DELTA [1,0,0,0,0,0,0,0,...] where DELTA is the operator defined in A084938. - Philippe Deléham, Aug 03 2007
From Peter Bala, Aug 05 2014: (Start)
Let B(x) = 1 + x + 2*x^2 + 5*x^3 + 15*x^4 + ... denote the o.g.f. for the Bell numbers A000110. Let f(x) = (B(x) - 1)/(x*B(x)) = 1 + x + x^2 + 2*x^3 + 6*x^4 + 22*x^5 + ..., the o.g.f. for the first column of this array. Then this array appears to be the Riordan array (f(x), x*f(x)).
If true, this gives the o.g.f. of the array as (B(x) - 1)/( x*(t + (1 - t)*B(x)) ) = 1 + (1 + t)*x + (2 + 2*t + t^2)*x^2 + ... and also the hockey-stick recurrence: T(n+1,k+1) = T(n,k) + T(n-1,k) + 2*T(n-2,k) + 6*T(n-3,k) + 22*T(n-4,k) + ..., n,k >= 1. (End)

			The partitions of 4 are
  4 31 22 211 1111
and the products are
  1*6 2*2 1*1 3*1 1*1
therefore row 4 of the table is
  6 5 3 1.
From _Philippe Deléham_, Aug 03 2007: (Start)
Triangle begins:
     1;
     1,    1;
     2,    2,   1;
     6,    5,   3,   1;
    22,   16,   9,   4,  1;
    92,   60,  31,  14,  5,  1;
   426,  252, 120,  52, 20,  6, 1;
  2146, 1160, 510, 209, 80, 27, 7, 1; ...
Triangle [0,1,1,2,1,3,1,4,1,...] DELTA [1,0,0,0,0,0,...] begins:
  1;
  0,    1;
  0,    1,    1;
  0,    2,    2,   1;
  0,    6,    5,   3,   1;
  0,   22,   16,   9,   4,  1;
  0,   92,   60,  31,  14,  5,  1;
  0,  426,  252, 120,  52, 20,  6, 1;
  0, 2146, 1160, 510, 209, 80, 27, 7, 1; ...
(End)

G. C. Greubel, Rows n=1..100 of triangle, flattened

Cf. A000041, A000110 (row sums), A074664 (1st column), A048996, A072881, A036043, A036042, A084938.

T[n_, m_] := T[n, m] = Sum[Sum[T[k+i, k]*Binomial[n-m-k-1, n-m-k-i], {i, 1, n-m-k}]*Binomial[k+m-1, k], {k, 1, n-m}] + Binomial[n-1, n-m]; Table[T[n, m], {n, 1, 10}, {m, 1, n}] // Flatten (* Jean-François Alcover, Mar 23 2015, after Vladimir Kruchinin *)

T(n,m):=sum((sum(T(k+i,k)*binomial(n-m-k-1,n-m-k-i),i,1,n-m-k))*binomial(k+m-1,k),k,1,n-m)+binomial(n-1,n-m); /* Vladimir Kruchinin, Mar 21 2015 */

{T(n,m) = sum(k=1,n-m, (sum(i=1, n-m-k, (T(k+i, k)*binomial(n-m-k-1, n-m-k-i))*binomial(k+m-1, k)))) + binomial(n-1, n-m)};
for(n=1, 10, for(m=1, n, print1(T(n,m), ", "))) \\ G. C. Greubel, Dec 06 2018

T(n, m) = Sum_{k=1..n-m}( Sum_{i=1..n-m-k}(T(k+i, k)*C(n-m-k-1, n-m-k-i))*C(k+m-1, k) ) + C(n-1, n-m). - Vladimir Kruchinin, Mar 21 2015

Edited by Franklin T. Adams-Watters, Jan 25 2010

A276122 a(0) = a(1) = a(2) = 1; for n > 2, a(n) = (a(n-1)^2+a(n-2)^2+a(n-1)+a(n-2))/a(n-3).

Original entry on oeis.org

1, 1, 1, 4, 22, 526, 69427, 219111589, 91273561736491, 119994570874632853695766, 65713991236617279734602790963627271046, 47311933073383646516067037755547920981262829886906923065810924

Offset: 0

Bruno Langlois, Aug 21 2016

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..16

Cf. A064098, A072881, A101879, A165903.

RecurrenceTable[{a[n] == (a[n - 1]^2 + a[n - 2]^2 + a[n - 1] + a[n - 2])/a[n - 3], a[0] == a[1] == a[2] == 1}, a, {n, 0, 11}] (* Michael De Vlieger, Aug 21 2016 *)

a(n) = 6*a(n-1)*a(n-2)-a(n-3)-1.

a(n) ~ 1/6 * c^(phi^n), where c = 2.059783590102273... and phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Mar 20 2017

a(10) corrected by Seiichi Manyama, Aug 21 2016

A283958 a(n) = (Sum_{j=1..h-1} a(n-j) + a(n-1)*a(n-h+1))/a(n-h) with a(1), ..., a(h)=1, where h = 4.

Original entry on oeis.org

1, 1, 1, 1, 4, 10, 25, 139, 391, 1033, 5806, 16384, 43345, 243685, 687709, 1819441, 10228936, 28867366, 76373161, 429371599, 1211741635, 3205853305, 18023378194, 50864281276, 134569465633, 756552512521, 2135088071929, 5648711703265, 31757182147660

Offset: 1

Seiichi Manyama, Mar 18 2017

Seiichi Manyama, Table of n, a(n) for n = 1..1852

Cf. A283329.

Cf. A072881 (h=3), this sequence (h=4), A283959 (h=5), A283960 (h=6).

a[n_]:= If[n<5, 1, (Sum[a[n-j] , {j, 3}] +  a[n - 1] a[n - 3])/a[n - 4]]; Table[a[n], {n, 29}] (* Indranil Ghosh, Mar 18 2017 *)

a(n) = if(n<5, 1, (sum(j=1, 3, a(n - j)) + a(n - 1)*a(n - 3))/a(n - 4));
for(n=1, 29, print1(a(n),", ")) \\ Indranil Ghosh, Mar 18 2017

a(3*k)   = 3*a(3*k-1) - a(3*k-2) - 1,
a(3*k+1) = 3*a(3*k)   - a(3*k-1) - 1,
a(3*k+2) = 6*a(3*k+1) - a(3*k)   - 1.
G.f.: -x*(4*x^8 + 10*x^7 + 25*x^6 - 33*x^5 - 39*x^4 - 42*x^3 + x^2 + x + 1) / ((x - 1)*(x^2 + x + 1)*(x^6 - 42*x^3 + 1)). - Alois P. Heinz, Mar 20 2017

cp's OEIS Frontend

A048736 Dana Scott's sequence: a(n) = (a(n-2) + a(n-1) * a(n-3)) / a(n-4), a(0) = a(1) = a(2) = a(3) = 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

Extensions

A133848 a(n)*a(n-11) = a(n-1)*a(n-10)+a(n-5)+a(n-6) with initial terms a(1)=...=a(11)=1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A092264 a(n)*a(n-5) = a(n-1)*a(n-4)+a(n-2)+a(n-3), with initial terms a(1) = ... = a(5) = 1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A133846 a(n)*a(n-7) = a(n-1)a(n-6)+a(n-3)+a(n-4) with initial terms a(1)=...=a(7)=1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A133847 a(n)*a(n-9) = a(n-1)*a(n-8)+a(n-4)+a(n-5) with initial terms a(1)=...=a(9)=1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A133854 a(n)*a(n-13) = a(n-1)*a(n-12)+a(n-6)+a(n-7) with initial terms a(1)=...=a(13)=1.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

A276123 a(0) = a(1) = a(2) = 1; for n > 2, a(n) = (a(n-1) + 1)*(a(n-2) + 1) / a(n-3).

Views

Author

A133848 a(n)a(n-11) = a(n-1)a(n-10)+a(n-5)+a(n-6) with initial terms a(1)=...=a(11)=1.

A092264 a(n)a(n-5) = a(n-1)a(n-4)+a(n-2)+a(n-3), with initial terms a(1) = ... = a(5) = 1.

A133847 a(n)a(n-9) = a(n-1)a(n-8)+a(n-4)+a(n-5) with initial terms a(1)=...=a(9)=1.

A133854 a(n)a(n-13) = a(n-1)a(n-12)+a(n-6)+a(n-7) with initial terms a(1)=...=a(13)=1.