A000078 -id:A000078 - cp's OEIS frontend

A159741 a(n) = 8*(2^n - 1).

8, 24, 56, 120, 248, 504, 1016, 2040, 4088, 8184, 16376, 32760, 65528, 131064, 262136, 524280, 1048568, 2097144, 4194296, 8388600, 16777208, 33554424, 67108856, 134217720, 268435448, 536870904, 1073741816, 2147483640, 4294967288, 8589934584, 17179869176, 34359738360

Offset: 1

Al Hakanson (hawkuu(AT)gmail.com), Apr 20 2009

Fifth diagonal of the array which contains m-acci numbers in the m-th row.
The base array is constructed from m-acci numbers starting each with 1, 1, and 2 and filling one row of the table (see the examples).
The main and the upper diagonals of the table are the powers of 2, A000079.
The first subdiagonal is essentially A000225, followed by essentially A036563.
The next subdiagonal is this sequence here, followed by A159742, A159743, A159744, A159746, A159747, A159748.
a(n) written in base 2: 1000, 11000, 111000, 1111000, ..., i.e., n times 1 and 3 times 0 (A161770). - Jaroslav Krizek, Jun 18 2009
Also numbers for which n^8/(n+8) is an integer. - Vicente Izquierdo Gomez, Jan 03 2013

			From _R. J. Mathar_, Apr 22 2009: (Start)
The base table is
.1..1....1....1....1....1....1....1....1....1....1....1....1....1
.1..1....1....1....1....1....1....1....1....1....1....1....1....1
.2..2....2....2....2....2....2....2....2....2....2....2....2....2
.0..2....3....4....4....4....4....4....4....4....4....4....4....4
.0..2....5....7....8....8....8....8....8....8....8....8....8....8
.0..2....8...13...15...16...16...16...16...16...16...16...16...16
.0..2...13...24...29...31...32...32...32...32...32...32...32...32
.0..2...21...44...56...61...63...64...64...64...64...64...64...64
.0..2...34...81..108..120..125..127..128..128..128..128..128..128
.0..2...55..149..208..236..248..253..255..256..256..256..256..256
.0..2...89..274..401..464..492..504..509..511..512..512..512..512
.0..2..144..504..773..912..976.1004.1016.1021.1023.1024.1024.1024
.0..2..233..927.1490.1793.1936.2000.2028.2040.2045.2047.2048.2048
.0..2..377.1705.2872.3525.3840.3984.4048.4076.4088.4093.4095.4096
Columns: A000045, A000073, A000078, A001591, A001592 etc. (End)

G. C. Greubel, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (3,-2).

Cf. A000079, A000225, A036563, A159742, A159743, A159744, A159746, A159747, A159748.

Cf. A000918, A028399, A161770, A173787, A175161, A175166.

[8*(2^n -1): n in [1..50]]; // G. C. Greubel, May 22 2018

T := proc(n,m) option remember ; if n < 0 then 0; elif n <= 1 then 1; elif n = 2 then 2; else add(procname(n-i,m),i=1..m) ; fi: end: A159741 := proc(n) T(n+4,n+1) ; end: seq(A159741(n),n=1..40) ; # R. J. Mathar, Apr 22 2009

Table[8(2^n-1),{n,60}] (* Vladimir Joseph Stephan Orlovsky, Apr 18 2011 *)
LinearRecurrence[{3,-2},{8,24},30] (* Harvey P. Dale, Jan 01 2019 *)

a(n)=8*(2^n-1) \\ Charles R Greathouse IV, Sep 24 2015

From R. J. Mathar, Apr 22 2009: (Start)
a(n) = 3*a(n-1) - 2*a(n-2).
a(n) = 8*(2^n-1).
G.f.: 8*x/((2*x-1)*(x-1)). (End)
From Jaroslav Krizek, Jun 18 2009: (Start)
a(n) = Sum_{i=3..(n+2)} 2^i.
a(n) = Sum_{i=1..n} 2^(i+2).
a(n) = a(n-1) + 2^(n+2) for n >= 2. (End)
a(n) = A173787(n+3,3) = A175166(2*n)/A175161(n). - Reinhard Zumkeller, Feb 28 2010
From Elmo R. Oliveira, Jun 15 2025: (Start)
E.g.f.: 8*exp(x)*(exp(x) - 1).
a(n) = 8*A000225(n) = 4*A000918(n+1) = 2*A028399(n+2). (End)

More terms from R. J. Mathar, Apr 22 2009
Edited by Al Hakanson (hawkuu(AT)gmail.com), May 11 2009
Comments claiming negative entries deleted by R. J. Mathar, Aug 24 2009

A107066 Expansion of 1/(1-2*x+x^5).

