A007317 -id:A007317 - cp's OEIS frontend

A227035 a(n) = Sum_{k=0..floor(n/4)} binomial(n,4k)binomial(5k,k)/(4k+1).

1, 1, 1, 1, 2, 6, 16, 36, 76, 172, 436, 1156, 3006, 7606, 19202, 49466, 130156, 345356, 915196, 2421532, 6427001, 17163581, 46087911, 124133531, 334850208, 904691576, 2449891276, 6651540676, 18100561856, 49344295152, 134719523056, 368350942416, 1008680051756

Offset: 0

Vaclav Kotesovec, Jun 28 2013

Generally, Sum(binomial(n,p*k)*binomial((p+1)*k,k)/(p*k+1), k=0..floor(n/p)) is asymptotic to (p+(p+1)^(1+1/p))^(n+3/2)/(p^(n+1)*(p+1)^(1+3/(2*p))*n^(3/2)*sqrt(2*Pi)).

Vincenzo Librandi, Table of n, a(n) for n = 0..1000

Cf. A002294, A007317 (p=1), A049130 (p=2), A226974 (p=3), A226910 (p=5).

Table[Sum[Binomial[n,4*k]*Binomial[5*k,k]/(4*k+1),{k,0,Floor[n/4]}],{n,0,20}]

a(n)=sum(k=0,n\4,binomial(n,4*k)*binomial(5*k,k)/(4*k+1)) \\ Charles R Greathouse IV, Jun 28 2013

Recurrence: -2869*(n-7)*(n-6)*(n-5)*(n-4)*a(n-8) + 2*(n-6)*(n-5)*(n-4)*(5226*n-17267)*a(n-7) - (n-5)*(n-4)*(11582*n^2-55156*n+50139)*a(n-6) - 3*(n-4)*(612*n^3 - 18926*n^2 + 102684*n - 155665)*a(n-5) + 5*(n-4)*(2959*n^3 - 26172*n^2 + 77408*n - 76800)*a(n-4) - 1024*(n-2)*(2*n-5)*(7*n^2-35*n+48)*a(n-3) + 1024*(n-2)*(n-1)*(7*n^2-28*n+30)*a(n-2) - 1024*(n-2)*(n-1)*n*(2*n-3)*a(n-1) + 256*(n-2)*(n-1)*n*(n+1)*a(n) = 0.
a(n) ~ (4+5^(1+1/4))^(n+3/2)/(4^(n+1)*5^(1+3/8)*n^(3/2)*sqrt(2*Pi)).
G.f. A(x) satisfies: A(x) = 1 / (1 - x) + x^4 * A(x)^5. - Ilya Gutkovskiy, Jul 25 2021
From Peter Bala, Sep 15 2021: (Start)
O.g.f.: A(x) = (1/x)*series reversion ( x*(1 - x^4)/(1 + x*(1 - x^4) )).
The g.f. of the m-th binomial transform of this sequence is equal to (1/x)*series reversion ( x*(1 - x^4)/(1 + (m + 1)*x*(1 - x^4)) ). The case m = -1 gives the sequence [1,0,0,0,1,0,0,0,5,0,0,0,35,0,0,0,285,...] - an aerated version of A002294. (End)

A108307 Number of set partitions of {1, ..., n} that avoid enhanced 3-crossings (or enhanced 3-nestings).

Original entry on oeis.org

1, 1, 2, 5, 15, 51, 191, 772, 3320, 15032, 71084, 348889, 1768483, 9220655, 49286863, 269346822, 1501400222, 8519796094, 49133373040, 287544553912, 1705548000296, 10241669069576, 62201517142632, 381749896129920, 2365758616886432, 14793705539872672

Offset: 0

Mireille Bousquet-Mélou, Jun 29 2005

