当前位置: 首页 > news >正文

8类放球问题

放球问题简介

放球问题是一类很有意思的排列组合问题。通俗来说,就是把n个小球放到m个盒子里,问有几种放法。根据小球是否相同,盒子是否相同,是否允许有空盒,又可以把问题细分为8个具体的问题。其中有一些问题是非常简单的,有一些问题经常出现在一些经典的排列组合问题当中,有一些问题则比较有难度,难以通过一个表达式直接写出答案。

放球问题的解法

我们分8种情况具体讨论这个问题。假设有n个小球,m个盒子,且默认n ≥ \geq m。我们就从易到难,慢慢来分析。

1.球不同,盒不同,允许有空盒

这是最简单的一种情况。对于每个小球,有m种放法,一共有n个小球,于是一共有 m n m^n mn种放法。

2.球相同,盒不同,不允许有空盒

由于球相同,我们可以把每个球看成一个0,n个球组成了一个长度为n的全0序列。放小球的过程可以看成把这个序列分为m段,且每段长度大于0。于是我们就可以用隔板法解决了。问题相当于在这个长度为n的序列中插入m-1个隔板,从而就把序列分成了m段。这个序列有n-1个间隙,为了保证每段长度大于0,则只需要两块隔板不放在同一个间隙中。于是问题就变成了,在n-1个间隙中,挑选m-1个位置放隔板,即 C n − 1 m − 1 C_{n-1}^{m-1} Cn1m1种放法。

3.球相同,盒不同,允许有空盒

这个有两种做法。第一种做法是这样的。跟上面那种情况类似,也是看成一个序列,但是两个隔板是可以相邻的。n个球,m-1个隔板,一共长度为n+m-1。我们只需要在这个n+m-1个位置中选m-1个位置作为隔板即可,于是有 C n + m − 1 m − 1 C_{n+m-1}^{m-1} Cn+m1m1种放法。
第二种做法是,可以认为我们一开始有n+m个小球,先在每个盒中放上一个小球。于是问题就转化为了n+m个球放在m个盒子里,不允许有空盒的情况。套用上面的公式,得有 C n + m − 1 m − 1 C_{n+m-1}^{m-1} Cn+m1m1种放法。

4.球不同,盒不相同,不允许有空盒

到这里,问题开始变得难起来了。正难则反,我们反过来,考虑必定存在空盒的情况。这里我们采用容斥原理的方法做。由于盒子不同,给每个盒子从1-m编个号。令 A i A_i Ai表示第i个盒子是空的情况,|A|表示在A情况下的方案数。比如 ∣ A i ∣ |A_i| Ai表示第i个盒子一定是空盒的方案数,那么 ∣ A i ∣ = ( m − 1 ) n |A_i|=(m-1)^n Ai=(m1)n
∣ A i ∩ A j ∣ |A_i \cap A_j| AiAj表示第i个盒子和第j个盒子同时是空盒的情况数,即 ( m − 2 ) n (m-2)^n (m2)n种。我们要求有空盒的方案数,即 ∣ A 1 ∪ A 2 ∪ ⋯ ∪ A m ∣ |A_1\cup A_2\cup \cdots \cup A_m| A1A2Am
根据容斥原理的公式,
∣ A 1 ∪ A 2 ∪ ⋯ ∪ A m ∣ = ∑ 1 ≤ i ≤ m ∣ A i ∣ − ∑ 1 ≤ i < j ≤ m ∣ A i ∩ A j ∣ + ∑ 1 ≤ i < j < k ≤ m ∣ A i ∩ A j ∩ A k ∣ − ⋯ + ( − 1 ) m − 1 ∣ A 1 ∩ A 2 ∩ ⋯ ∩ A m ∣ = C m 1 ( m − 1 ) n − C m 2 ( m − 2 ) n + C m 3 ( m − 3 ) n − ⋯ + ( − 1 ) m − 1 C m m ( m − m ) n = ∑ k = 1 m ( − 1 ) k − 1 C m k ( m − k ) n |A_1\cup A_2\cup \cdots \cup A_m|=\sum_{1\leq i \leq m}{|A_i|}-\sum_{1\leq i<j \leq m}{|A_i \cap A_j|}+\sum_{1 \leq i<j<k \leq m}{|A_i \cap A_j \cap A_k|}-\cdots+(-1)^{m-1}|A_1 \cap A_2 \cap \cdots \cap A_m|=C_m^1(m-1)^n-C_m^2(m-2)^n+C_m^3(m-3)^n-\cdots +(-1)^{m-1}C_m^m(m-m)^n=\sum_{k=1}^m{(-1)^{k-1}C_m^k(m-k)^n} A1A2Am=1imAi1i<jmAiAj+1i<j<kmAiAjAk+(1)m1A1A2Am=Cm1(m1)nCm2(m2)n+Cm3(m3)n+(1)m1Cmm(mm)n=k=1m(1)k1Cmk(mk)n
必定存在空盒的方案数有 ∑ k = 1 m ( − 1 ) k − 1 C m k ( m − k ) n \sum_{k=1}^m{(-1)^{k-1}C_m^k(m-k)^n} k=1m(1)k1Cmk(mk)n种,那么不存在空盒的方案数有 m n − ∑ k = 1 m ( − 1 ) k − 1 C m k ( m − k ) n = ∑ k = 0 m ( − 1 ) k C m k ( m − k ) n m^n-\sum_{k=1}^m{(-1)^{k-1}C_m^k(m-k)^n}=\sum_{k=0}^m{(-1)^kC_m^k(m-k)^n} mnk=1m(1)k1Cmk(mk)n=k=0m(1)kCmk(mk)n
总的来说,求解的思路是通过容斥原理,把较难的不允许有空盒的情况转化为较为容易的允许有空盒的情况。

