|
%I #40 Sep 26 2017 10:59:12
%S 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 1214,2119,1854,7,43,227,1001,3539,9403,16687,14833,8,57,356,1909,
%U 8544,30637,82508,148329,133496,9,73,527,3333,18089,81901,296967,808393
%N Table T(n,k) giving number of ways of obtaining exactly 0 correct answers on an (n,k)-matching problem (1 <= k <= n).
%C 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 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 T(n,k) is the number of injections from [1,...,k] into [1,...,n] with no fixed points. - _David Bevan_, Apr 29 2013
%H 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 StackExchange, <a href="http://math.stackexchange.com/questions/367686">How many injective functions f:[1,...,m]->[1,...,n] have no fixed point?</a>
%F 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 From _Johannes W. Meijer_, Jul 27 2011: (Start)
%F 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 T(n,k) = (1/(n-k)!)*A061312(n-1,k-1)
%F sum(T(n,k), k=1..n) = A193464(n); row sums. (End)
%F 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 0; 1,1; 2,3,2; 3,7,11,9; ...
%e Formatted as a square array:
%e 0 1 2 3 4 5 6 7 8
%e 1 3 7 13 21 31 43 57 which equals A002061
%e 2 11 32 71 134 227 356 which equals A094792
%e 9 53 181 465 1001 1909 which equals A094793
%e 44 309 1214 3539 8544 which equals A094794
%e 265 2119 9403 30637 which equals A023043
%e 1854 16687 82508 which equals A023044
%e 14833 148329 which equals A023045
%e Columns give A000255 A000153 A000261 A001909 A001910
%e Formatted as a triangular array (mirror image of A086764):
%e 0
%e 1 1
%e 2 3 2
%e 3 7 11 9
%e 4 13 32 53 44
%e 5 21 71 181 309 265
%e 6 31 134 465 1214 2119 1854
%e 7 43 227 1001 3539 9403 16687 14833
%e 8 57 356 1909 8544 30637 82508 148329 133496
%p 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 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 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 Cf. A076732, A086764.
%Y Similar to A060475.
%K nonn,tabl
%O 1,4
%A _Mohammad K. Azarian_, Oct 28 2002
%E Additional comments from _Zerinvary Lajos_, Mar 30 2006
|
