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
Row sums of A155083. - Paul Barry, Jan 19 2009
Hankel transform is n+1. - Paul Barry, Jul 31 2010
INVERT transform of A088218. - Michael Somos, Jan 01 2014
INVERT transform is A073525. - Michael Somos, Jan 09 2014
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.
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
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
a(0)=1 prepended by Alois P. Heinz, Dec 04 2015
STATUS
approved