OFFSET
0,3
COMMENTS
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
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
LINKS
Paul D. Hanna, Table of n, a(n) for n = 0..500
Wenqin Cao, Emma Yu Jin, and Zhicong Lin, Enumeration of inversion sequences avoiding triples of relations, Discrete Applied Mathematics (2019); see also author's copy
Megan A. Martinez and Carla D. Savage, Patterns in Inversion Sequences II: Inversion Sequences Avoiding Triples of Relations, arXiv:1609.08106 [math.CO], 2016.
FORMULA
G.f.: 1+x + Sum_{n>=1} 2*x^(n+1) * Product_{k=1..n} (k + n*x)/(1 + k*x + n*x^2).
From Peter Bala, Jul 09 2014: (Start)
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.
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)
a(n) = 2*A204064(n-1) for n>1.
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
From Alois P. Heinz, Jan 24 2018: (Start)
a(n) = Sum_{k=0..floor(n/2)} k! * Stirling2(n-k+1,k+1).
a(n) = Sum_{k=1..ceiling((n+1)/2)} A298668(n+1,k). (End)
EXAMPLE
G.f.: A(x) = 1 + x + 2*x^2 + 4*x^3 + 10*x^4 + 28*x^5 + 88*x^6 + 304*x^7 +...
where
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)) +...
Also, we have the identity (cf. A204064):
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)) +...
Also, by Peter Bala's o.g.f.:
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)) +...
MAPLE
a:= n-> add(k!*Stirling2(n-k+1, k+1), k=0..floor(n/2)):
seq(a(n), n=0..30); # Alois P. Heinz, Jan 24 2018
MATHEMATICA
a[n_] := Sum[k!*StirlingS2[n-k+1, k+1], {k, 0, n/2}];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jul 25 2018, after Alois P. Heinz *)
PROG
(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)
for(n=0, 30, print1(a(n), ", "))
(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)
for(n=0, 30, print1(a(n), ", "))
(PARI) /* After Peter Bala: Sum_{n>=0} x^n/((1+x)^(n+1)*(1 - (n+1)*x)) */
{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
for(n=0, 30, print1(a(n), ", "))
(PARI) a(n)=sum(k=0, floor(n/2), sum(i=0, k, (-1)^i*binomial(k, i)*(k-i+1)^(n-k)))
for(n=0, 30, print1(a(n), ", ")) \\ Paul D. Hanna, Jul 13 2014
CROSSREFS
KEYWORD
nonn
AUTHOR
Paul D. Hanna, Oct 27 2013
STATUS
approved