|
|
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) 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
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
|
Eric Weisstein's World of Mathematics, Clique
Eric Weisstein's World of Mathematics, Matching
|
|
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..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
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
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
|
|
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
option remember;
if n <= 1 then
n+1 ;
else
2*n*procname(n-1)-(n-1)^2*procname(n-2) ;
end if;
|
|
MATHEMATICA
|
Table[n! LaguerreL[n, -1], {n, 0, 25}]
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
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|