论坛 › 趣题妙解 › 这样的十位有多少个？

王守恩 发表于 2017-11-30 14:25:20

这样的十位有多少个？

有45个数字：9个1，8个2，7个3，6个4，5个5，4个6，3个7，2个8，1个9。
在这45个数字中选十个数字组成一个十位数，这样的十位有多少个？

kastin 发表于 2017-11-30 16:28:18

参考 http://bbs.emath.ac.cn/forum.php?mod=redirect&goto=findpost&ptid=5603&pid=54067&fromuid=8865

sheng_jianguo 发表于 2017-12-8 22:43:57

不知道你是要搞清楚具体怎样计算，还是只要知道满足条件的十位数有多少个？
1.搞清楚具体怎样计算，一般可采用递归法。
$设n_1个1，n_2个2，n_3个3，n_4个4，n_5个5，n_6个6，n_7个7，n_8个8，n_9个9组成数字中，选m个数字组成一个m位数，这样的m位数共有f_z(n_1,n_2,n_3,n_4,n_5,n_6,n_7,n_8,n_9,m)个$
$则f_z(9,8,7,6,5,4,3,2,1,10)=C_{10}^{1}f_z(9,8,7,6,5,4,3,2,0,9)　　{10位数中出现9情况，共有C_{10}^{1}种不同占位}$
$+f_z(8,8,7,6,5,4,3,2,0,9)　　{10位数中不出现9情况，第10位为1}$
$+f_z(9,7,7,6,5,4,3,2,0,9)　　{10位数中不出现9情况，第10位为2}$
$+f_z(9,8,6,6,5,4,3,2,0,9)　　{10位数中不出现9情况，第10位为3}$
$+f_z(9,8,7,5,5,4,3,2,0,9)　　{10位数中不出现9情况，第10位为4}$
$+f_z(9,8,7,6,4,4,3,2,0,9)　　{10位数中不出现9情况，第10位为5}$
$+f_z(9,8,7,6,5,3,3,2,0,9)　　{10位数中不出现9情况，第10位为6}$
$+f_z(9,8,7,6,5,4,2,2,0,9)　　{10位数中不出现9情况，第10位为7}$
$+f_z(9,8,7,6,5,4,3,1,0,9)　　{10位数中不出现9情况，第10位为8}$
$=.........　　{这样一直可以递归下去，直到最后等式中每一项都可以明确得出具体数值}$
2.只想知道满足条件的十位数有多少个，一般可采用暴力法（即编程法：将每一个十位数（明显不满足条件的可去掉）都进行判别是否满足条件，并记下否满足条件的十位数共有几个）。
在很一般的电脑上，我用此法（计算时间不到一分钟）得出：满足条件的十位数有1548342622个，希望有高手来验证这个结果。

mathe 发表于 2017-12-9 18:19:40

我的结果是2103049130种
#include <stdio.h>
#include <limits.h>

unsigned long long lltotal;
unsigned long long lltotal2;
int fac;
void initfac()
{
    int i;
    fac=1;
    for(i=1;i<=10;i++){
      fac=fac*i;
    }
}

void dump_pattern(int a[])
{
    int i;
    for(i=9;i>=1;i--){
      printf("%d ",a);
    }
}

void enumall(int a[], int k, int s)//a+a+...+a=s
{
    int i;
    if(k==1&&s<=1){
      a=s;
      dump_pattern(a);
      int c=fac;
      for(i=1;i<=9;i++){
            c/=fac];
      }
      printf("%d\n",c);
      lltotal+=c;
      if(lltotal2>=ULLONG_MAX-1-c){
            lltotal2+=c+1;
      }else{
            lltotal2+=c;
      }
      return;
    }
    int start = s;
    if(start>k)start=k;
    for(i=start;i>=0;i--){
      a=i;
      enumall(a,k-1,s-i);
    }
}

int main()
{
    int a;
    initfac();
    enumall(a,9,10);
    printf("Total %llu, %llu\n", lltotal, lltotal2);
    return 0;
}

王守恩 发表于 2017-12-9 19:03:08

mathe 发表于 2017-12-9 18:19
我的结果是2103049130种

