|
Search: id:A113485
|
|
|
| A113485 |
|
Number of partitions of [n] avoiding the pattern 12/34. |
|
+0
1
|
|
| 1, 2, 5, 14, 41, 122, 367, 1114, 3423, 10670, 33841, 109398, 361045, 1217346, 4195267, 14775986, 53172411, 195396310, 732806677, 2802898190, 10926431393, 43381582538, 175311002903, 720640632074, 3011495745175, 12786738800254
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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.
|
|
REFERENCES
|
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.
|
|
FORMULA
|
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]}]
|
|
EXAMPLE
|
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.
|
|
MATHEMATICA
|
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}]
|
|
CROSSREFS
|
Sequence in context: A124302 A123183 A088355 this_sequence A054391 A108626 A159772
Adjacent sequences: A113482 A113483 A113484 this_sequence A113486 A113487 A113488
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
Adam M. Goyt (goytadam(AT)msu.edu), Jan 09 2006
|
|
|
Search completed in 0.002 seconds
|
