分球问题

王守恩

这题目有点难。目的很明确——把18#的通解公式引出来了！！！——谢谢 aimisiyou！！！

题目\(将1, 2, 3, ..., i, ..., n,  这 n 个数重新排列, 得到新序列a_{1}, a_{2}, a_{3}, ..., a_{i}, ..., a _{n}。 约定 i-A≤a_{i}≤i+B。求满足条件的排列数量。\)

譬如——19#——A=1,B=8 。
Table[Permanent@Table[If[k - 1 <= i <= k + 8, 1, 0], {k, n}, {i, n}], {n, 24}]
{1, 2, 4, 8, 16, 32, 64, 128, 256, 511, 1021, 2040, 4076, 8144, 16272, 32512, 64960, 129792, 259328, 518145, 1035269, 2068498, 4132920, 8257696, 16499120, 32965728, 65866496, 131603200, 262947072, 525375999, 1049716729}

譬如——20#——A=2,B=6 。
Table[Permanent@Table[If[k - 2 <= i <= k + 6, 1, 0], {k, n}, {i, n}], {n, 21}]
{1, 2, 6, 18, 54, 162, 486, 1394, 3991, 11593, 33772, 98320, 286072, 831952, 2418664, 7030816, 20441944, 59441521, 172843609, 502580846, 1461344622, 4249102850, 12354982862, 35924300898, 104456501102, 303726483778},

譬如————A=3,B=5 。A072855——有个怪怪的公式。
Table[Permanent@Table[If[k - 3 <= i <= k + 5, 1, 0], {k, n}, {i, n}], {n, 16}]
{1, 2, 6, 24, 96, 384, 1374, 4718, 16275, 57749, 206756, 739780, 2637348, 9378840, 33318804, 118439044}

譬如————A=5,B=7 。A179347——没有公式了。
Table[Permanent@Table[If[k - 5 <= i <= k + 7, 1, 0], {k, n}, {i, n}], {n, 15}]
{1, 2, 6, 24, 120, 720, 4320, 25920, 140520, 714264, 3519294, 17234438, 85314915, 431525429, 2206564916}

譬如————A=5,B=11 。OEIS——没有这串数了。
Table[Permanent@Table[If[k - 5 <= i <= k + 11, 1, 0], {k, n}, {i, n}], {n, 15}]
{1, 2, 6, 24, 120, 720, 4320, 25920, 155520, 933120, 5598720, 33592320, 192178920, 1070271384, 5893613214}

aimisiyou

王守恩 发表于 2025-8-26 16:29
这题目有点难。目的很明确——把18#的通解公式引出来了！！！——谢谢 aimisiyou！！！

