|
|
题 每一位数字都比左边数字小的正整数，称为“降序数”。将所有五位数中的降序数，按照从小到大
次序排列，求排列中的第 109 个数。
解 一般来说，首位数不大于 m 的 n 位的所有降序数的总数，等于从 0,1,…,m 这 m+1 个数中取 n 个
作组合的组合种数 C(m+1,n) 。
当 m=7 ，n=5 时，C(7+1,5)=C(8,5)=56＜109 ；当 m=8 ，n=5 时，C(8+1,5)=C(9,5)=126＞109 。
可见，第 109 个数的首位数，也就是万位数，必定大于 7 ，但不会大于 8 ，所以万位必定是 8 。
万位不大于 7 的五位数有 56 个，剩下 109-56=53 个数的万位数都是 8 。再看万位后面的四位数：
当 m=6 ，n=4 时，C(6+1,4)=C(7,4)=35＜53 ；当 m=7 ，n=4 时，C(7+1,4)=C(8,4)=70＞53 。
可见，第 109 个数的第二位数，也就是千位数，必定大于 6 ，但不会大于 7 ，所以千位必定是 7 。
千位不大于 6 的四位数有 35 个，剩下 53-35=18 个数的千位数都是 7 。再看千位后面的三位数：
当 m=4 ，n=3 时，C(4+1,3)=C(5,3)=10＜18 ；当 m=5 ，n=3 时，C(5+1,3)=C(6,3)=20＞18 。
可见，第 109 个数的第三位数，也就是百位数，必定大于 4 ，但不会大于 5 ，所以百位必定是 5 。
百位不大于 4 的三位数有 10 个，剩下 18-10=8 个数的百位数都是 5 。再看百位后面的二位数：
当 m=3 ，n=2 时，C(3+1,2)=C(4,2)=6＜8 ；当 m=4 ，n=2 时，C(4+1,2)=C(5,2)=10＞8 。
可见，第 109 个数的第四位数，也就是十位数，必定大于 3 ，但不会大于 4 ，所以十位必定是 4 。
十位不大于 3 的二位数有 6 个，剩下 8-6=2 个数的十位数都是 4 ，再看十位后面的个位数：
当 m=0 ，n=1 时，C(0+1,1)=C(1,1)=1＜2 ；当 m=1 ，n=1 时，C(1+1,1)=C(2,1)=2 。
可见，第 109 个数的第五位数，也就是个位数，必定大于 0 ，但不会大于 1 ，所以个位必定是 1 。
综合以上分析，可知排列中的第 109 个数，是 87541 。
|
|
IP卡
狗仔卡
发表于 2020-5-3 01:51
提升卡
置顶卡
沉默卡
喧嚣卡
变色卡
显身卡
发表于 2020-5-3 20:53