征解：一道与数论有关的组合问题

957683999

已知n是正整数，集合S={1，2，…，2n}的子集A满足：(1)A恰有n个元素，(2)A的所有元素和p恰好整除S的所有元素和q.求所有这样子集A的个數f(n)

战巡

回复 1# 957683999


首先显然$q=n(2n+1)$
至于$p$，它的最小值自然是$A=\{1,2,...,n\}$时，$p=\frac{1}{2}n(n+1)$
最大值自然是$A=\{n+1,n+2,...,2n\}$时，$p=\frac{1}{2}n(3n+1)$
于是有：
\[4>\frac{n(2n+1)}{\frac{1}{2}n(n+1)}\ge \frac{q}{p}\ge \frac{n(2n+1)}{\frac{1}{2}n(3n+1)}>1\]
可能的值也就$\frac{q}{p}=2,3$

当$\frac{q}{p}=2$，也就是$p=\frac{1}{2}n(2n+1)$时，显然只有$n$为偶数才行，$n$为奇数则$p$不可能是整数
剩下就变成求从$S$里面取$n$个数使得其和为$\frac{1}{2}n(2n+1)$有多少种组合的问题
这个问题我目前还没见过哪里有过解答......
$\frac{q}{p}=3$时也有同类问题
只能得到当$n \mod 6=5$时，$f(n)=0$

realnumber

f(1)=0+1,f(2)=2+0,f(3)=0+1,f(4)=8+2,f(5)=0,f(6)=58+7,f(7)=0+15,f(8)=526+0,
f(9)=0+69,f(10)=5448+152
以下程序搜索的，f(4)=10,其中$\frac{q}{p}=2$的8个，依次是1278,1368,1458,1467,2358,2367,2457,3456;$\frac{q}{p}=3$的2个,1236,1245
,f(6)=65,其中$\frac{q}{p}=2$的58个，;$\frac{q}{p}=3$的7个.
(7)=15,$\frac{q}{p}=3$的15个.
f(8)=526,$\frac{q}{p}=2$的526个.
f(9)=69,$\frac{q}{p}=3$的69个.