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
Keywords
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.
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.