|
| |
|
|
A144085
|
|
a(n) is the number of partial bijections (or subpermutations) of an n-element set without fixed points (also called partial derangements)
|
|
4
| |
|
|
1, 1, 4, 18, 108, 780, 6600, 63840, 693840, 8361360, 110557440, 1590351840, 24713156160, 412393101120, 7352537512320, 139443752448000, 2802408959750400, 59479486120454400, 1329239028813696000, 31194214921732262400, 766888191387539020800, 19707387644116280908800, 528327710066244459571200
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| a(n) is also the Hosoya index of the n-crown graph - Eric Weisstein, Jul 11 2011
|
|
|
REFERENCES
| Laradji, A. and Umar, A. Combinatorial results for the symmetric inverse semigroup. Semigroup Forum 75, (2007), 221-236.
|
|
|
LINKS
| Eric Weisstein's World of Mathematics, Hosoya Index
|
|
|
FORMULA
| a(n) = n!*sum(m=0..n,(-1^m/m!)*sum(j=0,n-m,C(n-m,j)/j!))
a(n) = (2*n-1)*a(n-1)-(n-1)*(n-3)*a(n-2)-(n-1)*(n-2)*a(n-3), a(0)=1, a(n)=0 if n<0
E.g.f. for number of partial bijections of an n-element set with exactly k fixed points is x^k/k!*exp(x^2/(1-x))/(1-x). [From Vladeta Jovovic (vladeta(AT)eunet.yu), Nov 09 2008]
|
|
|
EXAMPLE
| a(3) = 18 because there are exactly 18 partial derangements (on a 3-element set), namely: the empty map, (1)->(2), (1)->(3), (2)->(1), (2)->(3), (3)->(1), (3)->(2), (1,2)->(2,1), (1,2)->(2,3), (1,2)->(3,1), (1,3)->(2,1), (1,3)->(3,1), (1,3)->(3,2), (2,3)->(1,2), (2,3)->(3,1), (2,3)->(3,2), (1,2,3)->(2,3,1), (1,2,3)->(3,1,2) - the mappings are coordinate-wise.
|
|
|
MATHEMATICA
| Tabke[n! Sum[(-1)^m/m! LaguerreL[-m + n, -1], {m, 0, n}], {n, 30}]
|
|
|
PROG
| (PARI) x='x+O('x^66); /* that many terms */
k=0; egf=x^k/k!*exp(x^2/(1-x))/(1-x);
Vec(serlaplace(egf)) /* show terms */ /* Joerg Arndt, Jul 11 2011 */
|
|
|
CROSSREFS
| a(n) is A144088(n, 0)
Sequence in context: A020114 A009597 A060223 * A003708 A000986 A143920
Adjacent sequences: A144082 A144083 A144084 * A144086 A144087 A144088
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| A. Umar (aumarh(AT)squ.edu.om), Sep 10 2008, Sep 15 2008
|
| |
|
|
