cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-6 of 6 results.

A000071 a(n) = Fibonacci(n) - 1.

Original entry on oeis.org

0, 0, 1, 2, 4, 7, 12, 20, 33, 54, 88, 143, 232, 376, 609, 986, 1596, 2583, 4180, 6764, 10945, 17710, 28656, 46367, 75024, 121392, 196417, 317810, 514228, 832039, 1346268, 2178308, 3524577, 5702886, 9227464, 14930351, 24157816, 39088168, 63245985, 102334154
Offset: 1

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is the number of allowable transition rules for passing from one change to the next (on n-1 bells) in the English art of bell-ringing. This is also the number of involutions in the symmetric group S_{n-1} which can be represented as a product of transpositions of consecutive numbers from {1, 2, ..., n-1}. Thus for n = 6 we have a(6) from (12), (12)(34), (12)(45), (23), (23)(45), (34), (45), for instance. See my 1983 Math. Proc. Camb. Phil. Soc. paper. - Arthur T. White, letter to N. J. A. Sloane, Dec 18 1986
Number of permutations p of {1, 2, ..., n-1} such that max|p(i) - i| = 1. Example: a(4) = 2 since only the permutations 132 and 213 of {1, 2, 3} satisfy the given condition. - Emeric Deutsch, Jun 04 2003 [For a(5) = 4 we have 2143, 1324, 2134 and 1243. - Jon Perry, Sep 14 2013]
Number of 001-avoiding binary words of length n-3. a(n) is the number of partitions of {1, ..., n-1} into two blocks in which only 1- or 2-strings of consecutive integers can appear in a block and there is at least one 2-string. E.g., a(6) = 7 because the enumerated partitions of {1, 2, 3, 4, 5} are 124/35, 134/25, 14/235, 13/245, 1245/3, 145/23, 125/34. - Augustine O. Munagi, Apr 11 2005
Numbers for which only one Fibonacci bit-representation is possible and for which the maximal and minimal Fibonacci bit-representations (A104326 and A014417) are equal. For example, a(12) = 10101 because 8 + 3 + 1 = 12. - Casey Mongoven, Mar 19 2006
Beginning with a(2), the "Recamán transform" (see A005132) of the Fibonacci numbers (A000045). - Nick Hobson, Mar 01 2007
Starting with nonzero terms, a(n) gives the row sums of triangle A158950. - Gary W. Adamson, Mar 31 2009
a(n+2) is the minimum number of elements in an AVL tree of height n. - Lennert Buytenhek (buytenh(AT)wantstofly.org), May 31 2010
a(n) is the number of branch nodes in the Fibonacci tree of order n-1. A Fibonacci tree of order n (n >= 2) is a complete binary tree whose left subtree is the Fibonacci tree of order n-1 and whose right subtree is the Fibonacci tree of order n-2; each of the Fibonacci trees of order 0 and 1 is defined as a single node (see the Knuth reference, p. 417). - Emeric Deutsch, Jun 14 2010
a(n+3) is the number of distinct three-strand positive braids of length n (cf. Burckel). - Maxime Bourrigan, Apr 04 2011
a(n+1) is the number of compositions of n with maximal part 2. - Joerg Arndt, May 21 2013
a(n+2) is the number of leafs of great-grandparent DAG (directed acyclic graph) of height n. A great-grandparent DAG of height n is a single node for n = 1; for n > 1 each leaf of ggpDAG(n-1) has two child nodes where pairs of adjacent new nodes are merged into single node if and only if they have disjoint grandparents and same great-grandparent. Consequence: a(n) = 2*a(n-1) - a(n-3). - Hermann Stamm-Wilbrandt, Jul 06 2014
2 and 7 are the only prime numbers in this sequence. - Emmanuel Vantieghem, Oct 01 2014
From Russell Jay Hendel, Mar 15 2015: (Start)
We can establish Gerald McGarvey's conjecture mentioned in the Formula section, however we require n > 4. We need the following 4 prerequisites.
(1) a(n) = F(n) - 1, with {F(n)}A000045.%20(2)%20(Binet%20form)%20F(n)%20=%20(d%5En%20-%20e%5En)/sqrt(5)%20with%20d%20=%20phi%20and%20e%20=%201%20-%20phi,%20de%20=%20-1%20and%20d%20+%20e%20=%201.%20It%20follows%20that%20a(n)%20=%20(d(n)%20-%20e(n))/sqrt(5)%20-%201.%20(3)%20To%20prove%20floor(x)%20=%20y%20is%20equivalent%20to%20proving%20that%20x%20-%20y%20lies%20in%20the%20half-open%20interval%20%5B0,%201).%20(4)%20The%20series%20%7Bs(n)%20=%20c1%20x%5En%20+%20c2%7D">{n >= 1} the Fibonacci numbers A000045. (2) (Binet form) F(n) = (d^n - e^n)/sqrt(5) with d = phi and e = 1 - phi, de = -1 and d + e = 1. It follows that a(n) = (d(n) - e(n))/sqrt(5) - 1. (3) To prove floor(x) = y is equivalent to proving that x - y lies in the half-open interval [0, 1). (4) The series {s(n) = c1 x^n + c2}{n >= 1}, with -1 < x < 0, and c1 and c2 positive constants, converges by oscillation with s(1) < s(3) < s(5) < ... < s(6) < s(4) < s(2). If follows that for any odd n, the open interval (s(n), s(n+1)) contains the subsequence {s(t)}_{t >= n + 2}. Using these prerequisites we can analyze the conjecture.
Using prerequisites (2) and (3) we see we must prove, for all n > 4, that d((d^(n-1) - e^(n-1))/sqrt(5) - 1) - (d^n - e^n)/sqrt(5) + 1 + c lies in the interval [0, 1). But de = -1, implying de^(n-1) = -e^(n-2). It follows that we must equivalently prove (for all n > 4) that E(n, c) = (e^(n-2) + e^n)/sqrt(5) + 1 - d + c = e^(n-2) (e^2 + 1)/sqrt(5) + e + c lies in [0, 1). Clearly, for any particular n, E(n, c) has extrema (maxima, minima) when c = 2*(1-d) and c = (1+d)*(1-d). Therefore, the proof is completed by using prerequisite (4). It suffices to verify E(5, 2*(1-d)) = 0, E(6, 2*(1-d)) = 0.236068, E(5, (1-d)*(1+d)) = 0.618034, E(6, (1-d)*(1+d)) = 0.854102, all lie in [0, 1).
(End)
a(n) can be shown to be the number of distinct nonempty matchings on a path with n vertices. (A matching is a collection of disjoint edges.) - Andrew Penland, Feb 14 2017
Also, for n > 3, the lexicographically earliest sequence of positive integers such that {phi*a(n)} is located strictly between {phi*a(n-1)} and {phi*a(n-2)}. - Ivan Neretin, Mar 23 2017
From Eric M. Schmidt, Jul 17 2017: (Start)
Number of sequences (e(1), ..., e(n-2)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) <= e(k). [Martinez and Savage, 2.5]
Number of sequences (e(1), ..., e(n-2)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) <= e(k) and e(i) != e(k). [Martinez and Savage, 2.5]
(End)
Numbers whose Zeckendorf (A014417) and dual Zeckendorf (A104326) representations are the same: alternating digits of 1 and 0. - Amiram Eldar, Nov 01 2019
a(n+2) is the length of the longest array whose local maximum element can be found in at most n reveals. See link to the puzzle by Alexander S. Kulikov. - Dmitry Kamenetsky, Aug 08 2020
a(n+2) is the number of nonempty subsets of {1,2,...,n} that contain no consecutive elements. For example, the a(6)=7 subsets of {1,2,3,4} are {1}, {2}, {3}, {4}, {1,3}, {1,4} and {2,4}. - Muge Olucoglu, Mar 21 2021
a(n+3) is the number of allowed patterns of length n in the even shift (that is, a(n+3) is the number of binary words of length n in which there are an even number of 0s between any two occurrences of 1). For example, a(7)=12 and the 12 allowed patterns of length 4 in the even shift are 0000, 0001, 0010, 0011, 0100, 0110, 0111, 1000, 1001, 1100, 1110, 1111. - Zoran Sunic, Apr 06 2022
Conjecture: for k a positive odd integer, the sequence {a(k^n): n >= 1} is a strong divisibility sequence; that is, for n, m >= 1, gcd(a(k^n), a(k^m)) = a(k^gcd(n,m)). - Peter Bala, Dec 05 2022
In general, the sum of a second-order linear recurrence having signature (c,d) will be a third-order recurrence having a signature (c+1,d-c,-d). - Gary Detlefs, Jan 05 2023
a(n) is the number of binary strings of length n-2 whose longest run of 1's is of length 1, for n >= 3. - Félix Balado, Apr 03 2025

