Joel B. Lewis - cp's OEIS frontend

A355281 Number of pairs of nested Dyck paths from (0,0) to (n,n) such that the upper path only touches the diagonal at its endpoints.

1, 1, 2, 9, 55, 400, 3266, 28999, 274537, 2734885, 28401315, 305352146, 3380956839, 38394091370, 445702108969, 5274935433915, 63507021523471, 776347636736261, 9621502184089320, 120726786082609207, 1531938384684090884, 19639252409244653785, 254143269904958943103, 3317204158078663935592

Offset: 0

Joel B. Lewis, Jun 26 2022

nonn

Let B be the 2 X n X n box of integer points with opposite corners (0, 0, 0) and (1, n - 1, n - 1). For n >= 1, a(n) is also the number of plane partitions that fit inside B and whose cells lie on or below the plane x + y + z = n - 1. Proof: after rotating by 90 degrees, the upper Dyck path is the outer boundary of the region of the plane partition filled with 2's and the lower Dyck path is the outer boundary of the region of the plane partition filled with 1's or 2's.

Alois P. Heinz, Table of n, a(n) for n = 0..841

Cf. A000108, A005700.

Column k=2 of A378112.

b:= proc(n) option remember; `if`(n=0, 1,
      b(n-1)*((4*n)^2-4)/(n+2)/(n+3))
    end:
a:= proc(n) option remember;
      b(n)-add(a(n-i)*b(i), i=1..n-1)
    end:
seq(a(n), n=0..23);  # Alois P. Heinz, Jun 26 2022

nmax = 23;
c = CatalanNumber;
B[x_] = Sum[(c[n] c[n+2] - c[n+1]^2) x^n, {n, 0, nmax}];
CoefficientList[2 - 1/B[x] + O[x]^(nmax+1), x] (* Jean-François Alcover, Jul 06 2022 *)

G.f.: 2 - 1/B(x) where B(x) is the generating function for A005700.

INVERTi transform of A005700.

A276356 Number of Hamiltonian cycles in the Cartesian product graph K_2 times K_n.

Original entry on oeis.org

0, 1, 3, 30, 480, 12000, 430920, 21052080, 1343381760, 108519626880, 10825535952000, 1307042125804800, 187849403155814400, 31691651643235584000, 6201948133744691328000, 1393497414722424211200000, 356287752381703180566528000, 102850159977463464656842752000

Offset: 1

Joel B. Lewis, Aug 31 2016

Twice the index k in the summation formula is the number of copies of K_2 in the cycle; this accounts for the factor binomial(n,2k). The remaining factors in each summand count the ways to connect these points to the others within each copy of K_n so that the result is a single cycle.

			For n = 1, the graph is K_2 and has no Hamiltonian cycles.
For n = 2, the graph is C_4, with a single Hamiltonian cycle.
For n = 3, the graph is the complement of C_6; each Hamiltonian cycle is determined by the choice of two edges of the 3 copies of K_2 to include.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Hamiltonian Cycle.
Eric Weisstein's World of Mathematics, Rook Graph.
Notamathematician et al., On a A089039 and pair of sequences with simple recursion, MathOverflow, 2024.

Second column of A269562.

Cf. A001040, A001053, A089039 (directed cycles).

a(n) = sum(k=1, n\2, binomial(n, 2*k) * (2*k-1)! * ((n-k-1)!/(k-1)!)^2); \\ Michel Marcus, Aug 31 2016

a(n) = Sum_{k=1..floor(n/2)} binomial(n, 2k) * (2k - 1)! * ((n - k - 1)! / (k - 1)!)^2.
For n > 1, a(n) = A089039(n)/2. - Mikhail Kurkov, Feb 10 2019
For n > 1, a(n) = ((n-1)!/2)*(A001040(n-1) + A001053(n)). - Conjectured by Mikhail Kurkov, Feb 10 2019; proved (see MO link) by Max Alekseyev, Apr 23 2024

