A162970 -id:A162970 - cp's OEIS frontend

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

0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 0, 1, 1, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 3, 2, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 2, 3, 2, 2, 2, 3, 2, 2, 2, 3, 2, 1, 2, 2, 2, 1, 2, 2, 2

Offset: 0

Rajan Murthy, Jun 12 2014

nonn

			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) = floor(E(2)) - floor(E(1)) - floor(E(1)) = 0.
For n = 5 = 2 + 3, E(5) = 20/13, E(2) = 0.5 and E(3) = 0.75 and a(5) = floor(E(5)) - floor(E(2)) - floor(E(3)) = 1.
Interestingly, for n = 8, E(8) = 532/191 and E(4) = 6/5, so a(n) = 2 - 1 - 1 = 0.

A162970 provides the numerator for calculating the expected value.

A000085 provides the denominator for calculating the expected value.

a(n) = floor(A162970(n)/A000085(n)) - floor(A162970(floor(n/2))/A000085(floor(n/2))) - floor(A162970(n-floor(n/2))/A000085(n-floor(n/2))).

A243841 Pair deficit of the most nearly equal partition of n into two parts using ceiling 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.

Original entry on oeis.org

0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, -1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 2, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1

Offset: 0

Rajan Murthy, Jun 12 2014

A162970 and A000085 provide the numerator and the denominator for calculating the expected value.

			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) = ceiling(E(2)) - (ceiling(E(1)) + ceiling(E(1))) = 1.
For n = 5 = 2 + 3, E(5) = 20/13, E(2) = 0.5 and E(3) = 0.75 and a(5) = ceiling(E(5)) - (ceiling(E(2)) + ceiling(E(3))) = 0.
Interestingly, for n = 8, E(8) = 532/191 and E(4) = 6/5, so a(n) = 3 - (2 + 2) = -1.

Cf. A000085, A162970.

a(n) = ceiling(A162970(n)/A000085(n)) - (ceiling(A162970(floor(n/2))/A000085(floor(n/2))) + ceiling(A162970(n-floor(n/2))/A000085(n-floor(n/2)))).

A174764 Sum of the numerators for computing the second moment of the probability mass function (PMF) of the number of 2-cycles in the involutions on n elements (A000085) assuming the involutions are all equally likely.

Original entry on oeis.org

0, 1, 3, 18, 70, 330, 1386, 6328, 28008, 130140, 603460, 2895816, 14024088, 69786808, 352043160, 1817317440, 9525774016, 50958843408, 276906491568, 1532719442080, 8615750596320, 49260355141536, 285887468809888

Offset: 1

Rajan Murthy, Nov 30 2010

nonn

Wikipedia, Probability Mass Function

First moment numerators are given by A162970. The denominator is given by A000085.

a(n) = sum(k=0, n\2 ,k^2*n!/((n-2*k)!*2^k*k!)); \\ Michel Marcus, Aug 10 2013

a(n) = Sum_{k=0..[ n/2 ]} k^2*n!/((n-2*k)!*2^k*k!).
a(n) = (n!/4*(n-4)!)*A000085(n-4) + (n!/2*(n-2)!)*A000085(n-2), n>3. - Vale Murthy, Nov 03 2014
a(n) = (n!/4*(n-4)!)*A000085(n-4) + A162970(n), n>3. - Rajan Murthy, Nov 03 2014
a(n) = (n!/2*(n-2)!)*A162970(n-2) + A162970(n), n>3. - Rajan Murthy, Nov 03 2014

More terms from Michel Marcus, Aug 10 2013

A174774 Sum of the numerators for computing the third moment of the probability mass function for probability of k pairs among the involutions on n elements (A000085) assuming equal likelihood.

Original entry on oeis.org

0, 1, 3, 30, 130, 780, 3696, 19768, 97560, 510660, 2603260, 13754136, 72333768, 390339040, 2116922640, 11722194240, 65521880896, 372897624528, 2146502657520, 12558129505120, 74371827119520, 447090649997376

Offset: 1

Rajan Murthy, Nov 30 2010

nonn

Wikipedia, Probability Mass Function

First moment numerators are given by A162970. The denominator is given by A000085.

a(n) = sum(k=0, n\2 ,k^3*n!/((n-2*k)!*2^k*k!)); \\ Michel Marcus, Aug 10 2013

a(n)=Sum_{k=0..[ n/2 ]} k^3*n!/((n-2*k)!*2^k*k!).

Corrected, and more terms from Michel Marcus, Aug 10 2013

A174782 Sum of the numerators for computing the fourth moment of the probability mass function for the number of involutions with k 2-cycles in n elements (A000085) assuming equal likelihood.

Original entry on oeis.org

0, 1, 3, 54, 250, 1950, 10206, 64288, 350064, 2065500, 11509300, 66905256, 380767608, 2226036904, 12949377000, 76842172800, 457297336576, 2766381692688, 16849247813424, 104116268476000, 649043824951200

Offset: 1

Rajan Murthy, Nov 30 2010

nonn

Since the PMF represents a probability function, there is no unique set of numerators. That is, only the relative magnitude of the sum of the numerators matter so long as the denominator is of the same relative magnitude (since the relative magnitudes cancel upon division).

Wikipedia, Probability Mass Function

First moment numerators are given by A162970. The denominator is given by A000085.

a(n) = sum(k=0, n\2 ,k^4*n!/((n-2*k)!*2^k*k!)); \\ Michel Marcus, Aug 10 2013

a(n)=Sum_{k=0..[ n/2 ]} k^4*n!/((n-2*k)!*2^k*k!).

More data from Michel Marcus, Aug 10 2013

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.

Original entry on oeis.org

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

Offset: 0

Rajan Murthy and Vale Murthy, Jun 12 2014

nonn

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

			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.

Oskar Perron, Die Lehre von den Kettenbrüchen Band I, II, B. G. Teubner, 1954.

S. Chowla, I. N. Hernstein, and 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)

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

Let Er(n) = round(A162970(n)/A000085(n)). Then a(n) = Er(n) - Er(floor(n/2)) - Er(n-floor(n/2)).

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Crossrefs

Formula

A243841 Pair deficit of the most nearly equal partition of n into two parts using ceiling 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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A174764 Sum of the numerators for computing the second moment of the probability mass function (PMF) of the number of 2-cycles in the involutions on n elements (A000085) assuming the involutions are all equally likely.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A174774 Sum of the numerators for computing the third moment of the probability mass function for probability of k pairs among the involutions on n elements (A000085) assuming equal likelihood.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

Extensions

A174782 Sum of the numerators for computing the fourth moment of the probability mass function for the number of involutions with k 2-cycles in n elements (A000085) assuming equal likelihood.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

Extensions

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.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Formula