A193463 -id:A193463 - cp's OEIS frontend

A076732 Table T(n,k) giving number of ways of obtaining exactly one correct answer on an (n,k)-matching problem (1 <= k <= n).

1, 1, 0, 1, 2, 3, 1, 4, 9, 8, 1, 6, 21, 44, 45, 1, 8, 39, 128, 265, 264, 1, 10, 63, 284, 905, 1854, 1855, 1, 12, 93, 536, 2325, 7284, 14833, 14832, 1, 14, 129, 908, 5005, 21234, 65821, 133496, 133497, 1, 16, 171, 1424, 9545, 51264, 214459, 660064, 1334961, 1334960

Offset: 1

Mohammad K. Azarian, Oct 28 2002

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 one correct answer, i.e., r=1, given k questions and n possible answers, 1 <= k <= n.

			Triangle begins
  1;
  1,0;
  1,2,3;
  1,4,9,8;
  ...

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

Columns: A000012(n), 2*A001477(n-2), 3*A002061(n-2), 4*A094792(n-4), 5*A094793(n-5), 6*A094794(n-6), 7*A094795(n-7); A000240(n), A000166(n). - Johannes W. Meijer, Jul 27 2011

A076732:=proc(n,k): (k/(n-k)!)*A047920(n,k) end: A047920:=proc(n,k): add(((-1)^j)*binomial(k-1,j)*(n-1-j)!, j=0..k-1) end: seq(seq(A076732(n,k), k=1..n), n=1..10); # Johannes W. Meijer, Jul 27 2011

A000240[n_] := Subfactorial[n] - (-1)^n;
T[n_, k_] := T[n, k] = Switch[k, 1, 1, n, A000240[n], _, k*T[n-1, k-1] + T[n-1, k]];
Table[T[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Nov 14 2023 *)

T(n,k) = F(n,k)*Sum{((-1)^j)*C(k-1, j)*(n-1-j)! (j=0 to k-1)}, where F(n,k) = k/(n-k)!, for 1 <= k <= n.
From Johannes W. Meijer, Jul 27 2011: (Start)
T(n,k) = k*T(n-1,k-1) + T(n-1,k) with T(n,1) = 1 and T(n,n) = A000240(n). [Hanson et al.]
T(n,k) = (n-1)*T(n-1,k-1) + (k-1)*T(n-2,k-2) + (1-k)*A076731(n-2,k-2) + A076731(n-1,k-1) with T(0,0) = T(n,0) = 0 and T(n,1) = 1. [Hanson et al.]
T(n,k) = k*A060475(n-1,k-1).
T(n,k) = (k/(n-k)!)*A047920(n-1,k-1).
Sum_{k=1..n} T(n,k) = A193463(n); row sums.
Sum_{k=1..n} T(n,k)/k = A003470(n-1). (End)

Edited and information added by Johannes W. Meijer, Jul 27 2011

A292898 Array read by ascending antidiagonals, A(m, n) = Sum_{k=1..m}(-1)^(k-n-m)* hypergeom([k, k-n-m], [], 1) for m>=1 and n>=0.

Original entry on oeis.org

1, 1, 0, 3, 2, 1, 8, 7, 5, 2, 31, 30, 27, 20, 9, 147, 146, 142, 129, 97, 44, 853, 852, 847, 826, 755, 574, 265, 5824, 5823, 5817, 5786, 5652, 5187, 3973, 1854, 45741, 45740, 45733, 45690, 45463, 44462, 40923, 31520, 14833

Offset: 0

Peter Luschny, Oct 05 2017

			Array starts:
[m\n]   0       1      2       3        4         5          6
-------------------------------------------------------------------
[1]     1,      0,     1,      2,       9,       44,       265, ...  [A000166]
[2]     1,      2,     5,     20,      97,      574,      3973, ...  [A259834(n+2)]
[3]     3,      7,    27,    129,     755,     5187,     40923, ...  [A292897]
[4]     8,     30,   142,    826,    5652,    44462,    394970, ...
[5]    31,    146,   847,   5786,   45463,   403514,   3990679, ...
[6]   147,    852,  5817,  45690,  405423,  4008768,  43692933, ...
[7]   853,   5823, 45733, 405779, 4012101, 43727687, 520723477, ...
  A003470,A193464,A293295.
Displayed as a triangle:
[1]     1;
[2]     1,      0;
[3]     3,      2,     1;
[4]     8,      7,     5,    2;
[5]    31,     30,    27,   20,    9;
[6]   147,    146,   142,  129,   97,   44;
[7]   853,    852,   847,  826,  755,  574,  265;
[8]  5824,   5823,  5817, 5786, 5652, 5187, 3973, 1854;
  A003470,A193464,A293295.
This triangle has row sums A193463.

Cf. A000166, A003470, A193463, A193464, A259834, A292897, A293295.

A := (m, n) -> add((-1)^(k-n-m)*hypergeom([k, k-n-m], [], 1), k=1..m):
seq(lprint(seq(simplify(A(m, n)), n=0..6)), m=1..7);

A[m_, n_] :=  Sum[(-1)^(k-n-m) HypergeometricPFQ[{k, k-n-m},{}, 1], {k, 1, m} ];
Table[Table[A[m, n], {n,0,6}], {m,1,7}]

cp's OEIS Frontend

A076732 Table T(n,k) giving number of ways of obtaining exactly one correct answer on an (n,k)-matching problem (1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions