|
| |
|
|
A076731
|
|
Table T(n,k) giving number of ways of obtaining exactly 0 correct answers on an (n,k)-matching problem (1 <= k <= n).
|
|
6
|
|
|
|
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, 1214, 2119, 1854, 7, 43, 227, 1001, 3539, 9403, 16687, 14833, 8, 57, 356, 1909, 8544, 30637, 82508, 148329, 133496, 9, 73, 527, 3333, 18089, 81901, 296967, 808393
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
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?
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.
T(n,k) is the number of injections from [1,...,k] into [1,...,n] with no fixed points. - David Bevan, Apr 29 2013
|
|
|
LINKS
|
|
|
|
FORMULA
|
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.
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.]
T(n,k) = (1/(n-k)!)*A061312(n-1,k-1)
sum(T(n,k), k=1..n) = A193464(n); row sums. (End)
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
|
|
|
EXAMPLE
|
0; 1,1; 2,3,2; 3,7,11,9; ...
Formatted as a square array:
0 1 2 3 4 5 6 7 8
1 3 7 13 21 31 43 57 which equals A002061
2 11 32 71 134 227 356 which equals A094792
9 53 181 465 1001 1909 which equals A094793
44 309 1214 3539 8544 which equals A094794
265 2119 9403 30637 which equals A023043
1854 16687 82508 which equals A023044
Formatted as a triangular array (mirror image of A086764):
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 1214 2119 1854
7 43 227 1001 3539 9403 16687 14833
8 57 356 1909 8544 30637 82508 148329 133496
|
|
|
MAPLE
|
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
|
|
|
MATHEMATICA
|
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[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 *)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