答案应该是2103049130。我想找一个数学公式来表达，怎么也写不好！下面的公式就是其中一个，减得太多了！
\(9^{10}-1×9-8×10×8-8^2×45×7-8^3×120×6-8^4×210×5-8^5×252×4-8^6×210×3-8^7×120×2-8^8×45×1=2025622088\)
          9^10：用9个数字组成的全体10位数。
8^0× 1 ×9(1,2,3,4,5,6,7,8,9)：10个数字相同的10位数。
8^1×10×8(2,3,4,5,6,7,8,9)：9个数字相同的10位数。
8^2×45×7(3,4,5,6,7,8,9)：8个数字相同的10位数。
8^3×120×6(4,5,6,7,8,9)：7个数字相同的10位数。
8^4×210×5(5,6,7,8,9)：6个数字相同的10位数。
8^5×252×4(6,7,8,9)：5个数字相同的10位数。
8^6×210×3(7,8,9)：4个数字相同的10位数。
8^7×120×2(8,9)：3个数字相同的10位数。
8^8×45×1(9)：2个数字相同的10位数。

sheng_jianguo 发表于 2017-12-12 14:02:06

王守恩 发表于 2017-12-9 19:03
答案应该是2103049130。我想找一个数学公式来表达，怎么也写不好！下面的公式就是其中一个，减得太多了！ ...

不好意思，我的程序在最后求和时系数输错，改正后结果和mathe完全一样，等于2103049130。
你的公式问题是没考虑交集的计数处理，漏掉了一些计算项。
举个例子说明这个问题：假定有三个不空的有限集$A，B，C，s(X)$表示集合X中元素的个数，则
$s(A∪B∪C)=(s(A)+s(B)+s(C))-(s(A∩B)+s(B∩C)+s(A∩C))+s(A∩B∩C)$
多个集合计算类似，右边等式项是1个集合交集，2个集合交集，3个集合交集，...。符号是+，-，+，...交替出现。
好在这个问题没有出现有4个集合交集不空的情况。
回到你的计算公式，设在n个不同元素中取2组不同元素，第1组$m_1$个，第2组$m_2$个，一共有$C_{n}^{m_1,m_2}$种组合取法，则
$C_{n}^{m_1,m_2}=frac{n!}{m_!!m_2!(n-m_1-m_2)!}$
同样，$C_{n}^{m_1,m_2,m_3}$表示取3组时的取法组合数，计算公式：
$C_{n}^{m_1,m_2,m_3}=frac{n!}{m_!!m_2!m_3!(n-m_1-m_2-m_3)!}$
再令$g_S(i_1,i_2)$表示在1到9中，某2个不同数字出现$i_1$次重复和$i_2$次重复且不满足问题要求的种数（不考虑其它数字变化）。
同样，令$g_S(i_1,i_2,i_3)$表示在1到9中，某3个不同数字出现$i_1$次重复、$i_2$次重复和$i_3$次重复且不满足问题要求的种数（不考虑其它数字变化）。
比如：$g_S(3,4)=4$　{9重复3次8重复4次；8重复3次9重复4次；9重复3次7重复4次；8重复3次7重复4次；共有4种情况}
比如：$g_S(2,3,5)=2$　{9重复2次8重复3次7重复5次；9重复2次8重复3次6重复5次；共有2种情况}
那么，按你的计算方法，满足条件的十位数个数计算公式为：
$f_z(9,8,7,6,5,4,3,2,1,10)=9^10-(1×9+8×10×8+8^2×45×7+8^3×120×6+8^4×210×5+8^5×252×4+8^6×210×3+8^7×120×2+8^8×45×1)$
$+(g_S(2,3)×C_{10}^{2,3}×7^5+g_S(2,4)×C_{10}^{2,4}×7^4+g_S(2,5)×C_{10}^{2,5}×7^3+g_S(2,6)×C_{10}^{2,6}×7^2+g_S(2,7)×C_{10}^{2,7}×7^1+g_S(2,8)×C_{10}^{2,8}×7^0$
$+g_S(3,3)×C_{10}^{3,3}×7^4+g_S(3,4)×C_{10}^{3,4}×7^3+g_S(3,5)×C_{10}^{3,5}×7^2+g_S(3,6)×C_{10}^{3,6}×7^1+g_S(3,7)×C_{10}^{3,7}×7^0$
$+g_S(4,4)×C_{10}^{4,4}×7^2+g_S(4,5)×C_{10}^{4,5}×7^1+g_S(4,6)×C_{10}^{4,6}×7^0+g_S(5,5)×C_{10}^{5,5}×7^0)$
$-(g_S(2,3,4)×C_{10}^{2,3,4}×6^1+g_S(2,3,5)×C_{10}^{2,3,5}×6^0+g_S(2,4,4)×C_{10}^{2,4,4}×6^0+g_S(3,3,4)×C_{10}^{3,3,4}×6^0)$
$=2025622088+(1×2520×7^5+2×3150×7^4+3×2520×7^3+4×1260×7^2+5×360×7^1+6×45×7^0$
$+1×4200×7^4+4×4200×7^3+6×2520×7^2+8×840×7^1+10×120×7^0$
$+3×3150×7^2+9×1260×7^1+12×210×7^0+6×252×7^0)$
$-(1×12600×6^1+2×2520×6^0+1×3150×6^0+1×4200×6^0)$
$=2103049130$

