| Displaying 1-6 of 6 results found.
page
1
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.
+10
8
1, 2, 14, 222, 6384, 291720, 19445040, 1781750880, 214899027840, 33007837322880, 6290830003852800, 1456812592995513600, 402910665227270323200, 131173228963370155161600, 49656810289225281849907200, 21628258853895305337293568000, 10739534026001485514941587456000
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
FORMULA
a(n) = Sum_{k=0..n} C(n,k) * (n+k)! / 2^k.
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 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)
EXAMPLE
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}) }|.
MAPLE
a:= n-> add(binomial(n, k)*(n+k)!/2^k, k=0..n):
MATHEMATICA
f[n_]:= Sum[Binomial[n, k]*(n+k)!/2^k, {k, 0, n}]; Table[f[n], {n, 0, 20}]
PROG
(Magma) [(&+[Binomial(n, j)*Factorial(n+j)/2^j: j in [0..n]]): n in [0..30]]; // G. C. Greubel, Sep 26 2023 (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
CROSSREFS
Replace "sets" by "lists": A099022.
AUTHOR
Robert A. Proctor (www.math.unc.edu/Faculty/rap/), Apr 18 2005
A(n,k) = Sum_{i_1=0..n} Sum_{i_2=0..n} ... Sum_{i_k=0..n} multinomial(i_1 + i_2 + ... + i_k; i_1, i_2, ..., i_k), square array A(n,k) read by antidiagonals, for n >= 0, k >= 0.
+10
6
1, 1, 1, 1, 2, 1, 1, 5, 3, 1, 1, 16, 19, 4, 1, 1, 65, 271, 69, 5, 1, 1, 326, 7365, 5248, 251, 6, 1, 1, 1957, 326011, 1107697, 110251, 923, 7, 1, 1, 13700, 21295783, 492911196, 191448941, 2435200, 3431, 8, 1, 1, 109601, 1924223799, 396643610629, 904434761801, 35899051101, 55621567, 12869, 9, 1
COMMENTS
For r > 1, row r is asymptotic to sqrt(2*Pi) * (r*n)^(r*n + 1/2) / ((r!)^n * exp(r*n-1)). - Vaclav Kotesovec, May 24 2020
FORMULA
A(n,k) = Sum_{i=0..k*n} b(i) where Sum_{i=0..k*n} b(i) * x^i/i! = (Sum_{i=0..n} x^i/i!)^k.
EXAMPLE
For (n,k) = (3,2), (Sum_{i=0..3} x^i/i!)^2 = (1 + x + x^2/2 + x^3/6)^2 = 1 + 2*x + 4*x^2/2 + 8*x^3/6 + 14*x^4/24 + 20*x^5/120 + 20*x^6/720. So A(3,2) = 1 + 2 + 4 + 8 + 14 + 20 + 20 = 69.
Square array begins:
1, 1, 1, 1, 1, 1, ...
1, 2, 5, 16, 65, 326, ...
1, 3, 19, 271, 7365, 326011, ...
1, 4, 69, 5248, 1107697, 492911196, ...
1, 5, 251, 110251, 191448941, 904434761801, ...
1, 6, 923, 2435200, 35899051101, 1856296498826906, ...
1, 7, 3431, 55621567, 7101534312685, 4098746255797339511, ...
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.
+10
4
1, 3, 10, 47, 313, 2744, 29751, 383273, 5713110, 96673861, 1830257967, 38326484944, 879473289521, 21944639630923, 591545277653354, 17131028946645255, 530424623323416617, 17485652721425863464, 611431929749388274471, 22604399407882099928577
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:
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
Replacing "collection" by "sequence" gives A003011. Replacing "sets" by "lists" gives A105747.
AUTHOR
Robert A. Proctor (www.math.unc.edu/Faculty/rap/), Apr 18 2005
Trinomial transform of the factorial numbers ( A000142).
+10
3
1, 4, 45, 1282, 70177, 6239016, 817234189, 147950506390, 35370826189857, 10791515504716012, 4091225768720823181, 1886585105032464025674, 1039774852573506696192385, 674970732343624159361034832
COMMENTS
Number of ways to use the elements of {1,..,k}, 0<=k<=2n, once each to form a sequence of n (possibly empty) lists, each of length at most 2. - Bob Proctor, Apr 18 2005
FORMULA
a(n) = Sum[ Trinomial[n, k] k!, {k, 0, 2n} ] where Trinomial[n, k] = trinomial coefficients ( A027907) Integral_{x=0..infinity} (x^2+x+1)^n*exp(-x) dx - Gerald McGarvey, Oct 14 2006
CROSSREFS
a(n) = Sum[C(n, k)* A099022(k), 0<=k<=n] Replace "sequence" by "collection" in comment: A105747. Replace "lists" by "sets" in comment: A003011.
Array read by ascending antidiagonals: T(n,k) is the number of n-letter words from a k-letter alphabet such that no letter appears more than twice.
+10
2
1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 0, 4, 3, 1, 0, 0, 6, 9, 4, 1, 0, 0, 6, 24, 16, 5, 1, 0, 0, 0, 54, 60, 25, 6, 1, 0, 0, 0, 90, 204, 120, 36, 7, 1, 0, 0, 0, 90, 600, 540, 210, 49, 8, 1, 0, 0, 0, 0, 1440, 2220, 1170, 336, 64, 9, 1, 0, 0, 0, 0, 2520, 8100, 6120, 2226, 504, 81, 10, 1
FORMULA
T(n, k) = T(n, k-1) + n*T(n-1, k-1) + binomial(n, 2)*T(n-2, k-1) for n >= 2 and k >= 1.
T(n, k) = Sum_{i=max(0,n-k)..floor(n/2)} n!*k!/(2^i*(n-2i)!*(k-n+i)!*i!)). - Robert FERREOL, Oct 30 2017 T(n,k) = (-1)^n*n!*2^(-n/2)*GegenbauerC(n, -k, 1/sqrt(2)) for k >= n. - Robert Israel, Nov 08 2017 G.f.: Sum({n>=0} T(n,k)x^n)=n!(1 + x + x^2/2)^k. See Walsh link. - Robert FERREOL, Nov 14 2017
EXAMPLE
Array begins:
1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, ...
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, ...
0, 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, ...
0, 0, 6, 24, 60, 120, 210, 336, 504, 720, 990, ...
0, 0, 6, 54, 204, 540, 1170, 2226, 3864, 6264, 9630, ...
0, 0, 0, 90, 600, 2220, 6120, 14070, 28560, 52920, 91440, ...
0, 0, 0, 90, 1440, 8100, 29520, 83790, 201600, 430920, 842400, ...
0, 0, 0, 0, 2520, 25200, 128520, 463680, 1345680, 3356640, 7484400, ...
MAPLE
T:=(n, k)->add(n!*k!/(n-2*i)!/i!/(k-n+i)!/2^i, i=max(0, n-k)..n/2):
or
T:=proc(n, k) option remember :if n=0 then 1 elif n=1 then k elif k=0 then 0 else T(n, k-1)+n*T(n-1, k-1)+binomial(n, 2)*T(n-2, k-1) fi end:
or
T:=(n, k)-> n!*coeff((1 + x + x^2/2)^k, x, n):
seq(seq(T(n-k, k), k=0..n), n=0..20);
MATHEMATICA
T[n_, k_] := Sum[n!*k!/(2^i*(n - 2 i)!*(k - n + i)!*i!), {i, Max[0, n - k], Floor[n/2]}];
PROG
(Python)
from math import factorial as f
def T(n, k):
return sum(f(n)*f(k)//f(n-2*i)//f(i)//f(k-n+i)//2**i for i in range(max(0, n-k), n//2+1))
[T(n-k, k) for n in range(21) for k in range(n+1)]
CROSSREFS
T(1, k) = A001477(k); T(2, k) = A000290(k); T(3, k) = A007531(k); T(n, n) = A012244(n); T(n, n+1) = A036774(n); T(n, n+2) = A003692(n+1); T(2*n, n) = A000680(n); sum(T(n, k), n=0..2*k) = A003011(k); sum(T(r, n-r), r=0..n) = A089976(n). See A141765 for an irregular triangle version : T(n,k)= A141765(k,n) for n <= 2k.
Triangle T, read by rows, such that row n equals column 0 of matrix power M^n where M is a triangular matrix defined by M(k+m,k) = binomial(k+m,k) for m=0..2 and zeros elsewhere. Width-2-restricted finite functions.
+10
1
1, 1, 1, 1, 1, 2, 4, 6, 6, 1, 3, 9, 24, 54, 90, 90, 1, 4, 16, 60, 204, 600, 1440, 2520, 2520, 1, 5, 25, 120, 540, 2220, 8100, 25200, 63000, 113400, 113400, 1, 6, 36, 210, 1170, 6120, 29520, 128520, 491400, 1587600, 4082400, 7484400, 7484400, 1, 7, 49, 336, 2226
COMMENTS
T(k,n) is the number of distinct ways in which n labeled objects can be distributed in k labeled urns allowing at most 2 objects to fall in each urn. - N-E. Fahssi, Apr 22 2009 T(k,n) is the number of functions f:[n]->[k] such that the preimage set under f of any element of [k] has size 2 or less. - Dennis P. Walsh, Feb 15 2011
FORMULA
T(k,n) = n!*Sum_{i=ceiling(n/2)..k} binomial(k,i)*binomial(i,n-i)*2^(i-n). - Dennis P. Walsh, Feb 15 2011 T(n,2*n) = (2n)!/2^n; thus the rightmost border of T equals A000680. Main diagonal (central terms) equals A012244. Row sums of triangle T equals A003011, the number of permutations of up to n kinds of objects, where each kind of object can occur at most two times. T(k,n) = n^k. Double e.g.f.: Sum_{k,n} T(k,n)*(z^k/k!)*(x^n/n!) = exp(z(1+x+x^2/2)). - N-E. Fahssi, Apr 22 2009 T(j+k,n) = Sum_{i=0..n} binomial(n,i)*T(j,i)*T(k,n-i). - Dennis P. Walsh, Feb 15 2011
EXAMPLE
This triangle T begins:
1;
1, 1, 1;
1, 2, 4, 6, 6;
1, 3, 9, 24, 54, 90, 90;
1, 4, 16, 60, 204, 600, 1440, 2520, 2520;
1, 5, 25, 120, 540, 2220, 8100, 25200, 63000, 113400, 113400;
1, 6, 36, 210, 1170, 6120, 29520, 128520, 491400, 1587600, 4082400, 7484400, 7484400;
1, 7, 49, 336, 2226, 14070, 83790, 463680, 2346120, 10636920, 42071400, 139708800, 366735600, 681080400, 681080400,
1, 8, 64, 504, 3864, 28560, 201600, 1345680, 8401680, 48444480, 254016000, 1187524800, 4819953600, 16345929600, 43589145600, 81729648000, 81729648000,
1, 9, 81, 720, 6264, 52920, 430920, 3356640, 24811920, 172504080, 1116536400, 6646147200, 35835307200, 171632260800, 711047937600, 2451889440000, 6620101488000, 12504636144000, 12504636144000,
...
Let M be the triangular matrix that begins:
1;
1, 1;
1, 2, 1;
0, 3, 3, 1;
0, 0, 6, 4, 1;
0, 0, 0, 10, 5, 1; ...
where M(k+m,k) = C(k+m,k) for m=0,1,2 and zeros elsewhere.
Illustrate that row n of T = column 0 of M^n for n >= 0 as follows.
The matrix square M^2 begins:
1;
2, 1;
4, 4, 1;
6, 12, 6, 1;
6, 24, 24, 8, 1;
0, 30, 60, 40, 10, 1; ...
with column 0 of M^2 forming row 2 of T.
The matrix cube M^3 begins:
1;
3, 1;
9, 6, 1;
24, 27, 9, 1;
54, 96, 54, 12, 1;
90, 270, 240, 90, 15, 1;
90, 540, 810, 480, 135, 18, 1; ...
with column 0 of M^3 forming row 3 of T.
T(2,3)=6 because there are 6 ways to lodge 3 distinguishable balls, labeled by numbers 1,2 and 3, in 2 distinguishable boxes, each of which can hold at most 2 balls. - N-E. Fahssi, Apr 22 2009 T(5,8)=63000 because there are 63000 ways to assign 8 students to a dorm room when there are 5 different two-bed dorm rooms that are available. (See link for details of the count.) - Dennis P. Walsh, Feb 15 2011
MAPLE
seq(seq(n!*sum(binomial(k, j)*binomial(j, n-j)*2^(j-n), j=ceil(n/2)..k), n=0..2*k), k=1..10); # Dennis P. Walsh, Feb 15 2011
MATHEMATICA
T[k_, n_] := If[n == 0, 1, n! Coefficient[(1 + x + x^2/2)^k, x^n]]; TableForm[Table[T[k, n], {k, 0, 10}, {n, 0, 2 k}]] (* N-E. Fahssi, Apr 22 2009 *)
PROG
(PARI) {T(n, k)=local(M=matrix(n+1, n+1, n, k, if(n>=k, if(n-k<=2, binomial(n-1, k-1))))); if(k>2*n, 0, (M^n)[k+1, 1])}
Search completed in 0.008 seconds
| 