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.

1, 4, 23, 216, 2937, 52108, 1136591, 29382320, 877838673, 29753600404, 1127881002535, 47278107653768, 2171286661012617, 108417864555606300, 5847857079417024031, 338841578119273846112

Offset: 0

Author

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

Keywords

• nonn
• easy

Examples

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

Links

• Seiichi Manyama, Table of n, a(n) for n = 0..365
• R. A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions! arXiv math.CO.0606404.
• Index entries for related partition-counting sequences

Crossrefs

First differences: A001517.

Replace "collection" by "sequence": A082765.

Replace "lists" by "sets": A105748.

Programs

Mathematica

Table[Sum[(k+i)!/i!/(k-i)!, {k, 0, n}, {i, 0, k}], {n, 0, 20}]

Formula

a(n) = Sum_{0<=i<=k<=n} (k+i)!/i!/(k-i)!.

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/(1-x)/Q(0), where Q(k)= 1 - x - 2*x*(k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 17 2013

a(n) ~ 2^(2*n + 1/2) * n^n / exp(n - 1/2). - Vaclav Kotesovec, May 15 2022