|
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,2
|
|
|
COMMENTS
| Equals INVERT transform of A001700 prefaced with a "1": (1, 1, 3, 10, 35, 126, 462,...) [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 26 2008]
Row sums of A155083. [From Paul Barry (pbarry(AT)wit.ie), Jan 19 2009]
Hankel transform is n+1. [From Paul Barry (pbarry(AT)wit.ie), Jul 31 2010]
|
|
|
REFERENCES
| Jozsef Losonczy, Maximally clustered elements and Schubert varieties, Annals of Combinatorics 11 (2) (2007) 195-212.
|
|
|
LINKS
| H. Denoncourt and B. Jones, The enumeration of maximally clustered permutations.
|
|
|
FORMULA
| G.f.: (2x^2) / (-1+4x-2x^2+sqrt(1-4x)).
G.f.: 1/(1-x-x/(1-2x-x^2/(1-2x-x^2/(1-2x-x^2/(1-..... (continued fraction). [From Paul Barry (pbarry(AT)wit.ie), Jan 19 2009]
G.f.: 1/(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). [From Paul Barry (pbarry(AT)wit.ie), 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)=0. [From 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
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
|
|
|
EXAMPLE
| a(5)=78 because there are 78 permutations of size 5 that avoid 3421, 4312 and 4321.
|
|
|
PROG
| (Maxima)
a(n):=if n=0 then 0 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; [From Vladimir Kruchinin, Oct 11 2011]
|
|
|
CROSSREFS
| Cf. A108600.
A001700 [From Gary W. Adamson (qntmpkt(AT)yahoo.com), Dec 26 2008]
Sequence in context: A144169 A124292 A129776 * A054515 A150190 A150191
Adjacent sequences: A129772 A129773 A129774 * A129776 A129777 A129778
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| Brant Jones (brant(AT)math.washington.edu), May 17 2007
|
| |
|
|
