login
This site is supported by donations 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)
45
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 count 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 lattice graph. - Eric W. Weisstein Jan 04, 2013

REFERENCES

C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy and D. Gouyou-Beauchamps, [http://algo.inria.fr/banderier/Papers/DiscMath99.ps Generating Functions for Generating Trees], Discrete Mathematics 246(1-3), March 2002, pp. 29-55.

Borwein, D., Rankin, S. and Renner, L. 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.

D. Daly and L. Pudwell, Pattern avoidance in rook monoids, 2013; http://faculty.valpo.edu/lpudwell/slides/sandiego2013.pdf. - From N. J. A. Sloane, Feb 03 2013

J. Godbout, Combinatorial Properties of the Mirabolic RSK Algorithm, Thesis presented to The Faculty of the Graduate College of The University of Vermont, http://www.uvm.edu/~jgodbout/mastersThesis/Thesis.pdf, May 2013.

J. M. Howie, Fundamentals of semigroup theory. Oxford: Clarendon Press, (1995). [From A. Umar, Sep 09 2008]

Lifschitz, V.; Pittel, B. The number of increasing subsequences of the random permutation. J. Combin. Theory Ser. A 31 (1981), no. 1, 1--20. MR0626437 (84e:05012)

Munn, W. D. The characters of the symmetric inverse semigroup. Proc. Cambridge Philos. Soc. 53 (1957), 13-18. [From A. Umar, Sep 09 2008]

J. Ser, Les Calculs Formels des S\'{e}ries de Factorielles. Gauthier-Villars, Paris, 1933, p. 78.

R. Simion, Combinatorial statistics on type-B analogues of non-crossing partitions and restricted permutations, Electronic J. of Comb. 7 (2000), Art #R9

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

T. D. Noe, Table of n, a(n) for n=0..100

A. I. Aptekarev, On linear forms containing the Euler constant, arXiv:0902.1768.

Teo Banica, Algebraic invariants of truncated Fourier matrices, arXiv preprint arXiv:1401.5023, 2014

P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 598

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 64

V. Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 219.

V. Kotesovec, Too many errors around coefficient C1 in asymptotic of sequence A002720, Sep 28 2012

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

Eric Weisstein's World of Mathematics, Complete Bipartite Graph

Eric Weisstein's World of Mathematics, Hosoya Index

Eric Weisstein's World of Mathematics, Independent Vertex Set

Eric Weisstein's World of Mathematics, Lattice Graph

Eric Weisstein's World of Mathematics, Vertex Cover

Index entries for sequences related to Laguerre polynomials

FORMULA

a(n) = sum(k=0..n, k!*C(n, k)^2 ).

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

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(P(n, k)C(n, k) {k=0...n}); a(n) = Sum(n!^2 / k!(n-k)!^2 {k=0...n}). - 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_{0<=k<n} 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) = .6065306597126334236... - Alec Mihailovs, Sep 06 2005, establishing a conjecture of Franklin T. Adams-Watters.

a(n) = sum {k=0..inf}[binomial(n+k,n)/k!] * n! / exp(1) - 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... . From 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' continued fraction for A073003, the Euler-Gompertz constant G := int {x = 0..inf} 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) )); (recursively defined 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

MAPLE

A002720 := proc(n) local i; exp(-x)*n!*hypergeom([n+1], [1], x); round(evalf(subs(x=1, %), 99)) end: seq(A002720 (n), n=0..18); # Peter Luschny, Mar 30, 2011

MATHEMATICA

Table[ n! LaguerreL[ n, -1 ], {n, 0, 12} ].

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

CROSSREFS

Main diagonal of A088699.

Cf. A000110, A020556, A069223, A000712, A001048, A090210, A002793, A073003.

Sequence in context: A011800 A112916 A145845 * A234239 A111539 A074059

Adjacent sequences:  A002717 A002718 A002719 * A002721 A002722 A002723

KEYWORD

nonn,easy,nice,changed

AUTHOR

N. J. A. Sloane.

EXTENSIONS

E.g.f. from D. E. Knuth 7/95. 2nd description from R. H. Hardin 11/97. 3rd description from Wouter Meeussen, Jun 01 1998.

More terms from James A. Sellers, Jul 29 2000

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified October 25 19:24 EDT 2014. Contains 248557 sequences.