A223911 Number of tiered orders on n nodes (corrected version of A006860).

Original entry on oeis.org

1, 1, 3, 13, 111, 1381, 25623, 678133, 26169951, 1447456261, 114973232583, 13034314621813, 2103826463800911, 481932523110975301, 156356753093586913143, 71729530379673590609653, 46471511649877647638694591, 42487759521494442057018000901, 54781291469300608901184153800103

Offset: 0

Joerg Arndt, Mar 29 2013, using information provided by Joel B. Lewis, M. F. Hasler and Michel Marcus in A006860

nonn

Joerg Arndt and Alois P. Heinz, Table of n, a(n) for n = 0..100 (terms n = 1..22 from Joerg Arndt)
D. Klarner, The number of tiered posets modulo six, Discrete Math., 62 (1986), 295-297.

Row sums of A361956.

Cf. A218695, A361912 (unlabeled version).

f:= (i, j)-> add((-1)^(i-k)*binomial(i, k) *(2^k-1)^j, k=0..i):
b:= proc(n, i) option remember;
      `if`(n=0, 1, add(b(n-j, j)/j!*f(i, j), j=1..n))
    end:
a:= n-> n!*b(n, 1):
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 23 2013

f[i_, j_] := Sum[(-1)^(i-k)*Binomial[i, k]*(2^k-1)^j, {k, 0, i}]; b[n_, i_] := b[n, i] = If[n==0, 1, Sum[b[n-j, j]/j!*f[i, j], {j, 1, n}]]; a[n_] := n!*b[n, 1]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Apr 08 2015, after Alois P. Heinz *)

f(m,n) = sum(k=0, m, (-1)^(m-k) * binomial(m,k) * (2^k-1)^n );
mn(n,V,m) = n! / prod(k=1, m, V[k]! ); /* multinomial of V[1..m] */
A223911(n)=
{
    my(m=n, C=vector(n,j,1), z, t, ret);
    while ( 1,  /* for all compositions C[1..m] of n */
        t = mn(n,C,m) * prod(j=1, m-1, f(C[j],C[j+1]) );
        ret += t;
        if ( m<=1, break() ); /* last composition? */
        /* create next composition: */
        C[m-1] += 1;
        z = C[m];
        C[m] = 1;
        m += z - 2;
    );
    return(ret);
}

\\ here f(m,n) is A218695.
f(m,n) = {sum(k=0, m, (-1)^(m-k) * binomial(m, k) * (2^k-1)^n )}
seq(n)={my(N=matrix(n,n,i,j, f(i,j)), T=vector(n), v=vector(n+1)); v[1]=1; for(r=1, n, T[r]=vector(r, k, (r==k) + binomial(r,k)*sum(i=1, r-k, T[r-k][i]*N[i,k])); v[1+r]=vecsum(T[r])); v} \\ Andrew Howroyd, Mar 29 2023

a(n) = sum(all composition C of n, M(C) * prod(j=1..m-1, f(C[j]*C[j+1]) ) ) where m is the number of parts of the current composition P, f(i,j) = sum(k=0..i, (-1)^(i-k) * binomial(i,k) * (2^k-1)^j ), and M(C) is the multinomial coefficient n!/prod(j=1..m, C[j]! ); see Pari code.
Klarner incorrectly gives prod(j=1..m-1, f(C[j]*C[m]) ) in the formula for a(n).
Conjecture: a(n) ~ c * 2^(n^2/4 + 3*n/2) / sqrt(n), where c = EllipticTheta[3, 0, 1/2^(1/4)] / (sqrt(Pi) * 2^(1/4)) = 2.020039... (based on the numerical analysis of 600 terms). - Vaclav Kotesovec, Apr 10 2015

Added a(0) = 1 by Alois P. Heinz, Jul 23 2013

A218531 The maximal number of solutions for a given row of a skyscraper puzzle of size n X n.

Original entry on oeis.org

