A003011 -id:A003011 - cp's OEIS frontend

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

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

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

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

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

Cf. A001515, A003011, A143990.
Replace "sets" by "lists": A099022.
Column n=2 of A181731.

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

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

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

[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

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)

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

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

Original entry on oeis.org

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

Offset: 0

Seiichi Manyama, May 19 2019

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

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

Seiichi Manyama, Antidiagonals n = 0..50, flattened

Columns k=0..4 give A000012, A000027(n+1), A030662(n+1), A144660, A144661.
Rows n=0..4 give A000012, A000522, A003011, A308294, A308295.
Main diagonal gives A274762.
Cf. A144510.

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.

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.

Original entry on oeis.org

1, 3, 10, 47, 313, 2744, 29751, 383273, 5713110, 96673861, 1830257967, 38326484944, 879473289521, 21944639630923, 591545277653354, 17131028946645255, 530424623323416617, 17485652721425863464, 611431929749388274471, 22604399407882099928577

Offset: 0

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

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

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

First differences: A001515.
Replacing "collection" by "sequence" gives A003011.
Replacing "sets" by "lists" gives A105747.

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

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

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

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
a(n) ~ 2^(n + 1/2) * n^n / exp(n-1). - Vaclav Kotesovec, May 05 2024

A082765 Trinomial transform of the factorial numbers (A000142).

Original entry on oeis.org

1, 4, 45, 1282, 70177, 6239016, 817234189, 147950506390, 35370826189857, 10791515504716012, 4091225768720823181, 1886585105032464025674, 1039774852573506696192385, 674970732343624159361034832

Offset: 0

Emanuele Munarini, May 21 2003

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

Robert A. Proctor, Let's Expand Rota's Twelvefold Way For Counting Partitions!, arXiv:math.CO/0606404, Jan 05, 2007
Index entries for related partition-counting sequences

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.

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

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

Original entry on oeis.org

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

Offset: 0

Paul Boddington, Nov 17 2003

			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, ...
  ... - _Robert FERREOL_, Nov 03 2017

Dennis Walsh, Width-Restricted Finite Functions

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.

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);
# Robert FERREOL, Nov 07 2017

T[n_, k_] := Sum[n!*k!/(2^i*(n - 2 i)!*(k - n + i)!*i!), {i, Max[0, n - k], Floor[n/2]}];
Table[T[n-k , k], {n, 0, 11}, {k, 0, n}] // Flatten (* Jean-François Alcover, Dec 05 2017, after Robert FERREOL *)

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)]
# Robert FERREOL, Oct 17 2017

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-2*i)!*(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

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

Original entry on oeis.org

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

Offset: 0

Paul D. Hanna, Jul 28 2008

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

			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,
...
Rows 6 and 8 appear in Park (2015). - _N. J. A. Sloane_, Jan 31 2016
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

Dennis Walsh, Width-restricted finite functions
Donghwi Park, Space-state complexity of Korean chess and Chinese chess, arXiv preprint arXiv:1507.06401, 2015

Cf. A003011 (row sums), A000680 (right border); diagonals: A012244, A036774, A003692.

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

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

{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])}

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.
Other diagonals include A036774 and A003692.
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![x^n](1+x+x^2/2)^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

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

SageMath

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A082765 Trinomial transform of the factorial numbers (A000142).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula