cp's OEIS Frontend

A002720 Number of partial permutations of an n-set; number of n X n binary matrices with at most one 1 in each row and column.

%I A002720 M1795 N0708 #348 May 04 2025 04:17:10
%S A002720 1,2,7,34,209,1546,13327,130922,1441729,17572114,234662231,3405357682,
%T A002720 53334454417,896324308634,16083557845279,306827170866106,
%U A002720 6199668952527617,132240988644215842,2968971263911288999,69974827707903049154,1727194482044146637521,44552237162692939114282
%N A002720 Number of partial permutations of an n-set; number of n X n binary matrices with at most one 1 in each row and column.
%C A002720 a(n) is also the total number of increasing subsequences of all permutations of [1..n] (see Lifschitz and Pittel). - _N. J. A. Sloane_, May 06 2012
%C A002720 a(n) = A000142 + A001563 + A001809 + A001810 + A001811 + A001812 + ... these sequences respectively give the number of increasing subsequences of length i for i=0,1,2,... in all permutations of [1..n]. - _Geoffrey Critzer_, Jan 17 2013
%C A002720 a(n) is also the number of matchings in the complete bipartite graph K(n,n). - Sharon Sela (sharonsela(AT)hotmail.com), May 19 2002
%C A002720 a(n) is also the number of 12-avoiding signed permutations in B_n (see Simion ref).
%C A002720 a(n) is also the order of the symmetric inverse semigroup (monoid) I_n. - A. Umar, Sep 09 2008
%C A002720 EXP transform of A001048(n) = n! + (n-1)!. - _Franklin T. Adams-Watters_, Dec 28 2006
%C A002720 From _Peter Luschny_, Mar 27 2011: (Start)
%C A002720 Let B_{n}(x) = Sum_{j>=0} exp(j!/(j-n)!*x-1)/j!; then a(n) = 2! [x^2] Taylor(B_{n}(x)), where [x^2] denotes the coefficient of x^2 in the Taylor series for B_{n}(x).
%C A002720 a(n) is column 2 of the square array representation of A090210. (End)
%C A002720 a(n) is the Hosoya index of the complete bipartite graph K_{n,n}. - _Eric W. Weisstein_, Jul 09 2011
%C A002720 a(n) is also number of non-attacking placements of k rooks on an n X n board, summed over all k >= 0. - _Vaclav Kotesovec_, Aug 28 2012
%C A002720 Also the number of vertex covers and independent vertex sets in the n X n rook graph. - _Eric W. Weisstein_, Jan 04 2013
%C A002720 a(n) is the number of injective functions from subsets of [n] to [n] where [n]={1,2,...,n}. For a subset D of size k, there are n!/(n-k)! injective functions from D to [n]. Summing over all subsets, we obtain a(n) = Sum_{k=0..n} C(n,k)*n!/(n-k)! = Sum_{k=0..n} k!*C(n,k)^2. - _Dennis P. Walsh_, Nov 16 2015
%C A002720 Also the number of cliques in the n X n rook complement graph. - _Eric W. Weisstein_, Sep 14 2017
%C A002720 a(n)/n! is the expected value of the n-th term of Ulam's "history-dependent random sequence". See Kac (1989), Eq.(2). - _N. J. A. Sloane_, Nov 16 2019
%C A002720 a(2*n) is odd and a(2*n+1) is even for all n. More generally, for each positive integer k, a(n+k) == a(n) (mod k) for all n. It follows that for each positive integer k, the sequence obtained by reducing a(n) modulo k is periodic, with period dividing k. Various divisibility properties of the sequence follow from this: for example, a(7*n+2) == 0 (mod 7), a(11*n+4) == 0 (mod 11), a(17*n+3) == 0 (mod 17) and a(19*n+4) == 0 (mod 19). - _Peter Bala_, Nov 07 2022
%C A002720 Conjecture: a(n)*k is the sum of the largest parts in all integer partitions containing their own first differences with n + 1 parts and least part k. - _John Tyler Rascoe_, Feb 28 2024
%D A002720 J. M. Howie, Fundamentals of semigroup theory. Oxford: Clarendon Press, (1995). [From A. Umar, Sep 09 2008]
%D A002720 J. Ser, Les Calculs Formels des Séries de Factorielles. Gauthier-Villars, Paris, 1933, p. 78.
%D A002720 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A002720 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A002720 H. S. Wall, Analytic Theory of Continued Fractions, Chelsea 1973, p. 356.
%H A002720 Alois P. Heinz, <a href="/A002720/b002720.txt">Table of n, a(n) for n = 0..443</a> (first 101 terms from T. D. Noe)
%H A002720 Francesca Aicardi, Diego Arcis, and Jesús Juyumaya, <a href="https://arxiv.org/abs/2210.17461">Ramified inverse and planar monoids</a>, arXiv:2210.17461 [math.RT], 2022.
%H A002720 A. I. Aptekarev, <a href="http://arxiv.org/abs/0902.1768">On linear forms containing the Euler constant</a>, arXiv:0902.1768 [math.NT], 2009.
%H A002720 T. Banica, <a href="http://arxiv.org/abs/1411.0577">The algebraic structure of quantum partial isometries</a>, arXiv:1411.0577 [math.OA], 2014-2015.
%H A002720 C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou-Beauchamps, <a href="http://dx.doi.org/10.1016/S0012-365X(01)00250-3">Generating Functions for Generating Trees</a>, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
%H A002720 Teo Banica, <a href="http://arxiv.org/abs/1401.5023">Algebraic invariants of truncated Fourier matrices</a>, arXiv preprint arXiv:1401.5023 [math.QA], 2014.
%H A002720 D. Borwein, S. Rankin, and L. Renner, <a href="http://dx.doi.org/10.1016/0012-365X(89)90272-0">Enumeration of injective partial transformations</a>, Discrete Math. (1989), 73: 291-296. [From A. Umar, Sep 09 2008]
%H A002720 D. Castellanos, <a href="https://web.archive.org/web/2024*/https://www.fq.math.ca/Scanned/27-5/castellanos.pdf">A generalization of Binet's formula and some of its consequences</a>, Fib. Quart., 27 (1989), 424-438.
%H A002720 Aria Chen, Tyler Cummins, Rishi De Francesco, Jate Greene, Tanya Khovanova, Alexander Meng, Tanish Parida, Anirudh Pulugurtha, Anand Swaroop, and Samuel Tsui, <a href="https://arxiv.org/abs/2405.21007">Card Tricks and Information</a>, arXiv:2405.21007 [math.HO], 2024. See p. 14.
%H A002720 Fabio Deelan Cunden, Jakub Czartowski, Giovanni Gramegna, and A. de Oliveira Junior, <a href="https://arxiv.org/abs/2410.23196">Relative volume of comparable pairs under semigroup majorization</a>, arXiv:2410.23196 [math-ph], 2024. See pp. 4, 15.
%H A002720 Dan Daly and Lara Pudwell, <a href="http://faculty.valpo.edu/lpudwell/slides/sandiego2013.pdf">Pattern avoidance in rook monoids</a>, Special Session on Patterns in Permutations and Words, Joint Mathematics Meetings, 2013. - From _N. J. A. Sloane_, Feb 03 2013
%H A002720 P. Flajolet and R. Sedgewick, <a href="http://algo.inria.fr/flajolet/Publications/books.html">Analytic Combinatorics</a>, 2009; see page 598.
%H A002720 Olof Giselsson, <a href="https://arxiv.org/abs/1801.10608">The Universal C*-Algebra of the Quantum Matrix Ball and its Irreducible *-Representations</a>, arXiv:1801.10608 [math.QA], 2018.
%H A002720 J. Godbout, <a href="http://www.uvm.edu/~jgodbout/mastersThesis/Thesis.pdf">Combinatorial Properties of the Mirabolic RSK Algorithm</a>, Thesis presented to The Faculty of the Graduate College of The University of Vermont, May 2013.
%H A002720 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=64">Encyclopedia of Combinatorial Structures 64</a>.
%H A002720 Z. Janelidze, F. van Niekerk, and J. Viljoen, <a href="https://arxiv.org/abs/2502.00704">What is the maximal connected partial symmetry index of a connected graph of a given size?</a>, arXiv:2502.00704 [math.CO], 2025. See p. 3.
%H A002720 Mark Kac, <a href="https://doi.org/10.1016/0196-8858(89)90014-6">A history-dependent random sequence defined by Ulam</a>, Advances in Applied Mathematics 10.3 (1989): 270-277.
%H A002720 Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Non-attacking chess pieces</a>, 6ed, 2013, p. 219.
%H A002720 Vaclav Kotesovec, <a href="https://oeis.org/wiki/User:Vaclav_Kotesovec">Too many errors around coefficient C1 in asymptotic of sequence A002720</a>, Sep 28 2012. [The bug in program Mathematica was fixed in version 10.2.0.0 / July 2015. _Vaclav Kotesovec_, Jul 25 2015]
%H A002720 V. Lifschitz and P. Pittel, <a href="http://dx.doi.org/10.1016/0097-3165(81)90049-2">The number of increasing subsequences of the random permutation</a> J. Combin. Theory Ser. A 31 (1981), no. 1, 1--20. MR0626437 (84e:05012)
%H A002720 Mathematica Stack Exchange, <a href="http://mathematica.stackexchange.com/questions/84077/wrong-limit-with-laguerrel">Wrong Limit with LaguerreL</a>, May 22 2015
%H A002720 W. D. Munn, <a href="http://dx.doi.org/10.1017/S0305004100031947">The characters of the symmetric inverse semigroup</a>, Proc. Cambridge Philos. Soc. 53 (1957), 13-18. [From A. Umar, Sep 09 2008]
%H A002720 K. A. Penson, P. Blasiak, A. Horzela, G. H. E. Duchamp, and A. I. Solomon, <a href="http://arxiv.org/abs/0904.0369">Laguerre-type derivatives: Dobinski relations and combinatorial identities</a>, J. Math. Phys. vol. 50, 083512 (2009).
%H A002720 Alexsandar Petojevic, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Petojevic/petojevic5.html">The Function vM_m(s; a; z) and Some Well-Known Sequences</a>, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7.
%H A002720 John Riordan, <a href="/A002720/a002720_2.pdf">Letter, Apr 28 1976</a>.
%H A002720 John Riordan, <a href="/A002720/a002720_1.pdf">Letter to N. J. A. Sloane, Oct 01 1978</a>.
%H A002720 John Riordan, <a href="/A002720/a002720_3.pdf">Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences</a>. Note that the sequences are identified by their N-numbers, not their A-numbers.
%H A002720 J. Ser, <a href="/A002720/a002720_4.pdf">Les Calculs Formels des Séries de Factorielles</a>, Gauthier-Villars, Paris, 1933 [Local copy].
%H A002720 J. Ser, <a href="/A002720/a002720.pdf">Les Calculs Formels des Séries de Factorielles</a>. (Annotated scans of some selected pages)
%H A002720 R. Simion, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v7i1r9/0">Combinatorial statistics on type-B analogues of non-crossing partitions and restricted permutations</a>, Electronic J. of Comb. 7 (2000), Art #R9.
%H A002720 A. Umar, <a href="http://www.mathnet.ru/adm33">Some combinatorial problems in the theory of symmetric ...</a>, Algebra Disc. Math. 9 (2010) 115-126.
%H A002720 Luis Verde-Star, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL24/Verde/verde4.html">A Matrix Approach to Generalized Delannoy and Schröder Arrays</a>, J. Int. Seq., Vol. 24 (2021), Article 21.4.1.
%H A002720 D. P. Walsh, <a href="http://capone.mtsu.edu/dwalsh/FINITEF.pdf">Notes on functions from subsets of {1,2,...,n} into {1,2,...,n}</a>.
%H A002720 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Clique.html">Clique</a>.
%H A002720 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CompleteBipartiteGraph.html">Complete Bipartite Graph</a>.
%H A002720 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependentVertexSet.html">Independent Vertex Set</a>.
%H A002720 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Matching.html">Matching</a>.
%H A002720 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RookComplementGraph.html">Rook Complement Graph</a>.
%H A002720 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/RookGraph.html">Rook Graph</a>.
%H A002720 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/VertexCover.html">Vertex Cover</a>.
%H A002720 <a href="/index/La#Laguerre">Index entries for sequences related to Laguerre polynomials</a>
%F A002720 a(n) = Sum_{k=0..n} k!*C(n, k)^2.
%F A002720 E.g.f.: (1/(1-x))*exp(x/(1-x)). - _Don Knuth_, Jul 1995
%F A002720 D-finite with recurrence: a(n) = 2*n*a(n-1) - (n-1)^2*a(n-2).
%F A002720 a(n) = Sum_{k>=0} (k+n)! / ((k!)^2*exp(1)). - _Robert G. Wilson v_, May 02 2002 [corrected by _Vaclav Kotesovec_, Aug 28 2012]
%F A002720 a(n) = Sum_{m>=0} (-1)^m*A021009(n, m). - _Philippe Deléham_, Mar 10 2004
%F A002720 a(n) = Sum_{k=0..n} C(n, k)n!/k!. - _Paul Barry_, May 07 2004
%F A002720 a(n) = Sum_{k=0..n} P(n, k)*C(n, k); a(n) = Sum_{k=0..n} n!^2/(k!*(n-k)!^2). - _Ross La Haye_, Sep 20 2004
%F A002720 a(n) = Sum_{k=0..n} (-1)^(n-k)*Stirling1(n, k)*Bell(k+1). - _Vladeta Jovovic_, Mar 18 2005
%F A002720 Define b(n) by b(0) = 1, b(n) = b(n-1) + (1/n) * Sum_{k=0..n-1} b(k). Then b(n) = a(n)/n!. - _Franklin T. Adams-Watters_, Sep 05 2005
%F A002720 Asymptotically, a(n)/n! ~ (1/2)*Pi^(-1/2)*exp(-1/2 + 2*n^(1/2))/n^(1/4) and so a(n) ~ C*BesselI(0, 2*sqrt(n))*n! with C = exp(-1/2) = 0.6065306597126334236... - Alec Mihailovs, Sep 06 2005, establishing a conjecture of _Franklin T. Adams-Watters_
%F A002720 a(n) = (n!/e) * Sum_{k>=0} binomial(n+k,n)/k!. - _Gottfried Helms_, Nov 25 2006
%F A002720 Integral representation as n-th moment of a positive function on a positive halfaxis (solution of the Stieltjes moment problem): a(n) = Integral_{x=0..oo} x^n*BesselI(0,2*sqrt(x))*exp(-x)/exp(1) dx, n >= 0. - _Karol A. Penson_ and G. H. E. Duchamp (gduchamp2(AT)free.fr), Jan 09 2007
%F A002720 a(n) = n! * LaguerreL[n, -1].
%F A002720 E.g.f.: exp(x) * Sum_{n>=0} x^n/n!^2 = Sum_{n>=0} a(n)*x^n/n!^2. - _Paul D. Hanna_, Nov 18 2011
%F A002720 From _Peter Bala_, Oct 11 2012: (Start)
%F A002720 Denominators in the sequence of convergents coming from Stieltjes's continued fraction for A073003, the Euler-Gompertz constant G := Integral_{x = 0..oo} 1/(1+x)*exp(-x) dx:
%F A002720 G = 1/(2 - 1^2/(4 - 2^2/(6 - 3^2/(8 - ...)))). See [Wall, Chapter 18, (92.7) with a = 1]. The sequence of convergents to the continued fraction begins [1/2, 4/7, 20/34, 124/209, ...]. The numerators are in A002793. (End)
%F A002720 G.f.: 1 = Sum_{n>=0} a(n) * x^n * (1 - (n+1)*x)^2. - _Paul D. Hanna_, Nov 27 2012
%F A002720 E.g.f.: exp(x/(1-x))/(1-x) = G(0)/(1-x) where G(k) = 1 + x/((2*k+1)*(1-x) - x*(1-x)*(2*k+1)/(x + (1-x)*(2*k+2)/G(k+1))); (continued fraction). - _Sergei N. Gladkovskii_, Dec 28 2012
%F A002720 a(n) = Sum_{k=0..n} L(n,k)*(k+1); L(n,k) the unsigned Lah numbers. - _Peter Luschny_, Oct 18 2014
%F A002720 a(n) = n! * A160617(n)/A160618(n). - _Alois P. Heinz_, Jun 28 2017
%F A002720 0 = a(n)*(-24*a(n+2) +99*a(n+3) -78*a(n+4) +17*a(n+5) -a(n+6)) +a(n+1)*(-15*a(n+2) +84*a(n+3) -51*a(n+4) +6*a(n+5)) +a(n+2)*(-6*a(n+2) +34*a(n+3) -15*a(n+4)) +a(n+3)*(+10*a(n+3)) for all n>=0. - _Michael Somos_, Jul 31 2018
%F A002720 a(n) = Sum_{k=0..n} C(n,k)*k!*A000262(n-k). - _Geoffrey Critzer_, Jan 07 2023
%F A002720 a(n) = A000262(n+1) - n * A000262(n). - _Werner Schulte_, Mar 29 2024
%F A002720 a(n) = denominator of (1 + n/(1 + n/(1 + (n-1)/(1 + (n-1)/(1 + ... + 1/(1 + 1/(1))))))). See A000262 for the numerators. - _Peter Bala_, Feb 11 2025
%e A002720 G.f. = 1 + 2*x + 7*x^2 + 34*x^3 + 209*x^4 + 1546*x^5 + 13327*x^6 + 130922*x^7 + ... - _Michael Somos_, Jul 31 2018
%p A002720 A002720 := proc(n) exp(-x)*n!*hypergeom([n+1], [1], x); simplify(subs(x=1, %)) end: seq(A002720(n), n=0..25); # _Peter Luschny_, Mar 30 2011
%p A002720 A002720 := proc(n)
%p A002720     option remember;
%p A002720     if n <= 1 then
%p A002720         n+1 ;
%p A002720     else
%p A002720         2*n*procname(n-1)-(n-1)^2*procname(n-2) ;
%p A002720     end if;
%p A002720 end proc: # _R. J. Mathar_, Mar 09 2017
%t A002720 Table[n! LaguerreL[n, -1], {n, 0, 25}]
%t A002720 Table[(-1)^n*HypergeometricU[-n, 1, -1], {n, 0, 25}] (* _Jean-François Alcover_, Jul 15 2015 *)
%t A002720 RecurrenceTable[{(n+1)^2 a[n] - 2(n+2) a[n+1] + a[n+2]==0, a[1]==2, a[2]==7}, a, {n, 25}] (* _Eric W. Weisstein_, Sep 27 2017 *)
%o A002720 (PARI) a(n) = sum(k=0, n, k!*binomial(n, k)^2 );
%o A002720 (PARI) a(n) = suminf ( k=0, binomial(n+k,n)/k! ) / ( exp(1)/n! ) /* _Gottfried Helms_, Nov 25 2006 */
%o A002720 (PARI) {a(n)=n!^2*polcoeff(exp(x+x*O(x^n))*sum(m=0,n,x^m/m!^2),n)} /* _Paul D. Hanna_, Nov 18 2011 */
%o A002720 (PARI) {a(n)=if(n==0,1,polcoeff(1-sum(m=0, n-1, a(m)*x^m*(1-(m+1)*x+x*O(x^n))^2), n))} /* _Paul D. Hanna_, Nov 27 2012 */
%o A002720 (PARI) my(x='x+O('x^22)); Vec(serlaplace((1/(1-x))*exp(x/(1-x)))) \\ _Joerg Arndt_, Aug 11 2022
%o A002720 (Magma) [Factorial(n)*Evaluate(LaguerrePolynomial(n), -1): n in [0..25]]; // _G. C. Greubel_, Aug 11 2022
%o A002720 (SageMath) [factorial(n)*laguerre(n, -1) for n in (0..25)] # _G. C. Greubel_, Aug 11 2022
%o A002720 (Python)
%o A002720 from math import factorial, comb
%o A002720 def A002720(n): return sum(factorial(k)*comb(n,k)**2 for k in range(n+1)) # _Chai Wah Wu_, Aug 31 2023
%Y A002720 Main diagonal of A088699. Column of A283500. Row sums of A144084.
%Y A002720 Cf. A000110, A020556, A069223, A000712, A001048, A090210, A002793, A073003, A000262.
%Y A002720 Column k=1 of A289192.
%Y A002720 Cf. A160617, A160618.
%Y A002720 Cf. A364673.
%K A002720 nonn,easy,nice
%O A002720 0,2
%A A002720 _N. J. A. Sloane_
%E A002720 2nd description from _R. H. Hardin_, Nov 1997
%E A002720 3rd description from _Wouter Meeussen_, Jun 01 1998