A030451 -id:A030451 - cp's OEIS frontend

A005044 Alcuin's sequence: expansion of x^3/((1-x^2)(1-x^3)(1-x^4)).

0, 0, 0, 1, 0, 1, 1, 2, 1, 3, 2, 4, 3, 5, 4, 7, 5, 8, 7, 10, 8, 12, 10, 14, 12, 16, 14, 19, 16, 21, 19, 24, 21, 27, 24, 30, 27, 33, 30, 37, 33, 40, 37, 44, 40, 48, 44, 52, 48, 56, 52, 61, 56, 65, 61, 70, 65, 75, 70, 80, 75, 85, 80, 91, 85, 96, 91, 102, 96, 108, 102, 114, 108, 120

Offset: 0

Robert G. Wilson v

a(n) is the number of triangles with integer sides and perimeter n.
Also a(n) is the number of triangles with distinct integer sides and perimeter n+6, i.e., number of triples (a, b, c) such that 1 < a < b < c < a+b, a+b+c = n+6. - Roger Cuculière
With a different offset (i.e., without the three leading zeros, as in A266755), the number of ways in which n empty casks, n casks half-full of wine and n full casks can be distributed to 3 persons in such a way that each one gets the same number of casks and the same amount of wine [Alcuin]. E.g., for n=2 one can give 2 people one full and one empty and the 3rd gets two half-full. (Comment corrected by Franklin T. Adams-Watters, Oct 23 2006)
For m >= 2, the sequence {a(n) mod m} is periodic with period 12*m. - Martin J. Erickson (erickson(AT)truman.edu), Jun 06 2008
Number of partitions of n into parts 2, 3, and 4, with at least one part 3. - Joerg Arndt, Feb 03 2013
For several values of p and q the sequence (A005044(n+p) - A005044(n-q)) leads to known sequences, see the crossrefs. - Johannes W. Meijer, Oct 12 2013
For n>=3, number of partitions of n-3 into parts 2, 3, and 4. - David Neil McGrath, Aug 30 2014
Also, a(n) is the number of partitions mu of n of length 3 such that mu_1-mu_2 is even and mu_2-mu_3 is even (see below example). - John M. Campbell, Jan 29 2016
For n > 1, number of triangles with odd side lengths and perimeter 2*n-3. - Wesley Ivan Hurt, May 13 2019
Number of partitions of n+1 into 4 parts whose largest two parts are equal. - Wesley Ivan Hurt, Jan 06 2021
For n>=3, number of weak partitions of n-3 (that is, allowing parts of size 0) into three parts with no part exceeding (n-3)/2. Also, number of weak partitions of n-3 into three parts, all of the same parity as n-3. - Kevin Long, Feb 20 2021
Also, a(n) is the number of incongruent acute triangles formed from the vertices of a regular n-gon. - Frank M Jackson, Nov 04 2022

			There are 4 triangles of perimeter 11, with sides 1,5,5; 2,4,5; 3,3,5; 3,4,4. So a(11) = 4.
