Solving Permutations Question with Restrictions

  • Context: MHB 
  • Thread starter Thread starter Lancelot1
  • Start date Start date
  • Tags Tags
    Permutations
Click For Summary

Discussion Overview

The discussion revolves around calculating the number of permutations for creating a 3-digit code from the digits 1 to 9, with the restriction that each digit must be equal to or larger than the previous one. The scope includes combinatorial reasoning and mathematical approaches to permutations with constraints.

Discussion Character

  • Exploratory, Mathematical reasoning, Debate/contested

Main Points Raised

  • One participant presents the initial problem and discusses the unrestricted permutations, suggesting that the approach depends on the digits selected.
  • Another participant proposes that the number of ordered tuples satisfying the restriction can be equated to the number of multisets, implying a unique ordering for each multiset.
  • A later reply reiterates the previous point about multisets and questions the rationale behind the proposed solution of \(\binom{11}{3}\).
  • Another participant confirms the solution of \(\binom{11}{3}\) and explains the bijection between multisets and non-decreasing triples.

Areas of Agreement / Disagreement

There is some agreement on the relationship between multisets and the problem of ordered tuples, but the understanding of the rationale behind the solution remains unclear for some participants. The discussion does not reach a consensus on the explanation of the solution.

Contextual Notes

Participants express uncertainty regarding the reasoning behind the combinatorial formula \(\binom{11}{3}\) and its application to the problem. There may be missing assumptions or definitions related to multisets and their properties.

Lancelot1
Messages
26
Reaction score
0
Hello all

Please look at this questions:

What is the number of permutations for creating a code of 3 digits from the digits 1,2,3,...,9 , such that every digit is equal or larger from the previous one ?

I know that if I wanted the number of permutations without restrictions it would be:

\[9^{3}\]

If all digits can be the same. Otherwise it would be

\[9\cdot 8\cdot 7\]

How do I approach the restriction, I mean, there are many possibilities, it depends on the numbers that I get.

Thank you.
 
Physics news on Phys.org
The number of ordered tuples $(a,b,c)$ where $1\le a\le b\le c\le 9$ is equal to the number of multisets $\{a,b,c\}$ because every multiset can be ordered in ascending order in a unique way.
 
Evgeny.Makarov said:
The number of ordered tuples $(a,b,c)$ where $1\le a\le b\le c\le 9$ is equal to the number of multisets $\{a,b,c\}$ because every multiset can be ordered in ascending order in a unique way.

Do you mean that the answer is :

\[\binom{11}{3}\] ?

I don't understand the rational behind it.
 
Lancelot said:
Do you mean that the answer is :

\[\binom{11}{3}\] ?
Yes. Because there is a bijection $f$ between the set of multisets of size 3 and the set of non-decreasing triples. Namely, $f(s)$ is $s$ sorted in increasing order.
 

Similar threads

High School Two interesting number theory tricks
  • · Replies 3 ·
Replies
3
Views
1K
High School Combinatorics and Magic squares
  • · Replies 2 ·
Replies
2
Views
2K
High School Really simple mistake in this combinatorics problem?
  • · Replies 19 ·
Replies
19
Views
4K
Graduate Mapping and Recovering Combinations: A Challenge in Combination Theory
  • · Replies 11 ·
Replies
11
Views
4K
Undergrad Permutation with exception/repetition
  • · Replies 2 ·
Replies
2
Views
3K
Undergrad How do I calculate permutations of a multi-set with limited elements?
  • · Replies 3 ·
Replies
3
Views
3K
High School How are permutations and probability related?
  • · Replies 1 ·
Replies
1
Views
2K
MHB Solve 6-Digit Combinations Question with 0-9
  • · Replies 3 ·
Replies
3
Views
3K
MHB Permutations of Comics, Novels, and Magazines Without Restrictions
  • · Replies 2 ·
Replies
2
Views
3K
MHB Solving 6-Digit Number Quandaries: 1, 2, 3, 4, 5, 6
  • · Replies 8 ·
Replies
8
Views
7K