login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

Table of n, a(n) for n=1..53.

D. Hanson, K. Seyffarth and J. H. Weston, Matchings, Derangements, Rencontres, Mathematics Magazine, Vol. 56, No. 4, September 1983.

StackExchange, How many injective functions f:[1,...,m]->[1,...,n] have no fixed point?

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.

From Johannes W. Meijer, Jul 27 2011: (Start)

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

14833 148329 which equals A023045

Columns give A000255 A000153 A000261 A001909 A001910

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

Cf. A076732, A086764.

Similar to A060475.

Sequence in context: A091533 A055376 A085215 * A085216 A300663 A102310

Adjacent sequences:  A076728 A076729 A076730 * A076732 A076733 A076734

KEYWORD

nonn,tabl

AUTHOR

Mohammad K. Azarian, Oct 28 2002

EXTENSIONS

Additional comments from Zerinvary Lajos, Mar 30 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 19 00:03 EDT 2019. Contains 321305 sequences. (Running on oeis4.)