Original entry on oeis.org

1, 2, 4, 8, 16, 31, 60, 116, 224, 432, 833, 1606, 3096, 5968, 11504, 22175, 42744, 82392, 158816, 306128, 590081, 1137418, 2192444, 4226072, 8146016, 15701951, 30266484, 58340524, 112454976, 216763936, 417825921, 805385358, 1552430192, 2992405408, 5768046880

Offset: 0

Paul Barry, May 10 2005

Row sums of number triangle A107065.
Same as A018922 plus first 3 additional terms. - Vladimir Joseph Stephan Orlovsky, Jul 08 2011
a(n) is the number of binary words of length n containing no subword 01011. - Alois P. Heinz, Mar 14 2012

			G.f. = 1 + 2*x + 4*x^2 + 8*x^3 + 16*x^4 + 31*x^5 + 60*x^6 + 116*x^7 + 224*x^8 + ...

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Otto Dunkel, Solutions of a probability difference equation, Amer. Math. Monthly, 32 (1925), 354-370; see p. 356.
Jia Huang, A coin flip game and generalizations of Fibonacci numbers, arXiv:2501.07463 [math.CO], 2025. See p. 7.
Thomas Langley, Jeffrey Liese, and Jeffrey Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011), Article #11.4.2.
Index entries for linear recurrences with constant coefficients, signature (2,0,0,0,-1).

Cf. A018922, A119407 (partial sums), A000078 (first differences).
Cf. A209888. - Alois P. Heinz, Mar 14 2012
Column k = 1 of array A140996 (with a different offset) and second main diagonal of A140995.
Column k = 4 of A172119 (with a different offset).

a:=[1,2,4,8,16];; for n in [6..40] do a[n]:=2*a[n-1]-a[n-5]; od; a; # G. C. Greubel, Jun 12 2019

I:=[1,2,4,8,16]; [n le 5 select I[n] else 2*Self(n-1) - Self(n-5): n in [1..40]]; // G. C. Greubel, Jun 12 2019

CoefficientList[Series[1/(1 - 2*z + z^5), {z, 0, 40}], z] (* Vladimir Joseph Stephan Orlovsky, Jul 08 2011 *)
LinearRecurrence[{2,0,0,0,-1}, {1,2,4,8,16}, 40] (* G. C. Greubel, Jun 12 2019 *)

{a(n) = if( n<0, n = -n; polcoeff( -x^5 / (1 - 2*x^4 + x^5) + x * O(x^n), n), polcoeff( 1 / (1 - 2*x + x^5) + x * O(x^n), n))} /* Michael Somos, Dec 28 2012 */

