cp's OEIS Frontend

A129775 Number of maximally clustered permutations in S_n; the maximally clustered permutations are those that avoid 3421, 4312 and 4321.

%I A129775 #75 Jan 12 2025 17:03:57
%S A129775 1,1,2,6,21,78,298,1157,4539,17936,71251,284188,1137076,4561093,
%T A129775 18333337,73816489,297635750,1201551286,4855672249,19640147061,
%U A129775 79501958895,322037615290,1305256267511,5293166568270,21475362822956,87166344495561,353933533606927
%N A129775 Number of maximally clustered permutations in S_n; the maximally clustered permutations are those that avoid 3421, 4312 and 4321.
%C A129775 Equals INVERT transform of A001700 prefaced with a "1": (1, 1, 3, 10, 35, 126, 462, ...). - _Gary W. Adamson_, Dec 26 2008
%C A129775 Row sums of A155083. - _Paul Barry_, Jan 19 2009
%C A129775 Hankel transform is n+1. - _Paul Barry_, Jul 31 2010
%C A129775 INVERT transform of A088218. - _Michael Somos_, Jan 01 2014
%C A129775 INVERT transform is A073525. - _Michael Somos_, Jan 09 2014
%H A129775 Paul Barry, <a href="https://arxiv.org/abs/1802.03443">On a transformation of Riordan moment sequences</a>, arXiv:1802.03443 [math.CO], 2018.
%H A129775 David Callan, Toufik Mansour, and Mark Shattuck, <a href="http://ami.ektf.hu/uploads/papers/finalpdf/AMI_47_from41to74.pdf">Twelve subsets of permutations enumerated as maximally clustered permutations</a>, Annales Mathematicae et Informaticae, 47 (2017) pp. 41-74.
%H A129775 H. Denoncourt and B. Jones, <a href="http://arXiv.org/abs/0704.3469">The enumeration of maximally clustered permutations</a>, arXiv:0704.3469 [math.CO], 2007-2008.
%H A129775 S. B. Ekhad and M. Yang, <a href="http://sites.math.rutgers.edu/~zeilberg/tokhniot/oMathar1maple12.txt">Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences</a>, (2017)
%H A129775 Jozsef Losonczy, <a href="http://myweb.cwpost.liu.edu/jlosoncz/man13.pdf">Maximally clustered elements and Schubert varieties</a>, Annals of Combinatorics 11 (2) (2007) 195-212.
%F A129775 G.f.: 1+(2x^2) / (-1+4x-2x^2+sqrt(1-4x)).
%F A129775 G.f.: 1 + x * (1 - 4*x + 2*x^2 + sqrt(1 - 4*x)) / (2 * (1 - 5*x + 4*x^2 - x^3)). - _Michael Somos_, Jan 01 2014
%F A129775 G.f.: 1+x/(1-x-x/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-... (continued fraction). [From _Paul Barry_, Jan 19 2009]
%F A129775 G.f.: 1+x/(1-x-x/(1-x-x/(1-x-x^2/(1-x-x/(1-x-x^2/(1-x-x/(1-x-x^2/(1-x-x/(1-x-x^2/(1-x-x/(1-x-x^2/(1-... (continued fraction). - _Paul Barry_, Jul 31 2010
%F A129775 a(n) = sum(m=1..n-1, sum(k=1..n-m, k*binomial(m+k-1,m-1)*binomial(2*(n-m),n-m-k))/(n-m))+1, a(0)=1. - _Vladimir Kruchinin_, Oct 11 2011
%F A129775 a(n) is the upper left term in M^n, M = an infinite square production matrix with (1, 1, 2, 4, 8, 16, ... powers of 2) as the left border, as follows:
%F A129775   1, 1, 0, 0, 0, ...
%F A129775   1, 1, 1, 0, 0, ...
%F A129775   2, 1, 1, 1, 0, ...
%F A129775   4, 1, 1, 1, 1, ...
%F A129775   ... - _Gary W. Adamson_, Nov 14 2011
%F A129775 D-finite with recurrence (n-1)*a(n) + 3*(5-3*n)*a(n-1) + 6*(4*n-9)*a(n-2) + (41-17*n)*a(n-3) + 2*(2*n-5)*a(n-4) = 0. - _R. J. Mathar_, Nov 15 2011
%F A129775 0 = a(n) * (16*a(n+1) - 74*a(n+2) + 120*a(n+3) - 66*a(n+4) + 10*a(n+5))+ a(n+1) * (-62*a(n+1) + 361*a(n+2) - 480*a(n+3) + 265*a(n+4) - 41*a(n+5)) + a(n+2) * (-342*a(n+2) + 615*a(n+3) - 335*a(n+4) + 54*a(n+5)) + a(n+3) * (-90*a(n+3) + 75*a(n+4) - 15*a(n+5)) + a(n+4) * (-3*a(n+4) + a(n+5)) if n>0. - _Michael Somos_, Jan 01 2014
%F A129775 G.f.: 1 / (1 - x / (1 - x / (1 - 2*x / (1 - x / (2 - 3*x / (1 - 2*x / (3 - 4*x / ... ))))))). - _Michael Somos_, Jan 09 2014
%F A129775 G.f.: 2/(2-x-x/sqrt(1-4*x)). - _Michael Somos_, Jan 09 2014
%F A129775 a(n) ~ 1/(r^(n-1) * (2*r - 2 + (16*r^2 - 60*r + 65)*sqrt(1-4*r))), where r = 1/3*(4 - (2/(25-3*sqrt(69)))^(1/3) - (1/2*(25-3*sqrt(69)))^(1/3)) = 0.2451223337533... is the root of the equation 5*r-4*r^2+r^3 = 1. - _Vaclav Kotesovec_, Jan 12 2014
%F A129775 G.f.: x/(2-x-C(x)) where C(x)=(1-sqrt(1-4*x))/(2*x) is the g.f. for Catalan numbers A000108. - _David Callan_, Dec 03 2015
%e A129775 a(5)=78 because there are 78 permutations of size 5 that avoid 3421, 4312 and 4321.
%e A129775 G.f. = 1 + x + 2*x^2 + 6*x^3 + 21*x^4 + 78*x^5 + 298*x^6 + 1157*x^7 + 4539*x^8 + ...
%t A129775 a[ n_] := SeriesCoefficient[ 1 + 2 x^2 / (-1 + 4 x - 2 x^2 + Sqrt[1 - 4 x]), {x, 0, n}]; (* _Michael Somos_, Jan 01 2014 *)
%t A129775 a[n_] := 1+Sum[(m Binomial[2(n-m), n-m-1] Hypergeometric2F1[m+1, m-n+1, n-m+2, -1])/(n-m), {m, 1, n-1}]; Table[a[n], {n, 0, 26}] (* _Jean-François Alcover_, Dec 14 2018, after _Vladimir Kruchinin_ *)
%o A129775 (Maxima) a(n):=if n=0 then 1 else sum(sum(k*binomial(m+k-1,m-1)*binomial(2*(n-m),n-m-k),k,1,n-m)/(n-m),m,1,n-1)+1; /* _Vladimir Kruchinin_, Oct 11 2011 */
%Y A129775 Cf. A108600.
%Y A129775 Cf. A001700. - _Gary W. Adamson_, Dec 26 2008
%K A129775 nonn
%O A129775 0,3
%A A129775 Brant Jones (brant(AT)math.washington.edu), May 17 2007
%E A129775 a(0)=1 prepended by _Alois P. Heinz_, Dec 04 2015