|
%I #49 Jan 09 2022 09:59:35
%S 1,1,2,4,10,28,88,304,1144,4648,20248,94024,463144,2409928,13198888,
%T 75848584,456066664,2862257608,18708144808,127096142344,895846801384,
%U 6540722530888,49392459602728,385251753351304,3099780861286504,25698921466247368,219294936264513448
%N G.f.: Sum_{n>=0} n! * x^n * (1+x)^n / Product_{k=1..n} (1 + k*x).
%C a(n-1) is the number of set partitions of [n] such that the absolute difference between least elements of consecutive blocks is always > 1. a(4) = 10: 12345, 1234|5, 1235|4, 123|45, 1245|3, 124|35, 124|3|5, 125|34, 12|345, 12|34|5. - _Alois P. Heinz_, May 22 2017
%C Conjecturally, the number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) = e(k). [Martinez and Savage, 2.13] - _Eric M. Schmidt_, Jul 17 2017
%H Paul D. Hanna, <a href="/A229046/b229046.txt">Table of n, a(n) for n = 0..500</a>
%H Wenqin Cao, Emma Yu Jin, and Zhicong Lin, <a href="https://doi.org/10.1016/j.dam.2019.01.035">Enumeration of inversion sequences avoiding triples of relations</a>, Discrete Applied Mathematics (2019); see also <a href="http://www.emmayujin.at/Pubs/CaoJinLin19.pdf">author's copy</a>
%H Megan A. Martinez and Carla D. Savage, <a href="https://arxiv.org/abs/1609.08106">Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations</a>, arXiv:1609.08106 [math.CO], 2016.
%F G.f.: 1+x + Sum_{n>=1} 2*x^(n+1) * Product_{k=1..n} (k + n*x)/(1 + k*x + n*x^2).
%F From _Peter Bala_, Jul 09 2014: (Start)
%F An alternative form of the o.g.f. appears to be the formal series A(x) = 1/(1 + x) * Sum_{n >= 0} 1/(1 - (n+1)*x)*(x/(1 + x))^n (checked up to a(26)). Cf. A105795.
%F Setting y = x/(1 + x) produces A(y) = (1 - y)^2*( Sum_{n >= 0} y^n/(1 - (n + 2)*y) ) = 1 + y + 3*y^2 + 9*y^3 + ..., the generating function for A112532. (End)
%F a(n) = 2*A204064(n-1) for n>1.
%F a(n) = Sum_{k=0..floor(n/2)} Sum_{i=0..k} (-1)^i * binomial(k,i) * (k-i+1)^(n-k). (See Paul Barry's formula in A105795). - _Paul D. Hanna_, Jul 13 2014
%F From _Alois P. Heinz_, Jan 24 2018: (Start)
%F a(n) = Sum_{k=0..floor(n/2)} k! * Stirling2(n-k+1,k+1).
%F a(n) = Sum_{k=1..ceiling((n+1)/2)} A298668(n+1,k). (End)
%e G.f.: A(x) = 1 + x + 2*x^2 + 4*x^3 + 10*x^4 + 28*x^5 + 88*x^6 + 304*x^7 +...
%e where
%e A(x) = 1 + x*(1+x)/(1+x) + 2!*x^2*(1+x)^2/((1+x)*(1+2*x)) + 3!*x^3*(1+x)^3/((1+x)*(1+2*x)*(1+3*x)) + 4!*x^4*(1+x)^4/((1+x)*(1+2*x)*(1+3*x)*(1+4*x)) + 5!*x^5*(1+x)^5/((1+x)*(1+2*x)*(1+3*x)*(1+4*x)*(1+5*x)) +...
%e Also, we have the identity (cf. A204064):
%e A(x) = 1 + x + 2*x^2*(1+x)/(1+x+x^2) + 2*x^3*(1+2*x)*(2+2*x)/((1+x+2*x^2)*(1+2*x+2*x^2)) + 2*x^4*(1+3*x)*(2+3*x)*(3+3*x)/((1+x+3*x^2)*(1+2*x+3*x^2)*(1+3*x+3*x^2)) + 2*x^5*(1+4*x)*(2+4*x)*(3+4*x)*(4+4*x)/((1+x+4*x^2)*(1+2*x+4*x^2)*(1+3*x+4*x^2)*(1+4*x+4*x^2)) +...
%e Also, by Peter Bala's o.g.f.:
%e A(x) = 1/((1+x)*(1-x)) + x/((1+x)^2*(1-2*x)) + x^2/((1+x)^3*(1-3*x))+ x^3/((1+x)^4*(1-4*x))+ x^4/((1+x)^5*(1-5*x)) + x^5/((1+x)^6*(1-6*x)) +...
%p a:= n-> add(k!*Stirling2(n-k+1,k+1), k=0..floor(n/2)):
%p seq(a(n), n=0..30); # _Alois P. Heinz_, Jan 24 2018
%t a[n_] := Sum[k!*StirlingS2[n-k+1, k+1], {k, 0, n/2}];
%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jul 25 2018, after _Alois P. Heinz_ *)
%o (PARI) a(n)=polcoeff( sum(m=0, n, m!*x^m*(1+x)^m/prod(k=1, m, 1+k*x +x*O(x^n))), n)
%o for(n=0,30,print1(a(n),", "))
%o (PARI) a(n)=polcoeff( 1-x + 2*x*sum(m=0, n, x^m*prod(k=1, m, (k+m*x)/(1+k*x+m*x^2 +x*O(x^n))) ), n)
%o for(n=0,30,print1(a(n), ", "))
%o (PARI) /* After Peter Bala: Sum_{n>=0} x^n/((1+x)^(n+1)*(1 - (n+1)*x)) */
%o {a(n)=polcoeff( sum(m=0, n, x^m/((1+x)^(m+1)*(1 - (m+1)*x) +x*O(x^n))), n)} \\ _Paul D. Hanna_, Jul 13 2014
%o for(n=0,30,print1(a(n), ", "))
%o (PARI) a(n)=sum(k=0, floor(n/2), sum(i=0, k, (-1)^i*binomial(k,i)*(k-i+1)^(n-k)))
%o for(n=0, 30, print1(a(n), ", ")) \\ _Paul D. Hanna_, Jul 13 2014
%Y Cf. A204064, A105795, A112532, A245373, A298668.
%K nonn
%O 0,3
%A _Paul D. Hanna_, Oct 27 2013
|
