cp's OEIS Frontend

A243842 Pair deficit of the most equal partition of n into two parts using standard rounding of the expectations of n, floor(n/2) and n-floor(n/2), assuming equal likelihood of states defined by the number of 2-cycles.

%I A243842 #61 Jan 21 2023 02:59:13
%S A243842 0,0,0,1,1,1,0,0,1,0,0,0,0,1,1,1,0,1,1,1,0,0,1,1,2,1,1,1,2,1,0,1,1,1,
%T A243842 0,1,1,1,0,1,1,2,2,1,1,1,2,1,1,1,2,1,1,1,2,1,0,1,1,2,2,2,1,2,2,2,1,2,
%U A243842 2,2,1,2,2,1,1,1,2,1,1,1
%N A243842 Pair deficit of the most equal partition of n into two parts using standard rounding of the expectations of n, floor(n/2) and n-floor(n/2), assuming equal likelihood of states defined by the number of 2-cycles.
%C A243842 The expectation for n = 2 is 0.5 so this is the first and only integer n for which the convention of rounding a half to an even number is pertinent. This affects a(2), a(3), a(4), and a(5). For n>2, twice the expectation, 2*E(n) must be an odd integer for this situation to arise. 2*E(n) = n*(n-1)*I(n-2)/I(n) for n>=2, where I(n) = A000085(n).
%C A243842 First notice that gcd(I(n), I(n-2)) = gcd(I(n-1) + (n-1)*I(n-2), I(n-2)) = gcd(I(n-1), I(n-2)). Now, suppose that there is an odd prime factor s that divides both I(m-1) and I(m-2) for some m. This would then imply that I(m), I(m+1), I(m+2), ... would all be a multiple of s, i.e., I(n) mod s would be zero for all n greater than or equal to m. A result of Chowla implies that I(n) mod s equals 1 infinitely often for any fixed odd prime s. This is a contradiction of the initial supposition. In other words, there is no odd prime factor that divides both I(m-1) and I(m-2), hence no odd prime factor in common between I(m) and I(m-2).
%C A243842 We can rewrite 2*E(n) as n*(n-1)*(2^a)*p/((2^b)*q), where gcd(p,q) = 1 and both p and q are odd. Using the result from Kim regarding b as a function of n, it can be shown that q > 2^(n/2) > n*(n-1) for all n greater than or equal to 16. Since q is larger than n*(n-1) we can reduce n*(n-1)/q to r/q', where gcd(r,q') = 1, q' odd, and q' is greater than 1. Let Z be an odd prime factor of q'. Z is not a divisor of r, p, or 2^a. Since Z is prime this implies that Z is not a divisor of the product r*2^a*p. Now rewrite 2*E(n) = r*(2^a)*p/(q'*(2^b)) as 2*E(n) = r*(2^a)*p/(Z*q"*(2^b)), where Z is an odd prime such that q' = Z*q". Let us suppose that 2*E(n) is an integer then 2*E(n)*Z*q"*(2^b) = r*(2^a)*p. This implies that Z is a divisor of r*(2^a)*p. This is a contradiction. We conclude that 2*E(n) is not an integer for n greater than or equal to 16. The remaining cases for 2*E(n) between 2 and 16 can be verified numerically.
%C A243842 Interestingly, given the recurrence relation I(n) = I(n-1) + (n-1)*I(n-2), 2*E(n) = n - n*I(n-1)/I(n).  Defining J(n) as I(n)/I(n-1), this yields 2*E(n) = n - n/J(n) where J(n) = 1+(n-1)/J(n-1). n/J(n) happens to be the finite continued fraction n/1+ (n-1)/1+ ...3/1+ 2/(1+1).
%D A243842 Oskar Perron, Die Lehre von den Kettenbrüchen Band I, II, B. G. Teubner, 1954.
%H A243842 S. Chowla, I. N. Hernstein, and W. K. Moore, <a href="http://dx.doi.org/10.4153/CJM-1951-038-3">On recursions connected with symmetric groups. I</a>, Canadian Journal of Mathematics, 3 (1951), 328-334.
%H A243842 Dongsu Kim, and J.S. Kim, <a href="http://arxiv.org/abs/0902.4311">A combinatorial approach to the power of 2 in the number of involutions</a>, arXiv:0902.4311 [math.CO], 2009-2010.
%H A243842 Dongsu Kim, and J.S. Kim, <a href="http://dx.doi.org/10.1016/j.jcta.2009.08.002">A combinatorial approach to the power of 2 in the number of involutions</a>, Journal of Combinatorial Theory, Series A 117 (8) (2010): 1082-1094
%H A243842 Wikipedia, <a href="http://en.wikipedia.org/wiki/Generalized_continued_fraction">Generalized continued fraction</a>
%H A243842 Wikipedia, <a href="http://en.wikipedia.org/wiki/Telephone_number_(mathematics)">Telephone number (mathematics)</a>
%F A243842 Let Er(n) = round(A162970(n)/A000085(n)). Then a(n) = Er(n) - Er(floor(n/2)) - Er(n-floor(n/2)).
%e A243842 Trivially, for n = 0,1 no pairs are possible so a(0) and a(1) are 0.
%e A243842 For n = 2, the expectation, E(n), equals 0.5. So a(2) = round(E(2)) - round(E(1)) - round(E(1)) = 0.
%e A243842 For n = 5 = 2 + 3, E(5) = 20/13, E(2) = 0.5 and E(3) = 0.75 and a(5) = round(E(5)) - round(E(2)) - round(E(3)) = 1.
%Y A243842 Cf. A162970 (numerator for calculating the expected value).
%Y A243842 Cf. A000085 (denominator for calculating the expected value).
%Y A243842 Cf. A243840 (analogous using floor rounding).
%Y A243842 Cf. A243841 (analogous using ceiling rounding).
%K A243842 nonn
%O A243842 0,25
%A A243842 _Rajan Murthy_ and _Vale Murthy_, Jun 12 2014