Also the number of 2-regular 3-noncrossing partitions. There is a bijection from 2-regular 3-noncrossing partitions of n to enhanced partition of n-1. - Jing Qin (qj(AT)cfc.nankai.edu.cn), Oct 30 2007
It appears that this is the number of sequences of length n, starting with a(1) = 1 and 1 <= a(2) <= 2, with 1 <= a(n) <= max(a(n-1),a(n-2)) + 1 for n > 2. - Franklin T. Adams-Watters, May 27 2008
From Eric M. Schmidt, Jul 17 2017: (Start)
Conjecturally, the number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(j) <= e(k) and e(i) >= e(k). [Martinez and Savage, 2.16]
Conjecturally, the number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) >= e(k). [Martinez and Savage, 2.16]
(End)
The second of the above-mentioned conjectures is proved in Zhicong Lin's paper. - Eric M. Schmidt, Nov 25 2017

			There are 52 partitions of 5 elements, but a(5)=51 because the partition (1,5)(2,4)(3) has an enhanced 3-nesting.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Nicholas R. Beaton, Mathilde Bouvel, Veronica Guerrini and Simone Rinaldi, Enumerating five families of pattern-avoiding inversion sequences; and introducing the powered Catalan numbers, arXiv:1808.04114 [math.CO], 2018.
Alin Bostan, Jordan Tirrell, Bruce W. Westbury and Yi Zhang, On sequences associated to the invariant theory of rank two simple Lie algebras, arXiv:1911.10288 [math.CO], 2019.
Alin Bostan, Jordan Tirrell, Bruce W. Westbury and Yi Zhang, On some combinatorial sequences associated to invariant theory, arXiv:2110.13753 [math.CO], 2021.
M. Bousquet-Mélou and G. Xin, On partitions avoiding 3-crossings, arXiv:math/0506551 [math.CO], 2005-2006.
Sophie Burrill, Sergi Elizalde, Marni Mishna and Lily Yen, A generating tree approach to k-nonnesting partitions and permutations, arXiv preprint arXiv:1108.5615 [math.CO], 2011.
W. Chen, E. Deng, R. Du, R. Stanley, and C. Yan, Crossings and nestings of matchings and partitions, arXiv:math/0501230 [math.CO], 2005.
Emma Y. Jin, Jing Qin and Christian M. Reidys, On 2-regular k-noncrossing partitions, arXiv:0710.5014 [math.CO], 2007.
Juan B. Gil and Jordan O. Tirrell, A simple bijection for classical and enhanced k-noncrossing partitions, arXiv:1806.09065 [math.CO], 2018.
Zhicong Lin, Restricted inversion sequences and enhanced 3-noncrossing partitions, arXiv:1706.07213 [math.CO], 2017.
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
Sherry H. F. Yan, Ascent sequences and 3-nonnesting set partitions, Eur. J. Comb. 39, 80-94 (2014), remark 3.6.

Cf. A124303, A073525, A007317.

Cf. A000110, A000108.

a:= proc(n) option remember; if n<=1 then 1 elif n=2 then 2 else (8*(n+1) *(n-1) *a(n-2)+ (7*(n-2)^2 +53*(n-2) +88) *a(n-1))/(n+6)/(n+5) fi end: seq(a(n), n=0..20);  # Alois P. Heinz, Sep 05 2008

a[n_] := a[n] = If[n <= 1, 1, If[n==2, 2, (8*(n+1)*(n-1)*a[n-2]+(7*(n-2)^2+53*(n-2)+88)*a[n-1])/(n+6)/(n+5)]]; Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Mar 30 2015, after Alois P. Heinz *)

