A002720 -id:A002720 - cp's OEIS frontend

A261763 Triangle read by rows: T(n,k) is the number of subpermutations of an n-set whose orbits are each of size at most k.

1, 1, 2, 1, 4, 7, 1, 8, 26, 34, 1, 16, 115, 179, 209, 1, 32, 542, 1102, 1402, 1546, 1, 64, 2809, 7609, 10759, 12487, 13327, 1, 128, 15374, 56534, 92234, 113402, 125162, 130922, 1, 256, 89737, 457993, 865393, 1139569, 1304209, 1396369, 1441729

Offset: 0

Samira Stitou, Sep 21 2015

			T(3, 2) = 26 because there are 26 subpermutations on {1,2,3}, each of whose orbit is of size at most 2, namely:
Empty map, 1-->1, 1-->2, 1-->3, 2-->1, 2-->2, 2-->3, 3-->1, 3-->2, 3-->3, (1,2) --> (1,2), (1,3) --> (1,3), (2,3) --> (2,3), (1,2) --> (2,1), (1,3) --> (3,1), (2,3) --> (3,2), (1,2) --> (1,3), (1,3) --> (1,2), (2,3) --> (2,1), (1,2) --> (3,2), (1,3) --> (2,3), (2,3) --> (1,3), (1,2,3) --> (1,3,2), (1,2,3) --> (3,2,1), (1,2,3) --> (2,1,3), (1,2,3) --> (1,2,3).
Triangle starts:
1;
1, 2;
1, 4, 7;
1, 8, 26, 34;
1, 16, 115, 179, 209;
...

A. Laradji and A. Umar, On the number of subpermutations with fixed orbit size, Ars Combinatoria, 109 (2013), 447-460.

Cf. A157400, A261762, A261764, A261765, A261766, A261767.

T(n,n) = A002720(n).
T(n,k) = Sum_{i=0..n} binomial(n,i)*A261762(n-i,k).
E.g.f. of column k: exp(Sum_{j=1..k} (j+1)*x^j/j).

More terms from Alois P. Heinz, Oct 07 2015

A277372 a(n) = Sum_{k=1..n} binomial(n,n-k)n^(n-k)n!/(n-k)!.

Original entry on oeis.org

0, 1, 10, 141, 2584, 58745, 1602576, 51165205, 1874935168, 77644293201, 3588075308800, 183111507687581, 10230243235200000, 621111794820235849, 40722033570202507264, 2867494972696071121125, 215840579093024990396416, 17294837586403146090259745, 1469799445329208661211021312

Offset: 0

Peter Luschny, Oct 11 2016

nonn

Cf. A097662, A239768.

Cf. A002720, A087912, A277382.

a := n -> add(binomial(n,n-k)*n^(n-k)*n!/(n-k)!, k=1..n):
seq(a(n), n=0..18);
# Alternatively:
A277372 := n -> n!*LaguerreL(n,-n) - n^n:
seq(simplify(A277372(n)), n=0..18);

a(n) = sum(k=1, n, binomial(n,n-k)*n^(n-k)*n!/(n-k)!); \\ Michel Marcus, Oct 12 2016

a(n) = n!*LaguerreL(n, -n) - n^n.
a(n) = (-1)^n*KummerU(-n, 1, -n) - n^n.
a(n) = n^n*(hypergeom([-n, -n], [], 1/n) - 1) for n>=1.
a(n) ~ n^n * phi^(2*n+1) * exp(n/phi-n) / 5^(1/4), where phi = A001622 = (1+sqrt(5))/2 is the golden ratio. - Vaclav Kotesovec, Oct 12 2016

A293985 Square array A(n,k), n >= 0, k >= 0, read by antidiagonals, where column k is the expansion of e.g.f. exp(x/(1-x))/(1-x)^k.

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 1, 3, 7, 13, 1, 4, 13, 34, 73, 1, 5, 21, 73, 209, 501, 1, 6, 31, 136, 501, 1546, 4051, 1, 7, 43, 229, 1045, 4051, 13327, 37633, 1, 8, 57, 358, 1961, 9276, 37633, 130922, 394353, 1, 9, 73, 529, 3393, 19081, 93289, 394353, 1441729, 4596553

Offset: 0

Seiichi Manyama, Oct 21 2017

			Square array begins:
    1,    1,    1,    1,     1, ... A000012;
    1,    2,    3,    4,     5, ... A000027;
    3,    7,   13,   21,    31, ... A002061;
   13,   34,   73,  136,   229, ... A135859;
   73,  209,  501, 1045,  1961, ...
  501, 1546, 4051, 9276, 19081, ...
