login
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

%I #13 Jun 21 2013 20:08:06

%S 1,0,1,3,0,1,26,9,0,1,453,104,18,0,1,11844,2265,260,30,0,1,439975,

%T 71064,6795,520,45,0,1,22056222,3079825,248724,15855,910,63,0,1,

%U 1436236809,176449776,12319300,663264,31710,1456,84,0,1

%N 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.

%C 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.

%H Alois P. Heinz, <a href="/A226780/b226780.txt">Rows n = 0..100, flattened</a>

%F T(n,k) = binomial(n,k) * A089041(n-k).

%F Row sums = n!^2.

%F T(n,0) = A089041(n).

%F The expected number of coincidences, Sum_{k=0..n} T(n,k)*k/n!^2 = 1/n.

%e 1;

%e 0, 1;

%e 3, 0, 1;

%e 26, 9, 0, 1;

%e 453, 104, 18, 0, 1;

%e 11844, 2265, 260, 30, 0, 1;

%e 439975, 71064, 6795, 520, 45, 0, 1;

%e 22056222, 3079825, 248724, 15855, 910, 63, 0, 1;

%p b:= proc(n) option remember;

%p `if`(n<2, 1-n, n^2*b(n-1)+n*(n-1)*b(n-2)+(-1)^n)

%p end:

%p T:= (n, k)-> binomial(n, k) * b(n-k):

%p seq(seq(T(n, k), k=0..n), n=0..10); # _Alois P. Heinz_, Jun 21 2013

%t 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

%Y Cf. A008290.

%K nonn,tabl

%O 0,4

%A _Geoffrey Critzer_, Jun 18 2013