Number of functions from $A$ to $B$ such that $i lt j$ then $f(i) le f(j)$

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP











up vote
1
down vote

favorite
1












Number of functions from $A=left1,2,3,4,5right$ to $B=left1,2,3right$ such that if $i lt j$, then $f(i) le f(j)$.



My try:



It is equivalent to finding number of five-digit numbers with digits $1,2,3$ with repetition such that digits are in non-decreasing order i.e.,



$$f(1) le f(2) le f(3) le f(4) le f(5)$$



Let $d_1d_2d_3d_4d_5$ be the five digit number satisfying $$d_1 le d_2 le d_3 le d_4 le d_5$$ where $d_1,d_2,d_3 in left1,2,3right$



So we have



$$a_1=d_1-1 ge 0$$



$$a_2=d_2-d_1 ge 0$$
$$a_3=d_3-d_2 ge 0$$
$$a_4=d_4-d_3 ge 0$$
$$a_5=d_5-d_4 ge0$$



$$a_6=3-d_5 ge0 $$



Using stars and bars, the number of nonnegative integer solutions of



$$a_1+a_2+a_3+a_4+a_5+a_6=2$$ is $$ binom2+6-16-1=21$$



Is this approach right?







share|cite|improve this question





















  • en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
    – Lord Shark the Unknown
    Aug 6 at 18:16














up vote
1
down vote

favorite
1












Number of functions from $A=left1,2,3,4,5right$ to $B=left1,2,3right$ such that if $i lt j$, then $f(i) le f(j)$.



My try:



It is equivalent to finding number of five-digit numbers with digits $1,2,3$ with repetition such that digits are in non-decreasing order i.e.,



$$f(1) le f(2) le f(3) le f(4) le f(5)$$



Let $d_1d_2d_3d_4d_5$ be the five digit number satisfying $$d_1 le d_2 le d_3 le d_4 le d_5$$ where $d_1,d_2,d_3 in left1,2,3right$



So we have



$$a_1=d_1-1 ge 0$$



$$a_2=d_2-d_1 ge 0$$
$$a_3=d_3-d_2 ge 0$$
$$a_4=d_4-d_3 ge 0$$
$$a_5=d_5-d_4 ge0$$



$$a_6=3-d_5 ge0 $$



Using stars and bars, the number of nonnegative integer solutions of



$$a_1+a_2+a_3+a_4+a_5+a_6=2$$ is $$ binom2+6-16-1=21$$



Is this approach right?







share|cite|improve this question





















  • en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
    – Lord Shark the Unknown
    Aug 6 at 18:16












up vote
1
down vote

favorite
1









up vote
1
down vote

favorite
1






1





Number of functions from $A=left1,2,3,4,5right$ to $B=left1,2,3right$ such that if $i lt j$, then $f(i) le f(j)$.



My try:



It is equivalent to finding number of five-digit numbers with digits $1,2,3$ with repetition such that digits are in non-decreasing order i.e.,



$$f(1) le f(2) le f(3) le f(4) le f(5)$$



Let $d_1d_2d_3d_4d_5$ be the five digit number satisfying $$d_1 le d_2 le d_3 le d_4 le d_5$$ where $d_1,d_2,d_3 in left1,2,3right$



So we have



$$a_1=d_1-1 ge 0$$



$$a_2=d_2-d_1 ge 0$$
$$a_3=d_3-d_2 ge 0$$
$$a_4=d_4-d_3 ge 0$$
$$a_5=d_5-d_4 ge0$$



$$a_6=3-d_5 ge0 $$



Using stars and bars, the number of nonnegative integer solutions of



$$a_1+a_2+a_3+a_4+a_5+a_6=2$$ is $$ binom2+6-16-1=21$$



Is this approach right?







share|cite|improve this question













Number of functions from $A=left1,2,3,4,5right$ to $B=left1,2,3right$ such that if $i lt j$, then $f(i) le f(j)$.



My try:



It is equivalent to finding number of five-digit numbers with digits $1,2,3$ with repetition such that digits are in non-decreasing order i.e.,



$$f(1) le f(2) le f(3) le f(4) le f(5)$$



