A171699 Square array of number of distinct m X n (0,1) matrices after iterated double sorting, read by antidiagonals.

1, 1, 1, 1, 2, 1, 1, 3, 3, 1, 1, 4, 7, 4, 1, 1, 5, 14, 14, 5, 1, 1, 6, 25, 45, 25, 6, 1, 1, 7, 41, 130, 130, 41, 7, 1, 1, 8, 63, 336, 650, 336, 63, 8, 1, 1, 9, 92, 785, 2942, 2942, 785, 92, 9, 1, 1, 10, 129, 1682, 11819, 24520, 11819, 1682, 129, 10, 1, 1, 11, 175

Offset: 0

Author

Randy Compton (RANDYRulerOfZexernet(AT)gmail.com), Dec 15 2009

Keywords

• nonn
• tabl

Comments

T(m,n) gives the number of distinct results obtained by repeatedly sorting the m X n (0,1) matrices by columns & then rows until reaching a fixed point. Its diagonal is A089006.

Examples

			Array begins:
  1,1,1,1,1,...
  1,2,3,4,5,...
  1,3,7,14,25,...
  1,4,14,45,130,...
  1,5,25,130,650,...
		

Crossrefs

Cf. A089006.

Programs

Haskell

-- with the function "t" producing the array.
import List
prod = foldr (\x xs -> [y:ys | y <- x, ys <- xs]) [[]]
f xs = let ys = sort (transpose (sort (transpose xs))) in if xs == ys then xs else f ys
t m n = length $ nub $ map f $ prod (replicate m (prod (replicate n [0,1])))

Extensions

Corrected & extended by Randy Compton (RANDYRulerOfZexernet(AT)gmail.com), Dec 18 2009