A273526 Number of 123-avoiding indecomposable permutations.

1, 1, 3, 11, 38, 127, 423, 1423, 4854, 16787, 58776, 208001, 742888, 2674427, 9694831, 35357655, 129644774, 477638683, 1767263172, 6564120401, 24466267000, 91482563619, 343059613628, 1289904147301, 4861946401428, 18367353072127, 69533550915978, 263747951750333, 1002242216651340, 3814986502092275

Offset: 1

Author

Alice L.L. Gao and Philip B. Zhang, May 24 2016

Keywords

• nonn

Links

• Indranil Ghosh, Table of n, a(n) for n = 1..1000
• A. L. L. Gao, S. Kitaev, P. B. Zhang. On pattern avoiding indecomposable permutations, arXiv:1605.05490 [math.CO], 2016.
• Murray Tannock, Equivalence classes of mesh patterns with a dominating pattern, MSc Thesis, Reykjavik Univ., May 2016.

Crossrefs

Cf. A000108, A003319.

Programs

Mathematica

a[n_] := CatalanNumber[n] - (n - 1)
Table[a[n], {n, 1, 30}] (* Alice L.L. Gao, May 24 2016 *)

PARI

a(n) = binomial(2*n,n)/(n+1) - n + 1; \\ Indranil Ghosh, Mar 04 2017

Python

import math
f=math.factorial
def C(n,r): return f(n)/f(r)/f(n-r)
def Catalan(n): return C(2*n,n)/(n+1)
def A273526(n): return Catalan(n)-n+1 # Indranil Ghosh, Mar 04 2017

Formula

a(n) = C(n) - n + 1, where C(n) is the Catalan number.