Christian Bean - cp's OEIS frontend

A277086 Irregular triangle read by rows: T(n,k) = number of size k subsets of S_n with respect to the symmetries of the square.

1, 1, 1, 1, 1, 1, 1, 1, 2, 5, 5, 5, 2, 1, 1, 7, 56, 317, 1524, 5733, 17728, 44767, 94427, 166786, 249624, 316950, 343424, 316950, 249624, 166786, 94427, 44767, 17728, 5733, 1524, 317, 56, 7, 1, 1, 23, 1012, 36125, 1035496, 23878229, 456936220, 7437730463

Offset: 0

Christian Bean, Sep 28 2016

A permutation, p, can be thought of as a set of points (i, p(i)). In this viewpoint it is natural to consider the symmetries of the square.

T(n,k) is the number of symmetry classes of subsets of size k from S_n.

			Triangle starts:
1, 1;
1, 1;
1, 1, 1;
1, 2, 5, 5, 5, 2, 1;

Christian Bean, Émile Nadeau, Jay Pantone, and Henning Ulfarsson, Permutations avoiding bipartite partially ordered patterns have a regular insertion encoding, The Electronic Journal of Combinatorics, Volume 31, Issue 3 (2024); arXiv preprint, arXiv:2312.07716 [math.CO], 2023.

Rows lengths give A038507.

Cf. A277080, A277081, A277083, A277085.

T(n,k) = 1/8 * (C(n,k) + 2*A277080(n,k) + 2*A277081(n,k) + 2*A277085(n,k) + A277083(n,k)).

A277083 Irregular triangle read by rows: T(n,k) = number of size k subsets of S_n that remain unchanged by a rotation of 180 degrees.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 2, 3, 4, 3, 2, 1, 1, 8, 36, 120, 322, 728, 1428, 2472, 3823, 5328, 6728, 7728, 8092, 7728, 6728, 5328, 3823, 2472, 1428, 728, 322, 120, 36, 8, 1, 1, 8, 84, 504, 3178, 15512, 74788, 311144, 1252819, 4577328, 16087512, 52691408, 165911284

Offset: 0

Christian Bean, Sep 28 2016

A permutation, p, can be thought of as a set of points (i, p(i)). If you plot all the points and rotate the picture by 180 degrees then you get a permutation back.

T(n,k) is the number of size k subsets of S_n that remain unchanged by a rotation of 180 degrees.

			For n = 3 and k = 3, the subsets unchanged by rotating 180 degrees are {213,132,123}, {231,312,123}, {321,132,213} and {321,231,312} so T(3,3) = 4.
Triangle starts:
1, 1;
1, 1;
1, 2, 1;
1, 2, 3, 4, 3, 2, 1;

Row lengths give A038507.

Cf. A037223.

T(n,k) = Sum_( binomial( n! - R(n), i ) * binomial( R(n), k-2*i ) for i in [0..floor(k/2)] ) where R(n) = A037223(n).

A277081 Irregular triangle read by rows: T(n,k) = number of size k subsets of S_n that remain unchanged under the operation of replacing a permutation with its inverse.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 4, 7, 8, 7, 4, 1, 1, 10, 52, 190, 546, 1302, 2660, 4754, 7535, 10692, 13672, 15820, 16604, 15820, 13672, 10692, 7535, 4754, 2660, 1302, 546, 190, 52, 10, 1, 1, 26, 372, 3822, 31306, 216086, 1300420, 6981650, 33992275, 151945820

Offset: 0

Christian Bean, Sep 28 2016

T(n,k) is the number of size k subsets of S_n that remain unchanged under the operation of replacing a permutation with its inverse.

			For n = 3 and k = 3 the subsets unchanged by inverse are {213,132,123}, {321,132,123}, {321,213,123}, {231,312,123}, {321,132,213}, {132,312,231},{213,312,231}, {321,231,312} hence T(3,3) = 8. (Here we are using the one-line notation for permutations, not the product of cycles form.)
Triangle starts:
1, 1;
1, 1;
1, 2, 1;
1, 4, 7, 8, 7, 4, 1;

Andrew Howroyd, Table of n, a(n) for n = 0..880 (rows 0..6)

Row lengths give A038507.

Cf. A000085.

\\ here b(n) is A000085(n).
b(n)={sum(k=0, n\2, n!/((n-2*k)!*2^k*k!))}
Row(n)={my(t=b(n)); vector(n!+1, k, k--; sum(i=0, k\2, binomial((n!-t)/2, i)*binomial(t, k-2*i)))}
{ for(n=0, 4, print(Row(n))) } \\ Andrew Howroyd, Feb 03 2021