G.f. = x^3 + x^5 + x^6 + 2*x^7 + x^8 + 3*x^9 + 2*x^10 + 4*x^11 + 3*x^12 + ...
From _John M. Campbell_, Jan 29 2016: (Start)
Letting n = 15, there are a(n)=7 partitions mu |- 15 of length 3 such that mu_1-mu_2 is even and mu_2-mu_3 is even:
(13,1,1) |- 15
(11,3,1) |- 15
(9,5,1) |- 15
(9,3,3) |- 15
(7,7,1) |- 15
(7,5,3) |- 15
(5,5,5) |- 15
(End)

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 74, Problem 7.
I. Niven and H. S. Zuckerman, An Introduction to the Theory of Numbers. Wiley, NY, Chap.10, Section 10.2, Problems 5 and 6, pp. 451-2.
D. Olivastro: Ancient Puzzles. Classic Brainteasers and Other Timeless Mathematical Games of the Last 10 Centuries. New York: Bantam Books, 1993. See p. 158.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
A. M. Yaglom and I. M. Yaglom: Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. New York: Dover Publications, Inc., 1987, p. 8, #30 (First published: San Francisco: Holden-Day, Inc., 1964)

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..1000 from T. D. Noe)
Alcuin of York, Propositiones ad acuendos juvenes, [Latin with English translation] - see Problem 12.
G. E. Andrews, A note on partitions and triangles with integer sides, Amer. Math. Monthly, 86 (1979), 477-478.
G. E. Andrews, MacMahon's Partition Analysis II: Fundamental Theorems, Annals Combinatorics, 4 (2000), 327-338.
G. E. Andrews, P. Paule and A. Riese, MacMahon's Partition Analysis IX: k-gon partitions, Bull. Austral Math. Soc., 64 (2001), 321-329.
G. E. Andrews, P. Paule and A. Riese, MacMahon's partition analysis III. The Omega package, p. 19.
Donald J. Bindner and Martin Erickson, Alcuin's Sequence, Amer. Math. Monthly, 119, February 2012, pp. 115-121.
P. Bürgisser and C. Ikenmeyer, Fundamental invariants of orbit closures, arXiv preprint arXiv:1511.02927 [math.AG], 2015. See Section 5.5.
James East and Ron Niles, Integer polygons of given perimeter, Bull. Aust. Math. Soc. 100 (2019), no. 1, 131-147.
James East and Ron Niles, Integer Triangles of Given Perimeter: A New Approach via Group Theory., Amer. Math. Monthly 126 (2019), no. 8, 735-739.
Wulf-Dieter Geyer, Lecture on history of medieval mathematics [broken link]
M. D. Hirschhorn, Triangles With Integer Sides
M. D. Hirschhorn, Triangles With Integer Sides, Revisited
R. Honsberger, Mathematical Gems III, Math. Assoc. Amer., 1985, p. 39. [Annotated scanned copy]
T. Jenkyns and E. Muller, Triangular triples from ceilings to floors, Amer. Math. Monthly, 107 (Aug. 2000), 634-639.
J. H. Jordan, R. Walch and R. J. Wisner, Triangles with integer sides, Amer. Math. Monthly, 86 (1979), 686-689.
Hermann Kremer, Posting to de.sci.mathematik (1), (2), and (3). [Dead links]
Hermann Kremer, Posting to alt.math.recreational, June 2004.
N. Krier and B. Manvel, Counting integer triangles, Math. Mag., 71 (1998), 291-295.
Mathforum, Triangle Perimeters
Augustine O. Munagi, Computation of q-partial fractions, INTEGERS: Electronic Journal Of Combinatorial Number Theory, 7 (2007), #A25.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992
S. A. Shirali, Case Studies in Experimental Mathematics, 2013.
David Singmaster, Triangles with Integer Sides and Sharing Barrels, College Math J, 21:4 (1990) 278-285.
James Tanton, Young students approach integer triangles, FOCUS 22 no. 5 (2002), 4 - 6.
James Tanton, Integer Triangles, Chapter 11 in "Mathematics Galore!" (MAA, 2012).
Eric Weisstein's World of Mathematics, Alcuin's Sequence, Integer Triangle, and Triangle.
Wikipedia, Propositiones ad acuendos juvenes.
R. G. Wilson v, Letter to N. J. A. Sloane, date unknown.
Index entries for two-way infinite sequences
Index entries for Molien series
Index entries for linear recurrences with constant coefficients, signature (0,1,1,1,-1,-1,-1,0,1).

See A266755 for a version without the three leading zeros.
Cf. A002620, A070083, A008795.
Both bisections give (essentially) A001399.
(See the comments.) Cf. A008615 (p=1, q=3, offset=0), A008624 (3, 3, 0), A008679 (3, -1, 0), A026922 (1, 5, 1), A028242 (5, 7, 0), A030451 (6, 6, 0), A051274 (3, 5, 0), A052938 (8, 4, 0), A059169 (0, 6, 1), A106466 (5, 4, 0), A130722 (2, 7, 0)
Cf. this sequence (k=3), A288165 (k=4), A288166 (k=5).
Number of k-gons that can be formed with perimeter n: this sequence (k=3), A062890 (k=4), A069906 (k=5), A069907 (k=6), A288253 (k=7), A288254 (k=8), A288255 (k=9), A288256 (k=10).

a005044 = p [2,3,4] . (subtract 3) where
p _ 0 = 1
p [] _ = 0
p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
-- Reinhard Zumkeller, Feb 28 2013

A005044 := n-> floor((1/48)*(n^2+3*n+21+(-1)^(n-1)*3*n)): seq(A005044(n), n=0..73);
A005044 := -1/(z**2+1)/(z**2+z+1)/(z+1)**2/(z-1)**3; # Simon Plouffe in his 1992 dissertation

