[seqfan] nXk permutations with a single error
Ron Hardin
rhhardin at att.net
Sat Oct 2 23:41:41 CEST 2010
Fussing with matrices containing a 1..n*k permutation with a single
mistake (one value omitted, one value repeated), and some numerology,
gives instead the formula, with the original application as a comment.
I don't offhand have a proof that the simple factor mentioned is the right one,
though it looks not unreasonable.
0,0,0,0,4,0,0,30,30,0,0,168,756,168,0,0,840,16632,16632,840,0,0,3960,
360360,1729728,360360,3960,0,0,18018,7876440,199536480,199536480,
7876440,18018,0,0,80080,174594420,25241364720,140229804000,25241364720
T(n,k) = 0!*1!*2!*...*(k-1)! *(n*k)! *k*(k-1)*n*(n-1) / 2*n!*(n+1)!*...*(n+k-1)!
(Empricial) T(n,k)=Number of nXk matrices containing a defective permutation of
1..n*k in strictly increasing order rowwise and columnwise, with one permutation
value omitted and one repeated (see example)
Formula is n*(n-1)*k*(k-1)/2 times nth k-dimensional Catalan number
Table starts
.0.......0.............0....................0...........................0
.0.......4............30..................168.........................840
.0......30...........756................16632......................360360
.0.....168.........16632..............1729728...................199536480
.0.....840........360360............199536480................140229804000
.0....3960.......7876440..........25241364720.............118949931243000
.0...18018.....174594420........3445446284280..........117015012361447200
.0...80080....3926434512......500598983364480.......129624266420759510400
.0..350064...89492111280....76591644454765440....158211402715245473193600
.0.1511640.2064420294300.12237255920840932800.209298196564031904834960000
Some solutions for 4X2
..2..4....1..4....1..3....1..3....2..5....1..3....1..3....2..4....1..2....1..3
..3..5....2..5....3..6....2..4....3..6....2..4....2..4....3..6....2..4....2..4
..5..7....6..7....4..7....4..6....4..7....4..5....4..7....5..7....3..5....4..7
..6..8....7..8....5..8....5..8....5..8....7..8....5..8....6..8....6..8....6..8
Cf. A060854 for permutation without defect.
rhhardin at mindspring.com
rhhardin at att.net (either)
More information about the SeqFan
mailing list