Combinatorial approach to count of numbers between L and R with no repeating digits

Revision en4, by siddhantuniyal, 2024-04-25 16:22:23

I tried this problem with L = 1 , R = 9999

The answer is 4275 (9 + 9*8 + 9*9*8 + 9*9*8*7) , but with the below approach I am getting 5617. I am trying this approach, because it is generalized for any L and R.Please help me in finding out what I am doing wrong.

Observation 1 : The numbers following this conditions are always >= 1

Observation 2 : let x = 456 , y = 467. We are only able to tell that y > x because we started from the first digit , iterated towards the last digit and compared digits. At the first point of inequality , we were able to conclude that 456 < 457

Hence , I am iterating over all possible points of inequality between digits. here 1 is represented as 0001

if inequality is at 1st digit , that means 1st digit has to be 1,2,3..9 -> hence 9C1. And for the rest 3 digits , choose any 3 digits from the remaining 9 digits (10 digits originally and removing one because we placed it at 1st digit) and rearrange them -> 9C3 * 3!

if inequality is at 2nd digit , that means 1st digit = 0 and 2nd digit = 1,2..9 -> hence 9C1. And for the rest 2 digits , choose any 2 digits from the remaining 8 (10 originally , one (0) already at 1st digit , one chosen for 2nd digit) and rearrange -> 8C2 * 2!

if inequality is at 3rd digit , that means 1st and 2nd digit -> 0 and 3rd digit = 1,2,3..9 -> 9C1. and for the remaining digit , 8C1 (0 already used at 1st and 2nd digit , and one already chosen for 3rd digit).

for 4th digit -> 8C1

and we also have to add 1 to the answer , because , we are only considering some number between 1 and 9999 which has atleast one digit unequal to its corresponding digit in 1. but , 1 itself can be part of answer and here it is.

so this gives 9C1 * 9C3 * 3! + 9C1 * 8C2 * 2! + 9C1 * 8C1 + 8C1 + 1 , which is 5617 and wrong.

#### History

Revisions

Rev. Lang. By When Δ Comment
en4 siddhantuniyal 2024-04-25 16:22:23 198 Tiny change: 'een digits\nhere 1 i' -> 'een digits.\nhere 1 i'
en3 siddhantuniyal 2024-04-25 16:19:36 69
en2 siddhantuniyal 2024-04-25 16:18:58 10
en1 siddhantuniyal 2024-04-25 16:17:55 1679 Initial revision (published)