login
Number of 123-avoiding indecomposable permutations.
8

%I #28 Jul 08 2017 12:02:19

%S 1,1,3,11,38,127,423,1423,4854,16787,58776,208001,742888,2674427,

%T 9694831,35357655,129644774,477638683,1767263172,6564120401,

%U 24466267000,91482563619,343059613628,1289904147301,4861946401428,18367353072127,69533550915978,263747951750333,1002242216651340,3814986502092275

%N Number of 123-avoiding indecomposable permutations.

%H Indranil Ghosh, <a href="/A273526/b273526.txt">Table of n, a(n) for n = 1..1000</a>

%H A. L. L. Gao, S. Kitaev, P. B. Zhang. <a href="https://arxiv.org/abs/1605.05490">On pattern avoiding indecomposable permutations</a>, arXiv:1605.05490 [math.CO], 2016.

%H Murray Tannock, <a href="https://skemman.is/bitstream/1946/25589/1/msc-tannock-2016.pdf">Equivalence classes of mesh patterns with a dominating pattern</a>, MSc Thesis, Reykjavik Univ., May 2016.

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

%t a[n_] := CatalanNumber[n] - (n - 1)

%t Table[a[n], {n, 1, 30}] (* _Alice L.L. Gao_, May 24 2016 *)

%o (PARI)

%o a(n) = binomial(2*n,n)/(n+1) - n + 1; \\ _Indranil Ghosh_, Mar 04 2017

%o (Python)

%o import math

%o f=math.factorial

%o def C(n,r): return f(n)/f(r)/f(n-r)

%o def Catalan(n): return C(2*n,n)/(n+1)

%o def A273526(n): return Catalan(n)-n+1 # _Indranil Ghosh_, Mar 04 2017

%Y Cf. A000108, A003319.

%K nonn

%O 1,3

%A _Alice L.L. Gao_ and _Philip B. Zhang_, May 24 2016