(1/(1-2*x+x^5)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, Jun 12 2019

a(n) = 2*a(n-1) - a(n-5).
a(n) = Sum_{k=0..floor(n/5)} C(n-4*k, k) * 2^(n-2*k) *(-1)^k.
a(n) = A018922(n-3) for n >= 3. - R. J. Mathar, Mar 09 2007
First difference of A119407. - Michael Somos, Dec 28 2012
From Petros Hadjicostas, Jun 12 2019: (Start)
G.f.: 1/((1 - x)*(1 - x - x^2 - x^3 - x^4)).
Setting k = 1 in the double recurrence for array A140996, we get that a(n+5) = 1 + a(n+1) + a(n+2) + a(n+3) + a(n+4) for n >= 0, which of course we can prove using other methods as well. See also Dunkel (1925).
(End)
a(n) = Sum_{k=0..n+3} A000078(k). - Greg Dresden, Jan 01 2021

A048888 a(n) = Sum_{m=1..n} T(m,n+1-m), array T as in A048887.

Original entry on oeis.org

0, 1, 2, 4, 7, 13, 23, 42, 76, 139, 255, 471, 873, 1627, 3044, 5718, 10779, 20387, 38673, 73561, 140267, 268065, 513349, 984910, 1892874, 3643569, 7023561, 13557019, 26200181, 50691977, 98182665, 190353369, 369393465, 717457655

Offset: 0

Clark Kimberling

nonn

From Marc LeBrun, Dec 12 2001: (Start)
Define a "numbral arithmetic" by replacing addition with binary bitwise inclusive-OR (so that [3] + [5] = [7] etc.) and multiplication becomes shift-&-OR instead of shift-&-add (so that [3] * [3] = [7] etc.). [d] divides [n] means there exists an [e] with [d] * [e] = [n]. For example the six divisors of [14] are [1], [2], [3], [6], [7] and [14]. Then it appears that this sequence gives the number of proper divisors of [2^n-1]. Conjecture confirmed by Richard C. Schroeppel, Dec 14 2001. (End)
The number of "prime endofunctions" on n points, meaning the cardinality of the subset of the A001372(n) mappings (or mapping patterns) up to isomorphism from n (unlabeled) points to themselves (endofunctions) which are neither the sum of prime endofunctions (i.e., whose disjoint connected components are prime endofunctions) nor the categorical product of prime endofunctions. The n for which a(n) is prime (n such that the number of prime endofunctions on n points is itself prime) are 2, 4, 5, 6, 9, 13, 19, ... - Jonathan Vos Post, Nov 19 2006
For n>=1, compositions p(1)+p(2)+...+p(m)=n such that p(k)<=p(1)+1, see example. - Joerg Arndt, Dec 28 2012

			From _Joerg Arndt_, Dec 28 2012: (Start)
There are a(6)=23 compositions p(1)+p(2)+...+p(m)=6 such that p(k)<=p(1)+1:
[ 1]  [ 1 1 1 1 1 1 ]
[ 2]  [ 1 1 1 1 2 ]
[ 3]  [ 1 1 1 2 1 ]
[ 4]  [ 1 1 2 1 1 ]
[ 5]  [ 1 1 2 2 ]
[ 6]  [ 1 2 1 1 1 ]
[ 7]  [ 1 2 1 2 ]
[ 8]  [ 1 2 2 1 ]
[ 9]  [ 2 1 1 1 1 ]
[10]  [ 2 1 1 2 ]
[11]  [ 2 1 2 1 ]
[12]  [ 2 1 3 ]
[13]  [ 2 2 1 1 ]
[14]  [ 2 2 2 ]
[15]  [ 2 3 1 ]
[16]  [ 3 1 1 1 ]
[17]  [ 3 1 2 ]
[18]  [ 3 2 1 ]
[19]  [ 3 3 ]
[20]  [ 4 1 1 ]
[21]  [ 4 2 ]
[22]  [ 5 1 ]
[23]  [ 6 ]
(End)

D. Applegate, M. LeBrun, N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.
A. Frosini and S. Rinaldi, On the Sequence A079500 and Its Combinatorial Interpretations, J. Integer Seq., Vol. 9 (2006), Article 06.3.1.

Cf. A007059.

Cf. A000312, A001372, A002861, A006961, A001373, A054050, A054745, A125024.

N = 66;  x = 'x + O('x^N);
gf = sum(n=0,N,  (1-x^n)*x^n/(1-2*x+x^(n+1)) ) + 'c0;
v = Vec(gf);  v[1]-='c0;  v
/* Joerg Arndt, Apr 14 2013 */

G.f.: Sum_{k>0} x^k*(1-x^k)/(1-2*x+x^(k+1)). - Vladeta Jovovic, Feb 25 2003

a(m) = Sum_{ n=2..m+1 } Fn(m) where Fn is a Fibonacci n-step number (Fibonacci, tetranacci, etc.) indexed as in A000045, A000073, A000078. - Gerald McGarvey, Sep 25 2004

A122189 Heptanacci numbers: each term is the sum of the preceding 7 terms, with a(0),...,a(6) = 0,0,0,0,0,0,1.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 32, 64, 127, 253, 504, 1004, 2000, 3984, 7936, 15808, 31489, 62725, 124946, 248888, 495776, 987568, 1967200, 3918592, 7805695, 15548665, 30972384, 61695880, 122895984, 244804400, 487641600, 971364608, 1934923521

Offset: 0

Roger L. Bagula and Gary W. Adamson, Oct 18 2006

See A066178 (essentially the same sequence) for more about the heptanacci numbers and other generalizations of the Fibonacci numbers (A000045).

Robert Price, Table of n, a(n) for n = 0..1000
Tomás Aguilar-Fraga, Jennifer Elder, Rebecca E. Garcia, Kimberly P. Hadaway, Pamela E. Harris, Kimberly J. Harry, Imhotep B. Hogan, Jakeyl Johnson, Jan Kretschmann, Kobe Lawson-Chavanu, J. Carlos Martínez Mori, Casandra D. Monroe, Daniel Quiñonez, Dirk Tolson III, and Dwight Anderson Williams II, Interval and L-interval Rational Parking Functions, arXiv:2311.14055 [math.CO], 2023. See p. 14.
Martin Burtscher, Igor Szczyrba, and Rafał Szczyrba, Analytic Representations of the n-anacci Constants and Generalizations Thereof, Journal of Integer Sequences, Vol. 18 (2015), Article 15.4.5.
Taras Goy and Mark Shattuck, Some Toeplitz-Hessenberg Determinant Identities for the Tetranacci Numbers, J. Int. Seq., Vol. 23 (2020), Article 20.6.8.
Tian-Xiao He, Impulse Response Sequences and Construction of Number Sequence Identities, J. Int. Seq. 16 (2013) #13.8.2.
F. T. Howard and Curtis Cooper, Some identities for r-Fibonacci numbers, Fibonacci Quart. 49 (2011), no. 3, 231-243.
Omar Khadir, László Németh, and László Szalay, Tiling of dominoes with ranked colors, Results in Math. (2024) Vol. 79, Art. No. 253. See p. 2.
Benjamin E. Merkel, Probabilities of Consecutive Events in Coin Flipping, Master's Thesis, Univ. Cincinatti, May 11 2011.
László Németh and László Szalay, Explicit solution of system of two higher-order recurrences, arXiv:2408.12196 [math.NT], 2024. See p. 10.
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1,1,1,1).

