login
A226780
Triangular array read by rows. T(n,k) is the number of 2 tuple lists of length n that have exactly k coincidences; n >= 0, 0 <= k <= n.
1
1, 0, 1, 3, 0, 1, 26, 9, 0, 1, 453, 104, 18, 0, 1, 11844, 2265, 260, 30, 0, 1, 439975, 71064, 6795, 520, 45, 0, 1, 22056222, 3079825, 248724, 15855, 910, 63, 0, 1, 1436236809, 176449776, 12319300, 663264, 31710, 1456, 84, 0, 1
OFFSET
0,4
COMMENTS
Consider the set (with cardinality n!^2) of (ordered) lists of n two tuples such that all numbers from 1 to n appear as the first as well as the second tuple entry. If the j-th two tuple of the list is (j,j) then call it a coincidence. T(n,k) is the number of such lists that have k coincidences.
LINKS
FORMULA
T(n,k) = binomial(n,k) * A089041(n-k).
Row sums = n!^2.
T(n,0) = A089041(n).
The expected number of coincidences, Sum_{k=0..n} T(n,k)*k/n!^2 = 1/n.
EXAMPLE
1;
0, 1;
3, 0, 1;
26, 9, 0, 1;
453, 104, 18, 0, 1;
11844, 2265, 260, 30, 0, 1;
439975, 71064, 6795, 520, 45, 0, 1;
22056222, 3079825, 248724, 15855, 910, 63, 0, 1;
MAPLE
b:= proc(n) option remember;
`if`(n<2, 1-n, n^2*b(n-1)+n*(n-1)*b(n-2)+(-1)^n)
end:
T:= (n, k)-> binomial(n, k) * b(n-k):
seq(seq(T(n, k), k=0..n), n=0..10); # Alois P. Heinz, Jun 21 2013
MATHEMATICA
a = Table[Sum[(-1)^k Binomial[n, k](n-k)!^2, {k, 0, n}], {n, 0, 15}]; Table[Drop[Transpose[Table[Table[Binomial[n, i]*a[[n-i+1]], {n, 0, 10}], {i, 0, 10}]][[j]], -11+j], {j, 10}]//Grid
CROSSREFS
Cf. A008290.
Sequence in context: A022695 A278325 A364527 * A270880 A217580 A197858
KEYWORD
nonn,tabl
AUTHOR
Geoffrey Critzer, Jun 18 2013
STATUS
approved