A006527 -id:A006527 - cp's OEIS frontend

A116731 Number of permutations of length n which avoid the patterns 321, 2143, 3124; or avoid the patterns 132, 2314, 4312, etc.

1, 2, 5, 12, 25, 46, 77, 120, 177, 250, 341, 452, 585, 742, 925, 1136, 1377, 1650, 1957, 2300, 2681, 3102, 3565, 4072, 4625, 5226, 5877, 6580, 7337, 8150, 9021, 9952, 10945, 12002, 13125, 14316, 15577, 16910, 18317, 19800, 21361, 23002, 24725, 26532

Offset: 1

Lara Pudwell, Feb 26 2006

Row sums of triangle A130154. Also, binomial transform of [1, 1, 2, 2, 0, 0, 0, ...]. - Gary W. Adamson, Oct 23 2007
Conjecture: also counts the distinct pairs (flips, iterations) that a bubble sort program generates when sorting all permutations of 1..n. - Wouter Meeussen, Dec 13 2008
a(n) is the number of lattice points (x,y) in the closed region bounded by the parabolas y = x*(x - n) and y = x*(n - x). - Clark Kimberling, Jun 01 2013

Guo-Niu Han, Enumeration of Standard Puzzles, 2011. [Cached copy]
Guo-Niu Han, Enumeration of Standard Puzzles, arXiv:2006.14070 [math.CO], 2020.
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, arXiv:1302.2274 [math.CO], 2013.
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Integers: Electronic Journal of Combinatorial Number Theory, 15 (2015), #A16.
Lara Pudwell, Systematic Studies in Pattern Avoidance, 2005.
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1)

Cf. A006527, A130154.

Table[(n^3-3*n^2+5*n)/3,{n,100}] (* Vladimir Joseph Stephan Orlovsky, May 04 2011 *)

G.f.: (3*x^2 - 2*x + 1)*x/(x - 1)^4.
a(n) = (n^3 - 3*n^2 + 5*n)/3. - Franklin T. Adams-Watters, Sep 13 2006
a(n) = A006527(n-1) + 1. - Vladimir Joseph Stephan Orlovsky, May 04 2011
E.g.f.: exp(x)*(x + x^3/3). - Nikolaos Pantelidis, Feb 05 2023

More terms from Franklin T. Adams-Watters, Sep 13 2006

A026035 Expansion of x^2(2 - x + x^2) / ((1 + x)(1 - x)^4).

Original entry on oeis.org

2, 5, 12, 22, 38, 59, 88, 124, 170, 225, 292, 370, 462, 567, 688, 824, 978, 1149, 1340, 1550, 1782, 2035, 2312, 2612, 2938, 3289, 3668, 4074, 4510, 4975, 5472, 6000, 6562, 7157, 7788, 8454, 9158, 9899, 10680, 11500, 12362, 13265, 14212, 15202, 16238

Offset: 2

Clark Kimberling

Equals (d(n)-r(n))/2, where d = A006527 and r is the periodic sequence with fundamental period (0,1,0,1).
Consider any of the permutations of (1,2,3,...,n) as p(1),p(2),p(3),...,p(n). Then take the sum S of products formed from the permutation as S = p(1)*p(2) + p(2)*p(3) + p(3)*p(4) +... + p(n-1)*p(n). This sequence represents the minimum possible S. - Leroy Quet and Rainer Rosenthal, Jan 30 2005
From Dmitry Kamenetsky, Dec 15 2006: (Start)
This sequence is related to A101986, except here we take the minimum sum of products of successive pairs. Here is a method for generating such permutations. Start with two lists, the first has numbers 1 to n, while the second is empty.
Repeat the following operations until the first list is empty:
1. Move the largest number of the first list to the leftmost available position in the second list. The move operation removes the original number from the first list.
2. Move the largest number of the first list to the rightmost available position in the second list.
3. Move the smallest number of the first list to the leftmost available position in the second list.
4. Move the smallest number of the first list to the rightmost available position in the second list. For example when n=8, the permutation is 8, 1, 6, 3, 4, 5, 2, 7.
(End)

M. Benoumhani and M. Kolli, Finite topologies and partitions, JIS 13 (2010) # 10.3.5, t_{N0}(n,5) in theorem 5.
Index entries for linear recurrences with constant coefficients, signature (3,-2,-2,3,-1).

Cf. A101986.