Cf. A000045 (k=2, Fibonacci numbers), A000073 (k=3, tribonacci) A000078 (k=4, tetranacci) A001591 (k=5, pentanacci) A001592 (k=6, hexanacci), A122189 (k=7, heptanacci).

Cf. A066178, A000322, A248700.

for n from 0 to 50 do k(n):=sum((-1)^i*binomial(n-6-7*i,i)*2^(n-6-8*i),i=0..floor((n-6)/8))-sum((-1)^i*binomial(n-7-7*i,i)*2^(n-7-8*i),i=0..floor((n-7)/8)):od:seq(k(n),n=0..50); a:=taylor((z^6-z^7)/(1-2*z+z^8),z=0,51);for p from 0 to 50 do j(p):=coeff(a,z,p):od :seq(j(p),p=0..50); # Richard Choulet, Feb 22 2010

LinearRecurrence[{1, 1, 1, 1, 1, 1, 1}, {0, 0, 0, 0, 0, 0, 1}, 50] (* Vladimir Joseph Stephan Orlovsky, May 25 2011 *)
a={0,0,0,0,0,0,1} For[n=7, n≤100, n++, sum=Plus@@a; Print[sum]; a=RotateLeft[a]; a[[7]]=sum] (* Robert Price, Dec 04 2014 *)

a(n)=([0,1,0,0,0,0,0; 0,0,1,0,0,0,0; 0,0,0,1,0,0,0; 0,0,0,0,1,0,0; 0,0,0,0,0,1,0; 0,0,0,0,0,0,1; 1,1,1,1,1,1,1]^n*[0;0;0;0;0;0;1])[1,1] \\ Charles R Greathouse IV, Jun 20 2015

G.f.: x^6/(1-x-x^2-x^3-x^4-x^5-x^6-x^7). - R. J. Mathar, Feb 13 2009
G.f.: Sum_{n >= 0} x^(n+5) * [ Product_{k = 1..n} (k + k*x + k*x^2 + k*x^3 + k*x^4 + k*x^5 + x^6)/(1 + k*x + k*x^2 + k*x^3 + k*x^4 + k*x^5 + k*x^6) ]. - Peter Bala, Jan 04 2015
Another form of the g.f.: f(z) = (z^6-z^7)/(1-2*z+z^8), then a(n) = Sum_{i=0..floor((n-6)/8)} (-1)^i*binomial(n-6-7*i,i)*2^(n-6-8*i) - Sum_{i=0..floor((n-7)/8)} (-1)^i*binomial(n-7-7*i,i)*2^(n-7-8*i) with Sum_{i=m..n} alpha(i) = 0 for m>n. - Richard Choulet, Feb 22 2010
Sum_{k=0..6*n} a(k+b)*A063265(n,k) = a(7*n+b), b>=0.
a(n) = 2*a(n-1) - a(n-8). - Joerg Arndt, Sep 24 2020

Edited by N. J. A. Sloane, Nov 20 2007

Wrong Binet-type formula removed by R. J. Mathar, Feb 13 2009

A106273 Discriminant of the polynomial x^n - x^(n-1) - ... - x - 1.

Original entry on oeis.org

1, 5, -44, -563, 9584, 205937, -5390272, -167398247, 6042477824, 249317139869, -11597205023744, -601139006326619, 34383289858207744, 2151954708695291177, -146323302326154543104, -10742330662077208945103, 846940331265064719417344, 71373256668946058057974997

Offset: 1

T. D. Noe, May 02 2005

sign

