A229046 G.f.: Sum_{n>=0} n! * x^n * (1+x)^n / Product_{k=1..n} (1 + k*x).

1, 1, 2, 4, 10, 28, 88, 304, 1144, 4648, 20248, 94024, 463144, 2409928, 13198888, 75848584, 456066664, 2862257608, 18708144808, 127096142344, 895846801384, 6540722530888, 49392459602728, 385251753351304, 3099780861286504, 25698921466247368, 219294936264513448

Offset: 0

Author

Paul D. Hanna, Oct 27 2013

Keywords

• nonn

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

Examples

			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)) +...
		

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.

Crossrefs

Cf. A204064, A105795, A112532, A245373, A298668.

Programs

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 *)

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

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)