The following text is written in Haskell literate style: lines in which ">" is the first character are program; other lines are comment. Haskell programs for A201376, A054225, A201377, A054242 ======================================================= Contents 1 Type Pair 2 Functions for OEIS entries 2.1 A201376 2.2 A201377 2.3 A054225 2.4 A054242 3 Abstract functions 3.1 to count partitions 3.1.1 into parts with possible repetitions 3.1.2 into distinct parts 3.2 to enunumerate partitions 3.2.1 into parts with possible repetitions 3.2.2 into distinct parts -------------------------------------------------------------------------------- 1 Pairs -------------------------------------------------------------------------------- > newtype Pair = Pair (Int, Int) deriving (Eq) > instance Num Pair where > Pair (u,v) + Pair (x,y) = Pair (u+x,v+y) > Pair (u,v) - Pair (x,y) = Pair (u-x,v-y) > fromInteger 0 = Pair (0,0) Incomplete declaration; sufficient for partitioning pairs. > instance Ord Pair where > Pair (u,v) > 0 = min u v >= 0 && max u v > 0 Incomplete declaration; sufficient to specify "positive pairs". > instance Show Pair where > show (Pair (u,v)) = "(" ++ show u ++ "," ++ show v ++ ")" > posLtEqu :: Int -> Int -> [Pair] > posLtEqu u v > | u < 0 || v < 0 = [] > | otherwise = tail [Pair (i,j) | i <- [0..u], j <- [0..v]] Examples: ------------------------------------------------------------------- ghci> Pair (5,2) (5,2) ghci> 0 :: Pair (0,0) ghci> Pair (3,2) > 0 True ghci> Pair (-3,1) > 0 False ghci> (0 :: Pair) > 0 False ghci> posLtEqu 3 0 [(1,0),(2,0),(3,0)] ghci> posLtEqu 3 2 [(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2),(3,0),(3,1),(3,2)] ghci> posLtEqu 0 0 [] ghci> posLtEqu 3 -2 [] -------------------------------------------------------------------------------- 2.1 A201376 Triangle read by rows, 0 <= k <= n: T(n,k) = number of partitions of (n,k) into positive pairs. -------------------------------------------------------------------------------- > a201376 :: Int -> Int -> Integer > a201376 n k = p (posLtEqu n k) (Pair (n,k)) > a201376_row :: Int -> [Integer] > a201376_row n = map (a201376 n) [0..n] > a201376_tabl :: [[Integer]] > a201376_tabl = map a201376_row [0..] Examples: ------------------------------------------------------------------- ghci> a201376 2 1 4 ghci> a201376 2 2 9 ghci> a201376 10 0 42 ghci> a201376_row 2 [2,4,9] ghci> a201376_row 3 [3,7,16,31] ghci> take 6 a201376_tabl [[1],[1,2],[2,4,9],[3,7,16,31],[5,12,29,57,109],[7,19,47,97,189,339]] -------------------------------------------------------------------------------- 2.2 A201377 Triangle read by rows, 0 <= k <= n: T(n,k) = number of partitions of (n,k) into distinct positive pairs. -------------------------------------------------------------------------------- > a201377 :: Int -> Int -> Integer > a201377 n k = p' (posLtEqu n k) (Pair (n,k)) > a201377_row :: Int -> [Integer] > a201377_row n = map (a201377 n) [0..n] > a201377_tabl :: [[Integer]] > a201377_tabl = map a201377_row [0..] Examples: ------------------------------------------------------------------- ghci> a201377 5 0 3 ghci> a201377 5 1 10 ghci> a201377_row 5 [3,10,21,42,74,123] ghci> take 6 a201377_tabl [[1],[1,2],[1,3,5],[2,5,9,17],[2,7,14,27,46],[3,10,21,42,74,123]] -------------------------------------------------------------------------------- 2.3 A054225 Square array read by antidiagonals, 0 <= k <= n: S(n,k) = number of partitions of (n,k) into positive pairs. -------------------------------------------------------------------------------- > a054225 :: Int -> Int -> Integer > a054225 n k = a054225_adiag (n + k) !! k > a054225_adiag :: Int -> [Integer] > a054225_adiag n = map (\k -> a201376 (n - k) k) [0..n] > a054225_square :: [[Integer]] > a054225_square = map a054225_adiag [0..] Examples: ------------------------------------------------------------------- ghci> a054225 2 1 4 ghci> a054225 2 2 9 ghci> a054225 10 0 42 ghci> a054225_row 2 [2,4,9] ghci> take 6 a054225_square [[1],[1,1],[2,2,2],[3,4,4,3],[5,7,9,7,5],[7,12,16,16,12,7]] -------------------------------------------------------------------------------- 2.4 A054242 Square array read by antidiagonals, 0 <= k <= n: S(n,k) = number of partitions of (n,k) into distinct positive pairs. -------------------------------------------------------------------------------- > a054242 :: Int -> Int -> Integer > a054242 n k = a054242_square !! (n + k) !! k > a054242_adiag :: Int -> [Integer] > a054242_adiag n = map (\k -> a201377 (n - k) k) [0..n] > a054242_square :: [[Integer]] > a054242_square = map a054242_adiag [0..] Examples: ------------------------------------------------------------------- ghci> a054242 5 0 3 ghci> a054242 4 2 14 ghci> a054242 3 3 17 ghci> take 7 a054242_square [[1],[1,1],[1,2,1],[2,3,3,2],[2,5,5,5,2],[3,7,9,9,7,3],[4,10,14,17,14,10,4]] -------------------------------------------------------------------------------- 3.1.1 Abstract function to count partitions into parts. ---------------------------------=====================-------------------------- > p :: (Num t, Ord t) => [t] -> t -> Integer The expression (p vs w) is the number of partitions of item w into elements of vs > p _ 0 = 1 > p [] _ = 0 > p ks'@(k:ks) m > | m > 0 = p ks' (m - k) + p ks m > | otherwise = 0 Examples: ------------------------------------------------------------------- ghci> p [1..10] 10 42 = A000040(10) ghci> p [1,3..12] 12 15 = A000009(12) ghci> p [2,3] 20 4 = A103221(12) ghci> p (posLtEqu 5 3) $ Pair (5,3) 97 = A201376(5,3) -------------------------------------------------------------------------------- 3.1.2 Abstract function to count partitions into distinct parts. ---------------------------------==============================----------------- > p' :: (Num t, Ord t) => [t] -> t -> Integer The expression (p' vs w) is the number of partitions of item w into distinct elements of vs > p' _ 0 = 1 > p' [] _ = 0 > p' (k:ks) m > | m > 0 = p' ks (m - k) + p' ks m > | otherwise = 0 Examples: ------------------------------------------------------------------- ghci> p' [1..12] 12 15 = A000009(12) ghci> p' (posLtEqu 5 3) $ Pair (5,3) 42 = A201377(5,3) -------------------------------------------------------------------------------- 3.2.1 Abstract function to enumerate partitions into distinct parts. -------------------------------------==============================------------- The expression (ps vs w) is the list of partitions of item w into elements of vs > ps :: (Num t, Ord t) => [t] -> t -> [t] -> [[t]] > ps _ 0 partits = [partits] > ps [] _ _ = [] > ps ks'@(k:ks) m partits > | m > 0 = ps ks' (m - k) (k:partits) ++ ps ks m partits > | otherwise = [] Examples: ------------------------------------------------------------------- ghci> ps [1..5] 5 [] [[1,1,1,1,1],[2,1,1,1],[3,1,1],[2,2,1],[4,1],[3,2],[5]] ghci> ps (posLtEqu 2 1) (Pair (2,1)) [] [[(1,0),(1,0),(0,1)],[(2,0),(0,1)],[(1,1),(1,0)],[(2,1)]] -------------------------------------------------------------------------------- 3.2.2 Abstract function to enumerate partitions into distinct parts. -------------------------------------==============================------------- > ps' :: (Num t, Ord t) => [t] -> t -> [t] -> [[t]] The expression (ps vs w) is the list of partitions of item w into distinct elements of vs > ps' _ 0 partits = [partits] > ps' [] _ _ = [] > ps' (k:ks) m partits > | m > 0 = ps' ks (m - k) (k:partits) ++ ps' ks m partits > | otherwise = [] Examples: ------------------------------------------------------------------- ghci> ps' [1..10] 10 [] [[4,3,2,1],[7,2,1],[6,3,1],[5,4,1],[9,1],[5,3,2],[8,2],[7,3],[6,4],[10]] ghci> ps' (posLtEqu 2 1) (Pair (2,1)) [] [[(2,0),(0,1)],[(1,1),(1,0)],[(2,1)]] ghci> ps' (posLtEqu 2 2) (Pair (2,2)) [] [[(1,1),(1,0),(0,1)],[(2,1),(0,1)],[(2,0),(0,2)],[(1,2),(1,0)],[(2,2)]] -- ----------------------------------------------------------------------------- a054225.lhs: reinhard.zumkeller@gmail.com Version 2: Dec 02 2011 2.3 and 2.4 added, programs for A054225, A054242 Version 1.1: Nov 30 2011 by Neil A. Sloane, new A-numbers, cf. History(A054225) Version 1: Nov 30 2011