数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 5176|回复: 17

将正整数 n 拆分成 3 个不全相等的正整数相加,有几种不同的拆分法?

[复制链接]
发表于 2021-10-31 12:31 | 显示全部楼层 |阅读模式
n 分成不完全相同 3 部分的分区数a(n)。
例子
a(4)=1: (1,1,2)
a(5)=2: (1,1,3),(1,2,2)       
a(6)=2: (1,1,4),(1,2,3)
a(7)=4: (1,1,5),(1,2,4),(1,3,3),(2,2,3)
a(8)=5: (1,1,6),(1,2,5),(1,3,4),(2,2,4),(2,3,3)
a(9)=6: (1,1,7),(1,2,6),(1,3,5),(1,4,4),(2,2,5),(2,3,4)               

发表于 2021-10-31 22:12 | 显示全部楼层
将正整数 n 拆分成 3 个不全相等的正整数相加,有几种不同的拆分法?

a(n)=[(n^2-1)/12] ,其中 [ ] 表示向下取整。

a(1)=0
a(2)=0
a(3)=0
a(4)=1
a(5)=2
a(6)=2
a(7)=4
a(8)=5
a(9)=6
a(10)=8
a(11)=10
a(12)=11
a(13)=14
a(14)=16
a(15)=18
a(16)=21
a(17)=24
a(18)=26
a(19)=30

评分

参与人数 1威望 +20 收起 理由
王守恩 + 20 厉害了!陆老师!谢谢!

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-11-1 08:03 | 显示全部楼层
本帖最后由 王守恩 于 2021-11-1 09:01 编辑

将正整数 n 拆分成 3 个不全相等的正整数相加,有几种不同的拆分法?

将正整数 n 拆分成 4 个不全相等的正整数相加,有几种不同的拆分法?
将正整数 n 拆分成 5 个不全相等的正整数相加,有几种不同的拆分法?
将正整数 n 拆分成 6 个不全相等的正整数相加,有几种不同的拆分法?
将正整数 n 拆分成 7 个不全相等的正整数相加,有几种不同的拆分法?
将正整数 n 拆分成 8 个不全相等的正整数相加,有几种不同的拆分法?
将正整数 n 拆分成 9 个不全相等的正整数相加,有几种不同的拆分法?
.............
将正整数 n 拆分成 m 个不全相等的正整数相加,有几种不同的拆分法?
挑战一下:做题目的最高境界,一次到位,还敢有吗?!

就这么些数字串,可是在《整数序列在线百科全书(OEIS)》找不到的。

谢谢 Nicolas2050!

点评

在告诉你一个事实:这类问题是BAT大厂笔试基础试题。自己对比下差距。你只想到计数,具体的分配方案你能给出吗?比如整数是100000.  发表于 2021-11-1 08:31
再提示下你:这类问题也叫非均匀分堆问题,在物流输送优化中是典型的模型。  发表于 2021-11-1 08:25
要不我提醒下你那个问题是整数拆分你会想这类问题?这就是眼界!  发表于 2021-11-1 08:23
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-11-1 14:57 | 显示全部楼层
本帖最后由 王守恩 于 2021-11-1 15:06 编辑
王守恩 发表于 2021-11-1 08:03
将正整数 n 拆分成 3 个不全相等的正整数相加,有几种不同的拆分法?

将正整数 n 拆分成 4 个不全相等的 ...

谢谢 Nicolas2050!

挑战一下:做题目的最高境界,一次到位,还敢有吗?!

