|
| |
|
|
A129775
|
|
Number of maximally clustered permutations in S_n; the maximally clustered permutations are those that avoid 3421, 4312 and 4321.
|
|
2
|
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Equals INVERT transform of A001700 prefaced with a "1": (1, 1, 3, 10, 35, 126, 462, ...). - Gary W. Adamson, Dec 26 2008
Hankel transform is n+1. - Paul Barry, Jul 31 2010
|
|
|
LINKS
|
|
|
|
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, ...
Conjecture: (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
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
|
|
|
EXAMPLE
|
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 + ...
|
|
|
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 *)
|
|
|
PROG
|
(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]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Brant Jones (brant(AT)math.washington.edu), May 17 2007
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
