Juan B. Gil - cp's OEIS frontend

A368178 Number of ordered trees with n+1 leaves, no node of outdegree 1, and having as many leaves marked as the number of nodes of outdegree greater than 1.

1, 2, 9, 54, 375, 2848, 22981, 193742, 1688427, 15101778, 137930199, 1281629088, 12081441411, 115288530516, 1111783691037, 10819906562622, 106147110898419, 1048748721598078, 10427413491373843, 104265186535823798, 1047894080773661481

Offset: 0

Juan B. Gil, Jan 03 2024

nonn

If T(n, k) denotes the number of ordered trees with n + 1 leaves, no node of outdegree 1, and k nodes of outdegree greater than 1, where k of the leaves are marked, then a(n) = Sum_{k=1..n} T(n, k).

			For n = 2 there are 9 such marked trees: There is one tree [ [][][] ] with only one node of outdegree > 1 (the root). This tree leads to 3 marked trees. The tree [ [] [[][]] ] has 2 nodes of outdegree > 1, so it gives binomial(3,2) = 3 marked trees. Similarly, the tree [ [[][]] [] ] gives 3 more marked trees for a total of 9.

Juan B. Gil, Emma G. Hoover, and Jessica A. Shearer, Bijections between colored compositions, Dyck paths, and polygon partitions, arXiv:2403.04575 [math.CO], 2024. See p. 8.

Cf. A001003, A001622.

Join[{1}, Table[Sum[Binomial[n + k, k]*Binomial[n, k - 1]*Binomial[n, k]/n, {k, 1, n}], {n, 1, 25}]] (* Vaclav Kotesovec, Jan 04 2024 *)

a(n) = if(n==0, 1, sum(k=1, n, binomial(n+k, k)*binomial(n, k-1)* binomial(n, k)/n)) \\ Andrew Howroyd, Jan 03 2024

def a(n): return (n + 1) * hypergeometric([1 - n, -n, n + 2], [2, 2], 1)
print([simplify(a(n)) for n in range(12)])  # Peter Luschny, Jan 03 2024

a(n) = Sum_{k=1..n} binomial(n+k, k) * binomial(n, k-1) * binomial(n, k)/n for n > 0.
a(n) = (n + 1) * hypergeom([1 - n, -n, n + 2], [2, 2], 1). - Peter Luschny, Jan 03 2024
a(n) ~ phi^(5*n + 7/2) / (2*Pi*5^(1/4)*n^2), where phi = A001622 is the golden ratio. - Vaclav Kotesovec, Jan 04 2024

A366774 Number of 2-distant 3-noncrossing partitions of {1,...,n}.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 203, 876, 4115, 20765, 111301, 627821, 3698873, 22623354, 142940629, 929208778, 6194162081, 42223649277, 293640007995, 2079196943605, 14964254850197, 109308213994757, 809340696014733, 6067405789245061, 46008536947670701, 352579939415882813

Offset: 0

Juan B. Gil, Nov 13 2023

nonn

a(n+1) is the binomial transform of A108304.

			There are 877 partitions of 7 elements, but a(7)=876 because the partition (1,5)(2,6)(3,7)(4) has a 2-distant 3-crossing.

Juan B. Gil and Jordan O. Tirrell, A simple bijection for enhanced, classical, and 2-distant k-noncrossing partitions, Discrete Math. 343 (2020), no. 6, 111705, 5 pp.

Jean-François Alcover, Table of n, a(n) for n = 0..200
Juan B. Gil and Jordan O. Tirrell, A simple bijection for enhanced, classical, and 2-distant k-noncrossing partitions, arXiv:1806.09065 [math.CO], 2018-2023.

Cf. A108304, A366775, A366776.

b[n_] := b[n] = If[n < 2, 1, (2*(5*n^2 + 12*n - 2)*b[n - 1] + 9*(-n^2 + n + 2)*b[n - 2])/((n + 4)*(n + 5))];
a[n_] := If[n == 0, 1, Sum[Binomial[n - 1, i]*b[i], {i, 0, n - 1}]];
Table[a[n], {n, 0, 200}] (* Jean-François Alcover, Nov 25 2023 *)

a(n+1) = Sum_{i=0..n} binomial(n,i)*A108304(i).

a(n) ~ 2^(n+1) * 5^(n+7) / (3^(9/2) * Pi * n^7). - Vaclav Kotesovec, Jan 04 2024

More terms from Jean-François Alcover, Nov 25 2023

