T(n,k) 表示将 1～n 排成一列，恰有 k 个数字与其位置吻合的排列种数，问一些有关问题

wintex

Treenewbee

(1)一一对应，唯一不对应，显然\[T_n^n=1,T_n^{n-1}=0\]
(2)T_n^0 即完全错排问题，易知\[T_n^0=(n-1)(T_{n-1}^0+T_{n-2}^0)\]
\[ T_n^0=n! \sum_{i=0}^{n}{\frac{(-1)^i}{i^i}} \approx\frac{n!}{e}\]
\[ T_{n+1}^1=T_{n+1}^0-(-1)^n=(n+1)*T_{n}^0\]

Treenewbee

\[T_n^k={\frac{n!}{k!} \sum _{i=0}^{n-k} \frac{(-1)^i}{i!}} \approx\frac{n!}{ek!}=round(\frac{n!}{ek!})\]

Treenewbee

\[T_n^k\]的计算，可以先从n个数中选n-k个放到对应位置，有\[C_n^{n-k}\]  种方法,然后对其余的k个数进行全错排，即
\[ T_n^k=C_{n}^{n-k}*T_k^0={\frac{n!}{k!} \sum _{i=0}^{n-k} \frac{(-1)^i}{i!}} \approx\frac{n!}{ek!}=round(\frac{n!}{ek!})\]

Treenewbee

\[T_5^k=round(\frac{5!}{ek!})=\{44, 45, 20, 10, 0, 1\}\]

王守恩

1. Table[n!/(k! (n - k)!)*Round[(n - k)!/E], {n, 2, 9}, {k, 0, n - 1}]

复制代码

{{1, 0}, {2, 3, 0}, {9, 8, 6, 0}, {44, 45, 20, 10, 0}, {265, 264, 135,40, 15, 0}, {1854, 1855, 924,315,70,21,0},
{14833, 14832, 7420,2464, 630, 112, 28, 0}, {133496, 133497, 66744, 22260, 5544, 1134, 168, 36, 0}}

王守恩

Treenewbee 发表于 2023-12-6 08:44
\[T_5^k=round(\frac{5!}{ek!})=\{44, 45, 20, 10, 0, 1\}\]

下面这串数可以出来，再下面这串数应该怎样出来？
                                        {{1}},
                                      {{2, 1}},
                                    {{2, 3, 2}},
                                  {{3, 4, 4, 2}},
                                {{3, 6, 7, 6, 3}},
                            {{4, 8, 12, 12, 7, 3}},
                       {{4, 11, 18, 22, 17, 10, 3}},
                     {{5, 13, 27, 37, 36, 25, 12, 4}},
                  {{5, 17, 37, 59, 67, 56, 34, 15, 4}},
             {{6, 20, 50, 89, 117, 115, 85, 46, 17, 4}},
        {{6, 24, 66, 130, 193, 218, 187, 122, 59, 21, 5}},
     {{7, 28, 84, 183, 303, 386, 381, 291, 171, 75, 24, 5}},
{{7, 33, 106, 252, 459, 649, 723, 635, 437, 233, 94, 28, 6}}

1. Table[Abs[n!/(k!(n-k)!)Round[(n-k)!/E]-Round[n!/(Ek!)]],{n,3,9},{k,2,n-1}]

复制代码

                    {{0}},0=2+1-3,
                  {{1, 1}},1=2+3-4,1=3+2-4,
                {{1, 1, 0}},1=3+4-6,1=4+4-7,0=4+2-6,
              {{1, 1, 1, 2}},1=3+6-8,1=6+7-12,1=7+6-12,2=6+3-7,
            {{1, 2, 2, 2, 0}},1=4+8-11,2=8+12-18,2=12+12-22,2=12+7-17,0=7+3-10,
          {{2, 2, 3, 3, 2, 1}},
        {{1, 3, 5, 6, 5, 3, 1}},
      {{2, 4, 7, 9, 8, 5, 3, 2}},
  {{2, 4, 9, 13, 14, 13, 9, 4, 0}},

Treenewbee

王守恩 发表于 2023-12-8 22:18
下面这串数可以出来，再下面这串数应该怎样出来？
                                        {{1}},
   ...

上面的数字怎么来的呢？

Treenewbee

你把原始递推公式代进去计算一下即可

luyuanhong