login
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.
4

%I #22 May 15 2022 03:49:54

%S 1,4,23,216,2937,52108,1136591,29382320,877838673,29753600404,

%T 1127881002535,47278107653768,2171286661012617,108417864555606300,

%U 5847857079417024031,338841578119273846112

%N 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.

%H Seiichi Manyama, <a href="/A105747/b105747.txt">Table of n, a(n) for n = 0..365</a>

%H R. A. Proctor, <a href="http://arXiv.org/abs/math.CO/0606404">Let's Expand Rota's Twelvefold Way for Counting Partitions!</a> arXiv math.CO.0606404.

%H <a href="/index/Par#partN">Index entries for related partition-counting sequences</a>

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

%F a(n+3) = (4*n+11)*a(n+2) - (4*n+9)*a(n+1) - a(n) - _Benoit Cloitre_, May 26 2006

%F 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

%F a(n) ~ 2^(2*n + 1/2) * n^n / exp(n - 1/2). - _Vaclav Kotesovec_, May 15 2022

%e a(2)=23:

%e {(),()},

%e {(),(1)},

%e {(),(1,2)},

%e {(),(2,1)},

%e {(1),(2)},

%e {(1),(2,3)},

%e {(1),(3,2)},

%e ...,

%e {(1,4),(2,3)},

%e {(1,4),(3,2)},

%e {(4,1),(2,3)},

%e {(4,1),(3,2)}.

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

%Y First differences: A001517.

%Y Replace "collection" by "sequence": A082765.

%Y Replace "lists" by "sets": A105748.

%K nonn,easy

%O 0,2

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