1, 1, 2, 6, 22, 105, 675, 4872, 40614, 403704, 4342080, 50457000, 631548456, 8484089328, 121882518576, 1865935562400, 30341974222944, 522466493255424, 9499883854364928, 181927524046316544, 3713847873452280000, 80378118226450517760, 1816649795206970760960, 42807228653571471429120

Offset: 1

Tanya Khovanova and Joel B. Lewis, Mar 27 2013

nonn

In skyscraper puzzles one row represent skyscrapers of different heights. The number on the left/right of the row says how many skyscrapers are seen from the left/right. For example the row of length 4 with number 2 on the left and 2 on the right can be resolved in 6 ways: 1423, 2143, 2413, 3142, 3241, 3412.

a(n) is the size of the largest equivalence class of permutations of length n, where two permutations are considered equivalent if they have the same number of left-to-right maxima and the same number of right-to-left maxima.

			Consider permutations of length 3.
Permutation 123 has 3 left-to-right maxima and 1 right-to-left maximum.
Permutation 321 has 1 left-to-right maximum and 3 right-to-left maxima.
Permutations 213 (312) have 2(1) left-to right maxima and 1(2) right-to-left maximum.
Permutations 132 and 231 have 2 left-to right maxima and 2 right-to-left maxima.
Hence, the largest class consists of 2 permutations and a(3)=2.

Mauro Fiorentini, Table of n, a(n) for n = 1..100
Tanya Khovanova and Joel Brewster Lewis, Skyscrapers
T. Khovanova and J. B. Lewis, Skyscraper Numbers, arXiv preprint arXiv:1304.6445 [math.CO], 2013.
T. Khovanova and J. B. Lewis, Skyscraper Numbers, J. Int. Seq. 16 (2013) #13.7.2.

st1[n_, k_] := Abs[StirlingS1[n, k]];
sm[n_, u_, v_] := Sum[Binomial[n, k] st1[k, u-1] st1[n-k, v-1], {k, 1, n}];
a[1] = a[2] = 1; a[n_] := Module[{r = 0, t}, Do[t = sm[n-1, u, v]; If[t>r, r = t], {u, 1, n-1}, {v, 1, n-1}]; r];
Array[a, 20] (* Jean-François Alcover, Jul 23 2018, after Joerg Arndt *)

st1(n,k) = abs(stirling(n,k,1));
sm(n,u,v) = sum(k=1,n, binomial(n,k) * st1(k,u-1) * st1(n-k,v-1));
a(n)= {
    my(r=0, t);
    if ( n<=2, return(1) );
    n -= 1;
    for (u=1, n,
        for (v=1, n,
            t = sm(n, u, v);
            if ( t>r, r=t );
        );
    );
    return( r );
}
/* Joerg Arndt, Mar 28 2013 */

a(n+1) is the maximum over all u, v of Sum_{k=1..n} binomial(n,k) * c(k,u-1) * c(n-k,v-1), where c(l,m) is an unsigned Stirling number of the first kind (see A132393).

a(13) corrected by Mauro Fiorentini, Jan 15 2019

A222865 Weakly graded (3+1)-free partially ordered sets (posets) on n labeled vertices.

Original entry on oeis.org

1, 1, 3, 19, 195, 2551, 41343, 826939, 20616795, 658486351, 28264985223, 1725711709459, 155998194920835, 21019550046219271, 4162663551546902223, 1192847436856343300779, 489879387071459457083115, 286844271719979335180726911, 238844671940165660117456403543

Offset: 0

Joel B. Lewis, Mar 07 2013

nonn

Here "weakly graded" means that there is a rank function rk from the vertices to the integers such that whenever x covers y we have rk(x) = rk(y) + 1. Alternate terminology includes "graded" and "ranked." A poset is said to be (3+1)-free if it does not contain four vertices a, b, c, d such that a < b < c and d is incomparable to the other three.

J. B. Lewis and Y. X. Zhang, Enumeration of Graded (3+1)-Avoiding Posets, To appear, J. Combinatorial Theory, Series A.

