A134057 -id:A134057 - cp's OEIS frontend

A027383 a(2n) = 32^n - 2; a(2*n+1) = 2^(n+2) - 2.

1, 2, 4, 6, 10, 14, 22, 30, 46, 62, 94, 126, 190, 254, 382, 510, 766, 1022, 1534, 2046, 3070, 4094, 6142, 8190, 12286, 16382, 24574, 32766, 49150, 65534, 98302, 131070, 196606, 262142, 393214, 524286, 786430, 1048574, 1572862, 2097150, 3145726, 4194302, 6291454

Offset: 0

R. K. Guy

Number of balanced strings of length n: let d(S) = #(1's) - #(0's), # == count in S, then S is balanced if every substring T of S has -2 <= d(T) <= 2.
Number of "fold lines" seen when a rectangular piece of paper is folded n+1 times along alternate orthogonal directions and then unfolded. - Quim Castellsaguer (qcastell(AT)pie.xtec.es), Dec 30 1999
Also the number of binary strings with the property that, when scanning from left to right, once the first 1 is seen in position j, there must be a 1 in positions j+2, j+4, ... until the end of the string. (Positions j+1, j+3, ... can be occupied by 0 or 1.) - Jeffrey Shallit, Sep 02 2002
a(n-1) is also the Moore lower bound on the order of a (3,n)-cage. - Eric W. Weisstein, May 20 2003 and Jason Kimberley, Oct 30 2011
Partial sums of A016116. - Hieronymus Fischer, Sep 15 2007
Equals row sums of triangle A152201. - Gary W. Adamson, Nov 29 2008
From John P. McSorley, Sep 28 2010: (Start)
a(n) = DPE(n+1) is the total number of k-double-palindromes of n up to cyclic equivalence. See sequence A180918 for the definitions of a k-double-palindrome of n and of cyclic equivalence. Sequence A180918 is the 'DPE(n,k)' triangle read by rows where DPE(n,k) is the number of k-double-palindromes of n up to cyclic equivalence. For example, we have a(4) = DPE(5) = DPE(5,1) + DPE(5,2) + DPE(5,3) + DPE(5,4) + DPE(5,5) = 0 + 2 + 2 + 1 + 1 = 6.
The 6 double-palindromes of 5 up to cyclic equivalence are 14, 23, 113, 122, 1112, 11111. They come from cyclic equivalence classes {14,41}, {23,32}, {113,311,131}, {122,212,221}, {1112,2111,1211,1121}, and {11111}. Hence a(n)=DPE(n+1) is the total number of cyclic equivalence classes of n containing at least one double-palindrome.
(End)
From Herbert Eberle, Oct 02 2015: (Start)
For n > 0, there is a red-black tree of height n with a(n-1) internal nodes and none with less.
In order a red-black tree of given height has minimal number of nodes, it has exactly 1 path with strictly alternating red and black nodes. All nodes outside this height defining path are black.
Consider:
mrbt5                R
                    / \
                   /   \
                  /     \
                 /       B
                /       / \
mrbt4          B       /   B
              / \     B   E E
             /   B   E E
mrbt3       R   E E
           / \
          /   B
mrbt2    B   E E
        / E
mrbt1  R
      E E
(Red nodes shown as R, blacks as B, externals as E.)
Red-black trees mrbt1, mrbt2, mrbt3, mrbt4, mrbt5 of respective heights h = 1, 2, 3, 4, 5; all minimal in the number of internal nodes, namely 1, 2, 4, 6, 10.
Recursion (let n = h-1): a(-1) = 0, a(n) = a(n-1) + 2^floor(n/2), n >= 0.
(End)
Also the number of strings of length n with the digits 1 and 2 with the property that the sum of the digits of all substrings of uneven length is not divisible by 3. An example with length 8 is 21221121. - Herbert Kociemba, Apr 29 2017
a(n-2) is the number of achiral n-bead necklaces or bracelets using exactly two colors.  For n=4, the four arrangements are AAAB, AABB, ABAB, and ABBB. - Robert A. Russell, Sep 26 2018
Partial sums of powers of 2 repeated 2 times, like A200672 where is 3 times. - Yuchun Ji, Nov 16 2018
Also the number of binary words of length n with cuts-resistance <= 2, where, for the operation of shortening all runs by one, cuts-resistance is the number of applications required to reach an empty word. Explicitly, these are words whose sequence of run-lengths, all of which are 1 or 2, has no odd-length run of 1's sandwiched between two 2's. - Gus Wiseman, Nov 28 2019
Also the number of up-down paths with n steps such that the height difference between the highest and lowest points is at most 2. - Jeremy Dover, Jun 17 2020
Also the number of non-singleton integer compositions of n + 2 with no odd part other than the first or last. Including singletons gives A052955. This is an unsorted (or ordered) version of A351003. The version without even (instead of odd) interior parts is A001911, complement A232580. Note that A000045(n-1) counts compositions without odd parts, with non-singleton case A077896, and A052952/A074331 count non-singleton compositions without even parts. Also the number of compositions y of n + 1 such that y_i = y_{i+1} for all even i. - Gus Wiseman, Feb 19 2022

			After 3 folds one sees 4 fold lines.
