V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
pangtianyu
V2EX  ›  数学

关于组合数学和整数拆分的问题

  •  
  •   pangtianyu · 2016-05-23 02:19:59 +08:00 · 5659 次点击
    这是一个创建于 2866 天前的主题,其中的信息可能已经有所发展或是发生改变。

    Composition

    Strict Composition

    一个正整数 n 的 (strict) composition 是把 n 写成一个正整数数列的和的形式。
    举例,正整数 4 可以拆分成

    • 4
    • 3 + 1
    • 1 + 3
    • 2 + 2
    • 2 + 1 + 1
    • 1 + 2 + 1
    • 1 + 1 + 2
    • 1 + 1 + 1 + 1

    一共 8 种 composition 。注意顺序不同是有所谓的。

    如何数一个正整数 n 有多少种 composition 呢?首先,一个正整数 n 可以变成 n 个 1 相加的形式。所以,我们可以先写出一个带有 n 个 1 的数列:

    1 _ 1 _ 1 _ 1 _ 1 _ 1 _ 1 _ ... 1 _ 1 _ 1 _ 1

    中间的空格保留留空。在空格中我们可以填入逗号「,」或者加号「+」。填入不同的逗号或者加号,我们就会组成不同的 composition 。所以,问题变成了有多少种方式去填入逗号。如果逗号的位置确定了,加号的位置也就会跟着确定。在这里,假设我们要把 n 分成 k 个部分,那么我们就需要填入 k-1 个逗号。我们现在知道一共有 n-1 个空格可以填。所以,一共有 种方式去填入逗号(详见组合)。这也就相当于把 n 分成 k 个部分的时候,一共有 种 composition 的样子。最少我们能分成 1 个部分,就是 n 自己本身;而最多我们能分成 n 个部分,也就是 n 个 1 相加。所以,对于一个 n 来讲,它的 composition 的个数就等于

    Weak Composition

    如果把 0 也算做一个部分,那么我们叫它 weak composition 。我们不能定义一个正整数 n 一共有多少种 weak composition ,因为可以有无限多个 0 相加;但是我们能得知当把 n 分成 k 个部分的时候,一共有多少种 weak composition 。例如,当 n = 4 的时候,如果把 4 分成 2 个部分,那么一共有 5 种 weak composition ,如下:

    • 3 + 1
    • 2 + 2
    • 1 + 3
    • 0 + 4
    • 4 + 0

    如何得知当把一个正整数 n 拆分成 k 个部分的时候有多少种 weak composition ?首先,把 n 想象成 n 个 1 ,如果要把 n 个 1 组成的数列分成 k 个部分,那么我们需要有 k-1 个隔板。举例:当 n = 9, k = 4 的时候,其中一种情况是: 1 1 1 1 | 1 1 || 1 1 1 ,也就是 4 + 2 + 0 + 3 。所以问题可以变成:一共有 n + (k - 1) 个物体组成一个数列,把其中 n 个物体变成 1 ,其余 k - 1 个物体变成隔板,一共有多少种方法?这里如果 n 个 1 的位置确定了,余下的隔板位置也就确定了,反之也是如此。所以,有 方法。综上,可以得出结论,把一个正整数 n 拆分成 k 个部分, weak composition 的个数为

    问题来了

    问题 1 :如果要把 n 分成 k 个部分,但是每个部分不能大于 m ,请问一共有多少种 composition ? 举例,当 n = 4, k = 2, m = 2 的时候,整数 4 的 composition 只有一个: 2 + 2 。

    问题 2 :要把 n 分成 k 个部分,但是每个部分不能大于 m ,请问一共有多少种 weak composition ?

    7 条回复    2018-04-18 01:26:08 +08:00
    pangtianyu
        1
    pangtianyu  
    OP
       2016-05-23 09:07:05 +08:00
    难道 V2EX 上面没有对这种感兴趣的嘛 0.0
    di00di
        2
    di00di  
       2016-05-23 21:09:19 +08:00   ❤️ 2
    可以按照这个思路解:
    step1. 算出没有约束也就是每个部分可以是 1 到 n 的解
    step2. 计算 k 个部分大于等于 m + 1 的解。此步计算可以作变量替换相当于把 n-k*(m+1)分成 k 个部分的解
    step3. 根据容斥原理计算出最后的解。
    nsqiang
        3
    nsqiang  
       2018-01-29 09:32:44 +08:00
    @pangtianyu 问题解决了么~
    nsqiang
        4
    nsqiang  
       2018-01-29 10:04:14 +08:00
    nsqiang
        6
    nsqiang  
       2018-02-01 22:36:00 +08:00
    @nsqiang 收藏~
    pangtianyu
        7
    pangtianyu  
    OP
       2018-04-18 01:26:08 +08:00
    @nsqiang #6 哈哈才看到不好意思 已经解决了 这是我一次数学课 final exam 的问题 我做了不太确定想来问问
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3101 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 12:43 · PVG 20:43 · LAX 05:43 · JFK 08:43
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.