login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 4
1, 3, 10, 47, 313, 2744, 29751, 383273, 5713110, 96673861, 1830257967, 38326484944, 879473289521, 21944639630923, 591545277653354, 17131028946645255, 530424623323416617, 17485652721425863464, 611431929749388274471, 22604399407882099928577 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,2

LINKS

Alois P. Heinz, Table of n, a(n) for n = 0..400

R. A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions!, arXiv:math.CO.0606404.

Index entries for related partition-counting sequences

FORMULA

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

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

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

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

EXAMPLE

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

MAPLE

a:= proc(n) option remember; `if`(n<3, [1, 3, 10][n+1],

      2*n*a(n-1)-(2*n-2)*a(n-2)-a(n-3))

    end:

seq(a(n), n=0..25);  # Alois P. Heinz, Mar 11 2015

MATHEMATICA

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

(* Second program: *)

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 *)

PROG

(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

CROSSREFS

First differences: A001515.

Replacing "collection" by "sequence" gives A003011.

Replacing "sets" by "lists" gives A105747.

Sequence in context: A005651 A249479 A236410 * A277746 A140964 A220362

Adjacent sequences:  A105745 A105746 A105747 * A105749 A105750 A105751

KEYWORD

nonn,easy

AUTHOR

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 03:04 EDT 2019. Contains 328315 sequences. (Running on oeis4.)