D-finite with recurrence: 8*(n+3)*(n+1)*a(n)+(7*n^2+53*n+88)*a(n+1)-(n+8)*(n+7)*a(n+2)=0. - Jing Qin (qj(AT)cfc.nankai.edu.cn), Oct 26 2007
G.f.: -(6*x^4-15*x^3-7*x^2-11*x-1)/(6*x^5)+(224*x^3-60*x^2+45*x+5) * hypergeom([1/3, 2/3],[2],27*x^2/(1-2*x)^3) / (30*x^5*(2*x-1))+(32*x^2+64*x+5) * hypergeom([2/3, 4/3],[3],27*x^2/(1-2*x)^3)/(5*x^3*(2*x-1)^2). - Mark van Hoeij, Oct 24 2011
a(n) ~ 5*sqrt(3)*2^(3*n+16)/(27*Pi*n^7). - Vaclav Kotesovec, Aug 16 2013
G.f.: (-6*x^4+15*x^3+7*x^2+11*x+1)/(6*x^5)-(1-8*x)^(4/3)*(1+x)^(2/3)*hypergeom([-2/3, 7/3],[2],-27*x/((1+x)*(-1+8*x)^2))/(6*x^5). - Mark van Hoeij, Jul 26 2021

Edited by N. J. A. Sloane at the suggestion of Franklin T. Adams-Watters, Apr 27 2008

A202058 Number of ascent sequences avoiding the pattern 000.

Original entry on oeis.org

1, 1, 2, 4, 10, 27, 83, 277, 1015, 4007, 17047, 77451, 374889, 1923168, 10427250, 59544957, 357236992, 2245822801, 14762969601, 101264286082, 723499803180, 5375063821727, 41459660565329, 331546282841906, 2745163969235517, 23505333233440927, 207895424692608432

Offset: 0

N. J. A. Sloane, Dec 10 2011

nonn

It appears that no formula or g.f. is known.

Andrew Conway and Miles Conway, Table of n, a(n) for n = 0..176
Andrew R. Conway, Miles Conway, Andrew Elvey Price and Anthony J. Guttmann, Pattern-avoiding ascent sequences of length 3, arXiv:2111.01279 [math.CO], Nov 01 2021.
P. Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641, 2011

Total number of ascent sequences is given by A022493. Number of ascent sequences avoiding 001 (and others) is A000079; 102 is A007051; 101 is A000108; 000 is A202058; 100 is A202059; 110 is A202060; 120 is A202061; 201 is A202062; 210 is A108304; 0123 is A080937; 0021 is A007317; 0000 is A317784.

Column k=2 of A294220.

b[n_, i_, t_, p_, k_] := b[n, i, t, p, k] = If[n==0, 1, Sum[If[Coefficient[ p, x, j]==k, 0, b[n-1, j, t + If[j>i, 1, 0], p+x^j, k]], {j, 1, t+1}]];
a[n_] := b[n, 0, 0, 0, Min[n, 2]];
Table[Print["a(", n, ") = ", a[n]]; a[n], {n, 0, 17}] (* Jean-François Alcover, Sep 01 2018, after Alois P. Heinz in A294220 *)

a(15)-a(17) from Alois P. Heinz, Nov 09 2012
a(18)-a(20) from Giovanni Resta, Jan 06 2014
a(21) from Vaclav Kotesovec, Aug 21 2018
a(22) from Vaclav Kotesovec, Aug 22 2018
More terms from Anthony Guttmann, Nov 04 2021

A202062 Number of ascent sequences avoiding the pattern 201.

Original entry on oeis.org

1, 1, 2, 5, 15, 52, 201, 843, 3764, 17659, 86245, 435492, 2261769, 12033165, 65369590, 361661809, 2033429427, 11597912588, 67004252081, 391599609911, 2312726369640, 13789161819383, 82932744795049, 502777950712812, 3070529443569777, 18879637374473465, 116815588935673706, 727011479685559453

Offset: 0

N. J. A. Sloane, Dec 10 2011

nonn

It appears that no formula or g.f. is known.

