login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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), 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

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

S. Chowla, and I.N. Hernstein, W.K. Moore, On recursions connected with symmetric groups. I, Canadian Journal of Mathematics, 3 (1951), 328-334.

Dongsu Kim, and J.S. Kim, A combinatorial approach to the power of 2 in the number of involutions, arXiv:0902.4311 [math.CO], 2009-2010.

Dongsu Kim, and J.S. Kim, A combinatorial approach to the power of 2 in the number of involutions, Journal of Combinatorial Theory, Series A 117 (8) (2010): 1082-1094

Wikipedia, Generalized continued fraction

Wikipedia, Telephone number (mathematics)

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).

Sequence in context: A281185 A260683 A092673 * A112400 A316523 A219185

Adjacent sequences:  A243839 A243840 A243841 * A243843 A243844 A243845

KEYWORD

nonn

AUTHOR

Rajan Murthy and Vale Murthy, Jun 12 2014

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 18 22:08 EDT 2019. Contains 322237 sequences. (Running on oeis4.)