Antidiagonal rows begin as:
  1;
  1, 1;
  1, 2,  3;
  1, 3,  7, 13;
  1, 4, 13, 34,  73;
  1, 5, 21, 73, 209, 501; - _G. C. Greubel_, Mar 09 2021

Seiichi Manyama, Antidiagonals n = 0..139, flattened
Wikipedia, Laguerre polynomials
Index entries for sequences related to Laguerre polynomials

Columns k=0..6 give: A000262, A002720, A000262(n+1), A052852(n+1), A062147, A062266, A062192.
Main diagonal gives A152059.
Similar table: A086885, A088699, A176120.

function t(n,k)
  if n eq 0 then return 1;
  else return Factorial(n-1)*(&+[(j+k)*t(n-j,k)/Factorial(n-j): j in [1..n]]);
  end if; return t;
end function;
[t(k,n-k): k in [0..n], n in [0..12]]; // G. C. Greubel, Mar 09 2021

t[n_, k_]:= t[n, k]= If[n==0, 1, (n-1)!*Sum[(j+k)*t[n-j,k]/(n-j)!, {j,n}]];
T[n_,k_]:= t[k,n-k]; Table[T[n,k], {n,0,12}, {k,0,n}]//Flatten (* G. C. Greubel, Mar 09 2021 *)

@CachedFunction
def t(n,k): return 1 if n==0 else factorial(n-1)*sum( (j+k)*t(n-j,k)/factorial(n-j) for j in (1..n) )
def T(n,k): return t(k,n-k)
flatten([[T(n,k) for k in (0..n)] for n in (0..12)]) # G. C. Greubel, Mar 09 2021

A(0,k) = 1 and A(n,k) = (n-1)! * Sum_{j=1..n} (j+k)*A(n-j,k)/(n-j)! for n > 0.
A(0,k) = 1, A(1,k) = k+1 and A(n,k) = (2*n-1+k)*A(n-1,k) - (n-1)*(n-2+k)*A(n-2,k) for n > 1.
From Seiichi Manyama, Jan 25 2025: (Start)
A(n,k) = n! * Sum_{j=0..n} binomial(n+k-1,j)/(n-j)!.
A(n,k) = n! * LaguerreL(n, k-1, -1). (End)

A308111 Isomorphism classes of Eulerian digraphs with n vertices, allowing loops.

Original entry on oeis.org

1, 2, 6, 24, 160, 2512, 129816, 22665792, 13056562208, 24953006054144, 160860329639968800, 3555065836569542246400, 273147301191314006316868352, 73832333258502021627712839197696, 70920540648597652305602460997787710080, 244186544390677638132290202415190606165938176, 3036252267734950687777830287721323374283100639476736

Offset: 0

Brendan McKay, May 11 2019

Eulerian means that for every vertex the in-degree equals the out-degree.

			For n=2 the a(2)=6 solutions are: two non-adjacent vertices with or without loops (3 cases), two vertices with or without loops connected by edges in each direction (3 cases).

Gus Wiseman, Non-isomorphic representatives of the a(3) = 24 Eulerian digraphs with loops.

For labeled digraphs rather than isomorphism classes see A229865.
For isomorphism classes with loops forbidden see A058338.
Cf. A308128 (connected version of this).
Cf. A000273, A000595, A002416, A002720, A308161.

Euler transform of A308128.

Terms a(10) and beyond from Andrew Howroyd, Apr 12 2020

A341014 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals, where T(n,k) = Sum_{j=0..n} k^j * j! * binomial(n,j)^2.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 1, 3, 7, 1, 1, 4, 17, 34, 1, 1, 5, 31, 139, 209, 1, 1, 6, 49, 352, 1473, 1546, 1, 1, 7, 71, 709, 5233, 19091, 13327, 1, 1, 8, 97, 1246, 13505, 95836, 291793, 130922, 1, 1, 9, 127, 1999, 28881, 318181, 2080999, 5129307, 1441729, 1

Offset: 0

Seiichi Manyama, Feb 02 2021

			Square array begins:
  1,    1,     1,     1,      1,      1, ...
  1,    2,     3,     4,      5,      6, ...
  1,    7,    17,    31,     49,     71, ...
  1,   34,   139,   352,    709,   1246, ...
  1,  209,  1473,  5233,  13505,  28881, ...
  1, 1546, 19091, 95836, 318181, 830126, ...

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

