3
$\begingroup$

I browsed one enumerative combinatorics problem in Zhihu.

This is also a problem on JAM October 2023.

Proprosed by Erik Vigren. Swedish Institute of Space Physics, Uppsala, Sweden. Suppose that $k$ and $n$ are integers with $n\geq 2$ and $1\leq k\leq n$. What is the average value of $\sum\limits_{i=1}^{\pi(k)}\pi(i)$ over all permutaions $\pi$ of $\{1,\ldots, n\}$?

Below is my Mathematica code:

n = 3; k = 2; kMax = 6; nMax = 6; calc[n_, k_] := Module[{}, permus = Permutations[Range[n]]; Mean[Table[Sum[p[[i]], {i, 1, p[[k]]}], {p, permus}]]] ref[n_, k_] := (n + 1) (3 n + 2)/12 + (n - k + 1) (k - 1)/(2 n - 2) Table[calc[n, k], {n, 2, nMax}, {k, 1, n}] // TableForm[#, TableHeadings -> {Table["n=" <> ToString@i, {i, 2, nMax}], Table["k=" <> ToString@i, {i, 1, kMax}]}] & Table[ref[n, k], {n, 2, nMax}, {k, 1, n}] // TableForm[#, TableHeadings -> {Table["n=" <> ToString@i, {i, 2, nMax}], Table["k=" <> ToString@i, {i, 1, kMax}]}] & 
$\endgroup$

1 Answer 1

5
$\begingroup$

Two-step FindSequenceFunction can do this:

f[n_Integer, k_Integer] /; 1 <= k <= n && n >= 2 := f[n, k] = Mean[Total[#[[1 ;; #[[k]]]]] & /@ Permutations[Range[n]]] 

For given $k$, find a formula that describes the $n$-dependence:

eq[k_Integer] /; k >= 1 := FindSequenceFunction[Table[{n, f[n, k]}, {n, Max[2, k], 11}], n] 

Make a list of these, and find the overall formula:

FindSequenceFunction[Table[{k, eq[k]}, {k, 1, 6}], k] (* (-8 + 12 k - 6 k^2 - 9 n + 6 k n + 2 n^2 + 3 n^3)/(12 (-1 + n)) *) 
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.