References

  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, id. 1.
  • GCHQ, The GCHQ Puzzle Book, Penguin, 2016. See page 28.
  • M. Kauers and P. Paule, The Concrete Tetrahedron, Springer 2011, p. 64.
  • D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd edition, Addison-Wesley, Reading, MA, 1998, p. 417.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 155.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29.

Links

Crossrefs

Cf. A000032, A000045, A000119, A001611, A001654, A001911, A005968, A005969.
Cf. A006327, A014417, A054761, A081006, A081007, A081008, A081009, A083368.
Cf. A098531, A098532, A098533, A101220, A104326, A105488, A105489, A119282.
Cf. A128697, A157725, A157726, A157727, A157728, A157729, A158950, A167616.
Cf. A001622, A228074.
Antidiagonal sums of array A004070.
Right-hand column 2 of triangle A011794.
Related to sum of Fibonacci(kn) over n. Cf. A099919, A058038, A138134, A053606.
Subsequence of A226538. Also a subsequence of A061489.

Programs

  • Haskell
    a000071 n = a000071_list !! n
a000071_list = map (subtract 1) $ tail a000045_list
-- Reinhard Zumkeller, May 23 2013
  • Magma
    [Fibonacci(n)-1: n in [1..60]]; // Vincenzo Librandi, Apr 04 2011
  • Maple
    A000071 := proc(n) combinat[fibonacci](n)-1 ; end proc; # R. J. Mathar, Apr 07 2011
a:= n-> (Matrix([[1, 1, 0], [1, 0, 0], [1, 0, 1]])^(n-1))[3, 2]; seq(a(n), n=1..50); # Alois P. Heinz, Jul 24 2008
  • Mathematica
    Fibonacci[Range[40]] - 1 (* or *) LinearRecurrence[{2, 0, -1}, {0, 0, 1}, 40] (* Harvey P. Dale, Aug 23 2013 *)
Join[{0}, Accumulate[Fibonacci[Range[0, 39]]]] (* Alonso del Arte, Oct 22 2017, based on Giorgi Dalakishvili's formula *)
  • PARI
    {a(n) = if( n<1, 0, fibonacci(n)-1)};
  • SageMath
    [fibonacci(n)-1 for n in range(1,60)] # G. C. Greubel, Oct 21 2024

Formula

a(n) = A000045(n) - 1.
a(0) = -1, a(1) = 0; thereafter a(n) = a(n-1) + a(n-2) + 1.
a(n) = A101220(1, 1, n-2), for n > 1.
G.f.: x^3/((1-x-x^2)*(1-x)). - Simon Plouffe in his 1992 dissertation, dropping initial 0's
a(n) = 2*a(n-1) - a(n-3). - R. H. Hardin, Apr 02 2011
Partial sums of Fibonacci numbers. - Wolfdieter Lang
a(n) = -1 + (A*B^n + C*D^n)/10, with A, C = 5 +- 3*sqrt(5), B, D = (1 +- sqrt(5))/2. - Ralf Stephan, Mar 02 2003
a(1) = 0, a(2) = 0, a(3) = 1, then a(n) = ceiling(phi*a(n-1)) where phi is the golden ratio (1 + sqrt(5))/2. - Benoit Cloitre, May 06 2003
Conjecture: for all c such that 2*(2 - Phi) <= c < (2 + Phi)*(2 - Phi) we have a(n) = floor(Phi*a(n-1) + c) for n > 4. - Gerald McGarvey, Jul 22 2004. This is true provided n > 3 is changed to n > 4, see proof in Comments section. - Russell Jay Hendel, Mar 15 2015
a(n) = Sum_{k = 0..floor((n-2)/2)} binomial(n-k-2, k+1). - Paul Barry, Sep 23 2004
a(n+3) = Sum_{k = 0..floor(n/3)} binomial(n-2*k, k)*(-1)^k*2^(n-3*k). - Paul Barry, Oct 20 2004
a(n+1) = Sum(binomial(n-r, r)), r = 1, 2, ... which is the case t = 2 and k = 2 in the general case of t-strings and k blocks: a(n+1, 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
a(n) = Sum_{k = 0..n-2} k*Fibonacci(n - k - 3). - Ross La Haye, May 31 2006
a(n) = term (3, 2) in the 3 X 3 matrix [1, 1, 0; 1, 0, 0; 1, 0, 1]^(n-1). - Alois P. Heinz, Jul 24 2008
For n >= 4, a(n) = ceiling(phi*a(n-1)), where phi is the golden ratio. - Vladimir Shevelev, Jul 04 2010
Closed-form without two leading zeros g.f.: 1/(1 - 2*x - x^3); ((5 + 2*sqrt(5))*((1 + sqrt(5))/2)^n + (5 - 2*sqrt(5))*((1 - sqrt(5))/2)^n - 5)/5; closed-form with two leading 0's g.f.: x^2/(1 - 2*x - x^3); ((5 + sqrt(5))*((1 + sqrt(5))/2)^n + (5 - sqrt(5))*((1 - sqrt(5))/2)^n - 10)/10. - Tim Monahan, Jul 10 2011
A000119(a(n)) = 1. - Reinhard Zumkeller, Dec 28 2012
a(n) = A228074(n - 1, 2) for n > 2. - Reinhard Zumkeller, Aug 15 2013
G.f.: Q(0)*x^2/2, where Q(k) = 1 + 1/(1 - x*(4*k + 2 - x^2)/( x*(4*k + 4 - x^2) + 1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 30 2013
A083368(a(n+3)) = n. - Reinhard Zumkeller, Aug 10 2014
E.g.f.: 1 - exp(x) + 2*exp(x/2)*sinh(sqrt(5)*x/2)/sqrt(5). - Ilya Gutkovskiy, Jun 15 2016
a(n) = A000032(3+n) - 1 mod A000045(3+n). - Mario C. Enriquez, Apr 01 2017
a(n) = Sum_{i=0..n-2} Fibonacci(i). - Giorgi Dalakishvili (mcnamara_gio(AT)yahoo.com), Apr 02 2005 [corrected by Doug Bell, Jun 01 2017]
a(n+2) = Sum_{j = 0..floor(n/2)} Sum_{k = 0..j} binomial(n - 2*j, k+1)*binomial(j, k). - Tony Foster III, Sep 08 2017
From Peter Bala, Nov 12 2021: (Start)
a(4*n) = Fibonacci(2*n+1)*Lucas(2*n-1) = A081006(n);
a(4*n+1) = Fibonacci(2*n)*Lucas(2*n+1) = A081007(n);
a(4*n+2) = Fibonacci(2*n)*Lucas(2*n+2) = A081008(n);
a(4*n+3) = Fibonacci(2*n+2)*Lucas(2*n+1) = A081009(n). (End)
G.f.: x^3/((1 - x - x^2)*(1 - x)) = Sum_{n >= 0} (-1)^n * x^(n+3) *( Product_{k = 1..n} (k - x)/Product_{k = 1..n+2} (1 - k*x) ) (a telescoping series). - Peter Bala, May 08 2024
Product_{n>=4} (1 + (-1)^n/a(n)) = 3*phi/4, where phi is the golden ratio (A001622). - Amiram Eldar, Nov 28 2024

Extensions

Edited by N. J. A. Sloane, Apr 04 2011

A048004 Triangular array read by rows: T(n,k) = number of binary vectors of length n whose longest run of consecutive 1's has length k, for n >= 0, 0 <= k <= n.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 4, 2, 1, 1, 7, 5, 2, 1, 1, 12, 11, 5, 2, 1, 1, 20, 23, 12, 5, 2, 1, 1, 33, 47, 27, 12, 5, 2, 1, 1, 54, 94, 59, 28, 12, 5, 2, 1, 1, 88, 185, 127, 63, 28, 12, 5, 2, 1, 1, 143, 360, 269, 139, 64, 28, 12, 5, 2, 1, 1, 232, 694, 563, 303, 143, 64, 28, 12, 5, 2, 1, 1, 376, 1328, 1167, 653, 315, 144, 64, 28, 12, 5, 2, 1
Offset: 0

Views

Author

Clark Kimberling

Keywords

Comments

Equivalently, number of compositions of n+1 having largest part (exactly) k+1. Example: T(4,2)=5 because we have 3+2, 2+3, 3+1+1, 1+3+1 and 1+1+3. - Emeric Deutsch, Apr 01 2005
Here is a bijection between the binary words and the compositions: prefix the vector with a 0, place a comma before each 0, then read the lengths of the runs. Example: 1100 -> 01100 -> ,011,0,0 -> 311 -> 3+1+1. - N. J. A. Sloane, Apr 03 2011
A formula based on the conjugates of the partitions of n with largest part k is given as a Sage program below. Note that it gives the compositions in the natural enumeration 'n with largest part k'. The 'conjugate' formula leads to A097805. - Peter Luschny, Jul 13 2015

Examples

			Triangle begins:
1;
1,  1;
1,  2,   1;
1,  4,   2,   1;
1,  7,   5,   2,  1;
1, 12,  11,   5,  2,  1;
1, 20,  23,  12,  5,  2,  1;
1, 33,  47,  27, 12,  5,  2, 1;
1, 54,  94,  59, 28, 12,  5, 2, 1;
1, 88, 185, 127, 63, 28, 12, 5, 2, 1;
...
Example: T(4,2) = 5 because we have 1100, 1101, 0110, 0011, 1011.

References

  • J. Kappraff, Beyond Measure, World Scientific, 2002; see pp. 471-472.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 155.

Links

Crossrefs

See A126198 and A048887 for closely related arrays.
T(n,2) = Fibonacci(n+2) - 1, A000071, T(n,3) = b(n) for n=3, 4, ..., where b=A000100, T(n,4) = c(n) for n = 4, 5, ..., where c=A000102.
Nonnegative elements of columns approach A045623.
Cf. A048003, A097805.

Programs

  • Haskell
    tri n k | (k < 0) || (k > n) = 0
        | (k == 0) || (k == n) = 1
        | otherwise = 2*tri (n-1) k + tri (n-1) (k-1) - 2*tri (n-2) (k-1)
                            + tri (n-k-1) (k-1) - tri (n-k-2) k
-- Valentin Hübner, Jul 20 2017, after David W. Wilson
  • Maple
    G:=k->(1-x)^2*x^k/(1-2*x+x^(k+1))/(1-2*x+x^(k+2)): for k from 0 to 14 do g[k]:=series(G(k),x=0,15) od: 1,seq(seq(coeff(g[k],x^n),k=0..n),n=1..12); # Emeric Deutsch, Apr 01 2005
# second Maple program:
B:= proc(n, k) option remember; `if`(n=0 or k=1, 1,
      add (B(n-j, k), j=1..min(n, k)))
    end:
T:= (n, k)-> B(n+1, k+1)-B(n+1, k):
seq(seq(T(n, k), k=0..n), n=0..14); # Alois P. Heinz, May 21 2013
  • Mathematica
    nn=10;f[list_]:=Select[list,#>0&];Map[f,Transpose[Table[ CoefficientList[ Series[(1-x^k)/(1-2x+x^(k+1))-(1-x^(k-1))/ (1-2x+x^k),{x,0,nn}],x],{k,1,nn}]]]//Grid  (* Geoffrey Critzer, Jan 13 2013 *)
B[n_, k_] := B[n, k] = If[n==0 || k==1, 1, Sum[B[n-j, k], {j, 1, Min[n, k]} ]]; T[n_, k_] := B[n+1, k+1] - B[n+1, k]; Table[T[n, k], {n, 0, 14}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 01 2015, after Alois P. Heinz *)
  • Python
    # See Richard Southern link.
  • Sage
    # Computes the triangle obtained by augmenting T(n,k) by appending the column
# 1,0,0,0,... on the left. Illustrates a basic partition formula, is not
# efficient as a program for large n.
def A048004_row(n):
    r = []
    for k in (0..n):
        s = 0
        for p in Partitions(n, max_part=k, inner=[k]):
            q = p.conjugate()
            s += mul(binomial(q[j],q[j+1]) for j in range(len(q)-1))
        r.append(s)
    return r
[A048004_row(n) for n in (0..9)] # Peter Luschny, Jul 13 2015

Formula

T(n, k) = 0 if k < 0 or k > n, 1 if k = 0 or k = n, 2T(n-1, k) + T(n-1, k-1) - 2T(n-2, k-1) + T(n-k-1, k-1) - T(n-k-2, k) otherwise. - David W. Wilson
T(n, k) = A048887(n+1, k+1) - A048887(n+1, k). - Henry Bottomley, Oct 29 2002
G.f. for column k: (1-x)^2*x^k/((1-2*x+x^(k+1))*(1-2*x+x^(k+2))). - Emeric Deutsch, Apr 01 2005
From Gary W. Adamson, Jun 23 2012: (Start)
Create an array of rows such that row 0 is the INVERT transform of (1,0,0,0,...); row 1 is the INVERT transform of (1,1,0,0,0,...); row 2 is the INVERT transform of (1,1,1,0,0,0,...) and so on:
1, 1, 1, 1, 1, 1, ...
1, 2, 3, 5, 8, 13, ...
1, 2, 4, 7, 13, 24, ...
1, 2, 4, 8, 15, 29, ...
... Then, take finite differences of column terms from the top -> down. Row terms of the triangle are finite differences of the array columns. (End)
T(n,k) = A126198(n+1,k+1) - A126198(n+1,k). - L. Edson Jeffery, May 21 2013
Recurrence: T(n+1,k) = Sum_{h=0..k} T(n-k, h) + Sum_{i=n-k+1..n} T(i, k); for example, T(7,3) = Sum_{h=0..3} T(3,h) + Sum_{i=4..6} T(i,3) or T(7,3) = (1+4+2+1) + (2+5+12) = 27. Example: T(4,2) = (1+1) + (1+2) = 5. - Richard Southern, Jul 09 2017
Difference between higher order Fibonacci numbers is equal to recurrence. T(n+1,k) = A126198 (n+1,k) - A126198 (n+1,k-1) = Sum_{i=n-k..n} A126198 (i,k) - Sum_{i=n-k+1..n} A126198 (i,k-1) = A126198 (n-k,k) + Sum_{i=n-k+1..n} (A126198 (i,k) - A126198 (i,k-1)) = Sum_{h=0..k} T(n-k, h) + Sum_{i=n-k+1..n} T(i, k). For example T(7,3) = A126198 (7,3) - A126198 (7,2) = 108 - 81 = (8+15+29+56) - (13+24+44) = 8 + (15-13) + (29-24) + (56-44) = 8 + (2+5+12) = (1+4+2+1) + (2+5+12). - Richard Southern, Aug 04 2017

Extensions

More terms from Emeric Deutsch, Apr 01 2005
Edited by N. J. A. Sloane, Apr 03 2011

A000100 a(n) is the number of compositions of n in which the maximal part is 3.

Original entry on oeis.org

0, 0, 0, 1, 2, 5, 11, 23, 47, 94, 185, 360, 694, 1328, 2526, 4781, 9012, 16929, 31709, 59247, 110469, 205606, 382087, 709108, 1314512, 2434364, 4504352, 8328253, 15388362, 28417385, 52451811, 96771787, 178473023, 329042890, 606466009, 1117506500
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

For n > 5, a(n) - (a(n-3)+a(n-2)+a(n-1)) = F(n-2) where F(i) is the i-th Fibonacci number; e.g., 11 - (1+2+5) = 3, 23 - (2+5+11) = 8; also lim_{n->oo} a(n)/(a(n-1)+a(n-2)+a(n-3)) = 1 and lim_{n->oo} a(n)*a(n-2)/a(n-1)^2 = 1. - Gerald McGarvey, Jun 26 2004
a(n) is also the number of binary sequences of length n-1 in which the longest run of 0's is exactly two. - Geoffrey Critzer, Nov 06 2008
a(n) is also the difference between the n-th tribonacci number and the n-th Fibonacci number; i.e., a(n) = A000073(n) - A000045(n). - Gregory L. Simay, Jan 31 2018
Let F_0(n) be the n-th Fibonacci number, A000045(n). Let F_1(n) = Sum_{j=1..n} A000045(n+1-j)*A000045(j). Let F_r(n) = Sum_{j=1..n} F_(r-1)(n+1-j)*A000045(j). Then the number of compositions of n having exactly r 3's as the highest part is F_r(n), and a(n+1) = F_1(n-3) + F_1(n-6) + ... - Gregory L. Simay, Apr 17 2018
The Apr 17 2018 comment can be generalized. Let F(n,k) be the n-th k-step Fibonacci number, with the convention that F(0,k)=0 and F(1,k)=1. Let F(n,k,0)= F(n,k) Let F(n, k, 1) = Sum_{j=1..n} F(n+1-j,k)*F(j,k). Let F(n,k,r) = Sum_{j=1..n} F(n+1-j, k, r-1) * A000045(j, k). Let G(n,k,r) be the number of compositions of n having k as the largest part exactly r times. Then G(n,k,r) = F(n+1 - kr, k-1, r). - Gregory L. Simay, May 17 2018

Examples

			For example, a(5)=5 counts 1+1+3, 2+3, 3+2, 3+1+1, 1+3+1. - _David Callan_, Dec 09 2004
a(5)=5 because there are 5 binary sequences of length 4 in which the longest run of consecutive 0's is exactly two: 0010, 0011, 0100, 1001, 1100. - _Geoffrey Critzer_, Nov 06 2008
G.f.: x^3 + 2*x^4 + 5*x^5 + 11*x^6 + 23*x^7 + 47*x^8 + 94*x^9 + 185*x^10 + 360*x^11 + ...

References

  • A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 47, ex. 4.
  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 155.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29.

Links

Crossrefs

Cf. A000045.

Programs

  • Haskell
    a000100 n = a000100_list !! (n-1)
a000100_list = f (tail a000045_list) [head a000045_list] where
   f (x:xs) ys = (sum $ zipWith (*) ys a000073_list) : f xs (x:ys)
-- Reinhard Zumkeller, Jul 31 2012
  • Maple
    a:= n -> (Matrix(5, (i,j)-> if (i=j-1) then 1 elif j=1 then [2,1,-1,-2,-1][i] else 0 fi)^(n))[1,4]: seq(a(n), n=0..40); # Alois P. Heinz, Aug 04 2008
  • Mathematica
    a[n_] := a[n] = a[n-1] + a[n-2] + a[n-3] + Fibonacci[n-2]; a[n_ /; n < 3] = 0; Table[a[n], {n, 0, 35}] (* Jean-François Alcover, Aug 03 2012, after Gerald McGarvey *)
a[ n_] := SeriesCoefficient[ If[ n > 0, x^3 / ((1 - x - x^2) (1 - x - x^2 - x^3)), -x^2 / ((1 + x - x^2) (1 + x + x^2 - x^3))], {x, 0, Abs@n}]; (* Michael Somos, Jun 01 2013 *)
LinearRecurrence[{2,1,-1,-2,-1},{0,0,0,1,2},40] (* Harvey P. Dale, Jul 22 2013 *)
  • PARI
    {a(n) = polcoeff( if( n>0, x^3 / ((1 - x - x^2) * (1 - x - x^2 - x^3)), -x^2 / ((1 + x - x^2) * (1 + x + x^2 - x^3))) + x * O(x^abs(n)), abs(n))}; /* Michael Somos, Jun 01 2013 */

Formula

G.f.: x^3/((1-x-x^2)*(1-x-x^2-x^3)).
a(n+3) = Sum_{k=0..n} F(k)*T(n-k), F(i)=A000045(i+1), T(i)=A000073(i+2).
a(n) = 2*a(n-1)+a(n-2)-a(n-3)-2*a(n-4)-a(n-5). Convolution of Fibonacci and tribonacci numbers (A000045 and A000073). - Franklin T. Adams-Watters, Jan 13 2006

Extensions

More terms from Henry Bottomley, Dec 15 2000
Better definition from David Callan and Franklin T. Adams-Watters

A006981 a(n) is the number of unlabeled modular lattices on n nodes.

Original entry on oeis.org

1, 1, 1, 1, 2, 4, 8, 16, 34, 72, 157, 343, 766, 1718, 3899, 8898, 20475, 47321, 110024, 256791, 601991, 1415768, 3340847, 7904700, 18752943, 44588803, 106247120, 253644319, 606603025, 1453029516, 3485707007, 8373273835, 20139498217, 48496079939, 116905715114, 282098869730
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Examples

			From _Jukka Kohonen_, Mar 06 2021: (Start)
a(5)=4: These are the four lattices.
  o     o       o        o
  |     |      / \      /|\
  o     o     o   o    o o o
  |    / \     \ /      \|/
  o   o   o     o        o
  |    \ /      |
  o     o       o
  |
  o
(End)

References

  • P. D. Lincoln, personal communication.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A006966 (lattices), A006982 (distributive), A342132 (modular vertically indecomposable).

Extensions

More terms from Nathan Lawless, Sep 15 2013
Corrected a(24) and added a(25)-a(30) by Jukka Kohonen, Aug 15 2017
a(31)-a(32) from Jukka Kohonen, Sep 23 2018
Name clarified by Jukka Kohonen, Sep 23 2018
a(33) from Jukka Kohonen, Sep 26 2018
a(34)-a(35) from Jukka Kohonen, Mar 06 2021

A000102 a(n) = number of compositions of n in which the maximum part size is 4.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 5, 12, 27, 59, 127, 269, 563, 1167, 2400, 4903, 9960, 20135, 40534, 81300, 162538, 324020, 644282, 1278152, 2530407, 5000178, 9863763, 19427976, 38211861, 75059535, 147263905, 288609341, 565047233, 1105229439, 2159947998, 4217784107, 8230006378
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

a(n) is also the number of binary sequences of length n-1 in which the longest run of consecutive 0's is exactly three. - Geoffrey Critzer, Nov 06 2008

Examples

			For example, a(6)=5 counts 1+1+4, 2+4, 4+2, 4+1+1, 1+4+1. - _David Callan_, Dec 09 2004
a(6)=5 because there are 5 binary sequences of length 5 in which the longest run of consecutive 0's is exactly 3; 00010, 00011, 01000, 10001, 11000. - _Geoffrey Critzer_, Nov 06 2008

References

  • J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 155.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • J. L. Yucas, Counting special sets of binary Lyndon words, Ars Combin., 31 (1991), 21-29.

Links

Programs

  • Maple
    a:= n-> (Matrix(7, (i,j)-> if i+1=j then 1 elif j=1 then [2, 1, 0, -2, -3, -2, -1][i] else 0 fi)^n)[1,5]: seq(a(n), n=0..40); # Alois P. Heinz, Oct 07 2008
  • Mathematica
    a[n_] := MatrixPower[ Table[ Which[i+1 == j, 1, j == 1, {2, 1, 0, -2, -3, -2, -1}[[i]], True, 0], {i, 1, 7}, {j, 1, 7}], n][[1, 5]]; Table[a[n], {n, 0, 34}] (* Jean-François Alcover, May 28 2013, after Alois P. Heinz *)
LinearRecurrence[{2,1,0,-2,-3,-2,-1},{0,0,0,0,1,2,5},40] (* Harvey P. Dale, Jul 01 2013 *)

Formula

G.f.: x^4/(1 - x - x^2 - x^3)/(1 - x - x^2 - x^3 - x^4).
a(n) = 2*a(n-1) + a(n-2) - 2*a(n-4) - 3*a(n-5) - 2*a(n-6) - a(n-7). Convolution of tribonacci and tetranacci numbers (A000073 and A000078). - Franklin T. Adams-Watters, Jan 13 2006

Extensions

More terms from Sascha Kurz, Aug 15 2002
Definition improved by David Callan and Franklin T. Adams-Watters

A048003 Triangular array T read by rows: T(h,k) = number of binary words of length h and maximal runlength k.

Original entry on oeis.org

2, 2, 2, 2, 4, 2, 2, 8, 4, 2, 2, 14, 10, 4, 2, 2, 24, 22, 10, 4, 2, 2, 40, 46, 24, 10, 4, 2, 2, 66, 94, 54, 24, 10, 4, 2, 2, 108, 188, 118, 56, 24, 10, 4, 2, 2, 176, 370, 254, 126, 56, 24, 10, 4, 2, 2, 286, 720, 538, 278, 128, 56, 24, 10, 4, 2, 2, 464, 1388, 1126, 606, 286, 128, 56, 24, 10, 4, 2
Offset: 1

Views

Author

Clark Kimberling

Keywords

Examples

			Rows: {2}; {2,2}; {2,4,2}; {2,8,4,2}; ...
T(3,2) = 4, because there are 4 binary words of length 3 and maximal runlength 2: 001, 011, 100, 110. - _Alois P. Heinz_, Oct 29 2008

Links

Crossrefs

T(h,2) = 2*a(h+1) for h=2, 3, ..., where a=A000071.
T(h,3) = 2*b(h) for h=3, 4, ..., where b=A000100.
T(h,4) = 2*c(h) for h=4, 5, ..., where c=A000102.
Cf. A048004.
Columns 5, 6 give: 2*A006979, 2*A006980. Row sums give: A000079.
Cf. A229756.

Programs

  • Maple
    gf:= proc(n) 2*x^n/ (1-add(x^i, i=1..n-1))/ (1-add(x^j, j=1..n)) end:
T:= (h,k)-> coeff(series(gf(k), x, h+1), x, h):
seq(seq(T(h,k), k=1..h), h=1..13);  # Alois P. Heinz, Oct 29 2008
  • Mathematica
    gf[n_] := 2*x^n*(x^2-2*x+1) / (x^(2*n+1)-2*x^(n+2)-x^(n+1)+x^n+4*x^2-4*x+1); t[h_, k_] := Coefficient[ Series[ gf[k], {x, 0, h+1}], x, h]; Table[ Table[ t[h, k], {k, 1, h}], {h, 1, 13}] // Flatten (* Jean-François Alcover, Oct 07 2013, after Alois P. Heinz *)

Formula

G.f. of column k: 2*x^k / ((1-Sum_{i=1..k-1} x^i) * (1-Sum_{j=1..k} x^j)). - Alois P. Heinz, Oct 29 2008
T(n, k) = 0 if k < 1 or k > n, 2 if k = 1 or k = n, 2T(n-1, k) + T(n-1, k-1) - 2T(n-2, k-1) + T(n-k, k-1) - T(n-k-1, k) otherwise (cf. similar formula for A048004). This is a simplification of the L-shaped sum T(n-1, k) + ... + T(n-k, k) + ... + T(n-k,1). - Andrew Woods, Oct 11 2013
For n > 2k, T(n, n-k) = 2*A045623(k). - Andrew Woods, Oct 11 2013

Extensions

More terms from Alois P. Heinz, Oct 29 2008
Showing 1-6 of 6 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.