Andrew Conway and Miles Conway, Table of n, a(n) for n = 0..133
Giulio Cerbai, Modified ascent sequences and Bell numbers, arXiv:2305.10820 [math.CO], 2023. See p. 27.
Giulio Cerbai, Anders Claesson and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.
Andrew R. Conway, Miles Conway, Andrew Elvey Price and Anthony J. Guttmann, Pattern-avoiding ascent sequences of length 3, arXiv:2111.01279 [math.CO], Nov 01 2021.
P. Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641 [math.CO], 2011.
Anthony Guttmann and Vaclav Kotesovec, L-convex polyominoes and 201-avoiding ascent sequences, arXiv:2109.09928 [math.CO], 2021.

Total number of ascent sequences is given by A022493.

Number of ascent sequences avoiding 001 (and others) is A000079; 102 is A007051; 101 is A000108; 000 is A202058; 100 is A202059; 110 is A202060; 120 is A202061; 201 is A202062; 210 is A108304; 0123 is A080937; 0021 is A007317.

Guttmann and Kotesovec give asymptotics: a(n) ~ c * d^n / n^(9/2), where d = (14/3*cos(arccos(13/14)/3) + 8/3) = 7.2958969432397723745722241... is the root of the equation 1 + 5*d - 8*d^2 + d^3 = 0 and c = 35*sqrt((4107 - 84*sqrt(9289) * cos(Pi/3 + arccos(255709*sqrt(9289)/24653006)/3))/Pi)/16 = 13.4299960869439... - Vaclav Kotesovec, Sep 22 2021

a(15) from Kanstancin Novikau, Mar 21 2017

a(16)-a(27) from Ildar Gainullin, Feb 11 2020

A338979 a(n) = Sum_{k=0..n} n^k * binomial(n,k) * Catalan(k).

Original entry on oeis.org

1, 2, 13, 199, 5073, 181776, 8413021, 478070020, 32238960193, 2517734880838, 223558608409101, 22248413487603887, 2453271411779452369, 296925818848604834448, 39138393489232585787037, 5581250331202285217569351, 856182695406472437496803585, 140595282922234695782098680030

Offset: 0

Seiichi Manyama, Jan 31 2021

Seiichi Manyama, Table of n, a(n) for n = 0..322

Cf. A000108, A007317, A162326, A337167, A339001.

a := n -> hypergeom([1/2, -n], [2], -4*n):
seq(simplify(a(n)), n = 0..17);  # Peter Luschny, Aug 27 2025

A338979[n_] :=  Sum[n^k*Binomial[n, k]*(2*k)!/(k!*(k + 1)!), {k, 0, n}];
Join[{1}, Table[A338979[n], {n, 1, 17}]] (* Robert P. P. McKone, Jan 31 2021 *)
A338979[n_] := Hypergeometric2F1[1/2, -n, 2, -4*n]; Table[A338979[n], {n, 0, 17}]  (* Peter Luschny, Aug 27 2025 *)

{a(n) = sum(k=0, n, n^k*binomial(n, k)*(2*k)!/(k!*(k+1)!))}

a(n) = n! * [x^n] exp((2*n+1)*x) * (BesselI(0,2*n*x) - BesselI(1,2*n*x)). - Ilya Gutkovskiy, Feb 02 2021
a(n) ~ exp(1/4) * 4^n * n^(n - 3/2) / sqrt(Pi). - Vaclav Kotesovec, Feb 14 2021
a(n) = hypergeom([1/2, -n], [2], -4*n). - Peter Luschny, Aug 27 2025

A346073 a(n) = 1 + Sum_{k=0..n-4} a(k) * a(n-k-4).

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 4, 5, 8, 13, 20, 29, 45, 73, 118, 185, 293, 475, 778, 1263, 2047, 3345, 5512, 9085, 14957, 24683, 40918, 67987, 113016, 188053, 313608, 524041, 876657, 1467797, 2460644, 4130893, 6942726, 11678687, 19663068, 33139295, 55904339, 94384167, 159470488

Offset: 0

Ilya Gutkovskiy, Jul 04 2021

nonn

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A000108, A007317, A090344, A216604, A307971, A346074.