For weakly graded (3+1)-free posets by height, see A222866. For strongly graded (3+1)-free posets, see A222863. For all weakly graded posets, see A001833. For all (3+1)-free posets, see A079145.

m = maxExponent = 19;
Psi[x_] = Sum[E^(2^n x) x^n/n!, {n, 0, m}] + O[x]^m;
W[x_, y_] = (1-x)y/x + (2x^3 + (x^3 - 2x^2)y)/(2x^2 + x + (x^2-2x-1) y);
CoefficientList[W[E^x, Psi[x]] + O[x]^m, x] Range[0, m-1]! (* Jean-François Alcover, Dec 11 2018 *)

G.f. is W(e^x, Psi(x)) where W(x, y) = (1 - x)y/x + (2x^3 + (x^3 - 2x^2)y)/(2x^2 + x + (x^2 - 2x - 1)y) and Psi(x) is the GF for A047863.

A222863 Strongly graded (3+1)-free partially ordered sets (posets) on n labeled vertices.

Original entry on oeis.org

1, 1, 3, 13, 111, 1381, 22383, 461413, 12163791, 420626821, 19880808303, 1337330559973, 130909732781391, 18649561895661061, 3830195104867879023, 1124247654215697637093, 469367653568553278229711, 278046313987470874905216901, 233462156432002170491075384943

Offset: 0

Joel B. Lewis, Mar 07 2013

nonn

Here "strongly graded" means that every maximal chain has the same length. Alternate terminology includes "graded" (e.g., in Stanley 2012) and "tiered" (as in A006860). A poset is said to be (3+1)-free if it does not contain four elements a, b, c, d such that a < b < c and d is incomparable to the other three.

R. P. Stanley, Enumerative Combinatorics, Volume 1. Cambridge University Press. 2nd edition, 2012. http://math.mit.edu/~rstan/ec/ec1/

J. B. Lewis and Y. X. Zhang, Enumeration of Graded (3+1)-Avoiding Posets, J. Combin. Theory Ser. A 120 (2013), no. 6, 1305-1327.

For strongly graded (3+1)-free posets by height, see A222864. For weakly graded (3+1)-free posets, see A222865. For all strongly graded posets, see A006860. For all (3+1)-free posets, see A079145.

m = maxExponent = 19;
Psi[x_] = Sum[E^(2^n*x)*x^n/n!, {n, 0, m}] + O[x]^m;
H[x_, y_] = 1+(2x^3 - 3x^2 + (x^3 - 4x^2 + 4x)y)/(2x^2 + x + (x^2-2x-1) y);
CoefficientList[H[E^x, Psi[x]] + O[x]^m, x] Range[0, m-1]! (* Jean-François Alcover, Dec 11 2018 *)

G.f.: H(e^x, Psi(x)) where H(x, y) = 1 + (2x^3 - 3x^2 + (x^3 - 4x^2 + 4x)y)/(2x^2 + x + (x^2 - 2x - 1)y) and Psi(x) is the g.f. for A047863.

A222866 Triangle T(n,k) of weakly graded (3+1)-free partially ordered sets (posets) on n labeled vertices with height k.

Original entry on oeis.org

1, 1, 2, 1, 12, 6, 1, 86, 84, 24, 1, 840, 1110, 480, 120, 1, 11642, 16620, 9120, 3240, 720, 1, 227892, 300846, 185640, 82320, 25200, 5040, 1, 6285806, 6810804, 4299624, 2142000, 816480, 221760, 40320, 1, 243593040, 199239270, 117205200, 60890760, 26157600

Offset: 1

Joel B. Lewis, Mar 07 2013

Here "weakly graded" means that there is a rank function rk from the vertices to the integers such that whenever x covers y we have rk(x) = rk(y) + 1. Alternate terminology includes "graded" and "ranked." A poset is said to be (3+1)-free if it does not contain four elements a, b, c, d such that a < b < c and d is incomparable to the other three.