[Binomial(n,3)+Floor(n^2/2): n in [2..50]]; // Bruno Berselli, Jun 08 2017

CoefficientList[Series[(2 - x + x^2)/((1 + x) (1 - x)^4), {x, 0, 45}], x] (* Robert G. Wilson v, Jan 29 2005 *)
LinearRecurrence[{3, -2, -2, 3, -1}, {2, 5, 12, 22, 38}, 50] (* Harvey P. Dale, May 31 2013 *)
Table[(2 n^3 + 4 n - 3 + 3 (-1)^n)/12, {n, 2, 50}] (* Bruno Berselli, Jun 08 2017 *)

a(n) = (2*n^3 + 4*n - 3 + 3*(-1)^n)/12. - Ralf Stephan, Jan 30 2005.
For n>6, a(n) = 3*a(n-1) - 2*a(n-2) - 2*a(n-3) + 3*a(n-4) - a(n-5), and a(2)=2, a(3)=5, a(4)=12, a(5)=22, a(6)=38. - Harvey P. Dale, May 31 2013
a(n) = binomial(n,3) + floor(n^2/2). - Bruno Berselli, Jun 08 2017

Corrected by Ralf Stephan, Jan 09 2005

A227177 n occurs n^2 - n + 1 times.

Original entry on oeis.org

0, 1, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7

Offset: 0

Antti Karttunen, Jul 03 2013

nonn

a(n) is the least integer k such that A006527(k) >= n, which implies that each n occurs A002061(n) times.

Antti Karttunen, Table of n, a(n) for n = 0..9951

Cf. A000196, A002061, A006527, A227179, A227181, A227147.

