A129775 Number of maximally clustered permutations in S_n; the maximally clustered permutations are those that avoid 3421, 4312 and 4321.
1, 1, 2, 6, 21, 78, 298, 1157, 4539, 17936, 71251, 284188, 1137076, 4561093, 18333337, 73816489, 297635750, 1201551286, 4855672249, 19640147061, 79501958895, 322037615290, 1305256267511, 5293166568270, 21475362822956, 87166344495561, 353933533606927
Offset: 0
Keywords
Examples
a(5)=78 because there are 78 permutations of size 5 that avoid 3421, 4312 and 4321. 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 + ...
Links
- Paul Barry, On a transformation of Riordan moment sequences, arXiv:1802.03443 [math.CO], 2018.
- David Callan, Toufik Mansour, and Mark Shattuck, Twelve subsets of permutations enumerated as maximally clustered permutations, Annales Mathematicae et Informaticae, 47 (2017) pp. 41-74.
- H. Denoncourt and B. Jones, The enumeration of maximally clustered permutations, arXiv:0704.3469 [math.CO], 2007-2008.
- S. B. Ekhad and M. Yang, Proofs of Linear Recurrences of Coefficients of Certain Algebraic Formal Power Series Conjectured in the On-Line Encyclopedia Of Integer Sequences, (2017)
- Jozsef Losonczy, Maximally clustered elements and Schubert varieties, Annals of Combinatorics 11 (2) (2007) 195-212.
Crossrefs
Cf. A108600.
Cf. A001700. - Gary W. Adamson, Dec 26 2008
Programs
-
Mathematica
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 *) 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 *) -
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 */
Formula
G.f.: 1+(2x^2) / (-1+4x-2x^2+sqrt(1-4x)).
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
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]
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
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
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:
1, 1, 0, 0, 0, ...
1, 1, 1, 0, 0, ...
2, 1, 1, 1, 0, ...
4, 1, 1, 1, 1, ...
... - Gary W. Adamson, Nov 14 2011
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
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
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
G.f.: 2/(2-x-x/sqrt(1-4*x)). - Michael Somos, Jan 09 2014
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
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
Extensions
a(0)=1 prepended by Alois P. Heinz, Dec 04 2015
Comments