login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A113485 Number of partitions of [n] avoiding the pattern 12/34. 1

%I

%S 1,2,5,14,41,122,367,1114,3423,10670,33841,109398,361045,1217346,

%T 4195267,14775986,53172411,195396310,732806677,2802898190,10926431393,

%U 43381582538,175311002903,720640632074,3011495745175,12786738800254

%N Number of partitions of [n] avoiding the pattern 12/34.

%C The first sum in the formula counts those partitions with a single block of size at least 3. The second sum counts those partitions with blocks of size at most 2. It's easy to see that to avoid 12/34 a partition cannot contain more than one block of size at least 3.

%C The elements shown satisfy the hypergeometric recurrence 2*a(n) -10*a(n-1) +(-n+13)*a(n-2) +2*(2*n+1)*a(n-3) +3*(-n-5)*a(n-4) +4*(-n+6)*a(n-5) +4*(n-5)*a(n-6)=0. - _R. J. Mathar_, Jan 25 2013

%D M. Klazar, Counting Pattern-free Set Partitions I: A Generalization of Stirling Numbers of the Second Kind, Europ. J. Combinatorics, Vol. 21 (2000), pp. 367-378.

%H G. C. Greubel, <a href="/A113485/b113485.txt">Table of n, a(n) for n = 1..880</a>

%F a(n) = Sum[Sum[(k+1)^2 binomial[n, 2k+p] k!, {k, 0, Floor[(n-p)/2]}], {p, 3, n}] + Sum[binomial[n, 2k] k!, {k, 0, Floor[n/2]}].

%F From _Vaclav Kotesovec_, Jun 10 2019: (Start)

%F Recurrence: 2*(n^2-8*n+13)*a(n) = 2*(4*n^2-31*n+43)*a(n-1) + (n^3-17*n^2+87*n-91)*a(n-2) - (3*n^3-27*n^2+78*n-64)*a(n-3) + 2*(n-3)*(n^2-6*n+6)*a(n-4).

%F a(n) ~ sqrt(Pi) * exp(sqrt(2*n) - n/2 - 1/2) * n^(n/2 + 1) / 2^(n/2 + 3/2) * (1 + 4*sqrt(2)/(3*sqrt(n))). (End)

%e For n=1,2,3 a(n)=B_n, where B_n is the n-th Bell number, since there aren't enough distinct elements for such a partition to contain a copy of 12/34. By a similar argument a(4)=B_4-1=14.

%t Table[Sum[Sum[(k+1)^2 Binomial[n, 2k+p] k!, {k, 0, Floor[(n-p)/2]}], {p, 3, n}]+Sum[Binomial[n, 2k] k!, {k, 0, Floor[n/2]}], {n, 1, 31}]

%o (PARI) a(n)=sum(p=3,n, sum(k=0,(n-p)\2, binomial(n,2*k+p)*(k+1)^2*k!)) + sum(k=0,n\2, binomial(n,2*k)) \\ _Charles R Greathouse IV_, Mar 12 2017

%Y Cf. A084261.

%K nonn

%O 1,2

%A _Adam Goyt_, Jan 09 2006

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 18 05:32 EDT 2019. Contains 327165 sequences. (Running on oeis4.)