A366776 Number of 2-distant 5-noncrossing partitions of {1,...,n}.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21147, 115975, 678569, 4213546, 27642948, 190866373, 1382340849, 10469739750, 82701857286, 679644668584, 5797647603036, 51228938289039, 467980667203765

Offset: 0

Juan B. Gil, Nov 13 2023

a(n+1) is the binomial transform of A192126.

			There are 678570 partitions of 11 elements, but a(11)=678569 because the partition (1,7)(2,8)(3,9)(4,10)(5,11)(6) has a 2-distant 5-crossing.

Juan B. Gil and Jordan O. Tirrell, A simple bijection for enhanced, classical, and 2-distant k-noncrossing partitions, Discrete Math. 343 (2020), no. 6, 111705, 5 pp.

Juan B. Gil and Jordan O. Tirrell, A simple bijection for enhanced, classical, and 2-distant k-noncrossing partitions, arXiv:1806.09065 [math.CO], 2018-2023.

Cf. A192126, A366774, A366775.

a(n+1) = Sum_{i=0..n} binomial(n,i)*A192126(i).

A366775 Number of 2-distant 4-noncrossing partitions of {1,...,n}.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 203, 877, 4140, 21146, 115938, 677765, 4200011, 27446229, 188255890, 1349652560, 10075332564, 78052115894, 625568350179, 5173033558415, 44028767332852, 384857341649657

Offset: 0

Juan B. Gil, Nov 13 2023

a(n+1) is the binomial transform of A108305.

			There are 21147 partitions of 9 elements, but a(9)=21146 because the partition (1,6)(2,7)(3,8)(4,9)(5) has a 2-distant 4-crossing.

Juan B. Gil and Jordan O. Tirrell, A simple bijection for enhanced, classical, and 2-distant k-noncrossing partitions, Discrete Math. 343 (2020), no. 6, 111705, 5 pp.

Juan B. Gil and Jordan O. Tirrell, A simple bijection for enhanced, classical, and 2-distant k-noncrossing partitions, arXiv:1806.09065 [math.CO], 2018-2023.

Cf. A108305, A366774, A366776.

a(n+1) = Sum_{i=0..n} binomial(n,i)*A108305(i).

A363431 Number of 123-avoiding stabilized-interval-free permutations of size n.

Original entry on oeis.org

1, 1, 1, 2, 5, 14, 44, 150, 496, 1758, 6018, 21782, 76414, 280448, 1001752, 3714032, 13450270, 50259604, 183995056, 691863078, 2555043320, 9657267848, 35921300392, 136360740016, 510267869416, 1944193285228, 7312488701868, 27950641500876, 105590010259396, 404724123141348, 1534775681029994

Offset: 0

Juan B. Gil, Jun 22 2023

nonn

A stabilized-interval-free (SIF) permutation on [n] = {1, 2, ..., n} is one that does not stabilize any proper subinterval of [n].

			For n=4 the a(4)=5 permutations are 2413, 3142, 3412, 3421, 4312.

Daniel Birmajer, Juan B. Gil, Jordan O. Tirrell, and Michael D. Weiner, Pattern-avoiding stabilized-interval-free permutations, arXiv:2306.03155 [math.CO], 2023.

Cf. A075834.

For n>2, a(n) = f_0(n) - f_1(n-1) + f_2(n) - Sum_{k=1..floor((n-3)/2)} C(k)^2*a(n-2*k), where C(k)=binomial(2*k,k)/(k+1) and f_j(m) denotes the number of 123-avoiding permutations of size m having j fixed points.

A363432 Number of 231-avoiding stabilized-interval-free permutations of size n.

Original entry on oeis.org

1, 1, 1, 1, 2, 6, 18, 54, 170, 551, 1817, 6092, 20722, 71325, 248055, 870402, 3077861, 10959008, 39261382, 141430953, 512002865, 1861872379, 6798330676, 24915934639, 91630864177, 338048560865, 1250793108398, 4640542045919, 17260221009367, 64349394615738, 240434325753052

Offset: 0

Juan B. Gil, Jun 22 2023

nonn

A stabilized-interval-free (SIF) permutation on [n] = {1, 2, ..., n} is one that does not stabilize any proper subinterval of [n].

a(n) is also the number of 312-avoiding SIF permutations of size n.

			For n=5 the a(5)=6 permutations are 51234, 51423, 53124, 54123, 54132, 54213.

