cp's OEIS Frontend

A076731 Table T(n,k) giving number of ways of obtaining exactly 0 correct answers on an (n,k)-matching problem (1 <= k <= n).

%I A076731 #40 Sep 26 2017 10:59:12
%S A076731 0,1,1,2,3,2,3,7,11,9,4,13,32,53,44,5,21,71,181,309,265,6,31,134,465,
%T A076731 1214,2119,1854,7,43,227,1001,3539,9403,16687,14833,8,57,356,1909,
%U A076731 8544,30637,82508,148329,133496,9,73,527,3333,18089,81901,296967,808393
%N A076731 Table T(n,k) giving number of ways of obtaining exactly 0 correct answers on an (n,k)-matching problem (1 <= k <= n).
%C A076731 Hanson et al. define the (n,k)-matching problem in the following realistic way. A matching question on an exam has k questions with n possible answers to choose from, each question having a unique answer. If a student guesses the answers at random, using each answer at most once, what is the probability of obtaining r of the k correct answers?
%C A076731 The T(n,k) represent the number of ways of obtaining exactly zero correct answers, i.e., r=0, given k questions and n possible answers, 1 <= k <= n.
%C A076731 T(n,k) is the number of injections from [1,...,k] into [1,...,n] with no fixed points. - _David Bevan_, Apr 29 2013
%H A076731 D. Hanson, K. Seyffarth and J. H. Weston, <a href="http://www.jstor.org/stable/2689812">Matchings, Derangements, Rencontres</a>, Mathematics Magazine, Vol. 56, No. 4, September 1983.
%H A076731 StackExchange, <a href="http://math.stackexchange.com/questions/367686">How many injective functions f:[1,...,m]->[1,...,n] have no fixed point?</a>
%F A076731 T(n,k) = F(n,k)*Sum{((-1)^j)*C(k, j)*(n-j)! (j=0 to k)}, where F(n,k) = 1/(n-k)! for 1 <= k <= n.
%F A076731 From _Johannes W. Meijer_, Jul 27 2011: (Start)
%F A076731 T(n,k) = (n-1)*T(n-1,k-1) + (k-1)*T(n-2,k-2) with T(n,1) = (n-1) and T(n,n) = A000166(n) [Hanson et al.]
%F A076731 T(n,k) = (1/(n-k)!)*A061312(n-1,k-1)
%F A076731 sum(T(n,k), k=1..n) = A193464(n); row sums. (End)
%F A076731 T(n,k) = k!(n-k)![z^n*u^k]J(z,u) where J(z,u) = exp(z(1-u+z*u^2)/(1-z*u))/(1-z*u) is the exponential generating function of labeled digraphs consisting just of directed paths and oriented cycles (of length at least 2), z marking the vertices and u the edges; [z^n*u^k]J(z,u) is the coefficient of z^n*u^k in J(z,u). - _David Bevan_, Apr 29 2013
%e A076731 0; 1,1; 2,3,2; 3,7,11,9; ...
%e A076731 Formatted as a square array:
%e A076731 0 1 2 3 4 5 6 7 8
%e A076731 1 3 7 13 21 31 43 57 which equals A002061
%e A076731 2 11 32 71 134 227 356 which equals A094792
%e A076731 9 53 181 465 1001 1909 which equals A094793
%e A076731 44 309 1214 3539 8544 which equals A094794
%e A076731 265 2119 9403 30637 which equals A023043
%e A076731 1854 16687 82508 which equals A023044
%e A076731 14833 148329 which equals A023045
%e A076731 Columns give A000255 A000153 A000261 A001909 A001910
%e A076731 Formatted as a triangular array (mirror image of A086764):
%e A076731 0
%e A076731 1 1
%e A076731 2 3 2
%e A076731 3 7 11 9
%e A076731 4 13 32 53 44
%e A076731 5 21 71 181 309 265
%e A076731 6 31 134 465 1214 2119 1854
%e A076731 7 43 227 1001 3539 9403 16687 14833
%e A076731 8 57 356 1909 8544 30637 82508 148329 133496
%p A076731 A076731 := proc(n,k): (1/(n-k)!)*A061312(n-1,k-1) end: A061312:=proc(n,k): add(((-1)^j)*binomial(k+1,j)*(n+1-j)!, j=0..k+1) end: for n from 1 to 7 do seq(A076731(n,k), k=1..n) od; seq(seq(A076731(n,k), k=1..n), n=1..9); # _Johannes W. Meijer_, Jul 27 2011
%t A076731 t[n_,k_] := k!(n - k)! SeriesCoefficient[Exp[z(1-u+u^2z)/(1-z u)]/(1-z u), {z,0,n}, {u,0,k}]; Table[t[n,k], {n,9}, {k,n}] //TableForm (* _David Bevan_, Apr 29 2013 *)
%t A076731 t[n_, k_] := Pochhammer[n-k+1, k]*Hypergeometric1F1[-k, -n, -1]; Table[t[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* _Jean-François Alcover_, Nov 29 2013 *)
%Y A076731 Cf. A076732, A086764.
%Y A076731 Similar to A060475.
%K A076731 nonn,tabl
%O A076731 1,4
%A A076731 _Mohammad K. Azarian_, Oct 28 2002
%E A076731 Additional comments from _Zerinvary Lajos_, Mar 30 2006