a[n_] := a[n] = 1 + Sum[a[k] a[n - k - 4], {k, 0, n - 4}]; Table[a[n], {n, 0, 42}]
nmax = 42; A[] = 0; Do[A[x] = 1/(1 - x) + x^4 A[x]^2 + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]

a(n) = sum(k=0, n\4, binomial(n-3*k, k)*binomial(2*k, k)/(k+1)); \\ Seiichi Manyama, Jan 22 2023

@CachedFunction
def a(n): # a = A346073
    if (n<4): return 1
    else: return 1 + sum(a(k)*a(n-k-4) for k in range(n-3))
[a(n) for n in range(51)] # G. C. Greubel, Nov 26 2022

G.f. A(x) satisfies: A(x) = 1 / (1 - x) + x^4 * A(x)^2.

a(n) = Sum_{k=0..floor(n/4)} binomial(n-3*k,k) * Catalan(k). - Seiichi Manyama, Jan 22 2023

A348857 G.f. A(x) satisfies: A(x) = 1 / ((1 - x) * (1 - x * A(2*x))).

Original entry on oeis.org

1, 2, 7, 44, 481, 9254, 326395, 21927776, 2874607189, 744650622170, 383510575423471, 393869218949592212, 807827718206737362889, 3311287802485779192925838, 27136007596894473408507305443, 444677773080105539125038867872456, 14572535437424416878539776253365375549

Offset: 0

Ilya Gutkovskiy, Nov 02 2021

nonn

Cf. A007317, A015083, A348858, A348859.

nmax = 16; A[] = 0; Do[A[x] = 1/((1 - x) (1 - x A[2 x])) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]
a[n_] := a[n] = 1 + Sum[2^k a[k] a[n - k - 1], {k, 0, n - 1}]; Table[a[n], {n, 0, 16}]

a(n) = 1 + Sum_{k=0..n-1} 2^k * a(k) * a(n-k-1).

a(n) ~ c * 2^(n*(n-1)/2), where c = 10.96416094535958612421479005398505892527943513193882801485045169159164... - Vaclav Kotesovec, Nov 02 2021

A366356 G.f. satisfies A(x) = 1/(1 - x) + x/A(x).

Original entry on oeis.org

1, 2, -1, 6, -17, 71, -292, 1284, -5807, 26961, -127627, 613815, -2990680, 14730714, -73229290, 366936232, -1851352819, 9397497759, -47957377933, 245903408245, -1266266092111, 6545667052321, -33954266444497, 176689391245147, -922112642288148, 4825154135801698

Offset: 0

Seiichi Manyama, Oct 08 2023

sign

Paolo Xausa, Table of n, a(n) for n = 0..1000

Partial sums give A363816.
Cf. A007317, A199475, A349289, A349290, A349291, A349292, A349293, A366357, A366358, A366359.
Cf. A112478, A366363.

A366356[n_]:=(-1)^(n-1)Sum[Binomial[2k-1,k]Binomial[2k-1,n-k]/(2k-1),{k,0,n}];
Array[A366356,30,0] (* Paolo Xausa, Oct 20 2023 *)

a(n) = (-1)^(n-1)*sum(k=0, n, binomial(2*k-1, k)*binomial(2*k-1, n-k)/(2*k-1));

G.f.: A(x) = -2*x*(1-x) / (1-sqrt(1+4*x*(1-x)^2)).

a(n) = (-1)^(n-1) * Sum_{k=0..n} binomial(2*k-1,k) * binomial(2*k-1,n-k)/(2*k-1).

A376125 a(n) = 1 + Sum_{k=0..n-1} (2k+1) a(k) * a(n-k-1).

Original entry on oeis.org

1, 2, 9, 67, 681, 8556, 126253, 2124340, 39991633, 831271006, 18893178381, 465972248083, 12394713108433, 353750057246236, 10784915257548041, 349874160411051511, 12036066260440602401, 437714593034154481686, 16780944423208533034861, 676482338975579658794689

Offset: 0

