{"id":125,"date":"2020-01-30T05:49:55","date_gmt":"2020-01-30T05:49:55","guid":{"rendered":"http:\/\/mathfun4kids.com\/mlog\/?p=125"},"modified":"2020-10-16T15:20:24","modified_gmt":"2020-10-16T15:20:24","slug":"mathcounts-exercises-18","status":"publish","type":"post","link":"https:\/\/mathfun4kids.com\/mlog\/?p=125","title":{"rendered":"MATHCOUNTS Exercises – 18"},"content":{"rendered":"\n

How many 4-digit integers between 1000 and 9999 have their digits in non-decreasing order, such as 3447?\nClick here for solutions.<\/a><\/p>\n

\n

Solution 1 – Brute Force<\/strong> Denote $f(m, n)$ as the number of $m$-digit\nintegers with their digits in non-decreasing order and the first digit value as $n$, where $0\\le n\\le 9$.\nWe have the following relation: $$ \\begin{array}{rcl}\nf(1,\\ n)&=&1 \\\\\nf(m,9)&=&1 \\\\\nf(m, n)&=&f(m-1, 9) + … + f(m-1, n+1) + f(m-1, n)\\\\\n&=&f(m, n+1) + f(m-1, n)\n\\end{array} $$\nThen we have the following table $$ \\begin{array}{c|rrrrrrrrrr}
\nf(m,n)& & & & & n & & & & & \\\\ \\hline
\nm & 9 & 8 & 7 & 6 & 5 & 4 & 3 & 2 & 1 & 0 \\\\ \\hline
\n1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\\\
\n2 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\\\
\n3 & 1 & 3 & 6 & 10 & 15 & 21 & 28 & 36 & 45 & 55 \\\\
\n4 & 1 & 4 & 10 & 20 & 35 & 56 & 84 & 120 & 165 & 220 \\\\
\n5 & 1 & 5 & 15 & 35 & 70 & 126 & 210 & 330 & 495 & 715 \\\\
\n\\hline\n\\end{array} $$\n<\/p>

\nThe answer to the question is equivalent to $f(5, 1)=495$, i.e. number of 5-digit integers with their digits in non-decreasing order and the first digit as $1$.\n
\nNote<\/strong> Do you notice the Pascal’s triangle in the above table?<\/p>\n

Solution 2 – Use Stars and Bars Theorem<\/a><\/strong>\nThis problem can be translated into inserting 4 identical balls in the boxes after 9 ordered digits as the following,\nwhere the number of balls in a box indicates the number of consecutive occurrences of the proceeding digit in forming a 4-digit number:\n$$\\fbox{1}\\Box{ }\\fbox{2}\\Box\\fbox{3}\\Box{ }\\fbox{4}\\Box{ }\\fbox{5}\\Box{ }\\fbox{6}\\Box{ }\\fbox{7}\\Box{ }\\fbox{8}\\Box{ }\\fbox{9}\\Box{ }$$\nFor example, 3447 will have 1 ball in the box after 3, 2 balls in the box after 4, and 1 ball in the box after 7 in the above figure.\nTherefore, using the formula<\/a>, the answer to the\nquestion is\n$$ {n+k-1\\choose n} = {4+9-1 \\choose 4} = {12 \\choose 4} = \\dfrac{12\\times 11\\times 10\\times 9}{4\\times 3\\times 2\\times 1} = 495$$\n<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

How many 4-digit integers between 1000 and 9999 have their digits in non-decreasing order, such as 3447? Click here for solutions. Solution 1 – Brute Force Denote $f(m, n)$ as the number of $m$-digit integers with their digits in non-decreasing … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"inline_featured_image":false},"categories":[10,11],"tags":[],"_links":{"self":[{"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/posts\/125"}],"collection":[{"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=125"}],"version-history":[{"count":5,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/posts\/125\/revisions"}],"predecessor-version":[{"id":1748,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=\/wp\/v2\/posts\/125\/revisions\/1748"}],"wp:attachment":[{"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=125"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=125"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/mathfun4kids.com\/mlog\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=125"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}