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,3

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.

Formula

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

Mathematica

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

Prog

(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

Crossrefs

Cf. A000108, A003319.

Sequence in context: A026361 A006189 A092201 * A026943 A307571 A047096

Adjacent sequences: A273523 A273524 A273525 * A273527 A273528 A273529

Keyword

nonn

Author

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

Status

approved