Ilya Gutkovskiy, Sep 11 2024

nonn

Seiichi Manyama, Table of n, a(n) for n = 0..402

Cf. A000699, A007317, A321087.

a[n_] := a[n] = 1 + Sum[(2 k + 1) a[k] a[n - k - 1], {k, 0, n - 1}]; Table[a[n], {n, 0, 19}]
nmax = 19; A[] = 0; Do[A[x] = 1/((1 - x) (1 - x A[x] - 2 x^2 A'[x])) + O[x]^(nmax + 1) // Normal, nmax + 1]; CoefficientList[A[x], x]

G.f. A(x) satisfies: A(x) = 1 / ( (1 - x) *  (1 - x * A(x) - 2 * x^2 * A'(x)) ).
a(n) ~ c * 2^n * n * n!, where c = 0.6018110636400677977754542011395053310779724922160159... - Vaclav Kotesovec, Sep 11 2024
a(n) = 1 + n * Sum_{k=0..n-1} a(k) * a(n-1-k). - Seiichi Manyama, Jul 15 2025

A202059 Number of ascent sequences avoiding the pattern 100.

Original entry on oeis.org

1, 1, 2, 5, 14, 44, 153, 583, 2410, 10721, 50965, 257393, 1374187, 7722862, 45520064, 280502924, 1802060232, 12040040899, 83475921469, 599400745354, 4449689901306, 34096169966924, 269286884243138, 2189193150557825, 18297258191472880, 157049750065028868

Offset: 0

N. J. A. Sloane, Dec 10 2011

nonn

It appears that no formula or g.f. is known.

Andrew Conway and Miles Conway, Table of n, a(n) for n = 0..628
Andrew R. Conway, Miles Conway, Andrew Elvey Price and Anthony J. Guttmann, Pattern-avoiding ascent sequences of length 3, arXiv:2111.01279 [math.CO], Nov 01 2021.
P. Duncan and Einar Steingrimsson, Pattern avoidance in ascent sequences, arXiv preprint arXiv:1109.3641, 2011

Total number of ascent sequences is given by A022493. Number of ascent sequences avoiding 001 (and others) is A000079; 102 is A007051; 101 is A000108; 000 is A202058; 100 is A202059; 110 is A202060; 120 is A202061; 201 is A202062; 210 is A108304; 0123 is A080937; 0021 is A007317.

Corrected a(7), was 383, but should be 583 according to Duncan-Steimgrimsson paper and independent computation. - Andrew Baxter, Jan 06 2014
a(0) and a(15)-a(21) from Alois P. Heinz, Jan 06 2014
a(22) from Alois P. Heinz, Oct 06 2014
a(23) from Alois P. Heinz, Apr 20 2016
More terms from Anthony Guttmann, Nov 04 2021

cp's OEIS Frontend

A227035 a(n) = Sum_{k=0..floor(n/4)} binomial(n,4*k)*binomial(5*k,k)/(4*k+1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A108307 Number of set partitions of {1, ..., n} that avoid enhanced 3-crossings (or enhanced 3-nestings).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A202058 Number of ascent sequences avoiding the pattern 000.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Extensions

A202062 Number of ascent sequences avoiding the pattern 201.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A338979 a(n) = Sum_{k=0..n} n^k * binomial(n,k) * Catalan(k).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A346073 a(n) = 1 + Sum_{k=0..n-4} a(k) * a(n-k-4).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

SageMath

Formula

A348857 G.f. A(x) satisfies: A(x) = 1 / ((1 - x) * (1 - x * A(2*x))).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

Formula

A366356 G.f. satisfies A(x) = 1/(1 - x) + x/A(x).

Views

Author

Keywords

Links

Crossrefs

A227035 a(n) = Sum_{k=0..floor(n/4)} binomial(n,4k)binomial(5k,k)/(4k+1).

A376125 a(n) = 1 + Sum_{k=0..n-1} (2k+1) a(k) * a(n-k-1).