a[n_] := Round[If[EvenQ[n], n^2, (n + 3)^2]/48] (* Peter Bertok, Jan 09 2002 *)
CoefficientList[Series[x^3/((1 - x^2)*(1 - x^3)*(1 - x^4)), {x, 0, 105}], x] (* Robert G. Wilson v, Jun 02 2004 *)
me[n_] := Module[{i, j, sum = 0}, For[i = Ceiling[(n - 3)/3], i <= Floor[(n - 3)/2], i = i + 1, For[j = Ceiling[(n - i - 3)/2], j <= i, j = j + 1, sum = sum + 1] ]; Return[sum]; ] mine = Table[me[n], {n, 1, 11}]; (* Srikanth (sriperso(AT)gmail.com), Aug 02 2008 *)
LinearRecurrence[{0,1,1,1,-1,-1,-1,0,1},{0,0,0,1,0,1,1,2,1},80] (* Harvey P. Dale, Sep 22 2014 *)
Table[Length@Select[IntegerPartitions[n, {3}], Max[#]*180 < 90 n &], {n, 1, 100}] (* Frank M Jackson, Nov 04 2022 *)

PARI
```
a(n) = round(n^2 / 12) - (n\2)^2 \ 4
```
PARI
```
a(n) = (n^2 + 6*n * (n%2) + 24) \ 48
```

a(n)=if(n%2,n+3,n)^2\/48 \\ Charles R Greathouse IV, May 02 2016

concat(vector(3), Vec((x^3)/((1-x^2)*(1-x^3)*(1-x^4)) + O(x^70))) \\ Felix Fröhlich, Jun 07 2017

a(n) = a(n-6) + A059169(n) = A070093(n) + A070101(n) + A024155(n).
For odd indices we have a(2*n-3) = a(2*n). For even indices, a(2*n) = nearest integer to n^2/12 = A001399(n).
For all n, a(n) = round(n^2/12) - floor(n/4)*floor((n+2)/4) = a(-3-n) = A069905(n) - A002265(n)*A002265(n+2).
For n = 0..11 (mod 12), a(n) is respectively n^2/48, (n^2 + 6*n - 7)/48, (n^2 - 4)/48, (n^2 + 6*n + 21)/48, (n^2 - 16)/48, (n^2 + 6*n - 7)/48, (n^2 + 12)/48, (n^2 + 6*n + 5)/48, (n^2 - 16)/48, (n^2 + 6*n + 9)/48, (n^2 - 4)/48, (n^2 + 6*n + 5)/48.
Euler transform of length 4 sequence [ 0, 1, 1, 1]. - Michael Somos, Sep 04 2006
a(-3 - n) = a(n). - Michael Somos, Sep 04 2006
a(n) = sum(ceiling((n-3)/3) <= i <= floor((n-3)/2), sum(ceiling((n-i-3)/2) <= j <= i, 1 ) ) for n >= 1. - Srikanth K S, Aug 02 2008
a(n) = a(n-2) + a(n-3) + a(n-4) - a(n-5) - a(n-6) - a(n-7) + a(n-9) for n >= 9. - David Neil McGrath, Aug 30 2014
a(n+3) = a(n) if n is odd; a(n+3) = a(n) + floor(n/4) + 1 if n is even. Sketch of proof: There is an obvious injective map from perimeter-n triangles to perimeter-(n+3) triangles defined by f(a,b,c) = (a+1,b+1,c+1). It is easy to show f is surjective for odd n, while for n=2k the image of f is only missing the triangles (a,k+2-a,k+1) for 1 <= a <= floor(k/2)+1. - James East, May 01 2016
a(n) = round(n^2/48) if n is even; a(n) = round((n+3)^2/48) if n is odd. - James East, May 01 2016
a(n) = (6*n^2 + 18*n - 9*(-1)^n*(2*n + 3) - 36*sin(Pi*n/2) - 36*cos(Pi*n/2) + 64*cos(2*Pi*n/3) - 1)/288. - Ilya Gutkovskiy, May 01 2016
a(n) = A325691(n-3) + A000035(n) for n>=3. The bijection between partition(n,[2,3,4]) and not-over-half partition(n,3,n/2) + partition(n,2,n/2) can be built by a Ferrers(part)[0+3,1,2] map. And the last partition(n,2,n/2) is unique [n/2,n/2] if n is even, it is given by A000035. - Yuchun Ji, Sep 24 2020
a(4n+3) = a(4n) + n+1, a(4n+4) = a(4n+1) = A000212(n+1), a(4n+5) = a(4n+2) + n+1, a(4n+6) = a(4n+3) = A007980(n). - Yuchun Ji, Oct 10 2020
a(n)-a(n-4) = A008615(n-1). - R. J. Mathar, Jun 23 2021
a(n)-a(n-2) = A008679(n-3). - R. J. Mathar, Jun 23 2021

Additional comments from Reinhard Zumkeller, May 11 2002
Yaglom reference and mod formulas from Antreas P. Hatzipolakis (xpolakis(AT)otenet.gr), May 27 2000
The reference to Alcuin of York (735-804) was provided by Hermann Kremer (hermann.kremer(AT)onlinehome.de), Jun 18 2004

A028242 Follow n+1 by n. Also (essentially) Molien series of 2-dimensional quaternion group Q_8.

Original entry on oeis.org

1, 0, 2, 1, 3, 2, 4, 3, 5, 4, 6, 5, 7, 6, 8, 7, 9, 8, 10, 9, 11, 10, 12, 11, 13, 12, 14, 13, 15, 14, 16, 15, 17, 16, 18, 17, 19, 18, 20, 19, 21, 20, 22, 21, 23, 22, 24, 23, 25, 24, 26, 25, 27, 26, 28, 27, 29, 28, 30, 29, 31, 30, 32, 31, 33, 32, 34, 33, 35, 34, 36, 35, 37, 36, 38

Offset: 0

N. J. A. Sloane

A two-way infinite sequences which is palindromic (up to sign). - Michael Somos, Mar 21 2003
Number of permutations of [n+1] avoiding the patterns 123, 132 and 231 and having exactly one fixed point. Example: a(0) because we have 1; a(2)=2 because we have 213 and 321; a(3)=1 because we have 3214. - Emeric Deutsch, Nov 17 2005
The ring of invariants for the standard action of Quaternions on C^2 is generated by x^4 + y^4, x^2 * y^2, and x * y * (x^4 - y^4). - Michael Somos, Mar 14 2011
A000027 and A001477 interleaved. - Omar E. Pol, Feb 06 2012
First differences are A168361, extended by an initial -1. (Or: a(n)-a(n-1) = A168361(n+1), for all n >= 1.) - M. F. Hasler, Oct 05 2017
Also the number of unlabeled simple graphs with n + 1 vertices and exactly n endpoints (vertices of degree 1). The labeled version is A327370. - Gus Wiseman, Sep 06 2019

			G.f. = 1 + 2*x^2 + x^3 + 3*x^4 + 2*x^5 + 4*x^6 + 3*x^7 + 5*x^8 + 4*x^9 + 6*x^10 + 5*x^11 + ...
Molien g.f. = 1 + 2*t^4 + t^6 + 3*t^8 + 2*t^10 + 4*t^12 + 3*t^14 + 5*t^16 + 4*t^18 + 6*t^20 + ...

D. Benson, Polynomial Invariants of Finite Groups, Cambridge, p. 23.
S. Mukai, An Introduction to Invariants and Moduli, Cambridge, 2003; see p. 15.
M. D. Neusel and L. Smith, Invariant Theory of Finite Groups, Amer. Math. Soc., 2002; see p. 97.
L. Smith, Polynomial Invariants of Finite Groups, A K Peters, 1995, p. 90.

Reinhard Zumkeller, Table of n, a(n) for n = 0..1000
Paul Barry, On a Central Transform of Integer Sequences, arXiv:2004.04577 [math.CO], 2020.
H. W. Gould, The inverse of a finite series and a third-order recurrent sequence, Fibonacci Quart. 44 (2006), no. 4, 302-315. See page 311.
T. Mansour and A. Robertson, Refined restricted permutations avoiding subsets of patterns of length three, Annals of Combinatorics, 6, 2002, 407-418 (Theorem 3.3).
MathOverflow, A question about an application of Molien's formula to find the generators and relations of an invariant ring.
Gus Wiseman, The a(3) = 2 through a(7) = 4 graphs with exactly n - 1 endpoints.
Index entries for Molien series.
Index entries for two-way infinite sequences.
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).

Cf. A000124 (a=1, a=n+a), A028242 (a=1, a=n-a).
Partial sums give A004652. A030451(n)=a(n+1), n>0.
Cf. A052938 (same sequence except no leading 1,0,2).
Cf. A000027, A001477.
Column k = n - 1 of A327371.
Cf. A000035, A004526, A004110, A059167, A109613, A110654, A110657, A110658, A110660, A168361, A245797, A327227, A327369, A327370, A327377.

a:=[1];; for n in [2..80] do a[n]:=(n-1)-a[n-1]; od; a; # Muniru A Asiru, Dec 16 2018

import Data.List (transpose)
a028242 n = n' + 1 - m where (n',m) = divMod n 2
a028242_list = concat $ transpose [a000027_list, a001477_list]
-- Reinhard Zumkeller, Nov 27 2012

&cat[ [n+1, n]: n in [0..37] ]; // Klaus Brockhaus, Nov 23 2009

series((1+x^3)/(1-x^2)^2,x,80);
A028242:=n->floor((n+1+(-1)^n)/2): seq(A028242(n), n=0..100); # Wesley Ivan Hurt, Mar 17 2015

Table[(1 + 2 n + 3 (-1)^n)/4, {n, 0, 74}] (* or *)
LinearRecurrence[{1, 1, -1}, {1, 0, 2}, 75] (* or *)
CoefficientList[Series[(1 - x + x^2)/((1 - x) (1 - x^2)), {x, 0, 74}], x] (* Michael De Vlieger, May 21 2017 *)
Table[{n,n-1},{n,40}]//Flatten (* Harvey P. Dale, Jun 26 2017 *)
Table[3*floor(n/2)-n+1,{n,0,40}] (* Pierre-Alain Sallard, Dec 15 2018 *)

{a(n) = (n\2) - (n%2) + 1} \\ Michael Somos, Oct 02 1999

A028242(n)=n\2+!bittest(n,0) \\ M. F. Hasler, Oct 05 2017

s=((1+x^3)/(1-x^2)^2).series(x, 80); s.coefficients(x, sparse=False) # G. C. Greubel, Dec 16 2018

Expansion of the Molien series for standard action of Quaternions on C^2: (1 + t^6) / (1 - t^4)^2 = (1 - t^12) / ((1 - t^4)^2 * (1 - t^6)) in powers of t^2.
Euler transform of length 6 sequence [0, 2, 1, 0, 0, -1]. - Michael Somos, Mar 14 2011
a(n) = n - a(n-1) [with a(0) = 1] = A000035(n-1) + A004526(n). - Henry Bottomley, Jul 25 2001
G.f.: (1 - x + x^2) / ((1 - x) * (1 - x^2)) = ( 1+x^2-x ) / ( (1+x)*(x-1)^2 ).
a(2*n) = n + 1, a(2*n + 1) = n, a(-1 - n) = -a(n).
a(n) = a(n - 1) + a(n - 2) - a(n - 3).
a(n) = floor(n/2) + 1 - n mod 2. a(2*k) = k+1, a(2*k+1) = k; A110657(n) = a(a(n)), A110658(n) = a(a(a(n))); a(n) = A109613(n)-A110654(n) = A110660(n)/A110654(n). - Reinhard Zumkeller, Aug 05 2005
a(n) = 2*floor(n/2) - floor((n-1)/2). - Wesley Ivan Hurt, Oct 22 2013
a(n) = floor((n+1+(-1)^n)/2). - Wesley Ivan Hurt, Mar 15 2015
a(n) = (1 + 2n + 3(-1)^n)/4. - Wesley Ivan Hurt, Mar 18 2015
a(n) = Sum_{i=1..floor(n/2)} floor(n/(n-i)) for n > 0. - Wesley Ivan Hurt, May 21 2017
a(2n) = n+1, a(2n+1) = n, for all n >= 0. - M. F. Hasler, Oct 05 2017
a(n) = 3*floor(n/2) - n + 1. - Pierre-Alain Sallard, Dec 15 2018
E.g.f.: ((2 + x)*cosh(x) + (x - 1)*sinh(x))/2. - Stefano Spezia, Aug 01 2022
Sum_{n>=2} (-1)^(n+1)/a(n) = 1. - Amiram Eldar, Oct 04 2022

First part of definition adjusted to match offset by Klaus Brockhaus, Nov 23 2009

A084964 Follow n+2 by n. Also solution of a(n+2)=a(n)+1, a(0)=2, a(1)=0.

Original entry on oeis.org

2, 0, 3, 1, 4, 2, 5, 3, 6, 4, 7, 5, 8, 6, 9, 7, 10, 8, 11, 9, 12, 10, 13, 11, 14, 12, 15, 13, 16, 14, 17, 15, 18, 16, 19, 17, 20, 18, 21, 19, 22, 20, 23, 21, 24, 22, 25, 23, 26, 24, 27, 25, 28, 26, 29, 27, 30, 28, 31, 29, 32, 30, 33, 31, 34, 32, 35, 33, 36, 34, 37, 35, 38, 36, 39

Offset: 0

Michael Somos, Jun 15 2003

Stefano Spezia, Table of n, a(n) for n = 0..10000
Index entries for linear recurrences with constant coefficients, signature (1,1,-1).
Index entries for two-way infinite sequences

Cf. A030451, A097065, A152832.

Cf. A217764(1,n) = a(n+2).

import Data.List (transpose)
a084964 n = a084964_list !! n
a084964_list = concat $ transpose [[2..], [0..]]
-- Reinhard Zumkeller, Apr 06 2015

&cat[ [n+2, n]: n in [0..37] ]; // Klaus Brockhaus, Nov 23 2009

A084964:=n->floor(n/2)+1+(-1)^n; seq(A084964(k), k=0..100); # Wesley Ivan Hurt, Nov 08 2013

lst={}; a=1; Do[a=n-a; AppendTo[lst, a], {n, 0, 100}]; lst (* Vladimir Joseph Stephan Orlovsky, Dec 14 2008 *)
Table[{n,n-2},{n,2,40}]//Flatten (* or *) LinearRecurrence[{1,1,-1},{2,0,3},80] (* Harvey P. Dale, Sep 12 2021 *)

PARI
```
a(n)=n\2-2*(n%2)+2
```

G.f.: (2-2x+x^2)/((1-x)(1-x^2)).
a(2n+1)=n. a(2n)=n+2. a(n+2)=a(n)+1. a(n)=-a(-3-n).
a(n) = floor(n/2) + 1 + (-1)^n. - Reinhard Zumkeller, Aug 27 2005
A112032(n)=2^a(n); A112033(n)=3*2^a(n); a(n)=A109613(n+2)-A052938(n). - Reinhard Zumkeller, Aug 27 2005
a(n) = n + 1 - a(n-1) (with a(0)=2). - Vincenzo Librandi, Aug 08 2010
a(n) = floor(n/2)*3 - floor((n-1)/2)*2. - Ross La Haye, Mar 27 2013
a(n) = 3*n - 3 - 5*floor((n-1)/2). - Wesley Ivan Hurt, Nov 08 2013
a(n) = (3 + 5*(-1)^n + 2*n)/4. - Wolfgang Hintze, Dec 13 2014
E.g.f.: ((4 + x)*cosh(x) - (1 - x)*sinh(x))/2. - Stefano Spezia, Jul 01 2023

First part of definition adjusted to match offset by Klaus Brockhaus, Nov 23 2009

A113881 Table of smallest number of squares, T(m,n), needed to tile an m X n rectangle, read by antidiagonals.

Original entry on oeis.org

1, 2, 2, 3, 1, 3, 4, 3, 3, 4, 5, 2, 1, 2, 5, 6, 4, 4, 4, 4, 6, 7, 3, 4, 1, 4, 3, 7, 8, 5, 2, 5, 5, 2, 5, 8, 9, 4, 5, 3, 1, 3, 5, 4, 9, 10, 6, 5, 5, 5, 5, 5, 5, 6, 10, 11, 5, 3, 2, 5, 1, 5, 2, 3, 5, 11, 12, 7, 6, 6, 5, 5, 5, 5, 6, 6, 7, 12, 13, 6, 6, 4, 6, 4, 1, 4, 6, 4, 6, 6, 13, 14, 8, 4, 6, 2, 3, 7, 7, 3, 2, 6, 4, 8, 14

Offset: 1

Devin Kilminster (devin(AT)27720.net), Jan 27 2006

a(n) = A338573(n) for n <= 105, as stated by R. J. Mathar. These sequences are essentially different though, because a(13433) = T(67,98) = T(98,67) = a(13464), but A338573(13433) != A338573(13464). The relationship between the tiling problem and resistor networks is remarkable. There are explanations in M. Ortolano et al., 2013. - Rainer Rosenthal, Nov 09 2020

			T(n,n) = 1 (1 n X n square).
T(n,1) = n (n 1 X 1 squares).
T(6,7) = 6 (2 3 X 3, 1 4 X 4, 1 2 X 2, 2 1 X 1).
T(11,13) = 6 (1 7 X 7, 1 6 X 6, 1 5 X 5, 2 4 X 4 1 1 X 1).
Table T(m,n) begins:
:   1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
:   2, 1, 3, 2, 4, 3, 5, 4, 6,  5, ...
:   3, 3, 1, 4, 4, 2, 5, 5, 3,  6, ...
:   4, 2, 4, 1, 5, 3, 5, 2, 6,  4, ...
:   5, 4, 4, 5, 1, 5, 5, 5, 6,  2, ...
:   6, 3, 2, 3, 5, 1, 5, 4, 3,  4, ...
:   7, 5, 5, 5, 5, 5, 1, 7, 6,  6, ...
:   8, 4, 5, 2, 5, 4, 7, 1, 7,  5, ...
:   9, 6, 3, 6, 6, 3, 6, 7, 1,  6, ...
:  10, 5, 6, 4, 2, 4, 6, 5, 6,  1, ...

Alois P. Heinz, Antidiagonals n = 1..350, flattened (using data from A219158)
Bertram Felgenhauer, Filling rectangles with integer-sided squares
Richard J. Kenyon, Tiling a rectangle with the fewest squares, Combin. Theory Ser. A 76 (1996), no. 2, 272-291.
M. Ortolano, M. Abrate, and L. Callegaro, On the synthesis of Quantum Hall Array Resistance Standards, arXiv preprint arXiv:1311.0756 [physics.ins-det], 2013.
Mark Walters, Rectangles as sums of squares, Discrete Math. 309 (2009), no. 9, 2913-2921.

Rows (or columns) m=1-10 give: A001477, A030451, A226576, A226577, A226578, A226579, A226580, A226581, A226582, A226583.

Cf. A219158, A219924, A226545, A338573.

(* *** Warning *** This empirical toy-program is based on the greedy algorithm. Its output was only verified for n+k <= 32. Any use outside this domain might produce only upper bounds instead of minimums. *)
nmax = 31; Clear[T];
Tmin[n_, k_] := Table[{1 + T[ c, k - c] + T[n - c, k], 1 + T[n, k - c] + T[n - c, c]}, {c, 1, k - 1}] // Flatten // Min;
Tmin2[n_, k_] := Module[{n1, n2, k1, k2}, 1 + T[n2, k1 + 1] + T[n - n1, k2] + T[n - n2, k1] + T[n1, k - k1] /. {Reduce[1 <= n1 <= n - 1 && 1 <= n2 <= n - 1 && 1 <= k1 <= k - 1 && 1 <= k2 <= k - 1 && n1 + 1 + n2 == n && k1 + 1 + k2 == k, Integers] // ToRules} // Min];
T[n_, n_] = 1;
T[n_, 1] := n;
T[1, k_] := k;
T[n_, k_ /; k > 1] /; n > k && Divisible[n, k] := n/k;
T[n_, k_ /; k > 1] /; n > k := T[n, k] = If[k >= 5 && n >= 6 && n - k <= 3, Min[Tmin[n, k], Tmin2[n, k], T[k, n - k] + 1], T[k, n - k] + 1];
T[n_, k_ /; k > 1] /; n < k := T[n, k] = T[k, n];
Table[T[n - k + 1, k], {n, 1, nmax}, {k, 1, n}] // Flatten (* Jean-François Alcover, Mar 11 2016, checked against first 496 terms of the b-file *)

A219158 Minimum number of integer-sided squares needed to tile an m X n rectangle.

Original entry on oeis.org

1, 2, 1, 3, 3, 1, 4, 2, 4, 1, 5, 4, 4, 5, 1, 6, 3, 2, 3, 5, 1, 7, 5, 5, 5, 5, 5, 1, 8, 4, 5, 2, 5, 4, 7, 1, 9, 6, 3, 6, 6, 3, 6, 7, 1, 10, 5, 6, 4, 2, 4, 6, 5, 6, 1, 11, 7, 6, 6, 6, 6, 6, 6, 7, 6, 1, 12, 6, 4, 3, 6, 2, 6, 3, 4, 5, 7, 1, 13, 8, 7, 7, 6, 6, 6, 6, 7, 7, 6, 7, 1

Offset: 1

David Radcliffe, Nov 12 2012

Triangular array read by rows. m=1,2,...,n; n=1,2,3,...

			T(6,5) = 5 because a 6 X 5 rectangle can be subdivided into two 3 X 3 squares and three 2 X 2 squares.
Triangle begins:
   1;
   2, 1;
   3, 3, 1;
   4, 2, 4, 1;
   5, 4, 4, 5, 1;
   6, 3, 2, 3, 5, 1;
   7, 5, 5, 5, 5, 5, 1;
   8, 4, 5, 2, 5, 4, 7, 1;
   9, 6, 3, 6, 6, 3, 6, 7, 1;
  10, 5, 6, 4, 2, 4, 6, 5, 6, 1;
  11, 7, 6, 6, 6, 6, 6, 6, 7, 6, 1;
  12, 6, 4, 3, 6, 2, 6, 3, 4, 5, 7, 1;
  13, 8, 7, 7, 6, 6, 6, 6, 7, 7, 6, 7, 1;
  14, 7, 7, 5, 7, 5, 2, 5, 7, 5, 7, 5, 7, 1;
  15, 9, 5, 7, 3, 4, 8, 8, 4, 3, 7, 5, 8, 7, 1;

Massimo Ortolano, Table of n, a(n) for n = 1..75466, rows 1..388 of triangle, flattened. Corrected version provided by Qizheng He.
Gary Antonick, Matt Enlow's Rectangle Division Puzzle, The New York Times, June 15, 2015.
Bertram Felgenhauer, Filling rectangles with integer-sided squares
Richard J. Kenyon, Tiling a rectangle with the fewest squares, Combin. Theory Ser. A 76 (1996), no. 2, 272-291.
M. Ortolano, M. Abrate, and L. Callegaro, On the synthesis of Quantum Hall Array Resistance Standards, arXiv preprint arXiv:1311.0756 [physics.ins-det], 2013.
Mark Walters, Rectangles as sums of squares, Discrete Math. 309 (2009), no. 9, 2913-2921.

First 19 terms agree with A049834.
Columns m=1..10 give A001477, A030451, A226576, A226577, A226578, A226579, A226580, A226581, A226582, A226583.
Cf. A113881, A338861.

A065423 Number of ordered length 2 compositions of n with at least one even summand.

Original entry on oeis.org

0, 0, 2, 1, 4, 2, 6, 3, 8, 4, 10, 5, 12, 6, 14, 7, 16, 8, 18, 9, 20, 10, 22, 11, 24, 12, 26, 13, 28, 14, 30, 15, 32, 16, 34, 17, 36, 18, 38, 19, 40, 20, 42, 21, 44, 22, 46, 23, 48, 24, 50, 25, 52, 26, 54, 27, 56, 28, 58, 29, 60, 30, 62, 31, 64, 32, 66, 33, 68, 34, 70, 35, 72, 36, 74

Offset: 1

Len Smiley, Nov 23 2001

			a(7) = 6 because we can write 7 = 1+6 = 2+5 = 3+4 = 4+3 = 5+2 = 6+1; a(8) = 3 because we can write 8 = 2+6 = 4+4 = 6+2.

Stefano Spezia, Table of n, a(n) for n = 1..10000
Mircea Merca and Emil Simion, n-Color Partitions into Distinct Parts as Sums over Partitions, Symmetry (2023) Vol. 15, Iss. 11.
Index entries for two-way infinite sequences
Index entries for linear recurrences with constant coefficients, signature (0,2,0,-1).

Cf. A026741, A097140 (first differences), A030451 (absolute first differences), A210530.

int a(int n){n--;return n>>(n&1);} // Mia Boudreau, Aug 27 2025

A065423 := proc(n)
    (3*n-4-(-1)^n*n)/4 ;
end proc:
seq(A065423(n),n=1..40) ; # R. J. Mathar, Jan 24 2022

LinearRecurrence[{0,2,0,-1},{0,0,2,1},100] (* Harvey P. Dale, May 14 2014 *)

PARI
```
a(n)=n-=2;if(n%2,n+1,n/2)
```

G.f.: x^3*(x+2)/(1-x^2)^2.
a(n) = floor((n-1)/2) + (n is odd)*floor((n-1)/2).
a(n+2) = Sum_{k=0..n} (gcd(n, k) mod 2). - Paul Barry, May 02 2005
a(n) = Sum_{i=1..n-1} (-1)^i (floor(i/2) + ((i+1) mod 2)). - Olivier Gérard, Jun 21 2007
a(n) = A210530(n,4)/2 for n>2. - Boris Putievskiy, Jan 29 2013
a(n) = (3*n-4-n*(-1)^n)/4. - Boris Putievskiy, Jan 29 2013, corrected Jan 24 2022
a(n) = A026741(n)-1. - Wesley Ivan Hurt, Jun 23 2013
a(n) = floor((n-1) / 2^mod(n-1,2)). - Mia Boudreau, Aug 27 2025
E.g.f.: 1 + (x - 1)*cosh(x) + (x - 2)*sinh(x)/2. - Stefano Spezia, Dec 17 2023

A123231 Row sums of A123230.

Original entry on oeis.org

1, 2, 1, 3, 2, 5, 3, 8, 5, 13, 8, 21, 13, 34, 21, 55, 34, 89, 55, 144, 89, 233, 144, 377, 233, 610, 377, 987, 610, 1597, 987, 2584, 1597, 4181, 2584, 6765, 4181, 10946, 6765, 17711, 10946, 28657, 17711, 46368, 28657, 75025, 46368, 121393, 75025, 196418

Offset: 1

Roger L. Bagula, Oct 06 2006

nonn

All terms are Fibonacci numbers A000045: a(2n-1) = Fibonacci(n), a(2n) = Fibonacci(n+2), a(2n-1) = a(2n+2). - Alexander Adamchuk, Oct 08 2006

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

Cf. A051792, A000045, A028242, A030451.

a:=[1,2,1,3];; for n in [5..50] do a[n]:=a[n-2]+a[n-4]; od; a; # Muniru A Asiru, Oct 12 2018

m:=50; R:=PowerSeriesRing(Integers(), m); Coefficients(R!(x*(1 + 2*x + x^3)/(1 - x^2 - x^4))); // G. C. Greubel, Oct 12 2018

seq(coeff(series(-x*(1+2*x+x^3)/(x^4+x^2-1),x,n+1), x, n), n = 1 .. 50); # Muniru A Asiru, Oct 12 2018

p[0, x] = 1; p[1, x] = x + 1; p[k_, x_] := p[k, x] = x*p[k - 1, x] + (-1)^(n + 1)p[k - 2, x]; Table[Sum[CoefficientList[p[n, x], x][[m]], {m, 1, n + 1}], {n, 0, 20}]
Rest[Flatten[Reverse/@Partition[Fibonacci[Range[30]],2,1]]] (* Harvey P. Dale, Mar 19 2013 *)

vector(50, n, fibonacci(3/4 -(-1)^(n+1)*3/4 +(n+1)/2)) \\ G. C. Greubel, Oct 12 2018

From Alexander Adamchuk, Oct 08 2006: (Start)
a(n) = Fibonacci(A028242(n+2)).
a(n) = Fibonacci(A030451(n+1)).
a(n) = Fibonacci(3/4 -(-1)^(n+1)*3/4 +(n+1)/2). (End)
a(n) = A053602(n+1) = A097594(n-5). - R. J. Mathar, Mar 08 2011
G.f. -x*(1+2*x+x^3) / ( -1+x^2+x^4 ). - R. J. Mathar, Mar 08 2011
a(n) = a(n-2) + a(n-4). - Muniru A Asiru, Oct 12 2018

More terms from Alexander Adamchuk, Oct 08 2006

cp's OEIS Frontend

A005044 Alcuin's sequence: expansion of x^3/((1-x^2)*(1-x^3)*(1-x^4)).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

PARI

Formula

Extensions

A028242 Follow n+1 by n. Also (essentially) Molien series of 2-dimensional quaternion group Q_8.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

GAP

Haskell

Magma

Maple

Mathematica

PARI

PARI

Sage

Formula

Extensions

A084964 Follow n+2 by n. Also solution of a(n+2)=a(n)+1, a(0)=2, a(1)=0.

Views

Author

Keywords

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

Formula

Extensions

A113881 Table of smallest number of squares, T(m,n), needed to tile an m X n rectangle, read by antidiagonals.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A219158 Minimum number of integer-sided squares needed to tile an m X n rectangle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A065423 Number of ordered length 2 compositions of n with at least one even summand.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

A005044 Alcuin's sequence: expansion of x^3/((1-x^2)(1-x^3)(1-x^4)).

A322544 a(n) is the reciprocal of the coefficient of x^n in the power series defined by ((1+2x)exp(x) + 3exp(-x) - 4)/ (4x^2).