5.球不同,盒相同,不允许有空盒

这个问题跟上一个问题相比,仅仅是盒不同改成了盒相同,那么由于球不同,所以这个问题的放法是上面问题放法的 1 m ! \frac{1}{m!} m!1,即 1 m ! ∑ k = 0 m ( − 1 ) k C m k ( m − k ) n \frac{1}{m!}\sum_{k=0}^m{(-1)^kC_m^k(m-k)^n} m!1k=0m(1)kCmk(mk)n
由于该问题求解起来较为复杂,所以人们为这个问题专门定义了一个术语——第二类斯特林数。第二类斯特林数 S ( n , m ) S(n,m) S(n,m)表示将n个不同的小球放在m个相同的盒子中,不允许有空盒的方案数。
那么,根据我们的推导, S ( n , m ) = 1 m ! ∑ k = 0 m ( − 1 ) k C m k ( m − k ) n S(n,m)=\frac{1}{m!}\sum_{k=0}^m{(-1)^kC_m^k(m-k)^n} S(n,m)=m!1k=0m(1)kCmk(mk)n
同时,这也是 S ( n , m ) S(n,m) S(n,m)的通项公式。

6.球不同,盒相同,允许有空盒

相比于上面的问题,这个问题允许有空盒了。那么我们只需要枚举非空盒的个数,就能转化为上面的问题了。有i个非空盒时,方案数为 S ( n , i ) S(n,i) S(n,i)。于是总方案数为 ∑ i = 1 m S ( n , i ) \sum_{i=1}^m{S(n,i)} i=1mS(n,i)

7.球相同,盒相同,允许有空盒

