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, 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

Author

Geoffrey Critzer, Jun 18 2013

Keywords

• nonn
• tabl

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.

Examples

			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;
		

Links

• Alois P. Heinz, Rows n = 0..100, flattened

Crossrefs

Cf. A008290.

Programs

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

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.