王守恩 发表于 2017-12-14 16:28:43

本帖最后由 王守恩 于 2017-12-14 16:31 编辑

sheng_jianguo 发表于 2017-12-12 14:02
不好意思，我的程序在最后求和时系数输错，改正后结果和mathe完全一样，等于2103049130。
你的公式问 ...
谢谢sheng_jianguo！您的解答让我长进不少！
还是这道题，可以用数学公式来表示答案吗？
有45个数字：9个1，8个2，7个3，6个4，5个5，4个6，3个7，2个8，1个9。
在这45个数字中选十个数字组成一个十位数，其中和是45的十位有多少个？

sheng_jianguo 发表于 2017-12-16 14:59:41

王守恩 发表于 2017-12-14 16:28
谢谢sheng_jianguo！您的解答让我长进不少！
还是这道题，可以用数学公式来表示答案吗？
有45个数字： ...

因为由1至9组成的十位数，其和是45 的十位数的种数没有发现有简单计算公式，故你这里提出的问题更没有办法用简单（不超过100项）的数学公式来表示。

王守恩 发表于 2017-12-20 08:53:44

sheng_jianguo 发表于 2017-12-16 14:59
因为由1至9组成的十位数，其和是45 的十位数的种数没有发现有简单计算公式，故你这里提出的问题更没有办 ...

和为11的十位数      10      
和为12的十位数      55      
和为13的十位数      220      
和为14的十位数      715      
和为15的十位数      2002      
和为16的十位数      5005      
和为17的十位数      11440      
和为18的十位数      24310      
和为19的十位数      48600   
和为20的十位数      92277      
和为21的十位数      167400      
和为22的十位数      291720      
和为23的十位数      490260      
和为24的十位数      797160      
和为25的十位数      1257444      
和为26的十位数      1928475      
和为27的十位数      2880990      
和为28的十位数      4198995      
和为29的十位数      5978070      
和为30的十位数      8322849
      
和为31的十位数      11341680      
和为32的十位数      15139395      
和为33的十位数      19808190      
和为34的十位数      25416240      
和为35的十位数      31994544      
和为36的十位数      39525330      
和为37的十位数      47930580      
和为38的十位数      57066120      
和为39的十位数      66713760      
和为40的十位数      76587432      
和为41的十位数      86338860      
和为42的十位数      95572950      
和为43的十位数      103872360      
和为44的十位数      110825370      
和为45的十位数      116052012      
和为46的十位数      119238990      
和为47的十位数      120164100      
和为48的十位数      118727070      
和为49的十位数      114950640      
和为50的十位数      108994200      

和为51的十位数      101141880      
和为52的十位数      91779450      
和为53的十位数      81365340      
和为54的十位数      70396410      
和为55的十位数      59377080      
和为56的十位数      48749190      
和为57的十位数      38896620      
和为58的十位数      30107490      
和为59的十位数      22553580      
和为60的十位数      16310910      
和为61的十位数      11338740      
和为62的十位数      7551600      
和为63的十位数      4787160      
和为64的十位数      2874060      
和为65的十位数      1612800      
和为66的十位数      831600      
和为67的十位数      390600      
和为68的十位数      163800      
和为69的十位数      50400      
和为70的十位数      12600         
                   2103049130      

zeus 发表于 2017-12-20 10:42:22

\=2103049130\]

查看完整版本: 这样的十位有多少个？