Joel B. Lewis, Rows n = 1..20 of triangle, flattened
J. B. Lewis and Y. X. Zhang, Enumeration of Graded (3+1)-Avoiding Posets, J. Combin. Theory Ser. A 120 (2013), no. 6, 1305-1327.

For row-sums (weakly graded (3+1)-free posets with n labeled vertices, disregarding height), see A222865. For strongly graded (3+1)-free posets, see A222863. For all weakly graded posets, see A001833. For all (3+1)-free posets, see A079145.

G.F. is given in the Lewis-Zhang paper.

A222864 Triangle T(n,k) of strongly graded (3+1)-free partially ordered sets (posets) on n labeled vertices with height k.

Original entry on oeis.org

1, 1, 2, 1, 6, 6, 1, 50, 36, 24, 1, 510, 510, 240, 120, 1, 7682, 7380, 4800, 1800, 720, 1, 161406, 141246, 91560, 47040, 15120, 5040, 1, 4747010, 3444756, 2162664, 1134000, 493920, 141120, 40320, 1, 194342910, 110729310, 61286400, 32253480, 14605920, 5594400

Offset: 1

Joel B. Lewis, Mar 07 2013

Here "strongly graded" means that every maximal chain has the same length. Alternate terminology includes "graded" (e.g., in Stanley 2011) and "tiered" (as in A006860). A poset is said to be (3+1)-free if it does not contain four elements a, b, c, d such that a < b < c and d is incomparable to the other three.

			For n = 3, there is 1 strongly graded poset of height 1 (the antichain), 6 strongly graded posets of height 2, and 6 strongly graded posets of height 3 (the chains), and all of these are (3+1)-free. Thus, the third row of the triangle is 1, 6, 6.

Joel B. Lewis, Rows n = 1..20 of triangle, flattened
J. B. Lewis and Y. X. Zhang, Enumeration of Graded (3+1)-Avoiding Posets, J. Combin. Theory Ser. A 120 (2013), no. 6, 1305-1327.

For row-sums (strongly graded (3+1)-free posets with n labeled vertices, disregarding height), see A222863. For weakly graded (3+1)-free posets, see A222865. For all strongly graded posets, see A006860. For all (3+1)-free posets, see A079145.

G.f. is given in the Lewis-Zhang paper.

A213090 Number of permutations of length n whose associated Schubert variety is defined by inclusions.

Original entry on oeis.org

1, 1, 2, 6, 23, 101, 477, 2343, 11762, 59786, 306132, 1574536, 8120782, 41957030, 217021682, 1123371986, 5817788471, 30139492189, 156174965473, 809382185187, 4195096032623, 21745137658765, 112720985668763, 584336632836945, 3029232133574325, 15703985220888071

Offset: 0

Joel B. Lewis, Jun 05 2012

nonn

Permutations avoiding the four permutation patterns 4231, 35142, 42513, 351624.

See references for several other characterizations.

Alois P. Heinz, Table of n, a(n) for n = 0..500
H. Abe and S. Billey, Consequences of the Lakshmibai-Sandhya theorem: the ubiquity of permutation patterns in Schubert calculus and related geometry, 2014. See Th. 4.13.
M. H. Albert and R. Brignall, Enumerating indices of Schubert varieties defined by inclusions, arXiv:1301.3188 [math.CO], 2013.
V. Gasharov and V. Reiner, Cohomology of smooth Schubert varieties in partial flag manifolds, J. Lond. Math. Soc. 66 (2002), 550-562.
A. Hultman, Inversion arrangements and Bruhat intervals, J. Combin. Theory Ser. A, 118(7) (2011), 1897-1906.
A. Hultman, S. Linusson, J. Shareshian, and J. Sjöstrand, From Bruhat intervals to intersection lattices and a conjecture of Postnikov, J. Combin. Theory Ser. A, 116(3) (2009), 564-580.
S. Oh, A. Postnikov and H. Yoo, Bruhat order, smooth Schubert varieties, and hyperplane arrangements, J. Combin. Theory Ser. A 115(7) (2008), 1156-1166.
A. Postnikov, Total positivity, Grassmannians, and networks, arXiv:math/0609764 [math.CO], 2006.
Vic Reiner, Richard Stanley, and Joel Lewis, P0011 in the Database of Permutation Pattern Avoidance.
J. Sjöstrand, Bruhat intervals as rooks on skew Ferrers boards, J. Combin. Theory Ser. A 114 (2007), 1182-1198.