This polynomial is the characteristic polynomial of the Fibonacci and Lucas n-step sequences. These discriminants are prime for n=2, 4, 6, 26, 158 (A106274). It appears that the term a(2n+1) always has a factor of 2^(2n). With that factor removed, the discriminants are prime for odd n=3, 5, 7, 21, 99, 405. See A106275 for the combined list.
a(n) is the determinant of an r X r Hankel matrix whose entries are w(i+j) where w(n) = x1^n + x2^n + ... + xr^n where x1,x2,...xr are the roots of the titular characteristic polynomial. E.g., A000032 for n=2, A001644 for n=3, A073817 for n=4, A074048 for n=5, A074584 for n=6, A104621 for n=7, ... - Kai Wang, Jan 17 2021
Luca proves that a(n) is a term of the corresponding k-nacci sequence only for n=2 and 3. - Michel Marcus, Apr 12 2025

Vincenzo Librandi, Table of n, a(n) for n = 1..200
Mohammad K. Azarian, On the Hyperfactorial Function, Hypertriangular Function, and the Discriminants of Certain Polynomials, International Journal of Pure and Applied Mathematics 36(2), 2007, pp. 251-257. MR2312537. Zbl 1133.11012.
Michael Baake and Uwe Grimm, Fourier transform of Rauzy fractals and point spectrum of 1D Pisot inflation tilings, arXiv:1907.11012 [math.MG], 2019.
Herbert Batte and Florian Luca, The Discriminant of the Characteristic Polynomial of the kth Fibonacci sequence is not a member of the kth Lucas sequence, arXiv:2504.02514 [math.NT], 2025.
Florian Luca, On the discriminant of the k-generalized Fibonacci polynomial, II, Fibonacci Quart. 62 (2024), no. 3, 193-200.
Eric Weisstein's World of Mathematics, Fibonacci n-Step Number
Eric Weisstein's World of Mathematics, Polynomial Discriminant

Cf. A086797 (discriminant of the polynomial x^n-x-1), A000045, A000073, A000078, A001591, A001592 (Fibonacci n-step sequences), A000032, A001644, A073817, A074048, A074584, A104621, A105754, A105755 (Lucas n-step sequences), A086937, A106276, A106277, A106278 (number of distinct zeros of these polynomials for n=2, 3, 4, 5).

Discriminant[p_?PolynomialQ, x_] := With[{n=Exponent[p, x]}, Cancel[((-1)^(n(n-1)/2) Resultant[p, D[p, x], x])/Coefficient[p, x, n]^(2n-1)]]; Table[Discriminant[x^n-Sum[x^i, {i, 0, n-1}], x], {n, 20}]

{a(n)=(-1)^(n*(n+1)/2)*((n+1)^(n+1)-2*(2*n)^n)/(n-1)^2}  \\ Max Alekseyev, May 05 2005

a(n)=poldisc('x^n-sum(k=0,n-1,'x^k)); \\ Joerg Arndt, May 04 2013

a(n) = (-1)^(n*(n+1)/2) * ((n+1)^(n+1)-2*(2*n)^n)/(n-1)^2. - Max Alekseyev, May 05 2005

A209972 Number of binary words of length n avoiding the subword given by the binary expansion of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 2, 3, 4, 1, 1, 1, 2, 4, 5, 5, 1, 1, 1, 2, 4, 7, 8, 6, 1, 1, 1, 2, 4, 7, 12, 13, 7, 1, 1, 1, 2, 4, 7, 12, 20, 21, 8, 1, 1, 1, 2, 4, 7, 12, 21, 33, 34, 9, 1, 1, 1, 2, 4, 8, 13, 20, 37, 54, 55, 10, 1, 1, 1, 2, 4, 8, 15, 24, 33, 65, 88, 89, 11, 1, 1

Offset: 0

Alois P. Heinz, Mar 16 2012

			Square array begins:
  1,  1,  1,   1,   1,   1,   1,   1,   1, ...
  1,  1,  2,   2,   2,   2,   2,   2,   2, ...
  1,  1,  3,   3,   4,   4,   4,   4,   4, ...
  1,  1,  4,   5,   7,   7,   7,   7,   8, ...
  1,  1,  5,   8,  12,  12,  12,  13,  15, ...
  1,  1,  6,  13,  20,  21,  20,  24,  28, ...
  1,  1,  7,  21,  33,  37,  33,  44,  52, ...
  1,  1,  8,  34,  54,  65,  54,  81,  96, ...
  1,  1,  9,  55,  88, 114,  88, 149, 177, ...

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

Columns give: 0, 1: A000012, 2: A001477(n+1), 3: A000045(n+2), 4, 6: A000071(n+3), 5: A005251(n+3), 7: A000073(n+3), 8, 12, 14: A008937(n+1), 9, 11, 13: A049864(n+2), 10: A118870, 15: A000078(n+4), 16, 20, 24, 26, 28, 30: A107066, 17, 19, 23, 25, 29: A210003, 18, 22: A209888, 21: A152718(n+3), 27: A210021, 31: A001591(n+5), 32: A001949(n+5), 33, 35, 37, 39, 41, 43, 47, 49, 53, 57, 61: A210031.