这个问题可以用母函数的方法做,但是由于本人才疏学浅,没有学过母函数的方法,于是在这里提供一种递推的解法。
设方案数为 f ( n , m ) f(n,m) f(n,m)
先给出边界情况,当小球数为0或盒子数为1,肯定就只有1种方案了。
再分类讨论,给出递推关系式。
若小球数比盒子数少,则多出来的盒子只能空着,于是有 f ( n , m ) = f ( n , n ) , n < m f(n,m)=f(n,n),n<m f(n,m)=f(n,n)n<m
若小球数不比盒子数少,那么我们就要放小球了。整体思路是,把盒子排成一排,后面的盒子放的小球数不能超过前面盒子的小球数。这样枚举的话,才能不重不漏。我们考虑当前的最后一个盒子,有放小球和不放小球两种情况。如果空着,方案数为 f ( n , m − 1 ) f(n,m-1) f(n,m1)。如果要放小球,由于这个盒子的小球必须是最少的,所以前面所有盒子都要放一个小球,这样的方案数为 f ( n − m , m ) f(n-m,m) f(nm,m)
合起来,可以得到 f ( n , m ) f(n,m) f(n,m)的递推表达式
f ( n , m ) = { 1 n = 0 ∣ ∣ m = 1 f ( n , n ) n < m f ( n − m , m ) + f ( n , m − 1 ) n ≥ m f(n,m)=\begin{cases} 1 & n=0 || m=1 \\ f(n,n) & n<m \\ f(n-m,m)+f(n,m-1) & n\geq m \end{cases} f(n,m)= 1f(n,n)f(nm,m)+f(n,m1)n=0∣∣m=1n<mnm

8.球相同,盒相同,不允许有空盒

既然球跟盒都相同,那不妨拿出m个球,先在每个盒子里放上一个球。这样问题就转化为,将n-m个相同的小球放到m个盒子里,允许有空盒的问题了。方案数即为 f ( n − m , m ) f(n-m,m) f(nm,m)

代码

下面是我写的python代码

import math
def f(n,m):if n==0 or m==1:return 1if n<m:return f(n,n)return f(n-m,m)+f(n,m-1)
def S(n,m):return sum((-1)**k * math.comb(m, k) * math.pow(m-k, n) for k in range(m+1))/math.factorial(m)
def fangqiu(n,m,qiu,he,kong): #n表示球数,m表示盒数,qiu表示小球是否相同,he表示盒子是否相同,kong表示是否允许有空盒if qiu==0 and he==0 and kong==1:return m**nif qiu==1 and he==0 and kong==0:return math.comb(n-1,m-1)if qiu==1 and he==0 and kong==1:return math.comb(n+m-1,m-1)if qiu==0 and he==0 and kong==0:return S(n, m)*math.factorial(m)if qiu==0 and he==1 and kong==0:return S(n, m)if qiu==0 and he==1 and kong==1:return sum(S(n,i) for i in range(1,m+1))if qiu==1 and he==1 and kong==1:return f(n,m)if qiu==1 and he==1 and kong==0:return f(n-m,m)
n,m=map(int,input().split())
print(int(fangqiu(n,m,0,0,1)))

总结

虽然我们按一定的标准,划分出了8个问题,但其实这8个问题又有很多变种。比如,我们只关注了 n ≥ m n\geq m nm的情况,我们得出的结论一部分对 n ≤ m n\leq m nm适用,一部分却不适用了。掌握解决这一类问题的方法比记住结论更加重要。

相关文章:

8类放球问题

放球问题简介 放球问题是一类很有意思的排列组合问题。通俗来说&#xff0c;就是把n个小球放到m个盒子里&#xff0c;问有几种放法。根据小球是否相同&#xff0c;盒子是否相同&#xff0c;是否允许有空盒&#xff0c;又可以把问题细分为8个具体的问题。其中有一些问题是非常简…...

【APP VTable】和市面上的 Table 组件一样,都是接收表格[] 以及数据源[]

博主&#xff1a;_LJaXi Or 東方幻想郷 专栏&#xff1a; uni-app | 小程序开发 开发工具&#xff1a;HBuilderX 这里写目录标题 表格组件USE 表格组件 <template><view class"scroll-table-wrapper"><view class"scroll-table-container"…...

深度学习 anaconda 安装问题

配置anaconda 在官网下载匹配版本的anaconda&#xff08;官网下载可能时间比较长&#xff09;&#xff0c;可以选择清华镜像。 安装过程默认即可&#xff0c;或者根据情况进行修改。 旧版本是可以在安装的时候勾选添加路径到环境变量中的&#xff0c;但是我安装的是2023.9月…...

为什么现在学Rust编程是最好时机?

1.摘要 Rust是由Mozilla主导开发的通用、编译型编程语言。设计准则为:安全、并发、实用,支持函数式、并发式、过程式以及面向对象的编程风格。Rust的设计目标之一,是要使设计大型的互联网客户端和服务器的任务变得更容易,因此更加强调安全性、存储器配置以及并发处理等方面的特…...

Java——Spring的控制反转(一文详解IOC)

Spring&#xff0c;Spring MVC&#xff0c;Spring Boot 三者比较 答&#xff1a; 这三者专注的领域不同&#xff0c;解决的问题也不一样&#xff1b;总的来说&#xff0c;Spring 就像一个大家族&#xff0c;有众多衍生产品例如 Boot&#xff0c;Security&#xff0c;JPA等等。…...

Android Glide限定onlyRetrieveFromCache取内存缓存submit超时阻塞方式,Kotlin

Android Glide限定onlyRetrieveFromCache取内存缓存submit超时阻塞方式,Kotlin import android.os.Bundle import android.util.Log import android.widget.ImageView import androidx.appcompat.app.AppCompatActivity import androidx.lifecycle.lifecycleScope import com.b…...

tinymce输入框怎么限制只输入空格或者回车时不能提交

项目场景&#xff1a; 项目相关背景&#xff1a; tinymce输入框只输入空格或者回车时提交的空数据毫无意义&#xff0c;所以需要限制一下 无意义的输入&#xff1a; 解决方案&#xff1a; 因为tinymce输入框传到后端的数据是代码形式&#xff0c;所以不能直接.trem&#…...

时间、空间复杂度的例题详解

文章前言 上篇文章带大家认识了数据结构和算法的含义&#xff0c;以及理解了时间、空间复杂度&#xff0c;那么接下来来深入理解一下时间、空间复杂度。 时间复杂度实例 实例1 // 计算Func2的时间复杂度&#xff1f; void Func2(int N) {int count 0;for (int k 0; k <…...

Ubuntu22.04 搭建 OpenHarmony 命令行开发环境

文章目录 简介安装工具链获取gitee源码安装编译工具编译测试 简介 在本文中&#xff0c;我们将介绍如何使用命令行工具在你的设备上安装OpenHarmony操作系统。OpenHarmony是一个开源的、面向物联网&#xff08;IoT&#xff09;设备的操作系统&#xff0c;它提供了一套全面的开…...

10.27 知识总结(前端)

一、 前端 1.1 什么是前端&#xff1f; 前端是所有跟用户直接打交道的都可以称之为是前端 比如&#xff1a;PC页面、手机页面、平板页面、汽车显示屏、大屏幕展示出来的都是前端内容 通俗点就是能够用肉眼看到的都是“前端” 1.2 为什么要学前端 学了前端以后我们就可以做全栈工…...

操作系统(02326)考试题库

博客主页&#xff1a;https://tomcat.blog.csdn.net 博主昵称&#xff1a;农民工老王 主要领域&#xff1a;Java、Linux、K8S 期待大家的关注&#x1f496;点赞&#x1f44d;收藏⭐留言&#x1f4ac; 目录 单选题多选题主观题 单选题 把并发进程中与共享变量有关的程序段称为…...

LeetCode题:70爬楼梯,126斐波那契数

目录 70&#xff1a;爬楼梯 题目要求&#xff1a; 解题思路&#xff1a;&#xff08;类似斐波那契数&#xff09; 递归解法&#xff1a; 非递归解法&#xff1a; 126&#xff1a;斐波那契数 题目要求&#xff1a; 解题思路&#xff1a; 递归解法&#xff1a; 非递归解…...

VTK OrientationMarker 方向 三维坐标系 相机坐标轴 自定义坐标轴

本文 以 Python 语言开发 我们在做三维软件开发时&#xff0c;经常会用到相机坐标轴&#xff0c;来指示当前空间位置&#xff1b; 坐标轴效果&#xff1a; 相机方向坐标轴 Cube 正方体坐标轴 自定义坐标轴&#xff1a; Code&#xff1a; Axes def main():colors vtkNamedC…...

工控安全与网络安全有什么不同?

在当代&#xff0c;全球制造业正在经历一场前所未有的技术变革。工业4.0不仅代表着自动化和数据交换的进步&#xff0c;它还揭示了工业自动化、智能制造与系统集成的融合。这种集成为企业带来了效率和质量的双重提升&#xff0c;但同时也暴露出新的安全隐患。工控系统成为了这一…...

性能测试工具:Jmeter介绍

JMeter是一个开源的Java应用程序&#xff0c;由Apache软件基金会开发和维护&#xff0c;可用于性能测试、压力测试、接口测试等。 1. 原理 JMeter的基本原理是模拟多用户并发访问应用程序&#xff0c;通过发送HTTP请求或其他协议请求&#xff0c;并测量响应时间、吞吐量、并发…...

Golang Struct 继承的深入讨论和细节

1&#xff09;结构体可以使用嵌套匿名结构体所有的字段和方法&#xff0c;即&#xff1a;首字母大写或者小写的字段、方法&#xff0c;都可以使用。 type A struct {Name stringage int }func (a *A) SayName() {fmt.Println("A say name", a.Name) }func (a *A) s…...

Android11分区介绍

1.分区汇总 3566及3568分区对应如下: rockdev/Image-rk3566_rgo/ ├── boot.img ├── dtbo.img ├── MiniLoaderAll.bin ├── misc.img ├── parameter.txt ├── recovery.img ├── super.img ├── uboot.img └── vbmeta.img 2.分区说明 分区 说明 boo…...

goland无法调试问题解决

goland 无法调试问题解决 golang 版本升级后&#xff0c;goland 无法进行调试了 首先请看自己下载的版本是否有误 1.apple系 M系列芯片的 arm64版本 2.apple系 intel系列芯片的x86_64 3.windows系 intel解决如下&#xff1a; 查看gopath ericsanchezErics-Mac-mini gww-api…...

关于近期IP-Guard新版本客户端重复发送邮件的问题处理说明

关于近期新版本客户端重复发送邮件的问题处理说明 一、问题描述 近期部分客户反馈,升级到新版本的客户端(4.81.341.0、4.82.621.0及以上),使用SMTP协议发送邮件时,会出现重复发送邮件的情况,主要表现为以下两种现象: Outlook发送包含大量收件人的邮件时,收件人邮箱可能…...

linux java 启动脚本

#!/bin/sh## java env #export JAVA_HOME/data/jdk1.8.0_121 #export JRE_HOME$JAVA_HOME/jre## service name #当前目录 SERVICE_DIR$(cd dirname $0; pwd) echo "$SERVICE_DIR" #jar包路径 JAR_DIRls -ltr $SERVICE_DIR/*.jar| tail -1 echo "JAR_DIR $JAR_DI…...

wordpress后台更新后 前端没变化的解决方法

使用siteground主机的wordpress网站&#xff0c;会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后&#xff0c;网站没有变化的情况。 不熟悉siteground主机的新手&#xff0c;遇到这个问题&#xff0c;就很抓狂&#xff0c;明明是哪都没操作错误&#x…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析

1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具&#xff0c;该工具基于TUN接口实现其功能&#xff0c;利用反向TCP/TLS连接建立一条隐蔽的通信信道&#xff0c;支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式&#xff0c;适应复杂网…...

网络六边形受到攻击

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 抽象 现代智能交通系统 &#xff08;ITS&#xff09; 的一个关键要求是能够以安全、可靠和匿名的方式从互联车辆和移动设备收集地理参考数据。Nexagon 协议建立在 IETF 定位器/ID 分离协议 &#xff08;…...

【Oracle APEX开发小技巧12】

有如下需求&#xff1a; 有一个问题反馈页面&#xff0c;要实现在apex页面展示能直观看到反馈时间超过7天未处理的数据&#xff0c;方便管理员及时处理反馈。 我的方法&#xff1a;直接将逻辑写在SQL中&#xff0c;这样可以直接在页面展示 完整代码&#xff1a; SELECTSF.FE…...

逻辑回归:给不确定性划界的分类大师

想象你是一名医生。面对患者的检查报告&#xff08;肿瘤大小、血液指标&#xff09;&#xff0c;你需要做出一个**决定性判断**&#xff1a;恶性还是良性&#xff1f;这种“非黑即白”的抉择&#xff0c;正是**逻辑回归&#xff08;Logistic Regression&#xff09;** 的战场&a…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

Auto-Coder使用GPT-4o完成:在用TabPFN这个模型构建一个预测未来3天涨跌的分类任务

通过akshare库&#xff0c;获取股票数据&#xff0c;并生成TabPFN这个模型 可以识别、处理的格式&#xff0c;写一个完整的预处理示例&#xff0c;并构建一个预测未来 3 天股价涨跌的分类任务 用TabPFN这个模型构建一个预测未来 3 天股价涨跌的分类任务&#xff0c;进行预测并输…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

C++中string流知识详解和示例

一、概览与类体系 C 提供三种基于内存字符串的流&#xff0c;定义在 <sstream> 中&#xff1a; std::istringstream&#xff1a;输入流&#xff0c;从已有字符串中读取并解析。std::ostringstream&#xff1a;输出流&#xff0c;向内部缓冲区写入内容&#xff0c;最终取…...