cp's OEIS Frontend

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

%I A105748 #28 May 05 2024 10:04:00
%S A105748 1,3,10,47,313,2744,29751,383273,5713110,96673861,1830257967,
%T A105748 38326484944,879473289521,21944639630923,591545277653354,
%U A105748 17131028946645255,530424623323416617,17485652721425863464,611431929749388274471,22604399407882099928577
%N A105748 Number of ways to use the elements of {1,..,k}, 0<=k<=2n, once each to form a collection of n (possibly empty) sets, each with at most 2 elements.
%H A105748 Alois P. Heinz, <a href="/A105748/b105748.txt">Table of n, a(n) for n = 0..400</a>
%H A105748 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 A105748 <a href="/index/Par#partN">Index entries for related partition-counting sequences</a>
%F A105748 a(n) = Sum_{0<=i<=k<=n} (k+i)!/i!/(k-i)!/2^i.
%F A105748 G.f.: 1/U(0)  where U(k)= 1 - 3*x + x^2 - x*4*k - x^2*(2*k+1)*(2*k+2)/U(k+1) ; (continued fraction, 1-step). - _Sergei N. Gladkovskii_, Oct 06 2012
%F A105748 G.f.: 1/(1-x)/Q(0), where Q(k)= 1 - x - x*(k+1)/Q(k+1); (continued fraction). - _Sergei N. Gladkovskii_, May 19 2013
%F A105748 a(n) = 2*n*a(n-1) -(2*n-2)*a(n-2) -a(n-3) for n>2. - _Alois P. Heinz_, Mar 11 2015
%F A105748 a(n) ~ 2^(n + 1/2) * n^n / exp(n-1). - _Vaclav Kotesovec_, May 05 2024
%e A105748 a(2) = 10 = |{ {{},{}}, {{},{1}}, {{},{1,2}}, {{1},{2}}, {{1},{2,3}}, {{2},{1,3}}, {{3},{1,2}}, {{1,2},{3,4}}, {{1,3},{2,4}}, {{1,4},{2,3}} }|.
%p A105748 a:= proc(n) option remember; `if`(n<3, [1, 3, 10][n+1],
%p A105748       2*n*a(n-1)-(2*n-2)*a(n-2)-a(n-3))
%p A105748     end:
%p A105748 seq(a(n), n=0..25);  # _Alois P. Heinz_, Mar 11 2015
%t A105748 Sum[(k+i)!/i!/(k-i)!/2^i, {k, 0, n}, {i, 0, k}]
%t A105748 (* Second program: *)
%t A105748 a[n_] := E*Sqrt[2/Pi]*Sum[BesselK[k + 1/2, 1], {k, 0, n}]; Table[a[n] // Round, {n, 0, 25}] (* _Jean-François Alcover_, Jul 15 2017 *)
%o A105748 (PARI) A105748(n) = sum(k=0,n,sum(i=0,k, binomial(k+i,k-i)*binomial(2*i,i)*i!>>i))  \\ _M. F. Hasler_, Oct 09 2012
%Y A105748 First differences: A001515.
%Y A105748 Replacing "collection" by "sequence" gives A003011.
%Y A105748 Replacing "sets" by "lists" gives A105747.
%K A105748 nonn,easy
%O A105748 0,2
%A A105748 Robert A. Proctor (www.math.unc.edu/Faculty/rap/), Apr 18 2005