How many 5-digit zip codes can exist where the digits are nondecreasing?

Clash Royale CLAN TAG#URR8PPP

up vote
1
down vote

favorite

I was reading over a combinatorics textbook and came across an example with a somewhat vague explanation:

$textitHow many 5-digit zip codes can exist where the digits are nondecreasing (like 12358 or 03399)?$

The solution provided was,

These are just the size-5 multisets of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. For example, the zip code 03399 is represented by the multiset 0, 3, 3, 9, 9, so the answer is $left(binom105right) = binom145 = 2002.$

My understanding of "multichoosing" is that it represents the number of ways to select $k$ indistinguishable objects amongst $n$ distinguishable ones. For instance, the number of ways to distribute $k$ identical candies to $n$ people is $left(binomnkright) = binomn+k-1k$.

How does this connect with the zip-code question? Wouldn't a zip code containing decreasing digits i.e. 30398 also be included as a size-5 multiset?

Thanks in advance for your help! I'd love to get some clarity on this issue.

combinatorics discrete-mathematics

share|cite|improve this question

asked Jul 22 at 3:10

Alex J. Lim

665

add a comment | 

up vote
1
down vote

favorite

I was reading over a combinatorics textbook and came across an example with a somewhat vague explanation:

$textitHow many 5-digit zip codes can exist where the digits are nondecreasing (like 12358 or 03399)?$

The solution provided was,

These are just the size-5 multisets of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. For example, the zip code 03399 is represented by the multiset 0, 3, 3, 9, 9, so the answer is $left(binom105right) = binom145 = 2002.$

My understanding of "multichoosing" is that it represents the number of ways to select $k$ indistinguishable objects amongst $n$ distinguishable ones. For instance, the number of ways to distribute $k$ identical candies to $n$ people is $left(binomnkright) = binomn+k-1k$.

How does this connect with the zip-code question? Wouldn't a zip code containing decreasing digits i.e. 30398 also be included as a size-5 multiset?

Thanks in advance for your help! I'd love to get some clarity on this issue.

combinatorics discrete-mathematics

share|cite|improve this question

asked Jul 22 at 3:10

Alex J. Lim

665

add a comment | 

up vote
1
down vote

favorite

up vote
1
down vote

favorite

I was reading over a combinatorics textbook and came across an example with a somewhat vague explanation:

$textitHow many 5-digit zip codes can exist where the digits are nondecreasing (like 12358 or 03399)?$

The solution provided was,

These are just the size-5 multisets of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. For example, the zip code 03399 is represented by the multiset 0, 3, 3, 9, 9, so the answer is $left(binom105right) = binom145 = 2002.$

My understanding of "multichoosing" is that it represents the number of ways to select $k$ indistinguishable objects amongst $n$ distinguishable ones. For instance, the number of ways to distribute $k$ identical candies to $n$ people is $left(binomnkright) = binomn+k-1k$.

How does this connect with the zip-code question? Wouldn't a zip code containing decreasing digits i.e. 30398 also be included as a size-5 multiset?

Thanks in advance for your help! I'd love to get some clarity on this issue.

combinatorics discrete-mathematics

share|cite|improve this question

asked Jul 22 at 3:10

Alex J. Lim

665

I was reading over a combinatorics textbook and came across an example with a somewhat vague explanation:

$textitHow many 5-digit zip codes can exist where the digits are nondecreasing (like 12358 or 03399)?$

The solution provided was,

These are just the size-5 multisets of 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. For example, the zip code 03399 is represented by the multiset 0, 3, 3, 9, 9, so the answer is $left(binom105right) = binom145 = 2002.$

My understanding of "multichoosing" is that it represents the number of ways to select $k$ indistinguishable objects amongst $n$ distinguishable ones. For instance, the number of ways to distribute $k$ identical candies to $n$ people is $left(binomnkright) = binomn+k-1k$.

How does this connect with the zip-code question? Wouldn't a zip code containing decreasing digits i.e. 30398 also be included as a size-5 multiset?

Thanks in advance for your help! I'd love to get some clarity on this issue.

combinatorics discrete-mathematics

share|cite|improve this question

asked Jul 22 at 3:10

Alex J. Lim

665

share|cite|improve this question

share|cite|improve this question

asked Jul 22 at 3:10

Alex J. Lim

665

asked Jul 22 at 3:10

Alex J. Lim

665

asked Jul 22 at 3:10

Alex J. Lim

665

665

add a comment | 

add a comment | 

1 Answer
1

active

oldest

votes

up vote
2
down vote



accepted

Multisets can have equal entries, but they have no order of the entries. The point is that given any multiset of digits you can find exactly one nondecreasing order of those digits. You do that by sorting them. Given the multiset $9,0,3,9,3$, which is the same as $0,3,3,9,9$, there is only one nondecreasing five digit sequence, which is $03399$, so if we can count the multisets we have a count of the nondecreasing zip codes.