Example: a(3) = 6 because the strings 001, 010, 100, 011, 101, 110 have the property.
Binary: 1, 10, 100, 110, 1010, 1110, 10110, 11110, 101110, 111110, 1011110, 1111110, 10111110, 11111110, 101111110, 111111110, 1011111110, 1111111110, 10111111110, ... - _Jason Kimberley_, Nov 02 2011
Example: Partial sums of powers of 2 repeated 2 times:
a(3) = 1+1+2 = 4;
a(4) = 1+1+2+2 = 6;
a(5) = 1+1+2+2+4 = 10.
_Yuchun Ji_, Nov 16 2018

John P. McSorley: Counting k-compositions of n with palindromic and related structures. Preprint, 2010. [John P. McSorley, Sep 28 2010]

Vincenzo Librandi, Table of n, a(n) for n = 0..5000
J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013
Leonard F. Klosinski, Gerald L. Alexanderson and Loren C. Larson, Under misprinted head B3, Amer Math. Monthly, 104(1997) 753-754.
Laurent Noé, Spaced seed design on profile HMMs for precise HTS read-mapping efficient sliding window product on the matrix semi-group, in Rapide Bilan 2012-2013, LIFL, Université Lille 1 - INRIA Journées au vert 11 et 12 juin 2013.
Eric Weisstein's World of Mathematics, Cage Graph
Index entries for sequences obtained by enumerating foldings
Index entries for linear recurrences with constant coefficients, signature (1,2,-2).

Cf. A132666, A152201.
Moore lower bound on the order of a (k,g) cage: A198300 (square); rows: A000027 (k=2), this sequence (k=3), A062318 (k=4), A061547 (k=5), A198306 (k=6), A198307 (k=7), A198308 (k=8), A198309 (k=9), A198310 (k=10), A094626 (k=11); columns: A020725 (g=3), A005843 (g=4), A002522 (g=5), A051890 (g=6), A188377 (g=7). - Jason Kimberley, Oct 30 2011
Cf. A000066 (actual order of a (3,g)-cage).
Bisections are A033484 (even) and A000918 (odd).
a(n) = A305540(n+2,2), the second column of the triangle.
Numbers whose binary expansion is a balanced word are A330029.
Binary words counted by cuts-resistance are A319421 or A329860.
Cf. A000975, A062011, A329862, A329863.
The complementary compositions are counted by A274230(n-1) + 1, with bisections A060867 (even) and A134057 (odd).
Cf. A000346, A000984, A001405, A001700, A011782 (compositions).
The following sequences are all essentially the same, in the sense that they are simple transformations of each other, with A029744 = {s(n), n>=1}, the numbers 2^k and 3*2^k, as the parent: A029744 (s(n)); A052955 (s(n)-1), A027383 (s(n)-2), A354788 (s(n)-3), A347789 (s(n)-4), A209721 (s(n)+1), A209722 (s(n)+2), A343177 (s(n)+3), A209723 (s(n)+4); A060482, A136252 (minor differences from A354788 at the start); A354785 (3*s(n)), A354789 (3*s(n)-7). The first differences of A029744 are 1,1,1,2,2,4,4,8,8,... which essentially matches eight sequences: A016116, A060546, A117575, A131572, A152166, A158780, A163403, A320770. The bisections of A029744 are A000079 and A007283. - N. J. A. Sloane, Jul 14 2022

import Data.List (transpose)
a027383 n = a027383_list !! n
a027383_list = concat $ transpose [a033484_list, drop 2 a000918_list]
-- Reinhard Zumkeller, Jun 17 2015

[2^Floor((n+2)/2)+2^Floor((n+1)/2)-2: n in [0..50]]; // Vincenzo Librandi, Aug 16 2011

a[0]:=0:a[1]:=1:for n from 2 to 100 do a[n]:=2*a[n-2]+2 od: seq(a[n], n=1..41); # Zerinvary Lajos, Mar 16 2008