T(n,k) = Sum( C((n! - I(n))/2, i)*C(I(n), k - 2*i) for i in [0..floor(k/2)]) where I(n) = A000085(n).

A277085 Irregular triangle read by rows: T(n,k) = number of size k subsets of S_n that remain unchanged by a rotation of 90 degrees.

Original entry on oeis.org

1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 2, 4, 6, 10, 14, 20, 26, 31, 36, 40, 44, 44, 44, 40, 36, 31, 26, 20, 14, 10, 6, 4, 2, 1, 1, 2, 4, 6, 34, 62, 116, 170, 547, 924, 1624, 2324, 5572, 8820, 14616, 20412, 40509, 60606, 95004, 129402, 224406, 319410

Offset: 0

Christian Bean, Sep 28 2016

A permutation, p, can be thought of as a set of points (i, p(i)). If you plot all the points and rotate the picture by 90 degrees then you get a permutation back.

T(n,k) is the number of size k subsets that remain unchanged by a rotation of 90 degrees.

			For n = 4 and k = 2, the subsets unchanged by a 90-degree rotation are {4321,1234}, {4231,1324}, {3412,2143} and {3142,2413}. Hence T(4,2) = 4.
Triangle starts:
1, 1;
1, 1;
1, 0, 1;
1, 0, 1, 0, 1, 0, 1;

Row lengths give A038507.

Cf. A037223, A037224.

