{"id":5501,"date":"2020-02-05T05:30:50","date_gmt":"2020-02-05T03:30:50","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=5501"},"modified":"2020-02-12T18:38:42","modified_gmt":"2020-02-12T16:38:42","slug":"numeros-de-bell","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/numeros-de-bell\/","title":{"rendered":"N\u00fameros de Bell"},"content":{"rendered":"<p>Una <a href=\"http:\/\/bit.ly\/2RtNivt\">partici\u00f3n de un conjunto<\/a> A es un conjunto de subconjuntos no vac\u00edos de A, disjuntos dos a dos y cuya uni\u00f3n es A. Por ejemplo, el conjunto {1, 2, 3} tiene exactamente 5 particiones:<\/p>\n<pre lang=\"text\">\n   {{1}, {2}, {3}}\n   {{1,2}, {3}}\n   {{1,3}, {2}}\n   {{1}, {2,3}}\n   {{1,2,3}}\n<\/pre>\n<p>El n-\u00e9simo <a href=\"http:\/\/bit.ly\/2uzZgKY\">n\u00famero de Bell<\/a>, B(n), es el n\u00famero de particiones de un conjunto de n elementos. Por lo visto anteriormentem B(3) = 5.<\/p>\n<p>Definir las funciones<\/p>\n<pre lang=\"text\">\n   particiones :: [a] -> [[[a]]]\n   bell :: Integer -> Integer\n<\/pre>\n<p>tales que<\/p>\n<ul>\n<li>(particiones xs) es el conjunto de las particiones de xs. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> particiones [1,2]\n     [[[1,2]],[[1],[2]]]\n     \u03bb> particiones [1,2,3]\n     [[[1,2,3]],[[1],[2,3]],[[1,2],[3]],[[2],[1,3]],[[1],[2],[3]]]\n     \u03bb> particiones \"abcd\"\n     [[\"abcd\"],[\"a\",\"bcd\"],[\"ab\",\"cd\"],[\"b\",\"acd\"],[\"abc\",\"d\"],[\"bc\",\"ad\"],\n      [\"ac\",\"bd\"],[\"c\",\"abd\"],[\"a\",\"b\",\"cd\"],[\"a\",\"bc\",\"d\"],[\"a\",\"c\",\"bd\"],\n      [\"ab\",\"c\",\"d\"],[\"b\",\"ac\",\"d\"],[\"b\",\"c\",\"ad\"],[\"a\",\"b\",\"c\",\"d\"]]\n<\/pre>\n<ul>\n<li>(bell n) es el n-\u00e9simo n\u00famero de Bell. Por ejemplo,<\/li>\n<\/ul>\n<pre lang=\"text\">\n     \u03bb> bell 3\n     5\n     \u03bb> map bell [0..10]\n     [1,1,2,5,15,52,203,877,4140,21147,115975]\n<\/pre>\n<p>Comprobar con QuickCheck que (bell n) es equivalente a la funci\u00f3n B(n) definida por<\/p>\n<ul>\n<li><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=B%280%29+%3D+1&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"B(0) = 1\" class=\"latex\" \/><\/li>\n<li><img decoding=\"async\" src=\"https:\/\/s0.wp.com\/latex.php?latex=B%28n%29+%3D+%5Cdisplaystyle+%5Csum_%7Bk%3D0%7D%5E%7Bn-1%7D+%5Cbinom%7Bn-1%7D%7Bk%7D+B%28k%29&#038;bg=ffffff&#038;fg=000&#038;s=0&#038;c=20201002\" alt=\"B(n) = &#92;displaystyle &#92;sum_{k=0}^{n-1} &#92;binom{n-1}{k} B(k)\" class=\"latex\" \/><\/li>\n<\/ul>\n<h4>Soluciones<\/h4>\n<pre lang=\"haskell\">\nimport Data.List (genericLength)\nimport Test.QuickCheck\n\n-- Definici\u00f3n de particiones\n-- =========================\n\nparticiones :: [a] -> [[[a]]]\nparticiones [] = [[]]\nparticiones (x:xs) =\n  concat [([x] : yss) : inserta x yss | yss <- ysss]\n  where ysss = particiones xs\n\n-- (inserta x yss) es la lista obtenida insertando x en cada uno de los\n-- elementos de yss. Por ejemplo, \n--    \u03bb> inserta 1 [[2,3],[4],[5,6,7]]\n--    [[[1,2,3],[4],[5,6,7]],[[2,3],[1,4],[5,6,7]],[[2,3],[4],[1,5,6,7]]]\ninserta :: a -> [[a]] -> [[[a]]]\ninserta _ []       = []\ninserta x (ys:yss) = ((x:ys):yss) : [ys : zs | zs <- inserta x yss] \n\n-- Definici\u00f3n de Bell\n-- ==================\n\nbell :: Integer -> Integer\nbell n = genericLength (particiones [1..n])\n\n-- Propiedad\n-- =========\n\nprop_Bell :: Integer -> Property\nprop_Bell n =\n  n >= 0 ==> bell n == b n\n\nb :: Integer -> Integer\nb 0 = 1\nb n = sum [comb (n-1) k * b k | k <- [0..n-1]]\n\ncomb :: Integer -> Integer -> Integer\ncomb n k = product [n-k+1..n] `div` product [1..k]\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheckWith (stdArgs {maxSize=10}) prop_Bell\n--    +++ OK, passed 100 tests.\n<\/pre>\n<h4>Otras soluciones<\/h4>\n<ul>\n<li>Se pueden escribir otras soluciones en los comentarios.\n<li>El c\u00f3digo se debe escribir entre una l\u00ednea con &#60;pre lang=\u00bbhaskell\u00bb&#62; y otra con &#60;\/pre&#62;\n<\/ul>\n<h4>Pensamiento<\/h4>\n<blockquote><p>\n\u00abCambiemos nuestra actitud tradicional en la construcci\u00f3n de programas. En lugar de imaginar que nuestra tarea principal es indicarle a una computadora lo que debe hacer, concentr\u00e9monos m\u00e1s bien en explicarle a los seres humanos lo que queremos que haga una computadora.\u00bb <\/p>\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Donald_Knuth\">Donald Knuth<\/a>.\n<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Una partici\u00f3n de un conjunto A es un conjunto de subconjuntos no vac\u00edos de A, disjuntos dos a dos y cuya uni\u00f3n es A. Por ejemplo, el conjunto {1, 2, 3} tiene exactamente 5 particiones: {{1}, {2}, {3}} {{1,2}, {3}} {{1,3}, {2}} {{1}, {2,3}} {{1,2,3}} El n-\u00e9simo n\u00famero de Bell, B(n), es el n\u00famero de&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[7],"tags":[8,12,30,258,157,6,146],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5501"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=5501"}],"version-history":[{"count":15,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5501\/revisions"}],"predecessor-version":[{"id":5559,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/5501\/revisions\/5559"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=5501"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=5501"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=5501"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}