Flatten[Map[ConstantArray[#,(#-2) (#-1)+1]-1&,Range[7]]] (* Peter J. C. Moses, Jul 14 2013 *)
Flatten[Table[#,{#^2-#+1}]&/@Range[0,7]] (* Harvey P. Dale, Sep 25 2013 *)

vec(N)=concat(vector(N, i, vector(i^2-i+1, j, i))) \\ Jinyuan Wang, Dec 01 2018

from sympy import integer_nthroot
def A227177(n): return (m:=integer_nthroot(k:=3*n,3)[0])+(k>m*(m**2+2)) # Chai Wah Wu, Nov 07 2024

a(k + (j^3-j^2+5*j)/3) = j for all j>=0, k=0..(j^2-j). - Jinyuan Wang, Nov 24 2018

a(n) = m+1 if 3n>m*(m^2+2) and a(n) = m otherwise where m=floor((3n)^(1/3)). - Chai Wah Wu, Nov 07 2024

A088003 Take the list t(n,0) = {1,...,n}; denote by t(n,j) this list after rotating to left (or right) by j positions. Calculate inner product of t(n,0) and t(n,j) and denote the value by s(n,j). Compute this inner product for all j = 1..n and choose the smallest. This is a(n).

Original entry on oeis.org

1, 4, 11, 22, 40, 64, 98, 140, 195, 260, 341, 434, 546, 672, 820, 984, 1173, 1380, 1615, 1870, 2156, 2464, 2806, 3172, 3575, 4004, 4473, 4970, 5510, 6080, 6696, 7344, 8041, 8772, 9555, 10374, 11248, 12160, 13130, 14140, 15211, 16324, 17501, 18722, 20010

Offset: 1

Labos Elemer, Oct 14 2003

If the largest were chosen rather than the smallest, then A000330(n), the square pyramidal numbers, would be obtained. Also, if the inner product of t with 1-rotated-t is calculated, then A006527(n) is produced.
From Jonathan Halabi, Dec 25 2017, on behalf of Maya Nicklas: (Start)
a(n) is the number of squares (of any size) that occur in a skewed n X n chessboard, having n rows of n squares, each offset by one square from the row above. For instance, a(4) is the number of squares in this diagram:
XXXX
.XXXX
..XXXX
...XXXX
which is 22.
(End)
It seems that if we connect the top row of this skewed board with its bottom row (in the same skewed way), i.e., make the board toroidal, and count squares, we will get A128624. - Andrey Zabolotskiy, Dec 25 2017

			For n=6: t(6,0) = {1,2,3,4,5,6}, t(6,3) = {4,5,6,1,2,3};
compute scalar products for all rotations:
{76,67,64,67,76,91} of which the smallest is 64, so a(6)=64.

Index entries for linear recurrences with constant coefficients, signature (2,1,-4,1,2,-1).

Cf. A000330, A006527, A094414.

t0[x_] := Table[w, {w, 1, x}]; jr[x_, j_] := RotateRight[t0[x], j]; Table[Min[Table[Apply[Plus, t0[g]*jr[g, i]], {i, 1, g}]], {g, 1, up}]

a(n) = Min{y; y=t(n, 0)*t(n, x)=s(n, x); for x=1..n}.
a(n) = n*(2*n*(5*n+12)-3*(-1)^n+11)/48.
G.f.: x*(1+2*x+2*x^2)/((1+x)^2*(1-x)^4). - Bruno Berselli, Dec 01 2010
For n >= 1, a(n) = A000330(n) - A034828(n). - Luce ETIENNE, Aug 11 2014
a(n) = Sum_{i=0..floor(n/2)} (n-i)*(n-2*i). For n=7, a(7) = 7*7 + 6*5 + 5*3 + 4*1 = 98. - Bruno Berselli, Oct 26 2015

Edited by Bruno Berselli, Dec 01 2010

A107735 Array read by antidiagonals: A(n,k) = Verlinde numbers for quasiparabolic bundles (n >= 3, k >= 0).

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 5, 3, 1, 1, 4, 13, 4, 1, 1, 21, 11, 25, 5, 1, 1, 8, 141, 24, 41, 6, 1, 1, 85, 43, 521, 45, 61, 7, 1, 1, 16, 1485, 160, 1401, 76, 85, 8, 1, 1, 341, 171, 10569, 461, 3101, 119, 113, 9, 1, 1, 32, 15565, 1088, 46649, 1112, 6021, 176, 145, 10

Offset: 3

N. J. A. Sloane, Jun 10 2005

			Array begins:
1 1 1 1 1 1 1 1 1 1 ...
1 2 3 4 5 6 7 8 9 10 ...
1 5 13 25 41 61 85 113 ...
1 4 11 24 45 76 119 ...
1 21 141 521 1401 3101 ...

S. Mukai, An Introduction to Invariants and Moduli, Cambridge, 2003; see p. 483.

Rows: A001844, A006527, A107731; columns: A107732-A107734.

Digits:=100;
A:=proc(n,k) local kp;
if (n mod 2) = 1 then
round( (1/(2*k+1))*add( (-1)^(n*j)*sin( (2*j+1)*Pi/(4*k+2) )^(-n+2), j=0..2*k))
else kp:=k/2;
round( (1/(2*kp+1))*add( (-1)^(n*j)*sin( (2*j+1)*Pi/(4*kp+2) )^(-n+2), j=0..2*kp)); fi;
end;

t[n_, k_] := With[{kp = If[!Divisible[n, 2], k, k/2]}, Round[1/(2*kp+1)*Sum[(-1)^(n*j)*Sin[(2*j+1)*Pi/(4*kp+2)]^(-n+2), {j, 0, 2*kp}]]]; Table[t[n-k, k], {n, 3, 13}, {k, 0, n-3}] // Flatten (* Jean-François Alcover, Jan 14 2014, after Michel Marcus *)

t(n, k) = {if (! (n % 2), k = k/2); return (round((1/(2*k+1))*sum(j=0, 2*k,(-1)^(n*j)*sin((2*j+1)*Pi/(4*k+2))^(-n+2))));} \\ Michel Marcus, Apr 20 2013

The reference gives an explicit formula. For odd n this is
A(n,k) = (1/(2*k+1))*sum( (-1)^(n*j)*sin( (2*j+1)*Pi/(4*k+2) )^(-n+2), j=0..2*k). - N. J. A. Sloane, Apr 20 2013.
For even n use the same formula but replace k by k/2. - Michel Marcus, Apr 20 2013

A217873 a(n) = 4n(n^2 + 2)/3.

Original entry on oeis.org

0, 4, 16, 44, 96, 180, 304, 476, 704, 996, 1360, 1804, 2336, 2964, 3696, 4540, 5504, 6596, 7824, 9196, 10720, 12404, 14256, 16284, 18496, 20900, 23504, 26316, 29344, 32596, 36080, 39804, 43776, 48004, 52496, 57260, 62304, 67636, 73264, 79196, 85440, 92004

Offset: 0

M. F. Hasler, Oct 13 2012

Occurs as 4th column in the table A142978 of figurate numbers for n-dimensional cross polytope.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (4,-6,4,-1).

Cf. A006527, A008412, A008590, A022144, A082138, A112087, A142978, A174794, A292022.

[4*n*(n^2+2)/3: n in [0..45]]; // Vincenzo Librandi, Nov 08 2012

Table[4n(n^2 + 2)/3, {n, 0, 39}] (* Alonso del Arte, Oct 22 2012 *)
LinearRecurrence[{4,-6,4,-1},{0,4,16,44},50] (* Harvey P. Dale, Mar 16 2015 *)

makelist(4*n*(n^2+2)/3, n, 0, 41); /* Martin Ettl, Oct 15 2012 */

PARI
```
a(n)=(n^2+2)*n/3*4
```

a(n) = 4*A006527(n).
From Peter Luschny, Oct 14 2012: (Start)
a(n) = A008412(n)/2.
a(n) = A174794(n+1) - 1.
First differences are in A112087.
Second differences are in A008590 and A022144.
Binomial transformation of (a(n), n > 0) is A082138.  (End)
G.f.: 4*x*(1 + x^2)/(x - 1)^4. - R. J. Mathar, Oct 15 2012
a(n) = 4*a(n-1) - 6*a(n-2) + 4*a(n-3) - a(n-4), a(0)=0, a(1)=4, a(2)=16, a(3)=44. - Harvey P. Dale, Mar 16 2015
From Elmo R. Oliveira, Aug 09 2025: (Start)
E.g.f.: 4*exp(x)*x*(3 + 3*x + x^2)/3.
a(n) = A292022(n)/3. (End)

A227179 After initial 0, integers from 0 to n(n-1) followed by integers from 0 to n(n+1) and so on.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jul 03 2013

nonn

Antti Karttunen, Table of n, a(n) for n = 0..9951

Cf. A002378, A006527, A227177, A227181, A227182.

Flatten[(Range[(#-2) (#-1)+1]-1&)[Range[7]]] (* Peter J. C. Moses, Jul 11 2013 *)

from sympy import integer_nthroot
def A227179(n): return n-1-(f:=lambda x:x*(x**2+2))((m:=integer_nthroot(k:=3*n,3)[0])-(k<=f(m)))//3 # Chai Wah Wu, Nov 07 2024

(define (A227179 n) (- n (+ 1 (A006527 (- (A227177 n) 1)))))

a(n) = n - (1 + A006527(A227177(n)-1)).

A054620 Number of ways to color vertices of a pentagon using <= n colors, allowing only rotations.

Original entry on oeis.org

0, 1, 8, 51, 208, 629, 1560, 3367, 6560, 11817, 20008, 32219, 49776, 74269, 107576, 151887, 209728, 283985, 377928, 495235, 640016, 816837, 1030744, 1287287, 1592544, 1953145, 2376296, 2869803, 3442096, 4102253, 4860024

Offset: 0

N. J. A. Sloane, Apr 16 2000

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Cf. A060446, A006527, A006528, A006565, A054621, ..., A075195.

[(n^5+4*n)/5: n in [0..40]]; // Vincenzo Librandi, Aug 31 2011

a(n) = (n^5+4*n)/5 = n*(n^2-2*n+2)*(n^2+2*n+2)/5.
G.f.: x*(1+2*x+18*x^2+2*x^3+x^4) / (x-1)^6 . - R. J. Mathar, Aug 30 2011
a(n) = -a(-n). - Bruno Berselli, Aug 31 2011

A084570 Partial sums of A084263.

Original entry on oeis.org

1, 2, 6, 12, 23, 38, 60, 88, 125, 170, 226, 292, 371, 462, 568, 688, 825, 978, 1150, 1340, 1551, 1782, 2036, 2312, 2613, 2938, 3290, 3668, 4075, 4510, 4976, 5472, 6001, 6562, 7158, 7788, 8455, 9158, 9900, 10680, 11501, 12362, 13266, 14212, 15203, 16238

Offset: 0

Paul Barry, May 31 2003

Partial sums give A084569.

Index entries for linear recurrences with constant coefficients, signature (3,-2,-2,3,-1).

[(-1)^n/4 + (2*n^3+6*n^2+10*n+ 9)/12: n in [0..50]]; // Vincenzo Librandi, Apr 04 2015

LinearRecurrence[{3,-2,-2,3,-1},{1,2,6,12,23},50] (* Harvey P. Dale, Nov 12 2014 *)
CoefficientList[Series[(1 - x + 2 x^2) / ((1 + x) (1 - x)^4), {x, 0, 50}], x] (* Vincenzo Librandi, Apr 04 2015 *)

a(n) = sum(j=0, n, sum(i=0, j, (i+(-1)^i)));
vector(50, n, n--; a(n)) \\ Michel Marcus, Apr 04 2015

a(n) = (-1)^n/4 + (2n^3 + 6n^2 + 10n + 9)/12.
a(n) = Sum_{j=0..n} (Sum_{i=0..j} (i + (-1)^i)).
From Arun Giridhar, Apr 03 2015: (Start)
a(n) = ceiling(A006527(n+1) / 2).
a(n) = ceiling((n^3 + 3n^2 + 5n + 3)/6).
(End)
G.f.: (1-x+2*x^2)/((1+x)*(1-x)^4). - Vincenzo Librandi, Apr 04 2015

A121306 Array read by antidiagonals: a(m,n) = a(m,n-1)+a(m-1,n) but with initialization values a(0,0)=0, a(m>=1,0)=1, a(0,1)=1, a(0,n>1)=0.

Original entry on oeis.org

2, 2, 3, 2, 5, 4, 2, 7, 9, 5, 2, 9, 16, 14, 6, 2, 11, 25, 30, 20, 7, 2, 13, 36, 55, 50, 27, 8, 2, 15, 49, 91, 105, 77, 35, 9, 2, 17, 64, 140, 196, 182, 112, 44, 10, 19, 81, 204, 336, 378, 294, 156, 54, 100, 285, 540, 714, 672, 450, 210, 385, 825, 1254, 1386, 1122

Offset: 0

Thomas Wieder, Aug 04 2006, Aug 06 2006

For a(1,0)=1, a(m>1,0)=0 and a(0,n>=0)=0 one gets Pascal's triangle A007318.

			Array begins
2 2 2 2 2 2 2 2 2 ...
3 5 7 9 11 13 15 17 19 ...
4 9 16 25 36 49 64 81 100 ...
5 14 30 55 91 140 204 285 385 ...
6 20 50 105 196 336 540 825 1210 ...
7 27 77 182 378 714 1254 2079 3289 ...

The first nine rows are: A006527, A005408, A000290, A000330, A002415, A005585, A040977, A050486, A053347.
The initial columns are: A000027, A000096, A005581, A005582, A005583, A005584.
Cf. A119800, A007318, A006527, A005408, A000290, A000330, A002415, A005585, A040977, A050486, A053347, A000027, A000096, A005581, A005582, A005583, A005584.

=Z(-1)S+ZS(-1). The very first row (not included into the table) contains the initialization values: a(0,1)=1, a(0,n>=2)=0. The very first column (not included into the table) contains the initialization values: a(m>=1,0)=1. The value a(0,0)=0 does not enter into the table.

a(m,n) = a(m,n-1)+a(m-1,n), a(0,0)=0, a(m>=1,0)=1, a(0,1)=1, a(0,n>1)=0.

Edited by N. J. A. Sloane, Sep 15 2006

cp's OEIS Frontend

A116731 Number of permutations of length n which avoid the patterns 321, 2143, 3124; or avoid the patterns 132, 2314, 4312, etc.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A026035 Expansion of x^2*(2 - x + x^2) / ((1 + x)*(1 - x)^4).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Formula

Extensions

A227177 n occurs n^2 - n + 1 times.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A088003 Take the list t(n,0) = {1,...,n}; denote by t(n,j) this list after rotating to left (or right) by j positions. Calculate inner product of t(n,0) and t(n,j) and denote the value by s(n,j). Compute this inner product for all j = 1..n and choose the smallest. This is a(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A107735 Array read by antidiagonals: A(n,k) = Verlinde numbers for quasiparabolic bundles (n >= 3, k >= 0).

Views

Author

Keywords

Examples

References

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A217873 a(n) = 4*n*(n^2 + 2)/3.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

Maxima

PARI

Formula

A227179 After initial 0, integers from 0 to n(n-1) followed by integers from 0 to n(n+1) and so on.

Views

Author

Keywords

Links

Crossrefs

Programs

A026035 Expansion of x^2(2 - x + x^2) / ((1 + x)(1 - x)^4).

A217873 a(n) = 4n(n^2 + 2)/3.