share|cite|improve this answer

answered Jul 22 at 3:14

Ross Millikan

276k21186352

• 
  
  
  

  
  

  
  
  
  
  
  

  
  oh wow. duh. i am an idiot. that makes so much sense! thanks so much for the help, Ross!
  – Alex J. Lim
  Jul 22 at 3:18
  

  
  
  
  

add a comment | 

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

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

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859067%2fhow-many-5-digit-zip-codes-can-exist-where-the-digits-are-nondecreasing%23new-answer', 'question_page');

);

Post as a guest

Name Email

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

active

oldest

votes

active

oldest

votes

up vote
2
down vote



accepted

Multisets can have equal entries, but they have no order of the entries. The point is that given any multiset of digits you can find exactly one nondecreasing order of those digits. You do that by sorting them. Given the multiset $9,0,3,9,3$, which is the same as $0,3,3,9,9$, there is only one nondecreasing five digit sequence, which is $03399$, so if we can count the multisets we have a count of the nondecreasing zip codes.

share|cite|improve this answer

answered Jul 22 at 3:14

Ross Millikan

276k21186352

• 
  
  
  

  
  

  
  
  
  
  
  

  
  oh wow. duh. i am an idiot. that makes so much sense! thanks so much for the help, Ross!
  – Alex J. Lim
  Jul 22 at 3:18
  

  
  
  
  

add a comment | 

up vote
2
down vote



accepted

Multisets can have equal entries, but they have no order of the entries. The point is that given any multiset of digits you can find exactly one nondecreasing order of those digits. You do that by sorting them. Given the multiset $9,0,3,9,3$, which is the same as $0,3,3,9,9$, there is only one nondecreasing five digit sequence, which is $03399$, so if we can count the multisets we have a count of the nondecreasing zip codes.

share|cite|improve this answer

answered Jul 22 at 3:14

Ross Millikan

276k21186352

• 
  
  
  

  
  

  
  
  
  
  
  

  
  oh wow. duh. i am an idiot. that makes so much sense! thanks so much for the help, Ross!
  – Alex J. Lim
  Jul 22 at 3:18
  

  
  
  
  

add a comment | 

up vote
2
down vote



accepted

up vote
2
down vote



accepted

Multisets can have equal entries, but they have no order of the entries. The point is that given any multiset of digits you can find exactly one nondecreasing order of those digits. You do that by sorting them. Given the multiset $9,0,3,9,3$, which is the same as $0,3,3,9,9$, there is only one nondecreasing five digit sequence, which is $03399$, so if we can count the multisets we have a count of the nondecreasing zip codes.

share|cite|improve this answer

answered Jul 22 at 3:14

Ross Millikan

276k21186352

Multisets can have equal entries, but they have no order of the entries. The point is that given any multiset of digits you can find exactly one nondecreasing order of those digits. You do that by sorting them. Given the multiset $9,0,3,9,3$, which is the same as $0,3,3,9,9$, there is only one nondecreasing five digit sequence, which is $03399$, so if we can count the multisets we have a count of the nondecreasing zip codes.

share|cite|improve this answer

answered Jul 22 at 3:14

Ross Millikan

276k21186352

share|cite|improve this answer

share|cite|improve this answer

answered Jul 22 at 3:14

Ross Millikan

276k21186352

answered Jul 22 at 3:14

Ross Millikan

276k21186352

answered Jul 22 at 3:14

Ross Millikan

276k21186352

276k21186352

• 
  
  
  

  
  

  
  
  
  
  
  

  
  oh wow. duh. i am an idiot. that makes so much sense! thanks so much for the help, Ross!
  – Alex J. Lim
  Jul 22 at 3:18
  

  
  
  
  

add a comment | 

• 
  
  
  

  
  

  
  
  
  
  
  

  
  oh wow. duh. i am an idiot. that makes so much sense! thanks so much for the help, Ross!
  – Alex J. Lim
  Jul 22 at 3:18
  

  
  
  
  

oh wow. duh. i am an idiot. that makes so much sense! thanks so much for the help, Ross!
– Alex J. Lim
Jul 22 at 3:18

oh wow. duh. i am an idiot. that makes so much sense! thanks so much for the help, Ross!
– Alex J. Lim
Jul 22 at 3:18

add a comment | 

 

draft saved

draft discarded

 

draft saved

draft discarded

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

Name Email

StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2859067%2fhow-many-5-digit-zip-codes-can-exist-where-the-digits-are-nondecreasing%23new-answer', 'question_page');

);

Post as a guest

Name Email

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

Name Email

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

Name Email

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

Post as a guest

Name Email

Name Email

Name

Email

Name Email

Name

Email