Columns 0..4 give A000012, A002720, A025167, A102757, A102773.
Rows 0..2 give A000012, A000027(n+1), A056220(n+1).
Main diagonal gives A330260.
Cf. A307883.

T[n_, k_] := Sum[If[j == k == 0, 1, k^j]*j!*Binomial[n, j]^2, {j, 0, n}]; Table[T[k, n - k], {n, 0, 9}, {k, 0, n}] // Flatten (* Amiram Eldar, Feb 02 2021 *)

{T(n,k) = sum(j=0, n, k^j*j!*binomial(n, j)^2)}

E.g.f. of column k: exp(x/(1-k*x)) / (1-k*x).

T(n,k) = (2*k*n-k+1) * T(n-1,k) - k^2 * (n-1)^2 * T(n-2,k) for n > 1.

A361600 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where T(n,k) = n! * Sum_{j=0..n} binomial(n+(k-1)j,kj)/j!.

Original entry on oeis.org

1, 1, 2, 1, 2, 5, 1, 2, 7, 16, 1, 2, 9, 34, 65, 1, 2, 11, 58, 209, 326, 1, 2, 13, 88, 473, 1546, 1957, 1, 2, 15, 124, 881, 4626, 13327, 13700, 1, 2, 17, 166, 1457, 10526, 52537, 130922, 109601, 1, 2, 19, 214, 2225, 20326, 145867, 677594, 1441729, 986410

Offset: 0

Seiichi Manyama, Mar 17 2023

			Square array begins:
    1,    1,    1,     1,     1,     1, ...
    2,    2,    2,     2,     2,     2, ...
    5,    7,    9,    11,    13,    15, ...
   16,   34,   58,    88,   124,   166, ...
   65,  209,  473,   881,  1457,  2225, ...
  326, 1546, 4626, 10526, 20326, 35226, ...

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

Columns k=0..3 give A000522, A002720, A361598, A361599.
Main diagonal gives A361607.
Cf. A293012.

T(n, k) = n!*sum(j=0, n, binomial(n+(k-1)*j, k*j)/j!);

E.g.f. of column k: exp( x/(1 - x)^k ) / (1-x).

T(n,k) = Sum_{j=0..n} (n+(k-1)*j)!/(k*j)! * binomial(n,j).

A098436 Triangle of 3rd central factorial numbers T(n,k).

Original entry on oeis.org

1, 1, 1, 1, 9, 1, 1, 73, 36, 1, 1, 585, 1045, 100, 1, 1, 4681, 28800, 7445, 225, 1, 1, 37449, 782281, 505280, 35570, 441, 1, 1, 299593, 21159036, 33120201, 4951530, 130826, 784, 1, 1, 2396745, 571593565, 2140851900, 652061451, 33209946, 399738, 1296, 1

Offset: 0

Ralf Stephan, Sep 08 2004

			  1;
  1,   1;
  1,   9,    1;
  1,  73,   36,   1;
  1, 585, 1045, 100, 1;
  ...

M. Domaratzki, A Generalization of the Genocchi Numbers with Applications to Enumeration of Finite Automata, Technical Report No. 2001-449, September 2001, 11 pages.
John Riordan, Letter, Apr 28 1976.

First column is A023001, first diagonal is A000537.
Row sums are in A098437.
Replace in recurrence (k+1)^3 with k: A008277; with k^2: A008957 (note offsets).

A098436 := proc(n,k)
    option remember;
    if k=0 or k = n then
        1;
    else
        (k+1)^3*procname(n-1,k)+procname(n-1,k-1) ;
    end if;
end proc:
seq(seq( A098436(n,k),k=0..n),n=0..12) ; # R. J. Mathar, Jan 13 2025

T[n_, n_] = 1;
T[n_ /; n>=0, k_] /; 0<=k<=n := T[n, k] = (k+1)^3 T[n-1, k]+T[n-1, k-1];
T[, ] = 0;
Table[T[n, k], {n, 0, 8}, {k, 0, n}] // Flatten (* Jean-François Alcover, May 08 2022 *)

Recurrence: T(n, k) = (k+1)^3*T(n-1, k) + T(n-1, k-1), T(0, 0)=1.

A121630 Finite sum involving signless Stirling numbers of the first kind and the Bell numbers. Appears in the process of normal ordering of n-th power of (a)^3(a+a), where a+ and a are boson creation and annihilation operators, respectively.