题目\(将1, 2, 3,  ...

递归，降次，……不是难事。

aimisiyou

王守恩 发表于 2025-8-26 16:29
这题目有点难。目的很明确——把18#的通解公式引出来了！！！——谢谢 aimisiyou！！！

题目\(将1, 2, 3,  ...

看不懂你说的意思。

王守恩

18#的题目: 将 $1, 2, 3, ..., i, ..., n$ 这 n 个数重新排列,  得到新序列 $a_{1}, a_{2}, a_{3}, ..., a_{i}, ..., a _{n}$ 。 约定 $ i-A≤a_{i}≤i+B。A,B$ 是不同或相同的正整数。求满足条件的排列数量。

可以有统一的公式！Table[Permanent@Table[If[$k - A <= i <= k + B, 1, 0$], {k, n}, {i, n}], {n, 24}]——OEIS没有这样简单的公式。

下面的公式可以提速。$A,B$不变。——可惜公式变长了。

g[n_, A_, B_] := Module[{W = A + B + 1, p, u, s = 0, t, k, v, i, d},  For[k = 0, k < W, k++, If[(d = 1 - A + k) < 1 || d > n, s = BitOr[s, 2^k]]]; p = UnitVector[2^W, s + 1];

For[i = 1, i <= n, i++, u = ConstantArray[0, 2^W]; For[t = 0, t < 2^W, t++, If[p[[t + 1]] > 0, For[k = 0, k < W, k++, If[BitAnd[t, 2^k] == 0 && 1 <= (d = i - A + k) <= n,

v = BitShiftRight[BitOr[t, 2^k], 1]; If[i + B > n, v = BitOr[v, 2^(W - 1)]]; u[[v + 1]] += p[[t + 1]]]]]]; p = u];Total[p]]  f = Table[g[n, 3, 5], {n, 24}]

aimisiyou

王守恩 发表于 2025-8-27 00:16
18#的题目: 将 $1, 2, 3, ..., i, ..., n$ 这 n 个数重新排列,  得到新序列 $a_{1}, a_{2}, a_{3}, ..., a_ ...

如图，黄色表示每行可选取的单元格，要求选取后每行每列有且仅有一个黄色单元格，求所有选取方案数F（N，B，A）。易得，F（N，N-1,1）=2^(N-1)

王守恩

朴素的解法。

A=1,B=1,
{1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025,121393,196418,317811,514229, 832040,1346269}
先得有前2项——a(1)=1,{1},  a(2)=2,{1,2},{2,1},
a(3)=2(每个a(2)后面加3)+1((每个a(1)后面加3,2))=3,
a(4)=3(每个a(3)后面加4)+2((每个a(2)后面加4,3))=5,
a(5)=5(每个a(4)后面加5)+3((每个a(3)后面加5,4))=8,
a(6)=8(每个a(5)后面加6)+5((每个a(4)后面加6,5))=13,
......
A=1,B=2,
{1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064}
先得有前3项——a(1)=1,{1},  a(2)=2,{1,2},{2,1},  a(3)=4,{1,2,3},{1,3,2},{2,1,3},{3,1,2},
a(4)=4(每个a(3)后面加4)+2((每个a(2)后面加4,3))+1((每个a(1)后面加4,2,3))=7,
a(5)=7(每个a(4)后面加5)+4((每个a(3)后面加5,4))+2((每个a(2)后面加5,3,4))=13,
a(6)=13(每个a(5)后面加6)+7((每个a(4)后面加6,5))+4((每个a(3)后面加6,4,5))=24,
a(7)=24(每个a(6)后面加7)+13((每个a(5)后面加7,6))+7((每个a(4)后面加7,5,6))=44,
......
A=1,B=3,
{1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, 1055026, 2033628, 3919944, 7555935, 14564533}
先得有前4项——a(1)=1,{1},  a(2)=2,{1,2},{2,1},  a(3)=4,{1,2,3},{1,3,2},{2,1,3},{3,1,2},  a(4)=8,{1,2,3,4},{1,2,4,3},{1,3,2,4},{1,4,2,3},{2,1,3,4},{2,1,4,3},{3,1,2,4},{4,1,2,3},
a(5)=8(每个a(4)后面加5)+4((每个a(3)后面加5,4))+2((每个a(2)后面加5,3,4))+1((每个a(1)后面加5,2,3,4))=15,
a(6)=15(每个a(5)后面加6)+8((每个a(4)后面加6,5))+4((每个a(3)后面加6,4,5))+2((每个a(2)后面加6,3,4,5))=29,
a(7)=29(每个a(6)后面加7)+15((每个a(5)后面加7,6))+8((每个a(4)后面加7,5,6))+4((每个a(3)后面加7,4,5,6))=56,
a(8)=56(每个a(7)后面加8)+29((每个a(6)后面加8,7))+15((每个a(5)后面加8,6,7))+8((每个a(4)后面加8,5,6,7))=108,
......
A=1,B=4,
{1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, 26784, 52656, 103519, 203513, 400096, 786568, 1546352, 3040048, 5976577, 11749641, 23099186}
先得有前5项——a(1)=1,{1},  a(2)=2,{1,2},{2,1},  a(3)=4,{1,2,3},{1,3,2},{2,1,3},{3,1,2},  a(4)=8,{1,2,3,4},{1,2,4,3},{1,3,2,4},{1,4,2,3},{2,1,3,4},{2,1,4,3},{3,1,2,4},{4,1,2,3},  a(5)=16,——自己补。
a(6)=16(每个a(5)后面加6)+8((每个a(4)后面加6,5))+4((每个a(3)后面加6,4,5))+2((每个a(2)后面加6,3,4,5))+1((每个a(1)后面加6,2,3,4,5))=31,
a(7)=31(每个a(6)后面加7)+16((每个a(5)后面加7,6))+8((每个a(4)后面加7,5,6))+4((每个a(3)后面加7,4,5,6))+2((每个a(2)后面加7,3,4,5,6))=61,
a(8)=61(每个a(7)后面加8)+31((每个a(6)后面加8,7))+16((每个a(5)后面加8,6,7))+8((每个a(4)后面加8,5,6,7))+4((每个a(3)后面加8,4,5,6,7))=120,
a(9)=120(每个a(8)后面加9)+61((每个a(7)后面加9,8))+31((每个a(6)后面加9,7,8))+16((每个a(5)后面加9,6,7,8))+8((每个a(4)后面加9,5,6,7,8))=236,
......

aimisiyou

王守恩 发表于 2025-8-27 15:53
朴素的解法。

A=1,B=1,

分割，递推，有点烧脑。

王守恩

题目: 将 $1, 2, 3, ..., i, ..., n$ 这 n 个数重新排列,  得到新序列 $a_{1}, a_{2}, a_{3}, ..., a_{i}, ..., a _{n}$ 。 约定 $ i-1≤a_{i}≤i+B$ 。求满足条件的排列数量a(n)。

给出找这串具体数的一种方法——既不重复又不遗漏的去找。——又不搞复杂。

B=1,——n只能出现在尾部的2项。
{1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025,121393,196418,317811,514229, 832040,1346269}
先得有前2项——a(1)=1,{1},  a(2)=2,{1,2},{2,1},
a(3)=2(每个a(2)后面加3)+1((每个a(1)后面加3,2))=3,——a(3)=3,{1,2,3},{2,1,3},{1,3,2},——后面加3,2——顺序不能动！
a(4)=3(每个a(3)后面加4)+2((每个a(2)后面加4,3))=5,——a(4)=5,{1,2,3,4},{2,1,3,4},{1,3,2,4},{1,2,4,3},{2,1,4,3},
a(5)=5(每个a(4)后面加5)+3((每个a(3)后面加5,4))=8,——a(5)=8,{1,2,3,4,5},{2,1,3,4,5},{1,3,2,4,5},{1,2,4,3,5},{2,1,4,3,5},{1,2,3,5,4},{2,1,3,5,4},{1,3,2,5,4},
a(6)=8(每个a(5)后面加6)+5((每个a(4)后面加6,5))=13,——{1,2,3,4,5,6}{2,1,3,4,5,6}{1,3,2,4,5,6}{1,2,4,3,5,6}{2,1,4,3,5,6}{1,2,3,5,4,6}{2,1,3,5,4,6}{1,3,2,5,4,6},{1,2,3,4,6,5}{2,1,3,4,6,5}{1,3,2,4,6,5}{1,2,4,3,6,5}{2,1,4,3,6,5},
......
B=2,——n只能出现在尾部的3项。
{1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, 121415, 223317, 410744, 755476, 1389537, 2555757, 4700770, 8646064}
先得有前3项——a(1)=1,{1},  a(2)=2,{1,2},{2,1},  a(3)=4,{1,2,3},{1,3,2},{2,1,3},{3,1,2},
a(4)=4(每个a(3)后面加4)+2((每个a(2)后面加4,3))+1((每个a(1)后面加4,2,3))=7,——a(4)=7,{1,2,3,4},{1,3,2,4},{2,1,3,4},{3,1,2,4},{1,2,4,3},{2,1,4,3},{1,4,2,3},——后面加4,2,3——顺序不能动！
a(5)=7(每个a(4)后面加5)+4((每个a(3)后面加5,4))+2((每个a(2)后面加5,3,4))=13,——{1,2,3,4,5}{1,3,2,4,5}{2,1,3,4,5}{3,1,2,4,5}{1,2,4,3,5}{2,1,4,3,5}{1,4,2,3,5},{1,2,3,5,4}{1,3,2,5,4}{2,1,3,5,4}{3,1,2,5,4},{1,2,5,3,4}{2,1,5,3,4},
a(6)=13(每个a(5)后面加6)+7((每个a(4)后面加6,5))+4((每个a(3)后面加6,4,5))=24,——a(6)=24,——注意尾项只有2种可能:6或5。
{1,2,3,4,5,6}{1,3,2,4,5,6}{2,1,3,4,5,6}{3,1,2,4,5,6}{1,2,4,3,5,6}{2,1,4,3,5,6}{1,4,2,3,5,6},{1,2,3,5,4,6}{1,3,2,5,4,6}{2,1,3,5,4,6}{3,1,2,5,4,6},{1,2,5,3,4,6}{2,1,5,3,4,6},
{1,2,3,4,6,5}{1,3,2,4,6,5}{2,1,3,4,6,5}{3,1,2,4,6,5}{1,2,4,3,6,5}{2,1,4,3,6,5}{1,4,2,3,6,5},{1,2,3,6,4,5}{1,3,2,6,4,5}{2,1,3,6,4,5}{3,1,2,6,4,5},
a(7)=24(每个a(6)后面加7)+13((每个a(5)后面加7,6))+7((每个a(4)后面加7,5,6))=44,——a(7)=44,——注意尾项只有2种可能:7或6。——后面加7,5,6——顺序不能动！
{1,2,3,4,5,6,7}{1,3,2,4,5,6,7}{2,1,3,4,5,6,7}{3,1,2,4,5,6,7}{1,2,4,3,5,6,7}{2,1,4,3,5,6,7}{1,4,2,3,5,6,7}{1,2,3,5,4,6,7}{1,3,2,5,4,6,7}{2,1,3,5,4,6,7}{3,1,2,5,4,6,7}{1,2,5,3,4,6,7}{2,1,5,3,4,6,7}
{1,2,3,4,6,5,7}{1,3,2,4,6,5,7}{2,1,3,4,6,5,7}{3,1,2,4,6,5,7}{1,2,4,3,6,5,7}{2,1,4,3,6,5,7}{1,4,2,3,6,5,7}{1,2,3,6,4,5,7}{1,3,2,6,4,5,7}{2,1,3,6,4,5,7}{3,1,2,6,4,5,7},
{1,2,3,4,5,7,6}{1,3,2,4,5,7,6}{2,1,3,4,5,7,6}{3,1,2,4,5,7,6}{1,2,4,3,5,7,6}{2,1,4,3,5,7,6}{1,4,2,3,5,7,6},{1,2,3,5,4,7,6}{1,3,2,5,4,7,6}{2,1,3,5,4,7,6}{3,1,2,5,4,7,6}{1,2,5,3,4,7,6}{2,1,5,3,4,7,6},
{1,2,3,4,7,5,6}{1,3,2,4,7,5,6}{2,1,3,4,7,5,6}{3,1,2,4,7,5,6}{1,2,4,3,7,5,6}{2,1,4,3,7,5,6}{1,4,2,3,7,5,6},
......
B=3,——n只能出现在尾部的4项。
{1, 2, 4, 8, 15, 29, 56, 108, 208, 401, 773, 1490, 2872, 5536, 10671, 20569, 39648, 76424, 147312, 283953, 547337, 1055026, 2033628, 3919944, 7555935, 14564533}
先得有前4项——a(1)=1,{1},  a(2)=2,{1,2},{2,1},  a(3)=4,{1,2,3},{1,3,2},{2,1,3},{3,1,2},  a(4)=8,{1,2,3,4},{1,2,4,3},{1,3,2,4},{1,4,2,3},{2,1,3,4},{2,1,4,3},{3,1,2,4},{4,1,2,3},
a(5)=8(每个a(4)后面加5)+4((每个a(3)后面加5,4))+2((每个a(2)后面加5,3,4))+1((每个a(1)后面加5,2,3,4))=15——注意尾项只有2种可能:5或4。——后面加5,2,3,4——顺序不能动！
{1,2,3,4,5}{1,2,4,3,5}{1,3,2,4,5}{1,4,2,3,5}{2,1,3,4,5}{2,1,4,3,5}{3,1,2,4,5}{4,1,2,3,5},{1,2,3,5,4}{1,3,2,5,4}{2,1,3,5,4}{3,1,2,5,4},{1,2,5,3,4}{2,1,5,3,4},{1,5,2,3,4},
a(6)=15(每个a(5)后面加6)+8((每个a(4)后面加6,5))+4((每个a(3)后面加6,4,5))+2((每个a(2)后面加6,3,4,5))=29,——注意尾项只有2种可能:6或5。——后面加6,3,4,5——顺序不能动！
{1,2,3,4,5,6}{1,2,4,3,5,6}{1,3,2,4,5,6}{1,4,2,3,5,6}{2,1,3,4,5,6}{2,1,4,3,5,6}{3,1,2,4,5,6}{4,1,2,3,5,6}{1,2,3,5,4,6}{1,3,2,5,4,6}{2,1,3,5,4,6}{3,1,2,5,4,6}{1,2,5,3,4,6}{2,1,5,3,4,6}{1,5,2,3,4,6},
{1,2,3,4,6,5}{1,2,4,3,6,5}{1,3,2,4,6,5}{1,4,2,3,6,5}{2,1,3,4,6,5}{2,1,4,3,6,5}{3,1,2,4,6,5}{4,1,2,3,6,5},{1,2,3,6,4,5}{1,3,2,6,4,5}{2,1,3,6,4,5}{3,1,2,6,4,5},{1,2,6,3,4,5}{2,1,6,3,4,5},
a(7)=29(每个a(6)后面加7)+15((每个a(5)后面加7,6))+8((每个a(4)后面加7,5,6))+4((每个a(3)后面加7,4,5,6))=56,——注意尾项只有2种可能:7或6。——中间的数也是蛮有规律的。
a(8)=56(每个a(7)后面加8)+29((每个a(6)后面加8,7))+15((每个a(5)后面加8,6,7))+8((每个a(4)后面加8,5,6,7))=108,——注意尾项只有2种可能:8或7。
......
B=4,——n只能出现在尾部的5项。
{1, 2, 4, 8, 16, 31, 61, 120, 236, 464, 912, 1793, 3525, 6930, 13624, 26784, 52656, 103519, 203513, 400096, 786568, 1546352, 3040048, 5976577, 11749641, 23099186}
先得有前5项——a(1)=1,{1},  a(2)=2,{1,2},{2,1},  a(3)=4,{1,2,3},{1,3,2},{2,1,3},{3,1,2},  a(4)=8,{1,2,3,4},{1,2,4,3},{1,3,2,4},{1,4,2,3},{2,1,3,4},{2,1,4,3},{3,1,2,4},{4,1,2,3},  a(5)=16,——... 。
a(6)=16(每个a(5)后面加6)+8((每个a(4)后面加6,5))+4((每个a(3)后面加6,4,5))+2((每个a(2)后面加6,3,4,5))+1((每个a(1)后面加6,2,3,4,5))=31,——注意尾项只有2种可能:6或5。——后面加6,2,3,4,5——顺序不能动！
{1,2,3,4,5,6}{1,2,3,5,4,6}{1,2,4,3,5,6}{1,2,5,3,4,6}{1,3,2,4,5,6}{1,3,2,5,4,6}{1,4,2,3,5,6},{1,5,2,3,4,6},{2,1,3,4,5,6}{2,1,3,5,4,6}{2,1,4,3,5,6}{2,1,5,3,4,6},{3,1,2,4,5,6}{3,1,2,5,4,6}{4,1,2,3,5,6}{5,1,2,3,4,6},
{1,2,3,4,6,5}{1,2,4,3,6,5}{1,3,2,4,6,5}{1,4,2,3,6,5}{2,1,3,4,6,5}{2,1,4,3,6,5}{3,1,2,4,6,5}{4,1,2,3,6,5},{1,2,3,6,4,5}{1,3,2,6,4,5}{2,1,3,6,4,5}{3,1,2,6,4,5},{1,2,6,3,4,5}{2,1,6,3,4,5},{1,6,2,3,4,5},
a(7)=31(每个a(6)后面加7)+16((每个a(5)后面加7,6))+8((每个a(4)后面加7,5,6))+4((每个a(3)后面加7,4,5,6))+2((每个a(2)后面加7,3,4,5,6))=61,——注意尾项只有2种可能:7或6。
a(8)=61(每个a(7)后面加8)+31((每个a(6)后面加8,7))+16((每个a(5)后面加8,6,7))+8((每个a(4)后面加8,5,6,7))+4((每个a(3)后面加8,4,5,6,7))=120,——注意尾项只有2种可能:8或7。
a(9)=120(每个a(8)后面加9)+61((每个a(7)后面加9,8))+31((每个a(6)后面加9,7,8))+16((每个a(5)后面加9,6,7,8))+8((每个a(4)后面加9,5,6,7,8))=236,——注意尾项只有2种可能:9或8。
......

王守恩

aimisiyou 发表于 2025-8-26 20:00
看不懂你说的意思。

丢了！——要不——试试——A062708——有个三角形数的三角形图(网页上找不到类似的图)——你来画得比它大一些(我不会画)——我来出道题——蛮好玩的！谢谢！

题目是这样。记"0"关于"n"的对称数为"a(n)"。譬如
a(1)=11,
a(2)=13,
a(3)=15,
a(4)=17,
a(5)=19,
a(6)=21,
a(7)=23,
a(8)=25,
a(9)=27,
a(10)=56,
a(11)=58,
a(12)=60,
a(13)=62,
a(14)=64,
a(15)=66,
a(16)=68,
a(17)=70,
a(18)=72,
a(19)=74,
a(20)=76,
a(21)=78,
a(22)=80,
a(23)=82,
a(24)=84,
a(25)=86,
a(26)=88,
a(27)=90,
a(28)=137,
a(29)=139,
a(30)=141,
a(31)=143,
a(32)=145,
......
得到一串数——11, 13, 15, 17, 19, 21, 23, 25, 27, 56, 58, 60, 62, 64, 66, 68, 70, 72, 74, 76, 78, 80, 82, 84, 86, 88, 90, 137, 139, 141, 143, 145,......,求通项公式。