Daniel Birmajer, Juan B. Gil, Jordan O. Tirrell, and Michael D. Weiner, Pattern-avoiding stabilized-interval-free permutations, arXiv:2306.03155 [math.CO], 2023.

Cf. A000108, A075834.

nmax = 30; CoefficientList[Series[1 + x/(1 + CatalanNumber[1]*x^2*(x + 1) + ContinuedFractionK[-x, 1 + CatalanNumber[k]*x^(k + 1)*(x + 1), {k, 2, nmax}]), {x, 0, nmax}], x] (* Vaclav Kotesovec, Jun 23 2023 *)

G.f.: 1 + x/(1+C(1)*x^2*(x+1)-x/(1+C(2)*x^3*(x+1)-x/(1+C(3)*x^4*(x+1)-x/(...)))), where C(k)=binomial(2*k,k)/(k+1).

A363433 Number of (123,231)-avoiding stabilized-interval-free permutations of size n.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 3, 3, 5, 5, 7, 7, 10, 9, 13, 12, 16, 15, 20, 18, 24, 22, 28, 26, 33, 30, 38, 35, 43, 40, 49, 45, 55, 51, 61, 57, 68, 63, 75, 70, 82, 77, 90, 84, 98, 92, 106, 100, 115, 108, 124, 117, 133, 126, 143, 135, 153, 145, 163, 155, 174, 165, 185, 176, 196

Offset: 0

Juan B. Gil, Jun 30 2023

A stabilized-interval-free (SIF) permutation on [n] = {1, 2, ..., n} is one that does not stabilize any proper subinterval of [n].

			For n from 1 to 5 the six permutations (1+1+1+1+2) are 1, 21, 312, 4312, 54132, 54213.

Paolo Xausa, Table of n, a(n) for n = 0..10000
Daniel Birmajer, Juan B. Gil, Jordan O. Tirrell, and Michael D. Weiner, Pattern-avoiding stabilized-interval-free permutations, arXiv:2306.03155 [math.CO], 2023.
Index entries for linear recurrences with constant coefficients, signature (0,2,1,-1,-2,0,1).

Cf. A075834, A363431, A363432.

A131713 := proc(n)
    op(1+modp(n,3),[1,-2,1]) ;
end proc:
A363433 := proc(n)
    if n < 3 then
        1;
    else
        16*A131713(n) +42*n-79+6*n^2-81*(-1)^n+18*n*(-1)^n;
        %/144 ;
    end if;
end proc:
seq(A363433(n),n=0..20) ; # R. J. Mathar, Jul 17 2023

LinearRecurrence[{0,2,1,-1,-2,0,1},{1,1,1,1,1,2,3,3,5,5},100] (* Paolo Xausa, Nov 18 2023 *)

Vec((x^9 + x^8 - 3*x^6 - 2*x^5 + x^4 + 2*x^3 + x^2 - x - 1)/((x^2 + x + 1)*(x + 1)^2*(x - 1)^3) + O(x^65)) \\ Michel Marcus, Jul 01 2023

G.f.: (x^9 + x^8 - 3*x^6 - 2*x^5 + x^4 + 2*x^3 + x^2 - x - 1)/((x^2 + x + 1)*(x + 1)^2*(x - 1)^3).
E.g.f.: (144 + 36*x*(2 + x) + (3*x^2 + 15*x - 80)*cosh(x) + 8*exp(-x/2)*(cos(sqrt(3)*x/2) - sqrt(3)*sin(sqrt(3)*x/2)) + (3*x^2 + 33*x + 1)*sinh(x))/72. - Stefano Spezia, Jul 01 2023
144*a(n) = 16*A131713(n) +42*n -79 +6*n^2 -81*(-1)^n +18*n*(-1)^n , for n>=3. - R. J. Mathar, Jul 17 2023

A361275 Number of 1423-avoiding even Grassmannian permutations of size n.

Original entry on oeis.org

1, 1, 1, 3, 5, 11, 17, 29, 41, 61, 81, 111, 141, 183, 225, 281, 337, 409, 481, 571, 661, 771, 881, 1013, 1145, 1301, 1457, 1639, 1821, 2031, 2241, 2481, 2721, 2993, 3265, 3571, 3877, 4219, 4561, 4941, 5321, 5741, 6161, 6623, 7085, 7591, 8097, 8649, 9201, 9801, 10401

Offset: 0

Juan B. Gil, Mar 10 2023

A permutation is said to be Grassmannian if it has at most one descent. A permutation is even if it has an even number of inversions.