Main diagonal equals A234005 or column k=0 of A233940.

A[n_, k_] := Module[{bb, cnt = 0}, Do[bb = PadLeft[IntegerDigits[j, 2], n]; If[SequencePosition[bb, IntegerDigits[k, 2], 1]=={}, cnt++], {j, 0, 2^n-1 }]; cnt];
Table[A[n-k, k], {n, 0, 12}, {k, n, 0, -1}] // Flatten (* Jean-François Alcover, Nov 01 2021 *)

A238888 Number A(n,k) of self-inverse permutations p on [n] with displacement of elements restricted by k: |p(i)-i| <= k, square array A(n,k), n>=0, k>=0, read by antidiagonals.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 3, 1, 1, 1, 2, 4, 5, 1, 1, 1, 2, 4, 8, 8, 1, 1, 1, 2, 4, 10, 15, 13, 1, 1, 1, 2, 4, 10, 22, 29, 21, 1, 1, 1, 2, 4, 10, 26, 48, 56, 34, 1, 1, 1, 2, 4, 10, 26, 66, 103, 108, 55, 1, 1, 1, 2, 4, 10, 26, 76, 158, 225, 208, 89, 1, 1, 1, 2, 4, 10, 26, 76, 206, 376, 492, 401, 144, 1

Offset: 0

Joerg Arndt and Alois P. Heinz, Mar 06 2014

A(n,k) is exactly the number of matchings of the k-th power of the path on n vertices. Here is A(4,1): o o o o (1234); o o o--o (1243); o o--o o (1324); o--o o o (2134); o--o o--o (2143). - Pietro Codara, Feb 17 2015

			A(4,0) = 1: 1234.
A(4,1) = 5: 1234, 1243, 1324, 2134, 2143.
A(4,2) = 8: 1234, 1243, 1324, 1432, 2134, 2143, 3214, 3412.
A(4,3) = 10: 1234, 1243, 1324, 1432, 2134, 2143, 3214, 3412, 4231, 4321.
Square array A(n,k) begins:
  1,  1,   1,   1,   1,   1,   1,   1,   1, ...
  1,  1,   1,   1,   1,   1,   1,   1,   1, ...
  1,  2,   2,   2,   2,   2,   2,   2,   2, ...
  1,  3,   4,   4,   4,   4,   4,   4,   4, ...
  1,  5,   8,  10,  10,  10,  10,  10,  10, ...
  1,  8,  15,  22,  26,  26,  26,  26,  26, ...
  1, 13,  29,  48,  66,  76,  76,  76,  76, ...
  1, 21,  56, 103, 158, 206, 232, 232, 232, ...
  1, 34, 108, 225, 376, 546, 688, 764, 764, ...

Joerg Arndt and Alois P. Heinz, Antidiagonals n = 0..48, flattened

Columns k=0-10 give: A000012, A000045(n+1), A000078(n+3), A239075, A239076, A239077, A239078, A239079, A239080, A239081, A239082.

Main diagonal gives A000085.

b:= proc(n, k, s) option remember; `if`(n=0, 1, `if`(n in s,
      b(n-1, k, s minus {n}), b(n-1, k, s) +add(`if`(i in s, 0,
      b(n-1, k, s union {i})), i=max(1, n-k)..n-1)))
    end:
A:= (n, k)-> `if`(k>n, A(n, n), b(n, k, {})):
seq(seq(A(n, d-n), n=0..d), d=0..12);

b[n_, k_, s_] := b[n, k, s] = If[n == 0, 1, If[MemberQ[s, n], b[n-1, k, DeleteCases[s, n]], b[n-1, k, s] + Sum[If[MemberQ[s, i], 0, b[n-1, k, s ~Union~ {i}]], {i, Max[1, n-k], n-1}]]]; A[n_, k_] := If[k>n, A[n, n], b[n, k, {}]]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Mar 12 2014, translated from Maple *)

T(n,k) = Sum_{i=0..k} A238889(n,i).

A050232 a(n) is the number of n-tosses having a run of 4 or more heads for a fair coin (i.e., probability is a(n)/2^n).

Original entry on oeis.org

0, 0, 0, 1, 3, 8, 20, 48, 111, 251, 558, 1224, 2656, 5713, 12199, 25888, 54648, 114832, 240335, 501239, 1042126, 2160676, 4468664, 9221281, 18989899, 39034824, 80103276, 164126496, 335808927, 686182387, 1400438814, 2854992080, 5814293120, 11829648225, 24046855887, 48840756608

Offset: 1

Eric W. Weisstein

a(n-1) is the number of compositions of n with at least one part >= 5. - Joerg Arndt, Aug 06 2012

