A056876 - OEIS

A056876

Number of permutations (p_1, ..., p_n) of {1,...,n} that are "balanced" in the sense that the sum of k*p_k equals the sum of (n+1-k)*p_k; equivalently, the expected value of k*p_k is (expected value of k) times (expected value of p_k), assuming the uniform distribution.

1, 1, 0, 0, 2, 6, 0, 184, 936, 6688, 0, 420480, 4298664, 44405142, 0, 6732621476, 92014579912, 1345077232898, 0, 349174373111790, 6179276762966832, 114913276077265202, 0

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,5

COMMENTS

a(4k+2) = 0; also, the same sequence enumerates permutations of {0,1,...,n-1} with the stated expected value property.

Also, central coefficients in the expansion of the probability generating function for the exact null distribution of Spearman's rho. - Antonio G. Astudillo (afg_astudillo(AT)hotmail.com), May 14 2002

a(n) is the central term in row n of A175929 if n in { A042965 } and a(n)=0 otherwise. - Alois P. Heinz, Dec 12 2025

REFERENCES

D. E. Knuth, The Art of Computer Programming: Generating all tuples and permutations, Volume 4, Fascicle 2, Addison-Wesley, Upper Saddle River, NJ (2005); p. 74, Exercise 104.

Ivan Moscovich, More Brainmatics Logic Puzzles, see p. 130. - from Neven Juric, Jan 21 2010.

LINKS

Table of n, a(n) for n=0..22.

Dongyang Cheng and Petros Hadjicostas, Right-invariant metrics applied to rank correlation coefficients, Australas. J. Combin. 57 (2013), 157-187; see Section 5 for similar questions about other non-parametric rank correlation coefficients.

E. I. Marshall, Conditions for rank correlation to be zero, Sankhyā 56(1) (1994), 59-66; he proved that a(n) = 0 if and only if n = 3 or n = 4*k+2 for some integer k >= 0 (see Theorem 2, p. 62).

M. A. van de Wiel and A. Di Bucchianico, Fast computation of the exact null distribution of Spearman's rho and Page's L statistic for samples with and without ties, Memorandum COSOR 98-17, 1998, Eindhoven University of Technology.

M. A. van de Wiel and A. Di Bucchianico, Fast computation of the exact null distribution of Spearman's rho and Page's L statistic for samples with and without ties, J. Statist. Plann. Inference, 92(1-2) (2001), 133-145.

Wikipedia, Spearman rank correlation coefficient.

EXAMPLE

a(5) = 6 because of the permutations 15432, 23451, 25314, 41352, 43215, 51234.

MAPLE

b:= proc(s, t) option remember; (n-> `if`(n=0, `if`(t=0, 1, 0), add(

(g-> `if`(g<0, 0, b(s minus {j}, g)))(t-j*n), j=s)))(nops(s))

end:

a:= n-> `if`(irem(n, 4)=2, 0, b({$1..n}, n*(n+1)^2/4)):

seq(a(n), n=0..14); # Alois P. Heinz, Dec 12 2025

CROSSREFS