|
| |
|
|
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)
|
|
34
| |
|
|
1, 2, 7, 34, 209, 1546, 13327, 130922, 1441729, 17572114, 234662231, 3405357682, 53334454417, 896324308634, 16083557845279, 306827170866106, 6199668952527617, 132240988644215842, 2968971263911288999
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,2
|
|
|
COMMENTS
| a(n) is the number of matchings in the complete bipartite graph K(n,n). - Sharon Sela (sharonsela(AT)hotmail.com), May 19 2002
Number of 12-avoiding signed permutations in B_n (see Simion ref).
EXP transform of A001048(n) = n! + (n-1)!. - Franklin T. Adams-Watters, Dec 28 2006
a(n) is also the order of the symmetric inverse semigroup (monoid), I sub n. [From A. Umar, Sep 09 2008]
Contribution 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.
a(n) is the Hosoya index of the complete bipartite graph K_{n,n}. - Eric Weisstein, Jul 9, 2011
|
|
|
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.
J. M. Howie, Fundamentals of semigroup theory. Oxford: Clarendon Press, (1995). [From A. Umar, Sep 09 2008]
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).
|
|
|
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, variable q.
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 598
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 64
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
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).
Sum( (k+n)!^2 / (k+n)!*(k!^2)*exp(1)), k = 0 .. infinity. - Robert G. Wilson v, May 02 2002
a(n) = Sum{m>=0} (-1)^m*A021009(n, m). - DELEHAM Philippe (kolotoko(AT)wanadoo.fr), 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 (rlahaye(AT)new.rr.com), Sep 20 2004
a(n) = Sum_{k=0..n}(-1)^(n-k)*Stirling1(n, k)*Bell(k+1). - Vladeta Jovovic (vladeta(AT)eunet.rs), 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 (penson(AT)lptl.jussieu.fr) 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. [From Paul D. Hanna, Nov 18 2011]
Conjecture: a(n) -2n*a(n-1) +(n-1)^2*a(n-2)=0. - R. J. Mathar, Dec 17 2011
|
|
|
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 */
|
|
|
CROSSREFS
| Main diagonal of A088699.
Cf. A000110, A020556, A069223.
Cf. A000712, A001048, A090210.
Sequence in context: A011800 A112916 A145845 * A111539 A074059 A177401
Adjacent sequences: A002717 A002718 A002719 * A002721 A002722 A002723
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| E.g.f. from D. E. Knuth 7/95. 2nd description from R. H. Hardin (rhhardin(AT)att.net) 11/97. 3rd description from wouter.meeussen(AT)pandora.be 6/98.
More terms from James A. Sellers (sellersj(AT)math.psu.edu), Jul 29 2000
|
| |
|
|