2,将正整数 n 拆分成 2 个不全相等的正整数相加,有a(n)种不同的拆分法。
  a(n)=CoefficientList\(\bigg[\)Series\(\bigg[\)\(\displaystyle\prod_{i=1}^2\frac{1}{1-x^i},(x,0,n)\bigg],x\bigg]+\bigg\lceil\frac{n_{2}}{2}\bigg\rceil-1\)    n=2,3,4,5,......
  {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16,

3,将正整数 n 拆分成 3 个不全相等的正整数相加,有a(n)种不同的拆分法。
  a(n)=CoefficientList\(\bigg[\)Series\(\bigg[\)\(\displaystyle\prod_{i=1}^3\frac{1}{1-x^i},(x,0,n)\bigg],x\bigg]+\bigg\lceil\frac{n_{3}}{3}\bigg\rceil-1\)    n=3,4,5,6,......
  {0, 1, 2, 2, 4, 5, 6, 8, 10, 11, 14, 16, 18, 21, 24, 26, 30, 33, 36, 40, 44, 47, 52, 56, 60, 65, 70, 74, 80,

4,将正整数 n 拆分成 4 个不全相等的正整数相加,有a(n)种不同的拆分法。
  a(n)=CoefficientList\(\bigg[\)Series\(\bigg[\)\(\displaystyle\prod_{i=1}^4\frac{1}{1-x^i},(x,0,n)\bigg],x\bigg]+\bigg\lceil\frac{n_{4}}{4}\bigg\rceil-1\)    n=4,5,6,7,......
  {0, 1, 2, 3, 4, 6, 9, 11, 14, 18, 23, 27, 33, 39, 47, 54, 63, 72, 84, 94, 107, 120, 136, 150, 168, 185, 206,

5,将正整数 n 拆分成 5 个不全相等的正整数相加,有a(n)种不同的拆分法。
  a(n)=CoefficientList\(\bigg[\)Series\(\bigg[\)\(\displaystyle\prod_{i=1}^5\frac{1}{1-x^i},(x,0,n)\bigg],x\bigg]+\bigg\lceil\frac{n_{5}}{5}\bigg\rceil-1\)    n=5,6,7,8,......
  {0, 1, 2, 3, 5, 6, 10, 13, 18, 23, 29, 37, 47, 57, 70, 83, 101, 119, 141, 164, 191, 221, 255, 291, 333, 376,

6,将正整数 n 拆分成 6 个不全相等的正整数相加,有a(n)种不同的拆分法。
  a(n)=CoefficientList\(\bigg[\)Series\(\bigg[\)\(\displaystyle\prod_{i=1}^6\frac{1}{1-x^i},(x,0,n)\bigg],x\bigg]+\bigg\lceil\frac{n_{6}}{6}\bigg\rceil-1\)    n=6,7,8,9,......
  {0, 1, 2, 3, 5, 7, 10, 14, 20, 26, 35, 44, 57, 71, 90, 110, 136, 163, 198, 235, 282, 331, 391, 454, 531, 612,

7,将正整数 n 拆分成 7 个不全相等的正整数相加,有a(n)种不同的拆分法。
  a(n)=CoefficientList\(\bigg[\)Series\(\bigg[\)\(\displaystyle\prod_{i=1}^7\frac{1}{1-x^i},(x,0,n)\bigg],x\bigg]+\bigg\lceil\frac{n_{7}}{7}\bigg\rceil-1\)    n=7,8,9,10,......
  {0, 1, 2, 3, 5, 7, 11, 14, 21, 28, 38, 49, 65, 82, 104, 131, 164, 201, 248, 300, 364, 435, 522, 618, 733, 860,

8,将正整数 n 拆分成 8 个不全相等的正整数相加,有a(n)种不同的拆分法。
  a(n)=CoefficientList\(\bigg[\)Series\(\bigg[\)\(\displaystyle\prod_{i=1}^8\frac{1}{1-x^i},(x,0,n)\bigg],x\bigg]+\bigg\lceil\frac{n_{8}}{8}\bigg\rceil-1\)    n=8,9,10,11,......
  {0, 1, 2, 3, 5, 7, 11, 15, 21, 29, 40, 52, 70, 89, 116, 146, 185, 230, 288, 352, 434, 525, 638, 764, 918, 1090,

9,将正整数 n 拆分成 9 个不全相等的正整数相加,有a(n)种不同的拆分法。
  a(n)=CoefficientList\(\bigg[\)Series\(\bigg[\)\(\displaystyle\prod_{i=1}^9\frac{1}{1-x^i},(x,0,n)\bigg],x\bigg]+\bigg\lceil\frac{n_{9}}{9}\bigg\rceil-1\)    n=9,10,11,12,......
  {0, 1, 2, 3, 5, 7, 11, 15, 22, 29, 41, 54, 73, 94, 123, 157, 201, 252, 317, 393, 488, 598, 732, 887,1076,1291,

就这么些数字串,可是在《整数序列在线百科全书(OEIS)》找不到的。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-11-4 10:02 | 显示全部楼层
王守恩 发表于 2021-11-1 14:57
谢谢 Nicolas2050!

挑战一下:做题目的最高境界,一次到位,还敢有吗?!

将正整数 n 拆分成 k 个不全相等的正整数相加,有a(n)种不同的拆分法。
这样就可以。 a(n)=Length@IntegerPartitions\(\bigg[n, k\bigg]+\bigg\lceil\frac{n_{k}}{k}\bigg\rceil-1\)  

点评

100拆分3个正整数之和,有多少种?给出完整方案。  发表于 2021-11-4 15:43
回复 支持 反对

使用道具 举报

发表于 2021-11-4 11:12 | 显示全部楼层
拆分数的计算机具体的实现方法有:  

1. 递归法
2. 动态规划
3. 母函数法
4. 五边形数定理  

,王寿嗯你可以学学母函数法。

回复 支持 反对

使用道具 举报

发表于 2021-11-4 11:39 | 显示全部楼层
能提出如此丑陋的问题在下实属佩服
回复 支持 反对

使用道具 举报

发表于 2021-11-4 16:00 | 显示全部楼层
在电影《知无涯者》中看到麦克马洪手算了前200个整数的拆分数,在观影时我注意到这个细节,自己编程算出了p(200) = 3972999029388,我才意识到每个时代的数学家都有着自己的伟大之处。

评分

参与人数 1威望 +20 收起 理由
王守恩 + 20 我这电脑怎么也出不来3972999029388

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 发表于 2021-11-4 17:58 | 显示全部楼层
本帖最后由 王守恩 于 2021-11-4 18:00 编辑
Nicolas2050 发表于 2021-11-4 11:12
拆分数的计算机具体的实现方法有:  

1. 递归法

自然数拆分成 3 块的,基本上是这串数。A001399       
   {1, 1, 2, 3, 4, 5, 7, 8, 10, 12, 14, 16, 19, 21, 24, 27, 30, 33, 37, 40, 44, 48, 52, 56, 61, 65, 70,
  75, 80, 85, 91, 96, 102, 108, 114, 120, 127, 133, 140, 147, 154, 161, 169, 176, 184, 192, 200,
208, 217, 225, 234, 243, 252, 261, 271, 280, 290, 300, 310, 320, 331, 341, 352, 363, 374, 385,
397, 408, 420, 432, 444, 456, 469, 481, 494, 507, 520, 533, 547, 560, 574, 588, 602, 616, 631,
645, 660, 675, 690, 705, 721, 736, 752, 768, 784, 800, 817, 833, 850, 867, 884, .......}
回复 支持 反对

使用道具 举报

发表于 2021-11-4 18:57 | 显示全部楼层
Nicolas2050 发表于 2021-11-4 16:00
在电影《知无涯者》中看到麦克马洪手算了前200个整数的拆分数,在观影时我注意到这个细节,自己编程算出了p ...

p(200) = 3972999029388

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x

评分

参与人数 1威望 +20 收起 理由
王守恩 + 20 先赞美了再说!

查看全部评分

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2024-7-18 10:14 , Processed in 0.093750 second(s), 17 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表