A185289 In a bipartite graph with 2n vertices (|V_1|=|V_2|=n), this sequence gives the number of ways to create n edges, one for each vertex of V_1, and to rank the vertices of V_2 which have incident edges.

1, 1, 6, 75, 1612, 52805, 2442666, 151382959, 12093970008, 1209295535049, 147859385866390, 21692929137930611, 3759744512444581860, 759740612270504941453, 177000400360669503651138, 47085371754008630756331255, 14182051733113750632290151856

Offset

0,3

Comments

a(n) is the number of ways to choose a function f:(1,2,...,n}->{1,2,...,n} and then linearly order the blocks of the coimage of f. - Geoffrey Critzer, Dec 23 2011

References

Paolo Hägler, Il problema dei pasti, Bollettino dei docenti di matematica, 63 (2011), 101-108

Links

Alois P. Heinz, Table of n, a(n) for n = 0..200

Formula

a(n) = Sum_{k=0..n} Sum_{j=0..k} (-1)^(k-j)*j^n*n!/(n-k)!*k!/(j!*(k-j)!). Paolo Hägler, Feb 20 2011

a(n) = Sum_{k=0..n} C(n,k)*Stirling2(n,k)*k!^2.

a(n) = Sum_{k=0..n} A090657(n,k)*k!.

Example

For n=2 the a(2)=6 solutions are Aab, Bab, AaBb, AbBa, BbAa, BaAb. The capital letters are the vertices of V_2, in order, and the lower-case letters are the vertices of V_1 joined to the vertex of V_2 represented by the capital letter.

Maple

f:= n-> add(add((-1)^(i-j)*j^n*n!*i!/(j!*(i-j)!*(n-i)!), j=0..i), i=0..n);
[seq(f(n), n=0..20)]; # N. J. A. Sloane, Mar 08 2011

Mathematica

Table[Sum[Binomial[n, k] StirlingS2[n, k] k!^2, {k, 0, n}], {n, 0, 20}]  (* Geoffrey Critzer, Dec 23 2011 *)

Prog

(PARI) a(n) = sum(k=0, n, binomial(n, k)*stirling(n, k, 2)*k!^2); \\ Michel Marcus, Mar 23 2016

Crossrefs

Sequence in context: A360471 A126462 A081066 * A336228 A326011 A350283

Adjacent sequences: A185286 A185287 A185288 * A185290 A185291 A185292

Keyword

nonn

Author

Paolo Hägler, Feb 20 2011

Status

approved