

A105747


Number of ways to use the elements of {1,..,k}, 0<=k<=2n, once each to form a collection of n (possibly empty) lists, each of length at most 2.


3



1, 4, 23, 216, 2937, 52108, 1136591, 29382320, 877838673, 29753600404, 1127881002535, 47278107653768, 2171286661012617, 108417864555606300, 5847857079417024031, 338841578119273846112
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


LINKS

Table of n, a(n) for n=0..15.
R. A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions! arXiv math.CO.0606404.
Index entries for related partitioncounting sequences


FORMULA

a(n) = sum(0<=i<=k<=n, (k+i)!/i!/(ki)! ).
a(n+3) = (4*n+11)*a(n+2)  (4*n+9)*a(n+1)  a(n)  Benoit Cloitre, May 26 2006
G.f.: 1/(1x)/Q(0), where Q(k)= 1  x  2*x*(k+1)/Q(k+1); (continued fraction).  Sergei N. Gladkovskii, May 17 2013


EXAMPLE

a(2)=23:
{(),()},
{(),(1)},
{(),(1,2)},
{(),(2,1)},
{(1),(2)},
{(1),(2,3)},
{(1),(3,2)},
...,
{(1,4),(2,3)},
{(1,4),(3,2)},
{(4,1),(2,3)},
{(4,1),(3,2)}.


MATHEMATICA

Sum[(k+i)!/i!/(ki)!, {k, 0, n}, {i, 0, k}]


CROSSREFS

First differences: A001517.
Replace "collection" by "sequence": A082765.
Replace "lists" by "sets": A105748.
Sequence in context: A221371 A056785 A188404 * A099692 A283499 A305787
Adjacent sequences: A105744 A105745 A105746 * A105748 A105749 A105750


KEYWORD

nonn,easy


AUTHOR

Robert A. Proctor (www.math.unc.edu/Faculty/rap/), Apr 18 2005


STATUS

approved



