A185289 - OEIS

%I #42 Oct 18 2024 20:32:04

%S 1,1,6,75,1612,52805,2442666,151382959,12093970008,1209295535049,

%T 147859385866390,21692929137930611,3759744512444581860,

%U 759740612270504941453,177000400360669503651138,47085371754008630756331255,14182051733113750632290151856

%N 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.

%C 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

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

%H Alois P. Heinz, <a href="/A185289/b185289.txt">Table of n, a(n) for n = 0..200</a>

%F 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

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

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

%e 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.

%p f:= n-> add(add((-1)^(i-j)*j^n*n!*i!/(j!*(i-j)!*(n-i)!),j=0..i),i=0..n);

%p [seq(f(n),n=0..20)]; # _N. J. A. Sloane_, Mar 08 2011

%t Table[Sum[Binomial[n, k] StirlingS2[n, k] k!^2, {k, 0, n}], {n, 0,20}]  (* _Geoffrey Critzer_, Dec 23 2011 *)

%o (PARI) a(n) = sum(k=0, n, binomial(n,k)*stirling(n,k,2)*k!^2); \\ _Michel Marcus_, Mar 23 2016

%K nonn

%O 0,3

%A _Paolo Hägler_, Feb 20 2011