Original entry on oeis.org

1, 4, 29, 302, 4089, 68056, 1342949, 30635074, 792915057, 22952573484, 734630159341, 25757268041814, 981687991859689, 40407710444419072, 1786311057929722549, 84404172618241446506, 4244839086310722228449

Offset: 0

Karol A. Penson, Aug 12 2006

nonn

Cf. A002720, A121629, A121631, A239301.

CoefficientList[Series[E^(((1-3*x)^(-1/3))-1)/(1-3*x), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Mar 14 2014 *)

a(n)=sum(abs(stirling1(n+1,p))*3^(n-p+1)*bell(p-1),p=1..n+1), n=0,1....
E.g.f.: exp(((1-3*x)^(-1/3))-1)/(1-3*x). - Vladeta Jovovic, Aug 13 2006
Recurrence: a(n) = 3*(4*n - 5)*a(n-1) - (54*n^2 - 189*n + 173)*a(n-2) + (108*n^3 - 729*n^2 + 1659*n - 1271)*a(n-3) - 9*(n-3)^2*(3*n - 8)*(3*n - 7)*a(n-4). - Vaclav Kotesovec, Mar 14 2014
a(n) ~ 1/2 * 3^(n+7/8) * exp(4*n^(1/4)/3^(3/4) - n - 1) * n^(n+3/8). - Vaclav Kotesovec, Mar 14 2014

A121631 Finite sum involving signless Stirling numbers of the first kind and the Bell numbers. Appears in the process of normal ordering of n-th power of (a)^4(a+a), where a+ and a are boson creation and annihilation operators, respectively.

Original entry on oeis.org

1, 5, 46, 613, 10679, 229576, 5868715, 173833661, 5853205468, 220767370219, 9219128625851, 422221005543250, 21041188313139901, 1133454896301865073, 65627299232007207934, 4064319309355535125201, 268077821490093243979235

Offset: 0

Karol A. Penson, Aug 12 2006

nonn

Cf. A002720, A121629, A121630, A239301.

CoefficientList[Series[E^(((1-4*x)^(-1/4))-1)/(1-4*x), {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Mar 14 2014 *)

a(n)=sum(abs(stirling1(n+1,p))*4^(n-p+1)*bell(p-1),p=1..n+1), n=0,1....
E.g.f.: exp(((1-4*x)^(-1/4))-1)/(1-4*x). - Vladeta Jovovic, Aug 13 2006
Recurrence: a(n) = 2*(10*n - 17)*a(n-1) - (160*n^2 - 704*n + 811)*a(n-2) + 2*(320*n^3 - 2592*n^2 + 7138*n - 6675)*a(n-3) - (1280*n^4 - 16384*n^3 + 79120*n^2 - 170816*n + 139079)*a(n-4) + 32*(n-4)^2*(2*n - 7)*(4*n - 15)*(4*n - 13)*a(n-5). - Vaclav Kotesovec, Mar 14 2014
a(n) ~ 1/sqrt(5) * 2^(2*n+9/5) * exp(5*n^(1/5)/2^(8/5)-n-1) * n^(n+2/5). - Vaclav Kotesovec, Mar 14 2014

A144088 T(n,k) is the number of partial bijections (or subpermutations) of an n-element set with exactly k fixed points.

Original entry on oeis.org

1, 1, 1, 4, 2, 1, 18, 12, 3, 1, 108, 72, 24, 4, 1, 780, 540, 180, 40, 5, 1, 6600, 4680, 1620, 360, 60, 6, 1, 63840, 46200, 16380, 3780, 630, 84, 7, 1, 693840, 510720, 184800, 43680, 7560, 1008, 112, 8, 1, 8361360, 6244560, 2298240, 554400, 98280, 13608, 1512, 144, 9, 1

Offset: 0

Abdullahi Umar, Sep 11 2008, Sep 16 2008

			Triangle begins:
      1;
      1,     1;
      4,     2,     1;
     18,    12,     3,    1;
    108,    72,    24,    4,   1;
    780,   540,   180,   40,   5,  1;
   6600,  4680,  1620,  360,  60,  6, 1;
  63840, 46200, 16380, 3780, 630, 84, 7, 1;
  ...
T(3,1) = 12 because there are exactly 12 partial bijections (on a 3-element set) with exactly 1 fixed point, namely: (1)->(1), (2)->(2), (3)->(3), (1,2)->(1,3), (1,2)->(3,2), (1,3)->(1,2), (1,3)->(2,3), (2,3)->(2,1), (2,3)->(1,3), (1,2,3)->(1,3,2), (1,2,3)->(3,2,1), (1,2,3)->(2,1,3) -- the mappings are coordinate-wise.

Andrew Howroyd, Table of n, a(n) for n = 0..1325 (rows n = 0..50)
A. Laradji and A. Umar, Combinatorial results for the symmetric inverse semigroup, Semigroup Forum 75, (2007), 221-236.
A. Umar, Some combinatorial problems in the theory of symmetric ..., Algebra Disc. Math. 9 (2010) 115-126.

T(n, 0) = A144085, T(n, 1) = A144086, T(n, 2) = A144087.

Row sums give A002720.

max = 7; f[x_, k_] := (x^k/k!)*(Exp[x^2/(1-x)]/(1-x)); t[n_, k_] := n!*SeriesCoefficient[ Series[ f[x, k], {x, 0, max}], n]; Flatten[ Table[ t[n, k], {n, 0, max}, {k, 0, n}]](* Jean-François Alcover, Mar 12 2012, from e.g.f. by Joerg Arndt *)

T(n) = {my(egf=exp(log(1/(1-x) + O(x*x^n)) - x + y*x + x/(1-x))); Vec([Vecrev(p) | p<-Vec(serlaplace(egf))])}
{ my(A=T(10)); for(n=1, #A, print(A[n])) } \\ Andrew Howroyd, Nov 29 2021

T(n,k) = C(n,k)*(n-k)! * Sum_{m=0..n-k} (-1^m/m!)*Sum_{j=0..n-m} C(n-m,j)/j!.
(n-k)*T(n,k) = n*(2n-2k-1)*T(n-1,k) - n*(n-1)*(n-k-3)*T(n-2,k) - n*(n-1)*(n-2)*T(n-3,k), T(k,k)=1 and T(n,k)=0 if n < k.
E.g.f.: exp(log(1/(1-x)) - x + y*x)*exp(x/(1-x)). - Geoffrey Critzer, Nov 29 2021
T(n,k) = (n!/k!) * Sum_{j=0..n-k} binomial(j,n-k-j)/(n-k-j)!. - Seiichi Manyama, Aug 06 2024

Terms a(36) and beyond from Andrew Howroyd, Nov 29 2021

cp's OEIS Frontend

A261763 Triangle read by rows: T(n,k) is the number of subpermutations of an n-set whose orbits are each of size at most k.

Views

Author

Keywords

Examples

References

Crossrefs

Formula

Extensions

A277372 a(n) = Sum_{k=1..n} binomial(n,n-k)*n^(n-k)*n!/(n-k)!.

Views

Author

Keywords

Crossrefs

Programs

Maple

PARI

Formula

A293985 Square array A(n,k), n >= 0, k >= 0, read by antidiagonals, where column k is the expansion of e.g.f. exp(x/(1-x))/(1-x)^k.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Mathematica

Sage

Formula

A308111 Isomorphism classes of Eulerian digraphs with n vertices, allowing loops.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A341014 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals, where T(n,k) = Sum_{j=0..n} k^j * j! * binomial(n,j)^2.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A361600 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where T(n,k) = n! * Sum_{j=0..n} binomial(n+(k-1)*j,k*j)/j!.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A098436 Triangle of 3rd central factorial numbers T(n,k).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A121630 Finite sum involving signless Stirling numbers of the first kind and the Bell numbers. Appears in the process of normal ordering of n-th power of (a)^3*(a+*a), where a+ and a are boson creation and annihilation operators, respectively.

Views

Author

Keywords

Crossrefs

Programs

Mathematica

A277372 a(n) = Sum_{k=1..n} binomial(n,n-k)n^(n-k)n!/(n-k)!.

A361600 Square array T(n,k), n >= 0, k >= 0, read by antidiagonals downwards, where T(n,k) = n! * Sum_{j=0..n} binomial(n+(k-1)j,kj)/j!.

A121630 Finite sum involving signless Stirling numbers of the first kind and the Bell numbers. Appears in the process of normal ordering of n-th power of (a)^3(a+a), where a+ and a are boson creation and annihilation operators, respectively.

A121631 Finite sum involving signless Stirling numbers of the first kind and the Bell numbers. Appears in the process of normal ordering of n-th power of (a)^4(a+a), where a+ and a are boson creation and annihilation operators, respectively.