a[n_?EvenQ] := 3*2^(n/2)-2; a[n_?OddQ] := 2^(2+(n-1)/2)-2; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Oct 21 2011, after Quim Castellsaguer *)
LinearRecurrence[{1, 2, -2}, {1, 2, 4}, 41] (* Robert G. Wilson v, Oct 06 2014 *)
Table[Length[Select[Tuples[{0,1},n],And[Max@@Length/@Split[#]<=2,!MatchQ[Length/@Split[#],{_,2,ins:1..,2,_}/;OddQ[Plus[ins]]]]&]],{n,0,15}] (* Gus Wiseman, Nov 28 2019 *)

a(n)=2^(n\2+1)+2^((n+1)\2)-2 \\ Charles R Greathouse IV, Oct 21 2011

def a(n): return 2**((n+2)//2) + 2**((n+1)//2) - 2
print([a(n) for n in range(43)]) # Michael S. Branicky, Feb 19 2022

a(0)=1, a(1)=2; thereafter a(n+2) = 2*a(n) + 2.
a(2n) = 3*2^n - 2 = A033484(n);
a(2n-1) = 2^(n+1) - 2 = A000918(n+1).
G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - David Callan, Jul 22 2008
a(n) = Sum_{k=0..n} 2^min(k, n-k).
a(n) = 2^floor((n+2)/2) + 2^floor((n+1)/2) - 2. - Quim Castellsaguer (qcastell(AT)pie.xtec.es)
a(n) = 2^(n/2)*(3 + 2*sqrt(2) + (3-2*sqrt(2))*(-1)^n)/2 - 2. - Paul Barry, Apr 23 2004
a(n) = A132340(A052955(n)). - Reinhard Zumkeller, Aug 20 2007
a(n) = A052955(n+1) - 1. - Hieronymus Fischer, Sep 15 2007
a(n) = A132666(a(n+1)) - 1. - Hieronymus Fischer, Sep 15 2007
a(n) = A132666(a(n-1)+1) for n > 0. - Hieronymus Fischer, Sep 15 2007
A132666(a(n)) = a(n-1) + 1 for n > 0. - Hieronymus Fischer, Sep 15 2007
G.f.: (1 + x)/((1 - x)*(1 - 2*x^2)). - David Callan, Jul 22 2008
a(n) = 2*( (a(n-2)+1) mod (a(n-1)+1) ), n > 1. - Pierre Charland, Dec 12 2010
a(n) = A136252(n-1) + 1, for n > 0. - Jason Kimberley, Nov 01 2011
G.f.: (1+x*R(0))/(1-x), where R(k) = 1 + 2*x/( 1 - x/(x + 1/R(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Aug 16 2013
a(n) = 2^((2*n + 3*(1-(-1)^n))/4)*3^((1+(-1)^n)/2) - 2. - Luce ETIENNE, Sep 01 2014
a(n) = a(n-1) + 2^floor((n-1)/2) for n>0, a(0)=1. - Yuchun Ji, Nov 23 2018
E.g.f.: 3*cosh(sqrt(2)*x) - 2*cosh(x) + 2*sqrt(2)*sinh(sqrt(2)*x) - 2*sinh(x). - Stefano Spezia, Apr 06 2022

More terms from Larry Reeves (larryr(AT)acm.org), Mar 24 2000

Replaced definition with a simpler one. - N. J. A. Sloane, Jul 09 2022

A029858 a(n) = (3^n - 3)/2.

Original entry on oeis.org

0, 3, 12, 39, 120, 363, 1092, 3279, 9840, 29523, 88572, 265719, 797160, 2391483, 7174452, 21523359, 64570080, 193710243, 581130732, 1743392199, 5230176600, 15690529803, 47071589412, 141214768239

Offset: 1

Christian G. Bower

Also the number of 2-block covers of a labeled n-set. a(n) = A055154(n,2). Generally, number of k-block covers of a labeled n-set is T(n,k) = (1/k!)*Sum_{i = 1..k + 1} Stirling1(k + 1,i)*(2^(i - 1) - 1)^n. In particular, T(n,2) = (1/2!)*(3^n - 3), T(n,3) = (1/3!)*(7^n - 6*3^n + 11), T(n,4) = (1/4)!*(15^n - 10*7^n + 35*3^n - 50), ... - Vladeta Jovovic, Jan 19 2001
Conjectured to be the number of integers from 0 to 10^(n-1) - 1 that lack 0, 1, 2, 3, 4, 5 and 6 as a digit. - Alexandre Wajnberg, Apr 25 2005. This is easily verified to be true. - Renzo Benedetti, Sep 25 2008
Number of monic irreducible polynomials of degree 1 in GF(3)[x1,...,xn]. - Max Alekseyev, Jan 23 2006
Also, the greatest number of identical weights among which an odd one can be identified and it can be decided if the odd one is heavier or lighter, using n weighings with a comparing balance. If the odd one only needs to be identified, the sequence starts 4, 13, 40 and is A003462 (3^n - 1)/2, n > 1. - Tanya Khovanova, Dec 11 2006; corrected by Samuel E. Rhoads, Apr 18 2016
Binomial transform yields A134057. Inverse binomial transform yields A062510 with one additional 0 in front. - R. J. Mathar, Jun 18 2008
Numbers k where the recurrence s(0)=0, if s(k-1) >= k then s(k) = s(k-1) - k otherwise s(k) = s(k-1) + k produces s(k) = 0. - Hugo Pfoertner, Jan 05 2012
For n > 1: A008344(a(n)) = a(n). - Reinhard Zumkeller, May 09 2012
Also the number of edges in the (n-1)-Hanoi graph. - Eric W. Weisstein, Jun 18 2017
A level 1 Sierpiński triangle graph is a triangle. Level n+1 is formed from three copies of level n by identifying pairs of corner vertices of each pair of triangles.  a(n) is the number of degree 4 vertices in the level n Sierpinski triangle graph. - Allan Bickle, Jul 30 2020
Also the number of minimum vertex cuts in the n-Apollonian network. - Eric W. Weisstein, Dec 20 2020
Also the minimum number of turns in n-dimensional Euclidean space needed to visit all 3^n points of the grid {0, 1, 2}^n, moving in straight lines between turns (repeated visits and direction changes at non-grid points are allowed). - Marco Ripà, Aug 06 2025

			For the Sierpiński triangle, Level 1 is a triangle, so a(1) = 0.
Level 2 has three corners (degree 2) and three degree 4 vertices, so a(2) = 3.
The level 2 Hanoi graph has 3 triangles joined by 3 edges, so a(2+1) = 12.

Vincenzo Librandi, Table of n, a(n) for n = 1..300
Allan Bickle, Properties of Sierpinski Triangle Graphs, Springer PROMS 448 (2021) 295-303.
Natalia Agudelo Muñetón, Agustín Moreno Cañadas, Pedro Fernando Fernández Espinosa, and Isaías David Marín Gaviria, Brauer Configuration Algebras and Their Applications in Graph Energy Theory, Mathematics (2021) Vol. 9, 3042.
Alex Born, Cor A. J. Hukrnes, and Gerhard J. Woeginger, How to detect a counterfeit coin: adaptive versus non-adaptive solutions, Inf. Proc. Lett. 86 (2003) 137-141.
Gary Darby, The Counterfeit Coin
Madeleine Goertz and Aaron Williams, The Quaternary Gray Code and How It Can Be Used to Solve Ziggurat and Other Ziggu Puzzles, arXiv:2411.19291 [math.CO], 2024. See p. 17.
Lorenz Halbeisen and Norbert Hungerbuhler, The general counterfeit coin problem, Discr. Math 147 (1-3) (1995) 139-150, Theorem 1 with b=1.
Andreas Hinz, Sandi Klavzar, and Sara Sabrina Zemljic, A survey and classification of Sierpinski-type graphs, Discrete Applied Mathematics 217 3 (2017), 565-600.
Bennet Manvel, Counterfeit coin problems, Math. Mag. 50 (2) (1977) 90-92, theorem 2.
Marco Ripà, Solving the 106 years old 3^k points problem with the clockwise-algorithm, Journal of Fundamental Mathematics and Applications, 2020, 3(2), 84-97.
Allen Stenger and Jack Wert, The Twelve Coins (or Twelve bags of Gold)
Eric Weisstein's World of Mathematics, Apollonian Network
Eric Weisstein's World of Mathematics, Edge Count
Eric Weisstein's World of Mathematics, Hanoi Graph
Eric Weisstein's World of Mathematics, Minimum Vertex Cut
Index entries for linear recurrences with constant coefficients, signature (4,-3).

Cf. A055154, A003462, A007051, A034472, A024023.
Cf. A000203, A008776.
Cf. A007283, A029858, A067771, A233774, A233775, A246959 (Sierpiński triangle graphs).
Cf. A000225, A029858, A058809, A375256 (Hanoi graphs).

a029858 = (`div` 2) . (subtract 3) . (3 ^)
a029858_list = iterate ((+ 3) . (* 3)) 0
-- Reinhard Zumkeller, May 09 2012

[(3^n-3)/2: n in [1..30]]; // Vincenzo Librandi, Jun 05 2011

a:=n->sum(3^j,j=1..n): seq(a(n),n=0..23); # Zerinvary Lajos, Jun 27 2007

Table[(3^n - 3)/2, {n, 24}] (* Alonso del Arte, Dec 29 2014 *)

a(n)=(3^n-3)\2 \\ Charles R Greathouse IV, Apr 17 2012

a(n) = 3*a(n-1) + 3. - Alexandre Wajnberg, Apr 25 2005
O.g.f: 3*x^2/((1-x)*(1-3*x)). - R. J. Mathar, Jun 18 2008
a(n) = 3^(n-1) + a(n-1) (with a(1)=0). - Vincenzo Librandi, Nov 18 2010
a(n) = 3*A003462(n-1). - R. J. Mathar, Sep 10 2015
E.g.f.: 3*(-1 + exp(2*x))*exp(x)/2. - Ilya Gutkovskiy, Apr 19 2016
a(n) = A067771(n-1) - 3. - Allan Bickle, Jul 30 2020
a(n) = sigma(A008776(n-2)) for n>=2. - Flávio V. Fernandes, Apr 20 2021

Corrected by T. D. Noe, Nov 07 2006

A274230 Number of holes in a sheet of paper when you fold it n times and cut off the four corners.

Original entry on oeis.org

0, 0, 1, 3, 9, 21, 49, 105, 225, 465, 961, 1953, 3969, 8001, 16129, 32385, 65025, 130305, 261121, 522753, 1046529, 2094081, 4190209, 8382465, 16769025, 33542145, 67092481, 134193153, 268402689, 536821761, 1073676289, 2147385345

Offset: 0

Philippe Gibone, Jun 15 2016

The folds are always made so the longer side becomes the shorter side.
We could have counted not only the holes but also all the notches: 4, 6, 9, 15, 25, 45, 81, 153, 289, ... which has the formula a(n) = (2^ceiling(n/2) + 1) * (2^floor(n/2) + 1) and appears to match the sequence A183978. - Philippe Gibone, Jul 06 2016
The same sequence (0,0,1,3,9,21,49,...) turns up when you start with an isosceles right triangular piece of paper and repeatedly fold it in half, snipping corners as you go. Is there an easy way to see why the two questions have the same answer? - James Propp, Jul 05 2016
Reply from Tom Karzes, Jul 05 2016: (Start)
This case seems a little more complicated than the rectangular case, since with the triangle you alternate between horizontal/vertical folds vs. diagonal folds, and the resulting fold pattern is more complex, but I think the basic argument is essentially the same.
Note that with the triangle, the first hole doesn't appear until after you've made 3 folds, so if you start counting at zero folds, you have three leading zeros in the sequence: 0,0,0,1,3,9,21,... (End)
Also the number of subsets of {1,2,...,n} that contain both even and odd numbers. For example, a(3)=3 and the 3 subsets are {1,2}, {2,3}, {1,2,3}; a(4)=9 and the 9 subsets are {1,2}, {1,4}, {2,3}, {3,4}, {1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}, {1,2,3,4}. (See comments in A052551 for the number of subsets of {1,2,...,n} that contain only odd and even numbers.) - Enrique Navarrete, Mar 26 2018
Also the number of integer compositions of n + 1 with an odd part other than the first or last. The complementary compositions are counted by A052955(n>0) = A027383(n) + 1. - Gus Wiseman, Feb 05 2022
Also the number of unit squares in the (n+1)-st iteration in the version of the dragon curve where the rotation directions alternate, so that any clockwise rotation is followed by a counterclockwise rotation, and vice versa (see image link below). - Talmon Silver, May 09 2023

Paolo P. Lava, Table of n, a(n) for n = 0..1000
Philippe Gibone, Illustration of a(0)-a(4) (idealized).
Talmon Silver, Illustration of alternating dragon.
N. J. A. Sloane, Illustration for a(4) = 9 (scan of an actual cut-up piece of paper)
N. J. A. Sloane, Illustration for a(5) = 21 (scan of an actual cut-up piece of paper)
Index entries for linear recurrences with constant coefficients, signature (3,0,-6,4).

Cf. A000225, A079667, A183978.
See A274626, A274627 for the three- and higher-dimensional analogs.
This is the main diagonal of A274635.
Counting fold lines instead of holes gives A027383.
Bisections are A060867 (even) and A134057 (odd).
Cf. A000712, A001405, A008549, A011782, A026010, A052955, A097613, A126869, A138364, A232580, A351003.

[(2^Ceiling(n/2)-1)*(2^Floor(n/2)-1 ): n in [0..35]]; // Vincenzo Librandi, Jul 02 2016

A274230:=n->(1+2^n-2^((n-3)/2)*(3-3*(-1)^n+2*sqrt(2)+2*(-1)^n*sqrt(2))): seq(A274230(n), n=0..50); # Wesley Ivan Hurt, Jul 07 2016

Table[(2^Ceiling@ # - 1) (2^Floor@ # - 1) &[n/2], {n, 0, 31}] (* Michael De Vlieger, Jun 30 2016 *)

a(n)=2^n+1-(n%2+2)<<(n\2) \\ Charles R Greathouse IV, Jul 05 2016

u(0) = 0; v(0) = 0; u(n+1) = v(n); v(n+1) = 2u(n) + 1; a(n) = u(n)*v(n).
a(n) = (2^ceiling(n/2) - 1)*(2^floor(n/2) - 1).
Proof from Tom Karzes, Jul 05 2016: (Start)
Let r be the number of times you fold along one axis and s be the number of times you fold along the other axis. So r is ceiling(n/2) and s is floor(n/2), where n is the total number of folds.
When unfolded, the resulting paper has been divided into a grid of (2^r) by (2^s) rectangles. The interior grid lines will have diamond-shaped holes where they intersect (assuming diagonal cuts).
There are (2^r-1) internal grid lines along one axis and (2^s-1) along the other. The total number of internal grid line intersections is therefore (2^r-1)*(2^s-1), or (2^ceiling(n/2)-1)*(2^floor(n/2)-1) as claimed. (End)
From Colin Barker, Jun 22 2016, revised by N. J. A. Sloane, Jul 05 2016: (Start)
It follows that:
a(n) = (2^(n/2)-1)^2 for n even, a(n) = 2^n+1-3*2^((n-1)/2) for n odd.
a(n) = 3*a(n-1)-6*a(n-3)+4*a(n-4) for n>3.
G.f.: x^2 / ((1-x)*(1-2*x)*(1-2*x^2)).
a(n) = (1+2^n-2^((n-3)/2)*(3-3*(-1)^n+2*sqrt(2)+2*(-1)^n*sqrt(2))). (End)
a(n) = A000225(n) - 2*A052955(n-2) for n > 1. - Yuchun Ji, Nov 19 2018
a(n) = A079667(2^(n-1)) for n >= 1. - J. M. Bergot, Jan 18 2021
a(n) = 2^(n-1) - A052955(n) = 2^(n-1) - A027383(n) - 1. - Gus Wiseman, Jan 29 2022
E.g.f.: cosh(x) + cosh(2*x) - 2*cosh(sqrt(2)*x) + sinh(x) + sinh(2*x) - 3*sinh(sqrt(2)*x)/sqrt(2). - Stefano Spezia, Apr 06 2022

A007179 Dual pairs of integrals arising from reflection coefficients.

Original entry on oeis.org

0, 1, 1, 4, 6, 16, 28, 64, 120, 256, 496, 1024, 2016, 4096, 8128, 16384, 32640, 65536, 130816, 262144, 523776, 1048576, 2096128, 4194304, 8386560, 16777216, 33550336, 67108864, 134209536, 268435456, 536854528, 1073741824, 2147450880, 4294967296, 8589869056

Offset: 0

N. J. A. Sloane, Simon Plouffe

			From _Gus Wiseman_, Feb 26 2022: (Start)
Also the number of integer compositions of n with at least one odd part. For example, the a(1) = 1 through a(5) = 16 compositions are:
  (1)  (1,1)  (3)      (1,3)      (5)
              (1,2)    (3,1)      (1,4)
              (2,1)    (1,1,2)    (2,3)
              (1,1,1)  (1,2,1)    (3,2)
                       (2,1,1)    (4,1)
                       (1,1,1,1)  (1,1,3)
                                  (1,2,2)
                                  (1,3,1)
                                  (2,1,2)
                                  (2,2,1)
                                  (3,1,1)
                                  (1,1,1,2)
                                  (1,1,2,1)
                                  (1,2,1,1)
                                  (2,1,1,1)
                                  (1,1,1,1,1)
(End)

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..200
Paul Barry, A Catalan Transform and Related Transformations on Integer Sequences, Journal of Integer Sequences, Vol. 8 (2005), Article 05.4.5.
J. Heading, Theorem relating to the development of a reflection coefficient in terms of a small parameter, J. Phys. A 14 (1981), 357-367.
Kyu-Hwan Lee, Se-jin Oh, Catalan triangle numbers and binomial coefficients, arXiv:1601.06685 [math.CO], 2016.
A. Yajima, How to calculate the number of stereoisomers of inositol-homologs, Bull. Chem. Soc. Jpn. 2014, 87, 1260-1264 | doi:10.1246/bcsj.20140204. See Tables 1 and 2 (and text). - _N. J. A. Sloane_, Mar 26 2015
Index entries for linear recurrences with constant coefficients, signature (2,2,-4).

Column k=2 of A309748.
Odd bisection is A000302.
Even bisection is A006516 = 2^(n-1)*(2^n - 1).
The complement is counted by A077957, internal version A027383.
The internal case is A274230, even bisection A134057.
A000045(n-1) counts compositions without odd parts, non-singleton A077896.
A003242 counts Carlitz compositions.
A011782 counts compositions.
A034871, A097805, and A345197 count compositions by alternating sum.
A052952 (or A074331) counts non-singleton compositions without even parts.
Cf. A000918, A033484, A052955, A060867, A116406, A138364.

[Floor(2^n/2-2^(n/2)*(1+(-1)^n)/4): n in [0..40]]; // Vincenzo Librandi, Aug 20 2011

f := n-> if n mod 2 = 0 then 2^(n-1)-2^((n-2)/2) else 2^(n-1); fi;

LinearRecurrence[{2,2,-4},{0,1,1},30] (* Harvey P. Dale, Nov 30 2015 *)
Table[2^(n-1)-If[EvenQ[n],2^(n/2-1),0],{n,0,15}] (* Gus Wiseman, Feb 26 2022 *)

Vec(x*(1-x)/((1-2*x)*(1-2*x^2)) + O(x^50)) \\ Michel Marcus, Jan 28 2016

From Paul Barry, Apr 28 2004: (Start)
  Binomial transform is (A000244(n)+A001333(n))/2.
  G.f.: x*(1-x)/((1-2*x)*(1-2*x^2)).
  a(n) = 2*a(n-1)+2*a(n-2)-4*a(n-3).
  a(n) = 2^n/2-2^(n/2)*(1+(-1)^n)/4. (End)
G.f.: (1+x*Q(0))*x/(1-x), where Q(k)= 1 - 1/(2^k - 2*x*2^(2*k)/(2*x*2^k - 1/(1 + 1/(2*2^k - 8*x*2^(2*k)/(4*x*2^k + 1/Q(k+1)))))); (continued fraction). - Sergei N. Gladkovskii, May 22 2013
a(n) = A011782(n+2) - A077957(n) - Gus Wiseman, Feb 26 2022

A334638 Three-column array pPT read by rows: subsequence of primitive Pythagorean triples (x, y, z) with x = A153893^2 - A000079^2, y = 2A153893A000079, z = A153893^2 + A000079^2, ordered by increasing z.

Original entry on oeis.org

3, 4, 5, 21, 20, 29, 105, 88, 137, 465, 368, 593, 1953, 1504, 2465, 8001, 6080, 10049, 32385, 24448, 40577, 130305, 98048, 163073, 522753, 392704, 653825, 2094081, 1571840, 2618369, 8382465, 6289408, 10479617, 33542145, 25161728, 41930753, 134193153, 100655104, 167747585, 536821761, 402636800, 671039489, 2147385345, 1610579968, 2684256257

Offset: 0

Ralf Steiner, May 07 2020

Let [h21] = {{1, 3}, {0, 2}} be the matrix [h_2]*[h_1] in Firstov's notation, from eqs. (24) and (39). Then primitive Pythagorean triples (pPT) (x(n), y(n), z(n)) = (u(n)^2 - v(n)^2, 2*u(n)*v(n), u(n)^2 + v(n)^2), with u(n) and v(n) of different parity, gcd(u(n), v(n)) = 1, and u(n) > v(n) > 0, are generated by (u(n), v(n))^T = [h21]^n*(2,1)^T (T for transpose).
For n > 0: (x(n), y(n), z(n)) = (1, 0, 1) (mod 4). Thus some z are Pythagorean primes (A002144).
The triples converge to the proportion (4:3:5) with:
lim_{n->infinity} x(n)/y(n) = 4/3, lim_{n->infinity} y(n)/z(n) = 3/5.
Altitude h(n) = x(n)*y(n)/z(n) is an irreducible fraction because of primitivity.
From Wolfdieter Lang, Jun 13 2020: (Start)
[h21]^n = sqrt(2)^n*(S(n, 3/sqrt(2))*[1_3] + S(n-1, 3/sqrt(2))*(1/sqrt(2))*([h21] - 3*[1_3])) with the Chebyshev S polynomials (A049310).
u(n) = sqrt(2)^n*(2*S(n, 3/sqrt(2)) - (1/sqrt(2))*S(n-1, 3/sqrt(2)))
     = A153893(n),
v(n) = sqrt(2)^n*(S(n, 3/sqrt(2)) - (1/sqrt(2))*S(n-1, 3/sqrt(2)))
     = A000079(n). Proof from the recurrence, using the Cayley-Hamilton theorem.
With the monic Chebyshev T polynomials, called R in A127672:
x(n)/3 = 2^(n+1)*(R(2*(n+1), 3/sqrt(2)) - (sqrt(2)/3)*R(2*n+1,3/sqrt(2)) - 1) = A171477(n),
y(n)/4 = 3*2^(n-1)*(sqrt(2)*R(2*n+1,3/sqrt(2)) - R(2*n,3/sqrt(2)) - 1/3)
= A010036(n),
z(n) = 3*2^(n+1)*((3/sqrt(2))*R(2*n+1, 3/sqrt(2)) - (4/3)*R(2*n,3/sqrt(2)) - 1).
Using 2^n*Rnx(2*n, 3/sqrt(2)) = A052539(n) = 2^(2*n) + 1, and
  2^(n)*(sqrt(2)/3)*Rnx(2*n+1, 3/sqrt(2)) = A007583(n) = (2^(2*n + 1) + 1)/3,
produces the explicit formulas given by the author in the formula section.
G.f.s for {x(n)} G0(x) = 3/((1 - 4*x)*(1 - 2*x)*(1 - x)), for {y(n)} G1(x) =  4*(1-x)/((1 - 4*x)*(1 - 2*x)), and for {z(n)} = (5 - 6*x + 4*x^2)/((1 - 4*x)*(1 - 2*x)*(1 - x)). This produces the g.f. for the array, read as sequence {a(n)}: G(x) = G0(x^3) + x*G1(x^3) + x^2*G2(x^3) given in the formula section by Colin Barker.
(End)

			The three-column array pPT(n,k) begins:
n\k        0        1         2
-------------------------------
0:         3        4         5
1:        21       20        29
2:       105       88       137
3:       465      368       593
4:      1953     1504      2465
5:      8001     6080     10049
6:     32385    24448     40577
7:    130305    98048    163073
8:    522753   392704    653825
9:   2094081  1571840   2618369
10:  8382465  6289408  10479617
... - _Wolfdieter Lang_, Jun 13 2020

V. E. Firstov, A Special Matrix Transformation Semigroup of Primitive Pairs and the Genealogy of Pythagorean Triples; Mathematical Notes, volume 84, number 2, August 2008, pages 263-279; Link of the page (for the Russian article).
Ralf Steiner, Weitere spezielle Folge primitiver pythagoraischer Dreiecke, ResearchGate.
Wikipedia, Tree of primitive Pythagorean triples.
Index entries for linear recurrences with constant coefficients, signature (0,0,7,0,0,-14,0,0,8).

Cf. A000079, A010035, A049310, A083329, A093357, A010036, A134057, A153893, A171477.

h21={{1, 3}, {0, 2}}; l = {}; Do[v = MatrixPower[h21, n, {2, 1}]; p = v[[1]]; q = v[[2]];
a = p^2 - q^2; b = 2 p q; c = p^2 + q^2; l = AppendTo[l, {a, b, c}], {n, 0, 14}]; l // Flatten

Vec((3 + 4*x + 5*x^2 - 8*x^4 - 6*x^5 + 4*x^7 + 4*x^8) / ((1 - x)*(1 + x + x^2)*(1 - 2*x^3)*(1 - 4*x^3)) + O(x^35)) \\ Colin Barker, Jun 12 2020

The three-column array PT(n, k) is for k = 0, 1, 2:  x(n), y(n), z(n), for n >= 0, with
x(n) = a(3*n + 0) = A153893(n)^2 - A000079(n)^2 = 1 - 3*2^(n+1) + 2^(2*n+3) = binomial(2^(n+2) - 1, 2) = 3*A171477(n),
y(n) = a(3*n + 1) = 2*A153893(n)*A000079(n) = 2^(n+1)*(-1 + 3*2^n) = 4*A010036(n),
z(n) = a(3*n + 2) = A153893(n)^2 + A000079(n)^2 = 1 - 6*2^n + 10*2^(2*n).
From Colin Barker, May 08 2020: (Start)
G.f. (read as sequence {a(n)}): (3 + 4*x + 5*x^2 - 8*x^4 - 6*x^5 + 4*x^7 + 4*x^8) / ((1 - x)*(1 + x + x^2)*(1 - 2*x^3)*(1 - 4*x^3)).
a(n) = 7*a(n-3) - 14*a(n-6) + 8*a(n-9), for n > 8.
(End)

Edited, and corrected proportion by Wolfdieter Lang, Jun 13 2020

Minor grammatical edits. - N. J. A. Sloane, Sep 12 2020

A346412 Triangular array read by rows: T(n,k) is the number of nilpotent n X n matrices over GF(2) having rank k, 0 <= k <= n-1, n >= 1.

Original entry on oeis.org

1, 1, 3, 1, 21, 42, 1, 105, 1470, 2520, 1, 465, 32550, 390600, 624960, 1, 1953, 605430, 36325800, 406848960, 629959680, 1, 8001, 10417302, 2768025960, 155009453760, 1680102466560, 2560156139520, 1, 32385, 172741590, 192779614440, 47809344381120, 2590958018073600, 27636885526118400, 41781748196966400

Offset: 1

Geoffrey Critzer, Jul 15 2021

			Array begins
  1;
  1,    3;
  1,   21,     42;
  1,  105,   1470,     2520;
  1,  465,  32550,   390600,    624960;
  1, 1953, 605430, 36325800, 406848960, 629959680
T(2,0) = 1 because the zero matrix has rank 0.
T(2,1) = 3 because {{0,0},{1,0}}, {{0,1},{0,0}}, {{1,1},{1,1}} have rank 1.

G. Lusztig, A note on counting nilpotent matrices of fixed rank, Bull. London Math. Soc. v.8 (1976), no. 1, 77--80; MR0407050.

Jason Fulman, A probabilistic approach toward the finite general linear and unitary group, arxiv.org, Dec 1997, page 12.
J. Kung, The cycle structure of a linear transformation over a finite field,Linear Algebra and its Applications, vol 36, March 1981,141-155.
Kent E. Morrison, Integer Sequences and Matrices Over Finite Fields, Journal of Integer Sequences, Vol. 9 (2006), Article 06.2.1.

Cf. A134057 (column k=1), A083402 (main diagonal), A053763 (row sums).

nn = 10; q = 2; b[p_, i_] := Count[p, i];d[p_, i_] :=Sum[j b[p, j], {j, 1, i}] + i Sum[b[p, j], {j, i + 1, Total[p]}]; aut[deg_, p_] :=  Product[Product[
   q^(d[p, i] deg) - q^((d[p, i] - k) deg), {k, 1, b[p, i]}], {i, 1, Total[p]}];
g[u_, v_] := Total[Map[v^(Total[#] - Length[#]) u^Total[#]/aut[1, #] &,
   Level[Table[IntegerPartitions[n], {n, 0, nn}], {2}]]];Map[Select[#, # > 0 &] &,Drop[Table[Product[q^n - q^i, {i, 0, n - 1}], {n, 0, nn}] CoefficientList[
     Series[g[u, v], {u, 0, nn}], {u, v}], 1]] // Grid

T(n,n-k) = A002884(n)*Product_{i=k..n-1}(1-1/2^i)/(A002884(k)*2^(n-k)*Product_{i=1..n-k}(1-1/2^i)) Theorem 6 in Fulman link. - Geoffrey Critzer, Dec 23 2024

A355315 Triangular array read by rows: T(n,k) is the number of independent collections of subsets of [n] having exactly k members, n>=0, 0<=k<=A347025(n).

Original entry on oeis.org

1, 1, 1, 1, 3, 3, 1, 7, 21, 26, 6, 1, 15, 105, 400, 803, 782, 340, 34

Offset: 0

Geoffrey Critzer, Jun 28 2022

Here, an independent collection of subsets of [n] is such that no member is a union of other members. The empty set is not contained in any independent set although the empty collection is independent. These collections are the bases of the union closed families counted in A102896 which gives the row sums of this sequence.

			T(3,4) = 6 because we have: {{1}, {2}, {1, 3}, {2, 3}}, {{1}, {3}, {1, 2}, {2, 3}}, {{1}, {1, 2}, {1, 3}, {2, 3}}, {{2}, {3}, {1, 2}, {1, 3}}, {{2}, {1, 2}, {1, 3}, {2, 3}}, {{3}, {1, 2}, {1, 3}, {2, 3}}.
Triangle T(n,k) begins:
  1;
  1,  1;
  1,  3,   3;
  1,  7,  21,  26,   6;
  1, 15, 105, 400, 803, 782, 340, 34;
  ...

K. H. Kim, Boolean Matrix Theory and Applications, Marcel Decker Inc., 1982, page 44.

P. Erdős and D. Kleitman, Extremal problems among subsets of a set, Discrete Mathematics, 8, 1974, 281-294.
D. Kleitman, On a combinatorial problem of Erdős, Proc. Amer. Math Soc, 17 (1966) 139-141.

Columns k=0..2 give: A000012, A000225, A134057.

Row sums give A102896.

independentQ[collection_] := If[MemberQ[collection, Table[0, {nn}]] \[Or] !
    DuplicateFreeQ[collection], False, Apply[And,Table[! MemberQ[   Map[Clip[Total[#]] &,Subsets[Drop[collection, {i}], {2, Length[collection]}]],
      collection[[i]]], {i, 1, Length[collection]}]]]; Map[Select[#, # > 0 &] &,
  Table[Table[Length[Select[Subsets[Tuples[{0, 1}, nn], {i}], independentQ[#] &]], {i, 0, 7}], {nn, 0, 4}]] // Grid

T(n,0) = 1 = A000012(n).
T(n,1) = 2^n - 1 = A000225(n).
T(n,2) = binomial(2^n-1,2) = A134057(n).

cp's OEIS Frontend

A027383 a(2*n) = 3*2^n - 2; a(2*n+1) = 2^(n+2) - 2.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Python

Formula

Extensions

A029858 a(n) = (3^n - 3)/2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

Extensions

A274230 Number of holes in a sheet of paper when you fold it n times and cut off the four corners.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A007179 Dual pairs of integrals arising from reflection coefficients.

Views

Author

Keywords

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Formula

A334638 Three-column array pPT read by rows: subsequence of primitive Pythagorean triples (x, y, z) with x = A153893^2 - A000079^2, y = 2*A153893*A000079, z = A153893^2 + A000079^2, ordered by increasing z.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A346412 Triangular array read by rows: T(n,k) is the number of nilpotent n X n matrices over GF(2) having rank k, 0 <= k <= n-1, n >= 1.

Views

Author

Keywords

Examples

A027383 a(2n) = 32^n - 2; a(2*n+1) = 2^(n+2) - 2.

A334638 Three-column array pPT read by rows: subsequence of primitive Pythagorean triples (x, y, z) with x = A153893^2 - A000079^2, y = 2A153893A000079, z = A153893^2 + A000079^2, ordered by increasing z.