A105749 Number of ways to use the elements of {1,...,k}, 0 <= k <= 2n, once each to form a sequence of n sets, each having 1 or 2 elements.

1, 2, 14, 222, 6384, 291720, 19445040, 1781750880, 214899027840, 33007837322880, 6290830003852800, 1456812592995513600, 402910665227270323200, 131173228963370155161600, 49656810289225281849907200, 21628258853895305337293568000, 10739534026001485514941587456000

Offset: 0

Author

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

Keywords

• nonn
• easy

Comments

Equivalently, number of sequences of n labeled items such that each item occurs just once or twice. - David Applegate, Dec 08 2008

Also, number of assembly trees for a certain star graph, see Vince-Bona, Theorem 4. - N. J. A. Sloane, Oct 08 2012

Examples

			a(2) = 14 = |{ ({1},{2}), ({2},{1}), ({1},{2,3}), ({2,3},{1}), ({2},{1,3}), ({1,3},{2}), ({3},{1,2}), ({1,2},{3}), ({1,2},{3,4}), ({3,4},{1,2}), ({1,3},{2,4}), ({2,4},{1,3}), ({1,4},{2,3}), ({2,3},{1,4}) }|.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..100
• Samuele Giraudo and Yannic Vargas, Operads of packed words, quotients, and monomial bases, Proc. 37th Conf. Formal Power Series Alg. Comb., Sém. Lotharingien Combin. (2025) Vol. 93B Art. No. 82. See p. 9.
• Robert A. Proctor, Let's Expand Rota's Twelvefold Way for Counting Partitions!, arXiv:math/0606404 [math.CO], 2006-2007.
• Andrew Vince and Miklos Bona, The Number of Ways to Assemble a Graph, arXiv preprint arXiv:1204.3842 [math.CO], 2012.
• Index entries for related partition-counting sequences

Crossrefs

Cf. A001515, A003011, A143990.

Replace "sets" by "lists": A099022.

Column n=2 of A181731.

Programs

Magma

[(&+[Binomial(n,j)*Factorial(n+j)/2^j: j in [0..n]]): n in [0..30]]; // G. C. Greubel, Sep 26 2023

Maple

a:= n-> add(binomial(n, k)*(n+k)!/2^k, k=0..n):
seq(a(n), n=0..20);  # Alois P. Heinz, Jul 21 2012

Mathematica

f[n_]:= Sum[Binomial[n,k]*(n+k)!/2^k, {k,0,n}]; Table[f[n], {n,0,20}]

SageMath

[sum(binomial(n,j)*factorial(n+j)//2^j for j in range(n+1)) for n in range(31)] # G. C. Greubel, Sep 26 2023

Formula

a(n) = Sum_{k=0..n} C(n,k) * (n+k)! / 2^k.

a(n) = n! * A001515(n).

A003011(n) = Sum_{k=0..n} C(n, k)*a(k).

a(n) = Gamma(n+1)*Hypergeometric2F0([-n, n+1], [], -1/2). - Peter Luschny, Jul 29 2014

a(n) ~ sqrt(Pi) * 2^(n + 1) * n^(2*n + 1/2) / exp(2*n - 1). - Vaclav Kotesovec, Nov 27 2017

From G. C. Greubel, Sep 26 2023: (Start)

a(n) = n*(2*n-1)*a(n-1) + n*(n-1)*a(n-2).

a(n) = e * sqrt(2/Pi) * n! * BesselK(n+1/2, 1).

a(n) = ((2*n)!/2^n) * Hypergeometric1F1(-n, -2*n, 2).

G.f.: (-2/x) * Integrate_{t=0..oo} exp(-t)/((t+1)^2 - 1 - 2/x) dt.

G.f.: e*( exp(-sqrt(1 + 2/x)) * ExpIntegralEi(-1 + sqrt(1 + 2/x)) - exp(sqrt(1 + 2/x)) * ExpIntegralEi(-1 - sqrt(1 + 2/x)) )/sqrt(x^2 + 2*x).

E.g.f.: ((1-x)/x) * Hypergeometric1F1(1, 3/2, -(1-x)^2/(2*x)).

E.g.f.: (1/(1-x))*Hypergeometric2F0([1, 1/2]; []; 2*x/(1-x)^2). (End)

Extensions

More terms from Robert G. Wilson v, Apr 23 2005