|
| |
|
|
A000700
|
|
Expansion of Product_{k>=0} (1 + x^(2k+1)); number of partitions of n into distinct odd parts; number of self-conjugate partitions; number of symmetric Ferrers graphs with n nodes.
(Formerly M0217 N0078)
|
|
1634
|
|
|
|
1, 1, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 8, 9, 11, 12, 12, 14, 16, 17, 18, 20, 23, 25, 26, 29, 33, 35, 37, 41, 46, 49, 52, 57, 63, 68, 72, 78, 87, 93, 98, 107, 117, 125, 133, 144, 157, 168, 178, 192, 209, 223, 236, 255, 276, 294, 312, 335, 361, 385
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,9
|
|
|
COMMENTS
|
Coefficients of replicable function number 96a. - N. J. A. Sloane, Jun 10 2015
For n >= 1, a(n) is the minimal row sum in the character table of the symmetric group S_n. The minimal row sum in the table corresponds to the one-dimensional alternating representation of S_n. The maximal row sum is in sequence A085547. - Yuval Dekel (dekelyuval(AT)hotmail.com), Sep 15 2003
Also the number of partitions of n into parts != 2 and differing by >= 6 with strict inequality if a part is even. [Alladi]
Let S be the set formed by the partial sums of 1+[2,3]+[2,5]+[2,7]+[2,9]+..., where [2,odd] indicates a choice, e.g., we may have 1+2, or 1+3+2, or 1+3+5+2+9, etc. Then A000700(n) is the number of elements of S that equal n. Also A000700(n) is the same parity as A000041(n) (the partition numbers). - Jon Perry, Dec 18 2003
a(n) is for n >= 2 the number of conjugacy classes of the symmetric group S_n which split into two classes under restriction to A_n, the alternating group. See the G. James - A. Kerber reference given under A115200, p. 12, 1.2.10 Lemma and the W. Lang link under A115198.
Also number of partitions of n such that if k is the largest part, then k occurs an odd number of times and each integer from 1 to k-1 occurs a positive even number of times (these are the conjugates of the partitions of n into distinct odd parts). Example: a(15)=4 because we have [3,3,3,2,2,1,1], [3,2,2,2,2,1,1,1,1], [3,2,2,1,1,1,1,1,1,1,1] and [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]. - Emeric Deutsch, Apr 16 2006
The INVERTi transform of A000009 (number of partitions of n into odd parts starting with offset 1) = (1, 0, 1, -1, 1, -1, 1, -2, 2, -2, 2, -3, 3, -3, 4, ...); = left border of triangle A146061. - Gary W. Adamson, Oct 26 2008
For n even: the sum over all even nonnegative integers, k, such that k^2 < n, of the number of partitions of (n-k^2)/2 into parts of size at most k. For n odd: the sum over all odd nonnegative integers, j, such that j^2 < n, of the number of partitions of (n-j^2)/2 into parts of size at most j. - Graham H. Hawkes, Oct 18 2013
This number is also (the number of conjugacy classes of S_n containing even permutations) - (the number of conjugacy classes of S_n containing odd permutations) = (the number of partitions of n into a number of parts having the same parity as n) - (the number of partitions of n into a number of parts having opposite parity as n) = (the number of partitions of n with largest part having same parity as n) - (the number of partitions with largest part having opposite parity as n). - David L. Harden, Dec 09 2016
a(n) is odd iff n belongs to A052002; that is, Sum_{n>=0} x^A052002(n) == Sum_{n>=0} a(n)*x^n (mod 2). - Peter Bala, Jan 22 2017
Also the number of conjugacy classes of S_n whose members yield unique square roots, i.e., there exists a unique h in S_n such that hh = g for any g in such a conjugacy class. Proof: first note that a permutation's square roots are determined by the product of the square roots of its decomposition into cycles of different lengths. h can only travel to one other cycle before it must "return home" (h^2(x) = g(x) must be in x's cycle), and, because if g^n(x) = x then h^2n(x) = x and h^2n(h(x)) = h(x), this "traveling" must preserve cycle length or one cycle will outpace the other. However, a permutation decomposing into two cycles of the same length has multiple square roots: for example, e = e^2 = (a b)^2, (a b)(c d) = (a c b d)^2 = (a d b c)^2, (a b c)(d e f) = (a d b e c f)^2 = (a e b f c d)^2, etc. This is true for any cycle length so we need only consider permutations with distinct cycle lengths. Finally, even cycle lengths are odd permutations and thus cannot be square, while odd cycle lengths have the unique square root h(x) = g^((n+1)/2)(x). Thus there is a correspondence between these conjugacy classes and partitions into distinct odd parts. - Keith J. Bauer, Jan 09 2024
|
|
|
REFERENCES
|
R. Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; see p. 197.
B. C. Berndt, Ramanujan's theory of theta-functions, Theta functions: from the classical to the modern, Amer. Math. Soc., Providence, RI, 1993, pp. 1-63. MR 94m:11054.
T. J. I'a. Bromwich, Introduction to the Theory of Infinite Series, Macmillan, 2nd. ed. 1949, p. 116, see q_2.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 277, Theorems 345, 347.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
Cristina Ballantine, Hannah E. Burson, Amanda Folsom, Chi-Yun Hsu, Isabella Negrini and Boya Wen, On a Partition Identity of Lehmer, arXiv:2109.00609 [math.CO], 2021.
R. K. Guy, A theorem in partitions, Research Paper 11, Jan. 1967, Math. Dept., Univ. of Calgary. [Annotated scanned copy]
|
|
|
FORMULA
|
G.f.: Product_{k>=1} (1 + x^(2*k-1)).
G.f.: Sum_{k>=0} x^(k^2)/Product_{i=1..k} (1-x^(2*i)). - Euler (Hardy and Wright, Theorem 345)
G.f.: 1/Product_{i>=1} (1 + (-x)^i). - Jon Perry, May 27 2004
Expansion of chi(q) = (-q; q^2)_oo = f(q) / f(-q^2) = phi(q) / f(q) = f(-q^2) / psi(-q) = phi(-q^2) / f(-q) = psi(q) / f(-q^4), where phi(), chi(), psi(), f() are Ramanujan theta functions.
Euler transform of period-4 sequence [1, -1, 1, 0, ...].
Expansion of q^(1/24) * eta(q^2)^2 /(eta(q) * eta(q^4)) in powers of q. - Michael Somos, Jun 11 2004
Asymptotics: a(n) ~ exp(Pi*l_n)/(2*24^(1/4)*l_n^(3/2)) where l_n = (n-1/24)^(1/2) (Ayoub). The asymptotic formula in Ayoub is incorrect, as that would imply faster growth than the total number of partitions. (It was quoted correctly, the book is just wrong, not sure what the correct asymptotic is.) - Edward Early, Nov 15 2002. Right formula is a(n) ~ exp(Pi*sqrt(n/6)) / (2*24^(1/4)*n^(3/4)). - Vaclav Kotesovec, Jun 23 2014
a(n) = (1/n)*Sum_{k = 1..n} (-1)^(k+1)*b(k)*a(n-k), n>1, a(0) = 1, b(n) = A000593(n) = sum of odd divisors of n. - Vladeta Jovovic, Jan 19 2002 [see Theorem 2(a) in N. Robbins's article]
For n > 0: a(n) = b(n, 1) where b(n, k) = b(n-k, k+2) + b(n, k+2) if k < n, otherwise (n mod 2) * 0^(k-n). - Reinhard Zumkeller, Aug 26 2003
Expansion of q^(1/24) * (m * (1 - m) / 16)^(-1/24) in powers of q where m = k^2 is the parameter and q is the nome for Jacobian elliptic functions.
Given g.f. A(x), B(q) = (1/q)* A(q^3)^8 satisfies 0 = f(B(q), B(q^2)) where f(u, v) = u*v * (u - v^2) * (v - u^2) - (4 * (1 - u*v))^2. - Michael Somos, Jul 16 2007
G.f. is a period 1 Fourier series which satisfies f(-1 / (2304 t)) = f(t) where q = exp(2 Pi i t). - Michael Somos, Jul 16 2007
Expansion of q^(1/24)*f(t) in powers of q = exp(Pi*i*t) where f() is Weber's function. - Michael Somos, Oct 18 2007
a(n) = S(n,1), where S(n,m) = Sum_{k=m..n/2} (-1)^(k+1)*S(n-k,k) + (-1)^(n+1), S(n,n)=(-1)^(n+1), S(0,m)=1, S(n,m)=0 for n < m. - Vladimir Kruchinin, Sep 07 2014
G.f.: Product_{k>0} (1 + x^(2*k-1)) = Product_{k>0} (1 - (-x)^k) / (1 - (-x)^(2*k)) = Product_{k>0} 1 / (1 + (-x)^k). - Michael Somos, Nov 08 2014
a(n) ~ Pi * BesselI(1, Pi*sqrt(24*n-1)/12) / sqrt(24*n-1) ~ exp(Pi*sqrt(n/6)) / (2^(7/4) * 3^(1/4) * n^(3/4)) * (1 - (3*sqrt(6)/(8*Pi) + Pi/(48*sqrt(6))) / sqrt(n) + (5/128 - 45/(64*Pi^2) + Pi^2/27648) / n). - Vaclav Kotesovec, Jan 08 2017
Given g.f. A(x), B(q) = (1/q) * A(q^24) / 2^(1/4) satisfies 0 = f(B(q), B(q^5)) where f(u, v) = u^6 + v^6 + 2*u*v * (1 - (u*v)^4). - Michael Somos, Mar 14 2019
G.f.: Sum_{n >= 0} x^n/Product_{i = 1..n} ( 1 + (-1)^(i+1)*x^i ). - Peter Bala, Nov 30 2020
G.f.: (1 + x) * Sum_{n >= 0} x^(n*(n+2))/Product_{k = 1..n} (1 - x^(2*k)) = (1 + x)*(1 + x^3) * Sum_{n >= 0} x^(n*(n+4))/Product_{k = 1..n} (1 - x^(2*k)) = (1 + x)*(1 + x^3)*(1 + x^5) * Sum_{n >= 0} x^(n*(n+6))/ Product_{k = 1..n} (1 - x^(2*k)) = ....
G.f.: 1/(1 + x) * Sum_{n >= 0} x^(n-1)^2/Product_{k = 1..n} (1 - x^(2*k)) = 1/((1 + x)*(1 + x^3)) * Sum_{n >= 0} x^(n-2)^2/Product_{k = 1..n} (1 - x^(2*k)) = 1/((1 + x)*(1 + x^3)*(1 + x^5)) * Sum_{n >= 0} x^(n-3)^2/ Product_{k = 1..n} (1 - x^(2*k)) = .... (End)
G.f.: A(x) = exp( Sum_{k >= 1} (-1)^k/(k*(x^k - x^(-k))) ). - Peter Bala, Dec 23 2021
|
|
|
EXAMPLE
|
T96a = 1/q + q^23 + q^71 + q^95 + q^119 + q^143 + q^167 + 2*q^191 + ...
G.f. = 1 + x + x^3 + x^4 + x^5 + x^6 + x^7 + 2*x^8 + 2*x^9 + 2*x^10 + 2*x^11 + 3*x^12 + ...
|
|
|
MAPLE
|
N := 100; t1 := series(mul(1+x^(2*k+1), k=0..N), x, N); A000700 := proc(n) coeff(t1, x, n); end;
# second Maple program:
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(n>i^2, 0,
b(n, i-1)+`if`(i*2-1>n, 0, b(n-(i*2-1), i-1))))
end:
a:= n-> b(n, iquo(n+1, 2)):
|
|
|
MATHEMATICA
|
CoefficientList[ Series[ Product[1 + x^(2k + 1), {k, 0, 75}], {x, 0, 70}], x] (* Robert G. Wilson v, Aug 22 2004 *)
a[ n_] := With[ {m = InverseEllipticNomeQ[ q]}, SeriesCoefficient[ ((1 - m) m /(16 q))^(-1/24), {q, 0, n}]]; (* Michael Somos, Jul 11 2011 *)
a[ n_] := SeriesCoefficient[ Product[1 + x^k, {k, 1, n, 2}], {x, 0, n}]; (* Michael Somos, Jul 11 2011 *)
p[n_] := p[n] = Select[Select[IntegerPartitions[n], DeleteDuplicates[#] == # &], Apply[And, OddQ[#]] &]; Table[p[n], {n, 0, 20}] (* shows partitions of n into distinct odd parts *)
Table[Length[p[n]], {n, 0, 20}] (* A000700(n), n >= 0 *)
conjugatePartition[part_] := Table[Count[#, _?(# >= i &)], {i, First[#]}] &[part]; s[n_] := s[n] = Select[IntegerPartitions[n], conjugatePartition[#] == # &]; Table[s[n], {n, 1, 20}] (* shows self-conjugate partitions *)
Table[Length[s[n]], {n, 1, 20}] (* A000700(n), n >= 1 *)
nmax = 100; poly = ConstantArray[0, nmax + 1]; poly[[1]] = 1; poly[[2]] = 1; Do[Do[If[OddQ[k], poly[[j + 1]] += poly[[j - k + 1]]], {j, nmax, k, -1}]; , {k, 2, nmax}]; poly (* Vaclav Kotesovec, Nov 24 2017 *)
|
|
|
PROG
|
(PARI) {a(n) = my(A); if( n<0, 0, A = x * O(x^n); polcoeff( eta(x^2 + A)^2 / (eta(x + A) * eta(x^4 + A)), n))}; /* Michael Somos, Jun 11 2004 */
(PARI) {a(n) = if( n<0, 0, polcoeff( 1 / prod( k=1, n, 1 + (-x)^k, 1 + x * O(x^n)), n))}; /* Michael Somos, Jun 11 2004 */
(PARI) my(x='x+O('x^70)); Vec(eta(x^2)^2/(eta(x)*eta(x^4))) \\ Joerg Arndt, Sep 07 2023
(Maxima)
S(n, m):=if n=0 then 1 else if n<m then 0 else if n=m then (-1)^(n+1) else sum((-1)^(k+1)*S(n-k, k), k, m, n/2)+(-1)^(n+1);
(Python)
from math import prod
from sympy import factorint
def A000700(n): return 1 if n== 0 else sum((-1)**(k+1)*A000700(n-k)*prod((p**(e+1)-1)//(p-1) for p, e in factorint(k).items() if p > 2) for k in range(1, n+1))//n # Chai Wah Wu, Sep 09 2021
(Magma)
m:=80;
R<x>:=PowerSeriesRing(Integers(), m);
Coefficients(R!( (&*[1 + x^(2*j+1): j in [0..m+2]]) )); // G. C. Greubel, Sep 07 2023
(SageMath)
from sage.modular.etaproducts import qexp_eta
m=80
def f(x): return qexp_eta(QQ[['q']], m+2).subs(q=x)
P.<x> = PowerSeriesRing(QQ, prec)
return P( f(x^2)^2/(f(x)*f(x^4)) ).list()
|
|
|
CROSSREFS
|
Cf. A000009, A000041, A000701, A046682, A052002, A053250, A069910, A069911, A081362 (a signed version), A085547, A088994 (labeled version), A146061, A169987 - A169995, A295291, A304044.
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