W. Feller, An Introduction to Probability Theory and Its Applications, Vol. 1, 2nd ed. New York: Wiley, p. 300, 1968.

T. D. Noe, Table of n, a(n) for n = 1..300
Simon Cowell, A Formula for the Reliability of a d-dimensional Consecutive-k-out-of-n:F System, arXiv preprint arXiv:1506.03580 [math.CO], 2015.
T. Langley, J. Liese, and J. Remmel, Generating Functions for Wilf Equivalence Under Generalized Factor Order, J. Int. Seq. 14 (2011) # 11.4.2.
Eric Weisstein's World of Mathematics, Run
Index entries for linear recurrences with constant coefficients, signature (3,-1,-1,-1,-2).

Cf. A000078, A008466, A050231, A050233.

Column 5 of A109435.

R:= PowerSeriesRing(Integers(), 50);
[0,0,0] cat Coefficients(R!( x^4/((1-2*x)*(1-x-x^2-x^3-x^4)) )); // G. C. Greubel, Jun 01 2025

Flatten[With[{tetrnos=LinearRecurrence[{1,1,1,1},{0,1,1,2},50]}, Table[ 2^n- Take[tetrnos,{n+3}],{n,40}]]] (* Harvey P. Dale, Dec 02 2011 *)
LinearRecurrence[{3,-1,-1,-1,-2}, {0,0,0,1,3}, 31] (* Ray Chandler, Aug 03 2015 *)

a(n)=([0,1,0,0,0; 0,0,1,0,0; 0,0,0,1,0; 0,0,0,0,1; -2,-1,-1,-1,3]^(n-1)*[0;0;0;1;3])[1,1] \\ Charles R Greathouse IV, Feb 09 2017

def a(n, adict={0:0, 1:0, 2:0, 3:1, 4:3}):
    if n in adict:
        return adict[n]
    adict[n]=3*a(n-1) - a(n-2) - a(n-3) - a(n-4) - 2*a(n-5)
    return adict[n] # David Nacin, Mar 07 2012

def A050232_list(prec):
    P.= PowerSeriesRing(QQ, prec)
    return P( x^4/((1-2*x)*(1-x-x^2-x^3-x^4)) ).list()
a=A050232_list(41); a[1:] # G. C. Greubel, Jun 01 2025

a(n) = 2^n - tetranacci(n+4), see A000078. - Vladeta Jovovic, Feb 23 2003
G.f.: x^4/((1-2*x)*(1-x-x^2-x^3-x^4)). - Geoffrey Critzer, Jan 29 2009
a(n) = 3*a(n-1) - a(n-2) - a(n-3) - a(n-4) - 2*a(n-5). - Wesley Ivan Hurt, Apr 23 2021

A126198 Triangle read by rows: T(n,k) (1 <= k <= n) = number of compositions of n into parts of size <= k.

Original entry on oeis.org

1, 1, 2, 1, 3, 4, 1, 5, 7, 8, 1, 8, 13, 15, 16, 1, 13, 24, 29, 31, 32, 1, 21, 44, 56, 61, 63, 64, 1, 34, 81, 108, 120, 125, 127, 128, 1, 55, 149, 208, 236, 248, 253, 255, 256, 1, 89, 274, 401, 464, 492, 504, 509, 511, 512, 1, 144, 504, 773, 912, 976, 1004, 1016, 1021, 1023, 1024

Offset: 1

N. J. A. Sloane, Mar 09 2007

Also has an interpretation as number of binary vectors of length n-1 in which the length of the longest run of 1's is <= k (see A048004). - N. J. A. Sloane, Apr 03 2011

Higher Order Fibonacci numbers: A126198(n,k) = Sum_{h=0..k} A048004(n,h); for example, A126198(7,3) = Sum_{h=0..3} A048004(7,h) or A126198(7,3) = 1 + 33 + 47 + 27 = 108, the 7th tetranacci number. A048004 row(7) produces A126198 row(7) list of 1,34,81,108,120,125,127,128 which are 1, the 7th Fibonacci, the 7th tribonacci, ... 7th octanacci numbers. - Richard Southern, Aug 04 2017

			Triangle begins:
  1;
  1,  2;
  1,  3,  4;
  1,  5,  7,  8;
  1,  8, 13, 15, 16;
  1, 13, 24, 29, 31, 32;
  1, 21, 44, 56, 61, 63, 64;
Could also be extended to a square array:
  1  1  1  1  1  1  1 ...
  1  2  2  2  2  2  2 ...
  1  3  4  4  4  4  4 ...
  1  5  7  8  8  8  8 ...
  1  8 13 15 16 16 16 ...
  1 13 24 29 31 32 32 ...
  1 21 44 56 61 63 64 ...