T(n,k) = Sum_( C( R(n) - T(n), i ) * Sum_(C(n! - R(n), j) * C(T(n), k - 4*i - 2*j) for j in [0..floor((k-4*i)/2)] for i in [0..floor(k/4)] ) where R(n) = A037223(n) and T(n) = A037224(n).

A277080 Irregular triangle read by rows: T(n,k) = number of size k subsets of S_n that remain unchanged by reverse.

Original entry on oeis.org

1, 1, 1, 1, 1, 0, 1, 1, 0, 3, 0, 3, 0, 1, 1, 0, 12, 0, 66, 0, 220, 0, 495, 0, 792, 0, 924, 0, 792, 0, 495, 0, 220, 0, 66, 0, 12, 0, 1, 1, 0, 60, 0, 1770, 0, 34220, 0, 487635, 0, 5461512, 0, 50063860, 0, 386206920, 0, 2558620845, 0, 14783142660, 0, 75394027566

Offset: 0

Christian Bean, Sep 28 2016

The reverse of a permutation is the reverse in one line notation. For example the reverse of 43521 is 12534.

T(n,k) is the number of size k bases of S_n which remain unchanged by reverse.

			For n = 4 and k = 2 the subsets that remain unchanged by reverse are {4321, 1234}, {1243, 3421}, {4231, 1324}, {1342, 2431}, {1423, 3241}, {1432, 2341}, {2134, 4312}, {3412, 2143}, {2314, 4132}, {3142, 2413}, {4213, 3124} and {4123, 3214} so T(4,2) = 12.
For n = 3 and k = 4 the subsets that remain unchanged by reverse are {231, 321, 132, 123}, {321, 213, 312, 123} and {231, 132, 312, 213} so T(3,4) = 3.
The triangle starts:
1, 1;
1, 1;
1, 0, 1;
1, 0, 3, 0, 3, 0, 1;

Row lengths give A038507.

def T(n,k):
    if k % 2 == 1:
        return 0
    return binomial( factorial(n)/2, k/2 )

T(n,k) = C(n!/2, k/2) if k is even and T(n,k) = 0 if k is odd.

A262370 Triangle read by rows in which T(n,k) is the number of permutations avoiding 132 of length n with an independent set of size k in its coregraph.

Original entry on oeis.org

1, 1, 1, 1, 1, 4, 1, 10, 3, 1, 20, 20, 1, 1, 35, 77, 19, 1, 56, 224, 139, 9, 1, 84, 546, 656, 141, 2, 1, 120, 1176, 2375, 1104, 86, 1, 165, 2310, 7172, 5937, 1181, 30, 1, 220, 4224, 18953, 24959, 9594, 830, 5, 1, 286, 7293, 45188, 87893, 56358, 10613, 380, 1, 364, 12012, 99242, 270452, 264012, 88472, 8240, 105, 1, 455, 19019, 203775, 747877, 1044085, 554395, 100339, 4480, 14

Offset: 1

Christian Bean, Oct 09 2015

If we consider constructing permutations avoiding 132 in terms of independent sets of coregraphs then this is the number of permutations avoiding 132 of length n using an independent set of size k. If we consider the staircase grid formed by the left-to-right minima, every rectangular region of boxes is increasing. Furthermore, for permutations avoiding 132, the presence of points in a box may constrain other boxes to be empty. To capture these constraints we create the coregraph by placing a vertex for every box and an edge between boxes that exclude one another. Therefore every permutation avoiding 132 can be uniquely built by a weighted independent set in the coregraph.

			Triangle starts:
  1;
  1;
  1,  1;
  1,  4;
  1, 10,   3;
  1, 20,  20,   1;
  1, 35,  77,  19;
  1, 56, 224, 139, 9;
  ...

C. Bean, M. Tannock and H. Ulfarsson, Pattern avoiding permutations and independent sets in graphs, arXiv:1512.08155 [math.CO], 2015.

m = 14; Clear[b]; b[, 0] = 1; b[0, ] = 0; b[1, 1] = 1; b[n_, k_] /; (k > 2n-1) = 0; F = Sum[b[n, k]*x^n*y^k, {n, 0, m}, {k, 0, m}]; s = Series[F - (1+x*F + x*y*(F^2/(1-y*(F-1)))), {x, 0, m-1}, {y, 0, m-1}]; eq = And @@ Thread[Flatten[CoefficientList[s, {x, y}]] == 0]; sol = NSolve[eq]; F = F /. sol[[1]] /. y -> x*(y/(1-x)); s = Series[F, {x, 0, m}, {y, 0, m}]; DeleteCases[#, 0]& /@ CoefficientList[s, {x, y}] // Floor // Flatten (* Jean-François Alcover, Dec 31 2015 *)

a(n,k) = Sum_{j=0..n} I(j,k) * C(n-j-1, k-1) for k > 0 and a(n,0) = 1
where I(n,k) = Sum_{j=0..n-1} C(n, k-j) * C(n, j+1) * C(n-1+j, n-1) / n = A278390(n,k).
G.f: Let F = F(x,y) be the generating function satisfying F = 1 + x*F +x*y*F^2/(1-y*(F-1)); then the generating function for this sequence is F(x,x*y/(1-x)).

A260696 The number of length-n permutations avoiding the patterns 1234, 1324, 1432 and 3214.

Original entry on oeis.org

1, 1, 2, 6, 20, 62, 172, 471, 1337, 3846, 11030, 31442, 89470, 254934, 727203, 2074435, 5915652, 16866988, 48093810, 137141828, 391072846, 1115164897, 3179915535, 9067592160, 25856510664, 73730732368, 210245631360, 599521974384, 1709555338705, 4874850377793, 13900789573274, 39638539791222

Offset: 0

Christian Bean, Nov 26 2015

nonn

C. Bean, M. Tannock and H. Ulfarsson, Pattern avoiding permutations and independent sets in graphs, arXiv:1512.08155 [math.CO], 2015.
Index entries for linear recurrences with constant coefficients, signature (2,1,2,4,8,0,-15,-14,-7).

Cf. A263790.

I:=[1,1,2,6,20,62,172,471,1337]; [n le 9 select I[n] else 2*Self(n-1)+Self(n-2)+2*Self(n-3)+4*Self(n-4)+8*Self(n-5)-15*Self(n-7)-14*Self(n-8)-7*Self(n-9): n in [1..35]]; // Vincenzo Librandi, Dec 31 2015

CoefficientList[Series[-(x^3 + x^2 + x - 1)/(7*x^9 + 14*x^8 + 15*x^7 - 8*x^5 - 4*x^4 - 2*x^3 - x^2 - 2*x + 1), {x, 0, 30}], x] (* Wesley Ivan Hurt, Dec 29 2015 *)
LinearRecurrence[{2, 1, 2, 4, 8, 0, -15, -14, -7}, {1, 1, 2, 6, 20, 62, 172, 471, 1337}, 40 ] (* Vincenzo Librandi, Dec 31 2015 *)

G.f.: -(x^3 + x^2 + x - 1)/(7*x^9 + 14*x^8 + 15*x^7 - 8*x^5 - 4*x^4 - 2*x^3 - x^2 - 2*x + 1).

a(n) = 2*a(n-1)+a(n-2)+2*a(n-3)+4*a(n-4)+8*a(n-5)-15*a(n-7)-14*a(n-8)-7*a(n-9) for n>8. - Wesley Ivan Hurt, Dec 29 2015

A263790 The number of length-n permutations avoiding the patterns 1234, 1324 and 2143.

Original entry on oeis.org

1, 1, 2, 6, 21, 75, 268, 958, 3425, 12245, 43778, 156514, 559565, 2000543, 7152292, 25570698, 91419729, 326841561, 1168515890, 4177649198, 14935828405, 53398205443, 190907947468, 682529386598, 2440162233937, 8724007852045, 31189857766034, 111509210441322, 398664979703373

Offset: 0

Christian Bean, Nov 23 2015

C. Bean, M. Tannock and H. Ulfarsson, Pattern avoiding permutations and independent sets in graphs, arXiv:1512.08155 [math.CO], 2015, eq. (4).
D. Callan, T. Mansour, Enumeration of small Wilf classes avoiding 1324 and two other 4-letter patterns, arXiv:1705.00933 [math.CO] (2017), Table 2 No 181.
Index entries for linear recurrences with constant coefficients, signature (4,-2,2,-1).

I:=[1,1,2,6]; [n le 4 select I[n] else 4*Self(n-1)-2*Self(n-2)+2*Self(n-3)-Self(n-4): n in [1..40]]; // Vincenzo Librandi, Jan 01 2016

t1:=(1-3*x-2*x^3)/(1-4*x+2*x^2-2*x^3+x^4);
series(t1,x,40);
seriestolist(%); # N. J. A. Sloane, Nov 09 2016

LinearRecurrence[{4, -2, 2, -1}, {1, 1, 2, 6}, 30] (* Jean-François Alcover, Dec 31 2015 *)
CoefficientList[Series[(2 x^3 + 3 x - 1)/(-x^4 + 2*x^3 - 2 x^2 + 4 x - 1), {x, 0, 35}], x] (* Vincenzo Librandi, Jan 01 2016 *)

Vec((2*x^3 + 3*x - 1)/(-x^4 + 2*x^3 - 2*x^2 + 4*x - 1) + O(x^50)) \\ Michel Marcus, Nov 23 2015

G.f.: (2*x^3 + 3*x - 1)/(-x^4 + 2*x^3 - 2*x^2 + 4*x - 1).

A249562 Number of length n permutations avoiding (123,{2},{}) and (123,{},{1}).

Original entry on oeis.org

1, 1, 2, 5, 14, 43, 143, 509, 1921, 7631, 31725, 137412, 617822, 2874819, 13809305, 68331089, 347657464, 1815839759, 9722708061, 53301771604, 298854490602, 1712023130016, 10011533550216, 59714205975048, 363008132101658, 2247599137530241, 14164805684388087, 90810818671081267, 591921142070249872

Offset: 0

Christian Bean, Nov 01 2014

nonn

(123,{2},{}) is a vincular pattern. It has underlying classical pattern 123 and the extra requirement that the 2 and the 3 are adjacent in the permutation.

(123,{},{1}) is a co-vincular pattern. It has underlying classical pattern 123 and the extra requirement that the 1 and 2 are exactly one apart in the permutation.

Christian Bean, Sage code
Christian Bean, A Claesson, H Ulfarsson, Simultaneous Avoidance of a Vincular and a Covincular Pattern of Length 3, arXiv preprint arXiv:1512.03226 [math.CO], 2015.
Zhicong Lin, Sherry H. F. Yan, Vincular patterns in inversion sequences, Applied Mathematics and Computation (2020), Vol. 364, 124672.

Cf. A249560, A249561, A249563.

If x appears after x-1 in the permutation then we say that x is a ceiling point.
if i = 1: aup(n,k,i,l) = sum( abar(n,k,i,l) for m in [0..k] )
otherwise: aup(n,k,i,l) = sum( abar(n-1,k,1,m) for m in [l..k] ) + sum( sum( adown(n-1,k,j,m) for m in [i..k]) for j in [1..i-1] )
abar(n,k,i,l) = sum( a(n-1,k-1,j,l-1) for j in [1..k-1] )
adown(n,k,i,l) = sum( aup(n-1,k,j,l) + adown(n-1,k,j,l) for j in [i..k] )
a(n,k,i,l) = aup(n,k,i,l) + adown(n,k,i,l) + abar(n,k,i,l)
where n is the length, k is the number of left to right minima, i is the position of the maximum, l is the position of the first ceiling point
aup implies that max is a ceiling point, abar implies that max is a left to right minimum and adown implies max is neither.
Initial conditions: if i > l or k > n or i > k or l > k then aup(n,k,i,l) = adown(n,k,i,l) = 0, if i < l or l <= 0 then aup(n,k,i,l) = 0, if n - k = 1 then a(n,k,i,l) = 1, if i does not equal 1 the abar(n,k,i,l) = 0, abar(n,n,1,0) = 1.
a(n) = sum( sum( sum( a(n,k,j,m) for m in [0..k] ) for j in [1..k] ) for k in [1..n] )

A249561 Number of length n permutations avoiding (123,{1},{}) and (231,{},{2}).

Original entry on oeis.org

1, 1, 2, 4, 9, 22, 57, 155, 440, 1299, 3977, 12596, 41181, 138711, 480548, 1709714, 6238685, 23319998, 89199763, 348799322, 1393087403, 5678298218, 23603135064, 99984420371, 431347901729, 1894074165622, 8460557754681, 38424506440883, 177342850025592, 831413025268569, 3957592646327463

Offset: 0

Christian Bean, Nov 01 2014

nonn

(123,{1},{}) is a vincular pattern. It has underlying classical pattern 123 and the extra requirement that the 1 and the 2 are adjacent in the permutation.
(231,{},{2}) is a co-vincular pattern. It has underlying classical pattern 231 and the extra requirement that the 2 and 3 are exactly one apart in the permutation.
These can be counted recursively in the following way. If you let n be the length, r be the number of left to right minima and i be the position of the leftmost point with respect to the left to right minima then we get that
a(n,r,1) = a(n-1,r,r) + a(n-1,r,1) + a(n-1,r-1,r-1)
a(n,r,r) = sum( a(n-1,r,j) for j in [1..r] )
a(n,r,i) = a(n-1,r,r) + sum( a(n-1,r,j) for j in [1..i] )
which with the initial conditions that n must be greater than or equal to r and r greater than or equal to i and a(n,1,1) = 1.
Then a(n) = sum( sum( a(n,r,i) for i in [1..r] ) for r in [1..n] ).

Alois P. Heinz, Table of n, a(n) for n = 0..400
Christian Bean, Sage Code
Christian Bean, A Claesson, H Ulfarsson, Simultaneous Avoidance of a Vincular and a Covincular Pattern of Length 3, arXiv preprint arXiv:1512.03226, 2015
Yan X Zhang, Four Variations on Graded Posets, arXiv preprint arXiv:1508.00318 [math.CO], 2015. See Fig. 8.

Cf. A249560, A249562, A249563.

a[n_, r_, i_] := a[n, r, i] = Which[nJean-François Alcover, Dec 02 2014, translated and adapted from Sage code *)

G.f: 1 + x/(1-x) * sum( sum( x^(i+k) * F_n+1,k(1/(1-x)) for k in [0..n+1] ) for n >= 0 ) where F_n,k(q) = q^n * q^C(k,2) * [n-1,k-1] and [a,b] is the q-binomial. - Christian Bean, Jun 03 2015

cp's OEIS Frontend

User: Christian Bean

A277086 Irregular triangle read by rows: T(n,k) = number of size k subsets of S_n with respect to the symmetries of the square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A277083 Irregular triangle read by rows: T(n,k) = number of size k subsets of S_n that remain unchanged by a rotation of 180 degrees.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A277081 Irregular triangle read by rows: T(n,k) = number of size k subsets of S_n that remain unchanged under the operation of replacing a permutation with its inverse.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A277085 Irregular triangle read by rows: T(n,k) = number of size k subsets of S_n that remain unchanged by a rotation of 90 degrees.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A277080 Irregular triangle read by rows: T(n,k) = number of size k subsets of S_n that remain unchanged by reverse.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Sage

Formula

A262370 Triangle read by rows in which T(n,k) is the number of permutations avoiding 132 of length n with an independent set of size k in its coregraph.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

Formula

A260696 The number of length-n permutations avoiding the patterns 1234, 1324, 1432 and 3214.

Views

Author

Keywords

Links

Crossrefs

Programs

Magma

Mathematica

Formula

A263790 The number of length-n permutations avoiding the patterns 1234, 1324 and 2143.

Views

Author

Keywords

Links

Programs

Magma

Maple

Mathematica

PARI

Formula

A249562 Number of length n permutations avoiding (123,{2},{}) and (123,{},{1}).