login
Number of 123 avoiding set partitions of [n].
1

%I #29 Oct 14 2016 04:24:06

%S 1,1,3,7,21,61,199,659,2345,8569,32971,130527,538045,2279733,9987727,

%T 44897131,207693905,983926001,4780294291,23740460215,120595843941,

%U 625175300653,3308054119767,17837452131139,98006292402553,548026191197801,3118110841312091

%N Number of 123 avoiding set partitions of [n].

%H Charles R Greathouse IV, <a href="/A270049/b270049.txt">Table of n, a(n) for n = 0..799</a>

%H B. E. Sagan, <a href="http://arxiv.org/abs/math/0604292">Pattern avoidance in set partitions</a>, arxiv:math/0604292 [math.CO], 2006, Theorems 2.5 and 3.4.

%F a(n) = Sum_{i=0..n/2} binomial(n,2*i)*(2*i)!!.

%F a(n) - 2*a(n-1) - (n-1)*a(n-2) + (n-2)*a(n-3) = 0.

%p A270049 := proc(n)

%p add( binomial(n,2*i)*doublefactorial(2*i),i=0..n/2) ;

%p end proc:

%t Table[Sum[Binomial[n, 2 i] (2 i)!!, {i, 0, n}], {n, 0, 26}] (* _Michael De Vlieger_, Mar 09 2016 *)

%o (PARI) a(n)=my(b=1,df=1,t); sum(i=1,n\2, t+=2; b*=(n-t+2)*(n-t+1)/(t*(t-1)); df*=t; b*df)+1 \\ _Charles R Greathouse IV_, Mar 10 2016

%Y Cf. A220913.

%K nonn,easy

%O 0,3

%A _R. J. Mathar_, Mar 09 2016

%E False conjecture deleted by _Colin Barker_, Oct 13 2016