Let $d_1d_2d_3d_4d_5$ be the five digit number satisfying $$d_1 le d_2 le d_3 le d_4 le d_5$$ where $d_1,d_2,d_3 in left1,2,3right$



So we have



$$a_1=d_1-1 ge 0$$



$$a_2=d_2-d_1 ge 0$$
$$a_3=d_3-d_2 ge 0$$
$$a_4=d_4-d_3 ge 0$$
$$a_5=d_5-d_4 ge0$$



$$a_6=3-d_5 ge0 $$



Using stars and bars, the number of nonnegative integer solutions of



$$a_1+a_2+a_3+a_4+a_5+a_6=2$$ is $$ binom2+6-16-1=21$$



Is this approach right?









share|cite|improve this question












share|cite|improve this question




share|cite|improve this question








edited Aug 6 at 18:49









N. F. Taussig

38.4k93053




38.4k93053









asked Aug 6 at 18:12









Umesh shankar

2,30111018




2,30111018











  • en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
    – Lord Shark the Unknown
    Aug 6 at 18:16
















  • en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
    – Lord Shark the Unknown
    Aug 6 at 18:16















en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
– Lord Shark the Unknown
Aug 6 at 18:16




en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
– Lord Shark the Unknown
Aug 6 at 18:16










1 Answer
1






active

oldest

votes

















up vote
1
down vote



accepted










Your solution is correct.



A different approach: Let $A = 1, 2, 3, 4, 5$; let $B = 1, 2, 3$. The number of functions $f: A to B$ satisfying
$i < j implies f(i) leq f(j)$ is completely determined by how many times each element of $B$ appears in the range. For instance, if $1$ appears once, $2$ appears twice, and $3$ appears twice, then $f$ is the function defined by
beginalign*
f(1) & = 1\
f(2) & = 2\
f(3) & = 2\
f(4) & = 3\
f(5) & = 3
endalign*
Hence, if we let $x_k$ be the number of times $k$, $1 leq k leq 3$, appears in the range, the number of non-decreasing functions $f: A to B$ is equal to the number of nonnegative integer solutions of the equation
$$x_1 + x_2 + x_3 = 5$$
which is
$$binom5 + 3 - 13 - 1 = binom72 = 21$$
as you found.






share|cite|improve this answer





















    Your Answer




    StackExchange.ifUsing("editor", function ()
    return StackExchange.using("mathjaxEditing", function ()
    StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
    StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
    );
    );
    , "mathjax-editing");

    StackExchange.ready(function()
    var channelOptions =
    tags: "".split(" "),
    id: "69"
    ;
    initTagRenderer("".split(" "), "".split(" "), channelOptions);

    StackExchange.using("externalEditor", function()
    // Have to fire editor after snippets, if snippets enabled
    if (StackExchange.settings.snippets.snippetsEnabled)
    StackExchange.using("snippets", function()
    createEditor();
    );

    else
    createEditor();

    );

    function createEditor()
    StackExchange.prepareEditor(
    heartbeatType: 'answer',
    convertImagesToLinks: true,
    noModals: false,
    showLowRepImageUploadWarning: true,
    reputationToPostImages: 10,
    bindNavPrevention: true,
    postfix: "",
    noCode: true, onDemand: true,
    discardSelector: ".discard-answer"
    ,immediatelyShowMarkdownHelp:true
    );



    );








     

    draft saved


    draft discarded


















    StackExchange.ready(
    function ()
    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2874172%2fnumber-of-functions-from-a-to-b-such-that-i-lt-j-then-fi-le-fj%23new-answer', 'question_page');

    );

    Post as a guest






























    1 Answer
    1






    active

    oldest

    votes








    1 Answer
    1






    active

    oldest

    votes









    active

    oldest

    votes






    active

    oldest

    votes








    up vote
    1
    down vote



    accepted










    Your solution is correct.



    A different approach: Let $A = 1, 2, 3, 4, 5$; let $B = 1, 2, 3$. The number of functions $f: A to B$ satisfying
    $i < j implies f(i) leq f(j)$ is completely determined by how many times each element of $B$ appears in the range. For instance, if $1$ appears once, $2$ appears twice, and $3$ appears twice, then $f$ is the function defined by
    beginalign*
    f(1) & = 1\
    f(2) & = 2\
    f(3) & = 2\
    f(4) & = 3\
    f(5) & = 3
    endalign*
    Hence, if we let $x_k$ be the number of times $k$, $1 leq k leq 3$, appears in the range, the number of non-decreasing functions $f: A to B$ is equal to the number of nonnegative integer solutions of the equation
    $$x_1 + x_2 + x_3 = 5$$
    which is
    $$binom5 + 3 - 13 - 1 = binom72 = 21$$
    as you found.






    share|cite|improve this answer

























      up vote
      1
      down vote



      accepted










      Your solution is correct.



      A different approach: Let $A = 1, 2, 3, 4, 5$; let $B = 1, 2, 3$. The number of functions $f: A to B$ satisfying
      $i < j implies f(i) leq f(j)$ is completely determined by how many times each element of $B$ appears in the range. For instance, if $1$ appears once, $2$ appears twice, and $3$ appears twice, then $f$ is the function defined by
      beginalign*
      f(1) & = 1\
      f(2) & = 2\
      f(3) & = 2\
      f(4) & = 3\
      f(5) & = 3
      endalign*
      Hence, if we let $x_k$ be the number of times $k$, $1 leq k leq 3$, appears in the range, the number of non-decreasing functions $f: A to B$ is equal to the number of nonnegative integer solutions of the equation
      $$x_1 + x_2 + x_3 = 5$$
      which is
      $$binom5 + 3 - 13 - 1 = binom72 = 21$$
      as you found.






      share|cite|improve this answer























        up vote
        1
        down vote



        accepted







        up vote
        1
        down vote



        accepted






        Your solution is correct.



        A different approach: Let $A = 1, 2, 3, 4, 5$; let $B = 1, 2, 3$. The number of functions $f: A to B$ satisfying
        $i < j implies f(i) leq f(j)$ is completely determined by how many times each element of $B$ appears in the range. For instance, if $1$ appears once, $2$ appears twice, and $3$ appears twice, then $f$ is the function defined by
        beginalign*
        f(1) & = 1\
        f(2) & = 2\
        f(3) & = 2\
        f(4) & = 3\
        f(5) & = 3
        endalign*
        Hence, if we let $x_k$ be the number of times $k$, $1 leq k leq 3$, appears in the range, the number of non-decreasing functions $f: A to B$ is equal to the number of nonnegative integer solutions of the equation
        $$x_1 + x_2 + x_3 = 5$$
        which is
        $$binom5 + 3 - 13 - 1 = binom72 = 21$$
        as you found.






        share|cite|improve this answer













        Your solution is correct.



        A different approach: Let $A = 1, 2, 3, 4, 5$; let $B = 1, 2, 3$. The number of functions $f: A to B$ satisfying
        $i < j implies f(i) leq f(j)$ is completely determined by how many times each element of $B$ appears in the range. For instance, if $1$ appears once, $2$ appears twice, and $3$ appears twice, then $f$ is the function defined by
        beginalign*
        f(1) & = 1\
        f(2) & = 2\
        f(3) & = 2\
        f(4) & = 3\
        f(5) & = 3
        endalign*
        Hence, if we let $x_k$ be the number of times $k$, $1 leq k leq 3$, appears in the range, the number of non-decreasing functions $f: A to B$ is equal to the number of nonnegative integer solutions of the equation
        $$x_1 + x_2 + x_3 = 5$$
        which is
        $$binom5 + 3 - 13 - 1 = binom72 = 21$$
        as you found.







        share|cite|improve this answer













        share|cite|improve this answer



        share|cite|improve this answer











        answered Aug 6 at 18:46









        N. F. Taussig

        38.4k93053




        38.4k93053






















             

            draft saved


            draft discarded


























             


            draft saved


            draft discarded














            StackExchange.ready(
            function ()
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2874172%2fnumber-of-functions-from-a-to-b-such-that-i-lt-j-then-fi-le-fj%23new-answer', 'question_page');

            );

            Post as a guest













































































            Comments

            Popular posts from this blog

            What is the equation of a 3D cone with generalised tilt?

            Color the edges and diagonals of a regular polygon

            Relationship between determinant of matrix and determinant of adjoint?