login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.
(Formerly M1795 N0708)
155
1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114, 234662231, 3405357682, 53334454417, 896324308634, 16083557845279, 306827170866106, 6199668952527617, 132240988644215842, 2968971263911288999, 69974827707903049154, 1727194482044146637521, 44552237162692939114282 (list; graph; refs; listen; history; text; internal format)
OFFSET
0,2
COMMENTS
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
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
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
a(n) is also the number of 12-avoiding signed permutations in B_n (see Simion ref).
a(n) is also the order of the symmetric inverse semigroup (monoid) I_n. - A. Umar, Sep 09 2008
EXP transform of A001048(n) = n! + (n-1)!. - Franklin T. Adams-Watters, Dec 28 2006
From Peter Luschny, Mar 27 2011: (Start)
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).
a(n) is column 2 of the square array representation of A090210. (End)
a(n) is the Hosoya index of the complete bipartite graph K_{n,n}. - Eric W. Weisstein, Jul 09 2011
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
Also the number of vertex covers and independent vertex sets in the n X n rook graph. - Eric W. Weisstein, Jan 04 2013
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
Also the number of cliques in the n X n rook complement graph. - Eric W. Weisstein, Sep 14 2017
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
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
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
REFERENCES
J. M. Howie, Fundamentals of semigroup theory. Oxford: Clarendon Press, (1995). [From A. Umar, Sep 09 2008]
J. Ser, Les Calculs Formels des Séries de Factorielles. Gauthier-Villars, Paris, 1933, p. 78.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
H. S. Wall, Analytic Theory of Continued Fractions, Chelsea 1973, p. 356
LINKS
Francesca Aicardi, Diego Arcis, and Jesús Juyumaya, Ramified inverse and planar monoids, arXiv:2210.17461 [math.RT], 2022.
A. I. Aptekarev, On linear forms containing the Euler constant, arXiv:0902.1768 [math.NT], 2009.
T. Banica, The algebraic structure of quantum partial isometries, arXiv:1411.0577 [math.OA], 2014-2015.
C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, Generating Functions for Generating Trees, Discrete Mathematics 246(1-3), March 2002, pp. 29-55.
Teo Banica, Algebraic invariants of truncated Fourier matrices, arXiv preprint arXiv:1401.5023 [math.QA], 2014.
D. Borwein, S. Rankin, S. and L. Renner, Enumeration of injective partial transformations, Discrete Math. (1989), 73: 291-296. [From A. Umar, Sep 09 2008]
D. Castellanos, A generalization of Binet's formula and some of its consequences, Fib. Quart., 27 (1989), 424-438.
Dan Daly and Lara Pudwell, Pattern avoidance in rook monoids, Special Session on Patterns in Permutations and Words, Joint Mathematics Meetings, 2013. - From N. J. A. Sloane, Feb 03 2013
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 598.
J. Godbout, Combinatorial Properties of the Mirabolic RSK Algorithm, Thesis presented to The Faculty of the Graduate College of The University of Vermont, May 2013.
Mark Kac, A history-dependent random sequence defined by Ulam, Advances in Applied Mathematics 10.3 (1989): 270-277.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 219.
Vaclav Kotesovec, Too many errors around coefficient C1 in asymptotic of sequence A002720, Sep 28 2012. [The bug in program Mathematica was fixed in version 10.2.0.0 / July 2015. Vaclav Kotesovec, Jul 25 2015]
V. Lifschitz and P. Pittel, The number of increasing subsequences of the random permutation J. Combin. Theory Ser. A 31 (1981), no. 1, 1--20. MR0626437 (84e:05012)
Mathematica Stack Exchange, Wrong Limit with LaguerreL, May 22 2015
W. D. Munn, The characters of the symmetric inverse semigroup, Proc. Cambridge Philos. Soc. 53 (1957), 13-18. [From A. Umar, Sep 09 2008]
K. A. Penson, P. Blasiak, A. Horzela, G. H. E. Duchamp and A. I. Solomon, Laguerre-type derivatives: Dobinski relations and combinatorial identities, J. Math. Phys. vol. 50, 083512 (2009)
Alexsandar Petojevic, The Function vM_m(s; a; z) and Some Well-Known Sequences, Journal of Integer Sequences, Vol. 5 (2002), Article 02.1.7
John Riordan, Letter, Apr 28 1976.
John Riordan, Letter to N. J. A. Sloane, Sep 26 1980 with notes on the 1973 Handbook of Integer Sequences. Note that the sequences are identified by their N-numbers, not their A-numbers.
J. Ser, Les Calculs Formels des Séries de Factorielles, Gauthier-Villars, Paris, 1933 [Local copy].
J. Ser, Les Calculs Formels des Séries de Factorielles (Annotated scans of some selected pages)
A. Umar, Some combinatorial problems in the theory of symmetric ..., Algebra Disc. Math. 9 (2010) 115-126.
Luis Verde-Star A Matrix Approach to Generalized Delannoy and Schröder Arrays, J. Int. Seq., Vol. 24 (2021), Article 21.4.1.
Eric Weisstein's World of Mathematics, Clique
Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Eric Weisstein's World of Mathematics, Independent Vertex Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Rook Complement Graph
Eric Weisstein's World of Mathematics, Rook Graph
Eric Weisstein's World of Mathematics, Vertex Cover
FORMULA
a(n) = Sum_{k=0..n} k!*C(n, k)^2.
E.g.f.: (1/(1-x))*exp(x/(1-x)). - Don Knuth, Jul 1995
D-finite with recurrence: a(n) = 2*n*a(n-1) - (n-1)^2*a(n-2).
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]
a(n) = Sum_{m>=0} (-1)^m*A021009(n, m). - Philippe Deléham, Mar 10 2004
a(n) = Sum_{k=0..n} C(n, k)n!/k!. - Paul Barry, May 07 2004
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
a(n) = Sum_{k=0..n} (-1)^(n-k)*Stirling1(n, k)*Bell(k+1). - Vladeta Jovovic, Mar 18 2005
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
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
a(n) = (n!/e) * Sum_{k>=0} binomial(n+k,n)/k!. - Gottfried Helms, Nov 25 2006
Integral representation as n-th moment of a positive function on a positive halfaxis (solution of the Stieltjes moment problem), in Maple notation: a(n) = int(x^n*BesselI(0,2*sqrt(x))*exp(-x)/exp(1), x=0..infinity), n=0,1... . - Karol A. Penson and G. H. E. Duchamp (gduchamp2(AT)free.fr), Jan 09 2007
a(n) = n! * LaguerreL[n, -1].
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
From Peter Bala, Oct 11 2012: (Start)
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:
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)
G.f.: 1 = Sum_{n>=0} a(n) * x^n * (1 - (n+1)*x)^2. - Paul D. Hanna, Nov 27 2012
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
a(n) = Sum_{k=0..n} L(n,k)*(k+1); L(n,k) the unsigned Lah numbers. - Peter Luschny, Oct 18 2014
a(n) = n! * A160617(n)/A160618(n). - Alois P. Heinz, Jun 28 2017
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
a(n) = Sum_{k=0..n} C(n,k)*k!*A000262(n-k). - Geoffrey Critzer, Jan 07 2023
EXAMPLE
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
MAPLE
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
A002720 := proc(n)
option remember;
if n <= 1 then
n+1 ;
else
2*n*procname(n-1)-(n-1)^2*procname(n-2) ;
end if;
end proc: # R. J. Mathar, Mar 09 2017
MATHEMATICA
Table[n! LaguerreL[n, -1], {n, 0, 25}]
Table[(-1)^n*HypergeometricU[-n, 1, -1], {n, 0, 25}] (* Jean-François Alcover, Jul 15 2015 *)
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 *)
PROG
(PARI) a(n) = sum(k=0, n, k!*binomial(n, k)^2 );
(PARI) a(n) = suminf ( k=0, binomial(n+k, n)/k! ) / ( exp(1)/n! ) /* Gottfried Helms, Nov 25 2006 */
(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 */
(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 */
(PARI) my(x='x+O('x^22)); Vec(serlaplace((1/(1-x))*exp(x/(1-x)))) \\ Joerg Arndt, Aug 11 2022
(Magma) [Factorial(n)*Evaluate(LaguerrePolynomial(n), -1): n in [0..25]]; // G. C. Greubel, Aug 11 2022
(SageMath) [factorial(n)*laguerre(n, -1) for n in (0..25)] # G. C. Greubel, Aug 11 2022
(Python)
from math import factorial, comb
def A002720(n): return sum(factorial(k)*comb(n, k)**2 for k in range(n+1)) # Chai Wah Wu, Aug 31 2023
CROSSREFS
Main diagonal of A088699. Column of A283500. Row sums of A144084.
Column k=1 of A289192.
Cf. A364673.
Sequence in context: A112916 A145845 A355292 * A234239 A249833 A111539
KEYWORD
nonn,easy,nice
AUTHOR
EXTENSIONS
2nd description from R. H. Hardin, Nov 1997
3rd description from Wouter Meeussen, Jun 01 1998
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 18 22:50 EDT 2024. Contains 370951 sequences. (Running on oeis4.)