1 + ((1 - 5x - 2x^2 + 8x^3) - Sqrt[1-4x] (1 - 5x - 2x^2))/(2(1 - 6x + 5x^2 - 4x^3)) + O[x]^26 // CoefficientList[#, x]& (* Jean-François Alcover, Nov 28 2018 *)

(1-3*x-2*x^2-(1-x-2*x^2)*sqrt(1-4*x))/(1-3*x-(1-x+2*x^2)*sqrt(1-4*x)) \\ Charles R Greathouse IV, Oct 20 2015

G.f.: 1 + (1-3*x-2*x^2-(1-x-2*x^2)*sqrt(1-4*x)) / (1-3*x-(1-x+2*x^2) * sqrt(1-4*x)). - Michael Albert, Jan 15 2013

D-finite with recurrence n*a(n) +(-15*n+16)*a(n-1) +(77*n-158)*a(n-2) +(-149*n+408)*a(n-3) +2*(39*n-55)*a(n-4) +4*(-8*n+7)*a(n-5) +16*(-2*n+11)*a(n-6)=0. - R. J. Mathar, May 30 2014

A212884 Number of permutations in S_n whose Rothe diagram can be rearranged to give the complement of a skew shape.

Original entry on oeis.org

1, 1, 2, 6, 24, 112, 572, 3116, 17871, 106959, 663526, 4243490, 27856087, 187029655, 1280660596, 8921737864, 63108620169, 452503644985, 3284213633684, 24098433889312, 178583179551488, 1335346240984360

Offset: 0

Joel B. Lewis, May 29 2012

nonn

Equivalent definitions:
(1) Permutations that have the form (a_1, a_2, ..., a_k, b_1, b_2, ..., b_(n - k)), where the subsequences (a_1, a_2, ..., a_k) and (b_1, b_2, ..., b_(n - k)) avoid the permutation pattern 2143 and a_i < b_j for all i, j.
(2) Permutations that avoid the nine permutation patterns 24153, 25143, 31524, 31542, 32514, 32541, 42153, 52143, and 214365.

Joel B. Lewis, Table of n, a(n) for n = 0..50
A. J. Klein, J. B. Lewis and A. H. Morales, Counting matrices over finite fields with support on skew Young diagrams and complements of Rothe diagrams.
R. J. Mathar, D-finite recurrence

Ordinary g.f. is (1 - x)*V(x)^2 - V(x) + 1/(1 - x), where V(x) is the (ordinary) g.f. for A005802.

cp's OEIS Frontend

User: Joel B. Lewis

A355281 Number of pairs of nested Dyck paths from (0,0) to (n,n) such that the upper path only touches the diagonal at its endpoints.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A276356 Number of Hamiltonian cycles in the Cartesian product graph K_2 times K_n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A223911 Number of tiered orders on n nodes (corrected version of A006860).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A218531 The maximal number of solutions for a given row of a skyscraper puzzle of size n X n.

Views

Author

Keywords

Comments

Examples

Links

Programs

Mathematica

PARI

Formula

Extensions

A222865 Weakly graded (3+1)-free partially ordered sets (posets) on n labeled vertices.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A222863 Strongly graded (3+1)-free partially ordered sets (posets) on n labeled vertices.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

A222866 Triangle T(n,k) of weakly graded (3+1)-free partially ordered sets (posets) on n labeled vertices with height k.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A222864 Triangle T(n,k) of strongly graded (3+1)-free partially ordered sets (posets) on n labeled vertices with height k.

Views