这样的十位有多少个？

王守恩

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

kastin

参考 http://bbs.emath.ac.cn/forum.php ... 67&fromuid=8865

sheng_jianguo

不知道你是要搞清楚具体怎样计算，还是只要知道满足条件的十位数有多少个？
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

我的结果是2103049130种

1. #include <stdio.h>
   
2. #include <limits.h>
   
3. 
   
4. unsigned long long lltotal;
   
5. unsigned long long lltotal2;
   
6. int fac[11];
   
7. void initfac()
   
8. {
   
9.     int i;
   
10.     fac[0]=1;
    
11.     for(i=1;i<=10;i++){
    
12.         fac[i]=fac[i-1]*i;
    
13.     }
    
14. }
    
15. 
    
16. void dump_pattern(int a[])
    
17. {
    
18.     int i;
    
19.     for(i=9;i>=1;i--){
    
20.         printf("%d ",a[i]);
    
21.     }
    
22. }
    
23. 
    
24. void enumall(int a[], int k, int s)//a[1]+a[2]+...+a[k]=s
    
25. {
    
26.     int i;
    
27.     if(k==1&&s<=1){
    
28.         a[1]=s;
    
29.         dump_pattern(a);
    
30.         int c=fac[10];
    
31.         for(i=1;i<=9;i++){
    
32.             c/=fac[a[i]];
    
33.         }
    
34.         printf("%d\n",c);
    
35.         lltotal+=c;
    
36.         if(lltotal2>=ULLONG_MAX-1-c){
    
37.             lltotal2+=c+1;
    
38.         }else{
    
39.             lltotal2+=c;
    
40.         }
    
41.         return;
    
42.     }
    
43.     int start = s;
    
44.     if(start>k)start=k;
    
45.     for(i=start;i>=0;i--){
    
46.         a[k]=i;
    
47.         enumall(a,k-1,s-i);
    
48.     }
    
49. }
    
50. 
    
51. int main()
    
52. {
    
53.     int a[10];
    
54.     initfac();
    
55.     enumall(a,9,10);
    
56.     printf("Total %llu, %llu\n", lltotal, lltotal2);
    
57.     return 0;
    
58. }
    

复制代码

王守恩

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-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$

王守恩

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-14 16:28
谢谢sheng_jianguo！您的解答让我长进不少！
还是这道题，可以用数学公式来表示答案吗？
有45个数字： ...

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

王守恩

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

\[10! \text{Coefficient}\left[\prod _{k=1}^9 \sum _{n=0}^{10-k} \frac{x^n}{n!},x^{10}\right]=2103049130\]