• Support PF! Buy your school textbooks, materials and every day products Here!

Compute how many n-digit numbers

  • Thread starter knowLittle
  • Start date
  • #1
307
0

Homework Statement


Compute how many n-digit numbers can be made from the digits of at least one of {0,1,2,3,4,5,6,7,8,9 }
Assume, repetition or order do not matter.

Homework Equations


## a_{1}, a_{2}, ..., a_{n} ##

The Attempt at a Solution


10 choices for the 1st sub-index, 10 choices for the second sub-index, ..., 10 choices for the nth- sub-index.
## 10^{n} ## total possible combinations.
I think that now we need to add 'n' for a set full of one identical digit. i.e.: {2,2,...,n-th}
Now, n*9 for all possibilities

Now, I need to take some n_i number into account in pairs and each of the n-2 numbers repeated for each number.
So, groups of two repeated for each i-th number?
Also, then I would extend this to include triple identical numbers and the rest (n-3) numbers in the set?
And, so on...?

I am sorry, if this does not make any sense or it is too messy.
Could someone give me any guidance?
Thank you.
 

Answers and Replies

  • #2
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,535
751

Homework Statement


Compute how many n-digit numbers can be made from the digits of at least one of {0,1,2,3,4,5,6,7,8,9 }
Assume, repetition or order do not matter.
How can order not matter for numbers?

Homework Equations


## a_{1}, a_{2}, ..., a_{n} ##

The Attempt at a Solution


10 choices for the 1st sub-index,
Is it OK to have a string of 0's for leading digits?

10 choices for the second sub-index, ..., 10 choices for the nth- sub-index.
## 10^{n} ## total possible combinations.
I think that now we need to add 'n' for a set full of one identical digit. i.e.: {2,2,...,n-th}
Now, n*9 for all possibilities

Now, I need to take some n_i number into account in pairs and each of the n-2 numbers repeated for each number.
So, groups of two repeated for each i-th number?
Also, then I would extend this to include triple identical numbers and the rest (n-3) numbers in the set?
And, so on...?
I don't follow what you are doing in this last section. Is there something about the problem you haven't told us?
 
  • #3
307
0
The question is for a Theoretical Computer Science class.
How can order not matter for numbers?
You might be right, but he said that it does not matter. My professor was very vague in posing the question. I asked it twice.
He gave some examples:
## {0, 0, 0,0, ...,0_{n} }={0} ##
## {0, 0, 0, ..., 0, 1_{n}}={0,1}##

Is it OK to have a string of 0's for leading digits?
Yes, it is.
This counts as a valid number.
## { a_{0}, a_{1}, ..., a_{n} } \equiv {0_{0},0_{1},...,0_{n} } ##

I don't follow what you are doing in this last section. Is there something about the problem you haven't told us?
Sadly, I have told you everything that was given to me.

In the last section, I wanted to start counting numbers as if repetition mattered, but I recalled that the professor said that they do not.

I will for sure ask for more clarity next time, I see him.
 
  • #4
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,535
751
OK. Since leading zeroes are OK it seems to me that your original calculation of ##10^n## should do it.
 
  • Like
Likes 1 person
  • #5
307
0
Let me get back to you in a few days, I believe I can obtain more specific information about the problem. Thank you for your help so far.
 
  • #6
307
0
It turns out that order does matter after all. One 'gotta' love language.
An example helped to elucidate.

Example:
{0,1,2,3,...,8,9, ...<whatever>,...} is a vector of size n and 1 solution that satisfies the constraints.
{3,4,7,...,9,2,1,...<whatever>,... } is another vector of size n and another solution.

Let me work it out. If you have any leads, they are welcome.
Thanks :>
 
  • #7
307
0
Please, check the solution in attachment.
Apparently, it is incorrect. Can someone verify?
I think that I am not taking into account cases such as {m, o ,m } or {1,0,1}, where there could be repetitions.

The solution should be in the form:
Order matters
{ ... , <at least digits from 0 to 9>,..., <any numbers>, ... }

Thank you.
 

Attachments

  • #8
307
0
So, here is the solution.

## \dfrac{ |n| !}{ |n_{1}|! |n_{2}|!... |n_{k}|!} \text{, where n is the size of the vector and the values in denominator are types of symbols in n that repeat.}## ##\text{For instance, if I have a vector called v={e, i, g, e, n, v, a, l, u, e}, there are say n1 type symbols.}## ##\text{n1 relates to, say, e and our |n1|=3. The numerator in the equation takes care of all combination including repetitions}## ##\text{and the denominator takes care of cases as the one just mentioned. } ##
 

Related Threads on Compute how many n-digit numbers

Replies
8
Views
2K
Replies
5
Views
2K
Replies
2
Views
4K
Replies
9
Views
3K
Replies
10
Views
3K
  • Last Post
Replies
13
Views
3K
Replies
3
Views
7K
Replies
5
Views
3K
Replies
4
Views
2K
Top