|
| |
|
|
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.
|
|
0
|
|
|
|
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, 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, 2, 2, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,25
|
|
|
COMMENTS
|
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).
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).
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.
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).
|
|
|
REFERENCES
|
Oskar Perron, Die Lehre von den Kettenbrüchen Band I, II, B. G. Teubner, 1954.
|
|
|
LINKS
|
|
|
|
FORMULA
|
Let Er(n) = round(A162970(n)/A000085(n)). Then a(n) = Er(n) - Er(floor(n/2)) - Er(n-floor(n/2)).
|
|
|
EXAMPLE
|
Trivially, for n = 0,1 no pairs are possible so a(0) and a(1) are 0.
For n = 2, the expectation, E(n), equals 0.5. So a(2) = round(E(2)) - round(E(1)) - round(E(1)) = 0.
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.
|
|
|
CROSSREFS
|
Cf. A162970 (numerator for calculating the expected value).
Cf. A000085 (denominator for calculating the expected value).
Cf. A243840 (analogous using floor rounding).
Cf. A243841 (analogous using ceiling rounding).
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