which when read by antidiagonals (downwards) gives A048887.

J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, pp. 154-155.

Alois P. Heinz, Rows n = 1..141

Rows are partial sums of rows of A048004. Cf. A048887, A092921 for other versions.
2nd column = Fibonacci numbers, next two columns are A000073, A000078; last three diagonals are 2^n, 2^n-1, 2^n-3.
Cf. A082267.

A126198 := proc(n,k) coeftayl( x*(1-x^k)/(1-2*x+x^(k+1)),x=0,n); end: for n from 1 to 11 do for k from 1 to n do printf("%d, ",A126198(n,k)); od; od; # R. J. Mathar, Mar 09 2007
# second Maple program:
T:= proc(n, k) option remember;
      if n=0 or k=1 then 1
    else add(T(n-j, k), j=1..min(n, k))
      fi
    end:
seq(seq(T(n, k), k=1..n), n=1..15);  # Alois P. Heinz, Oct 23 2011

rows = 11; t[n_, k_] := Sum[ (-1)^i*2^(n-i*(k+1))*Binomial[ n-i*k, i], {i, 0, Floor[n/(k+1)]}] - Sum[ (-1)^i*2^((-i)*(k+1)+n-1)*Binomial[ n-i*k-1, i], {i, 0, Floor[(n-1)/(k+1)]}]; Flatten[ Table[ t[n, k], {n, 1, rows}, {k, 1, n}]](* Jean-François Alcover, Nov 17 2011, after Max Alekseyev *)

G.f. for column k: (x-x^(k+1))/(1-2*x+x^(k+1)). [Riordan]
T(n,3) = A008937(n) - A008937(n-3) for n>=3. T(n,4) = A107066(n-1) - A107066(n-5) for n>=5. T(n,5) = A001949(n+4) - A001949(n-1) for n>=5. - R. J. Mathar, Mar 09 2007
T(n,k) = A181695(n,k) - A181695(n-1,k). - Max Alekseyev, Nov 18 2010
Conjecture: Sum_{k=1..n} T(n,k) = A039671(n), n>0. - L. Edson Jeffery, Nov 29 2013

More terms from R. J. Mathar, Mar 09 2007

A135492 Number of ways to toss a coin n times and not get a run of five.

Original entry on oeis.org

1, 2, 4, 8, 16, 30, 58, 112, 216, 416, 802, 1546, 2980, 5744, 11072, 21342, 41138, 79296, 152848, 294624, 567906, 1094674, 2110052, 4067256, 7839888, 15111870, 29129066, 56148080, 108228904, 208617920, 402123970, 775118874, 1494089668, 2879950432

Offset: 0

James R FitzSimons (cherry(AT)getnet.net), Feb 07 2008

G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (1,1,1,1).

Cf. A135491, A135493.

a[n_] := a[n] = a[n - 1] + a[n - 2] + a[n - 3] + a[n - 4]; a[1] = 2; a[2] = 4; a[3] = 8; a[4] = 16; Array[a, 33] (* Robert G. Wilson v, Feb 10 2008 *)
LinearRecurrence[{1, 1, 1, 1}, {2, 4, 8, 16}, 25] (* G. C. Greubel, Oct 15 2016 *)

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; 1,1,1,1]^(n-1)*[2;4;8;16])[1,1] \\ Charles R Greathouse IV, Oct 17 2016

a(n) = a(n-1) + a(n-2) + a(n-3) + a(n-4).
a(n) = 2*A000078(n+3) for n>=1.
G.f.: 1-2*x*(x+1)*(1+x^2)/(x^4+x^3+x^2+x-1). - Colin Barker, Jun 12 2012

Corrected and extended by Robert G. Wilson v, Feb 10 2008

a(0)=1 prepended by Alois P. Heinz, May 22 2025

cp's OEIS Frontend

A159741 a(n) = 8*(2^n - 1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

Extensions

A107066 Expansion of 1/(1-2*x+x^5).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Mathematica

PARI

Sage

Formula

A048888 a(n) = Sum_{m=1..n} T(m,n+1-m), array T as in A048887.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A122189 Heptanacci numbers: each term is the sum of the preceding 7 terms, with a(0),...,a(6) = 0,0,0,0,0,0,1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A106273 Discriminant of the polynomial x^n - x^(n-1) - ... - x - 1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A209972 Number of binary words of length n avoiding the subword given by the binary expansion of k; square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A238888 Number A(n,k) of self-inverse permutations p on [n] with displacement of elements restricted by k: |p(i)-i| <= k, square array A(n,k), n>=0, k>=0, read by antidiagonals.

Views

Author

Keywords