Avoiding any of the patterns 2314 or 3412 gives the same sequence.

			For n=4 the a(4) = 5 permutations are 1234, 1342, 2314, 3124, 3412.

Juan B. Gil and Jessica A. Tomasko, Pattern-avoiding even and odd Grassmannian permutations, arXiv:2207.12617 [math.CO], 2022.
Index entries for linear recurrences with constant coefficients, signature (2,1,-4,1,2,-1).

Cf. A356185, A361272, A361273, A361274.

For the corresponding odd permutations, cf. A005993.

seq(1 - 5*n/24 + n^3/12 - (-1)^n * n/8, n = 0 .. 100); # Robert Israel, Mar 10 2023

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

a(n) = 1 - 5*n/24 + n^3/12 - (-1)^n * n/8. - Robert Israel, Mar 10 2023

A361276 Number of 2413-avoiding even Grassmannian permutations of size n.

Original entry on oeis.org

1, 1, 1, 3, 6, 13, 22, 37, 55, 81, 111, 151, 196, 253, 316, 393, 477, 577, 685, 811, 946, 1101, 1266, 1453, 1651, 1873, 2107, 2367, 2640, 2941, 3256, 3601, 3961, 4353, 4761, 5203, 5662, 6157, 6670, 7221, 7791, 8401, 9031, 9703, 10396, 11133, 11892, 12697, 13525, 14401

Offset: 0

Juan B. Gil, Mar 10 2023

A permutation is said to be Grassmannian if it has at most one descent. A permutation is even if it has an even number of inversions.

			For n=4 the a(4) = 6 permutations are 1234, 1342, 1423, 2314, 3124, 3412.

Juan B. Gil and Jessica A. Tomasko, Pattern-avoiding even and odd Grassmannian permutations, arXiv:2207.12617 [math.CO], 2022.
Index entries for linear recurrences with constant coefficients, signature (2,1,-4,1,2,-1).

Cf. A356185, A361272, A361273, A361274, A361275.

For the corresponding odd permutations, cf. A006918.

LinearRecurrence[{2,1,-4,1,2,-1},{1,1,1,3,6,13},50] (* Harvey P. Dale, Aug 14 2023 *)

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

A361274 Number of 1342-avoiding even Grassmannian permutations of size n.

Original entry on oeis.org

1, 1, 1, 3, 5, 12, 17, 32, 41, 67, 81, 121, 141, 198, 225, 302, 337, 437, 481, 607, 661, 816, 881, 1068, 1145, 1367, 1457, 1717, 1821, 2122, 2241, 2586, 2721, 3113, 3265, 3707, 3877, 4372, 4561, 5112, 5321, 5931, 6161, 6833, 7085, 7822, 8097, 8902, 9201, 10077, 10401

Offset: 0

Juan B. Gil, Mar 09 2023

A permutation is said to be Grassmannian if it has at most one descent. A permutation is even if it has an even number of inversions.

a(n) is also the number of 3124-avoiding even Grassmannian permutations of size n.

			For n=4 the a(4) = 5 permutations are 1234, 1423, 2314, 3124, 3412.

Juan B. Gil and Jessica A. Tomasko, Pattern-avoiding even and odd Grassmannian permutations, arXiv:2207.12617 [math.CO], 2022.
Index entries for linear recurrences with constant coefficients, signature (1,3,-3,-3,3,1,-1).

Cf. A356185, A361271.

LinearRecurrence[{1,3,-3,-3,3,1,-1},{1,1,1,3,5,12,17},51] (* Stefano Spezia, Mar 09 2023 *)

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

E.g.f.: ((24 - 9*x + 6*x^2 + 2*x^3)*cosh(x) + (33 - 6*x + 9*x^2 + 2*x^3)*sinh(x))/24. - Stefano Spezia, Mar 09 2023

cp's OEIS Frontend

User: Juan B. Gil

A368178 Number of ordered trees with n+1 leaves, no node of outdegree 1, and having as many leaves marked as the number of nodes of outdegree greater than 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

SageMath

Formula

A366774 Number of 2-distant 3-noncrossing partitions of {1,...,n}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A366776 Number of 2-distant 5-noncrossing partitions of {1,...,n}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A366775 Number of 2-distant 4-noncrossing partitions of {1,...,n}.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula

A363431 Number of 123-avoiding stabilized-interval-free permutations of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A363432 Number of 231-avoiding stabilized-interval-free permutations of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A363433 Number of (123,231)-avoiding stabilized-interval-free permutations of size n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI