Mixing
Number of functions from $A$ to $B$ such that $i lt j$ then $f(i) le f(j)$
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
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?
combinatorics functions
edited Aug 6 at 18:49
N. F. Taussig
38.4k93053
asked Aug 6 at 18:12
Umesh shankar
2,30111018
add a comment |Â
up vote
1
down vote
favorite
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?
combinatorics functions
edited Aug 6 at 18:49
N. F. Taussig
38.4k93053
asked Aug 6 at 18:12
Umesh shankar
2,30111018
en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
– Lord Shark the Unknown
Aug 6 at 18:16
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
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?
combinatorics functions
edited Aug 6 at 18:49
N. F. Taussig
38.4k93053
asked Aug 6 at 18:12
Umesh shankar
2,30111018
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?
combinatorics functions
edited Aug 6 at 18:49
N. F. Taussig
38.4k93053
asked Aug 6 at 18:12
Umesh shankar
2,30111018
edited Aug 6 at 18:49
N. F. Taussig
38.4k93053
edited Aug 6 at 18:49
N. F. Taussig
38.4k93053
edited Aug 6 at 18:49
N. F. Taussig
38.4k93053
38.4k93053
asked Aug 6 at 18:12
Umesh shankar
2,30111018
asked Aug 6 at 18:12
Umesh shankar
2,30111018
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
add a comment |Â
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
add a comment |Â
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.
answered Aug 6 at 18:46
N. F. Taussig
38.4k93053
add a comment |Â
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.
answered Aug 6 at 18:46
N. F. Taussig
38.4k93053
add a comment |Â
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.
answered Aug 6 at 18:46
N. F. Taussig
38.4k93053
add a comment |Â
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.
answered Aug 6 at 18:46
N. F. Taussig
38.4k93053
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.
answered Aug 6 at 18:46
N. F. Taussig
38.4k93053
answered Aug 6 at 18:46
N. F. Taussig
38.4k93053
answered Aug 6 at 18:46
N. F. Taussig
38.4k93053
answered Aug 6 at 18:46
N. F. Taussig
38.4k93053
38.4k93053
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
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
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)
– Lord Shark the Unknown
Aug 6 at 18:16