Displaying 1-10 of 24 results found.
1, 0, 0, -1, 0, -2, 0, -2, -1, -2, 0, -4, 0, -2, -2, -3, 0, -4, 0, -4, -2, -2, 0, -6, -1, -2, -2, -4, 0, -6, 0, -4, -2, -2, -2, -7, 0, -2, -2, -6, 0, -6, 0, -4, -4, -2, 0, -8, -1, -4, -2, -4, 0, -6, -2, -6, -2, -2, 0, -10, 0, -2, -4, -5, -2, -6, 0, -4, -2, -6, 0, -10, 0, -2, -4, -4, -2, -6, 0, -8, -3, -2, 0, -10
FORMULA
a(1) = 1, and for n > 1, a(n) = -Sum_{d|n, d<n} A174725(n/d) * a(d).
PROG
(PARI) A378216(n) = if(1==n, n, 2-numdiv(n));
1, 1, 1, 2, 2, 4, 4, 6, 7, 9, 9, 13, 13, 15, 17, 21, 21, 25, 25, 29, 31, 33, 33, 43, 44, 46, 48, 52, 52, 58, 58, 66, 68, 70, 72, 85, 85, 87, 89, 99, 99, 105, 105, 109, 113, 115, 115, 139, 140, 144, 146, 150, 150, 160, 162, 172, 174, 176, 176, 198, 198, 200, 204, 220, 222
COMMENTS
By fitting a second order polynomial in Excel to the 77 first terms we get 0,039x^2+0,8859x-3,5396 with the R-square value 0,9974.
Möbius (or Moebius) function mu(n). mu(1) = 1; mu(n) = (-1)^k if n is the product of k different primes; otherwise mu(n) = 0.
+10
1516
1, -1, -1, 0, -1, 1, -1, 0, 0, 1, -1, 0, -1, 1, 1, 0, -1, 0, -1, 0, 1, 1, -1, 0, 0, 1, 0, 0, -1, -1, -1, 0, 1, 1, 1, 0, -1, 1, 1, 0, -1, -1, -1, 0, 0, 1, -1, 0, 0, 0, 1, 0, -1, 0, 1, 0, 1, 1, -1, 0, -1, 1, 0, 0, 1, -1, -1, 0, 1, -1, -1, 0, -1, 1, 0, 0, 1, -1
COMMENTS
Moebius inversion: f(n) = Sum_{d|n} g(d) for all n <=> g(n) = Sum_{d|n} mu(d)*f(n/d) for all n.
a(n) depends only on prime signature of n (cf. A025487). So a(24) = a(375) since 24 = 2^3 * 3 and 375 = 3 * 5^3 both have prime signature (3, 1). Conjecture: a(n) is the determinant of Redheffer matrix A143104 where T(n, n) = 0. Verified for the first 50 terms. - Mats Granvik, Jul 25 2008 The Editorial Office of the Journal of Number Theory kindly provided (via B. Conrey) the following proof of the conjecture: Let A be A143104 and B be A143104 where T(n, n) = 0. "Suppose you expand det(B_n) along the bottom row. There is only a 1 in the first position and so the answer is (-1)^n times det(C_{n-1}) say, where C_{n-1} is the (n-1) by (n-1) matrix obtained from B_n by deleting the first column and the last row. Now the determinant of the Redheffer matrix is det(A_n) = M(n) where M(n) is the sum of mu(m) for 1 <= m <= n. Expanding det(A_n) along the bottom row, we see that det(A_n) = (-1)^n * det(C_{n-1}) + M(n-1). So we have det(B_n) = (-1)^n * det(C_{n-1}) = det(A_n) - M(n-1) = M(n) - M(n-1) = mu(n)." (End)
Conjecture: Consider the table A051731 and treat 1 as a divisor. Move the value in the lower right corner vertically to a divisor position in the transpose of the table and you will find that the determinant is the Moebius function. The number of permutation matrices that contribute to the Moebius function appears to be A074206. - Mats Granvik, Dec 08 2008 [Pickover, p. 226]: "The probability that a number falls in the -1 mailbox turns out to be 3/Pi^2 - the same probability as for falling in the +1 mailbox". - Gary W. Adamson, Aug 13 2009 Let A = A176890 and B = A * A * ... * A, then the leftmost column in matrix B converges to the Moebius function. - Mats Granvik, Gary W. Adamson, Apr 28 2010 and May 28 2020 Formulas for the numerous OEIS entries involving the Möbius transform (Dirichlet convolution of a(n) and some sequence h(n)) can be derived using the following (n >= 1):
Sum_{d|n} mu(d)*h(n/d) = Sum_{k=1..n} h(gcd(n,k))*mu(n/gcd(n,k))/phi(n/gcd(n,k)) = Sum_{k=1..n} h(n/gcd(n,k))*mu(gcd(n,k))/phi(n/gcd(n,k)), where phi = A000010. Use of gcd(n,k)*lcm(n,k) = n*k provides further variations. (End)
Formulas for products corresponding to the sums above are also available for sequences f(n) > 0: Product_{d|n} f(n/d)^mu(d) = Product_{k=1..n} f(gcd(n,k))^(mu(n/gcd(n,k))/phi(n/gcd(n,k))) = Product_{k=1..n} f(n/gcd(n,k))^(mu(gcd(n,k))/phi(n/gcd(n,k))). - Richard L. Ollerton, Nov 08 2021
REFERENCES
T. M. Apostol, Introduction to Analytic Number Theory, Springer-Verlag, 1976, page 24.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 161, #16.
G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, 1979, th. 262 and 287.
Clifford A. Pickover, "The Math Book, from Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics", Sterling Publishing, 2009, p. 226. - Gary W. Adamson, Aug 13 2009 G. Pólya and G. Szegő, Problems and Theorems in Analysis Volume II. Springer_Verlag 1976.
FORMULA
Sum_{d|n} mu(d) = 1 if n = 1 else 0.
Dirichlet generating function: Sum_{n >= 1} mu(n)/n^s = 1/zeta(s). Also Sum_{n >= 1} mu(n)*x^n/(1-x^n) = x.
phi(n) = Sum_{d|n} mu(d)*n/d.
Multiplicative with a(p^e) = -1 if e = 1; 0 if e > 1. - David W. Wilson, Aug 01 2001 Sum_{d|n} (-1)^(n/d)*mobius(d) = 0 for n > 2. - Emeric Deutsch, Jan 28 2005 a(n) = (-1)^omega(n) * 0^(bigomega(n) - omega(n)) for n > 0, where bigomega(n) and omega(n) are the numbers of prime factors of n with and without repetition ( A001222, A001221, A046660). - Reinhard Zumkeller, Apr 05 2003 mu(n) = -Sum_{d < n, d|n} mu(d) if n > 1 and mu(1) = 1. - Alois P. Heinz, Aug 13 2008 a(n) = first column in the matrix inverse of a triangular table with the definition: T(1, 1) = 1, n > 1: T(n, 1) is any number or sequence, k = 2: T(n, 2) = T(n, k-1) - T(n-1, k), k > 2 and n >= k: T(n,k) = (Sum_{i = 1..k-1} T(n-i, k-1)) - (Sum_{i = 1..k-1} T(n-i, k)). - Mats Granvik, Jun 12 2010 Product_{n >= 1} (1-x^n)^(-a(n)/n) = exp(x) (product form of the exponential function). - Joerg Arndt, May 13 2011 a(n) = Sum_{k=1..n, gcd(k,n)=1} exp(2*Pi*i*k/n), the sum over the primitive n-th roots of unity. See the Apostol reference, p. 48, Exercise 14 (b). - Wolfdieter Lang, Jun 13 2011 mu(n) = Sum_{k=1..n} A191898(n,k)*exp(-i*2*Pi*k/n)/n. (conjecture). - Mats Granvik, Nov 20 2011 Sum_{k=1..n} a(k)*floor(n/k) = 1 for n >= 1. - Peter Luschny, Feb 10 2012 G.f. A(x) satisfies: x^2/A(x) = Sum_{n>=1} A( x^(2*n)/A(x)^n ). - Paul D. Hanna, Apr 19 2016 Conjecture: a(n) = Sum_{k>=0} (-1)^(k-1)*binomial( A001222(n)-1, k)*binomial( A001221(n)-1+k, k), for n > 1. Verified for the first 100000 terms. - Mats Granvik, Sep 08 2018 Sum_{n >= 1} mu(n)*x^n/(1 + x^n) = x - 2*x^2. See, for example, Pólya and Szegő, Part V111, Chap. 1, No. 71.
Sum_{n >= 1} (-1)^(n+1)*mu(n)*x^n/(1 - x^n) = x + 2*(x^2 + x^4 + x^8 + x^16 + ...).
Sum_{n >= 1} (-1)^(n+1)*mu(n)*x^n/(1 + x^n) = x - 2*(x^4 + x^8 + x^16 + x^32 + ...).
Sum_{n >= 1} |mu(n)|*x^n/(1 - x^n) = Sum_{n >= 1} (2^w(n))*x^n, where w(n) is the number of different prime factors of n (Hardy and Wright, Chapter XVI, Theorem 264).
Sum_{n odd} |mu(n)|*x^n/(1 + x^(2*n)) = Sum_{n in S_1} (2^w_1(n))*x^n, where S_1 = {1, 5, 13, 17, 25, 29, ...} is the multiplicative semigroup of positive integers generated by 1 and the primes p = 1 (mod 4), and w_1(n) is the number of different prime factors p = 1 (mod 4) of n.
Sum_{n odd} (-1)^((n-1)/2)*mu(n)*x^n/(1 - x^(2*n)) = Sum_{n in S_3} (2^w_3(n))*x^n, where S_3 = {1, 3, 7, 9, 11, 19, 21, ...} is the multiplicative semigroup of positive integers generated by 1 and the primes p = 3 (mod 4), and where w_3(n) is the number of different prime factors p = 3 (mod 4) of n. (End)
G.f. A(x) satisfies: A(x) = x - Sum_{k>=2} A(x^k). - Ilya Gutkovskiy, May 11 2019 a(n) = Sum_{k = 1..n} gcd(k, n)*a(gcd(k, n)) = Sum_{d divides n} a(d)*d*phi(n/d). - Peter Bala, Jan 16 2024
EXAMPLE
G.f. = x - x^2 - x^3 - x^5 + x^6 - x^7 + x^10 - x^11 - x^13 + x^14 + x^15 + ...
MAPLE
with(numtheory): A008683 := n->mobius(n); with(numtheory): [ seq(mobius(n), n=1..100) ];
# Note that older versions of Maple define mobius(0) to be -1.
# This is unwise! Moebius(0) is better left undefined.
with(numtheory):
mu:= proc(n::posint) option remember; `if`(n=1, 1,
-add(mu(d), d=divisors(n) minus {n}))
end:
MATHEMATICA
Array[ MoebiusMu, 100]
(* Second program: *)
m = 100; A[_] = 0;
Do[A[x_] = x - Sum[A[x^k], {k, 2, m}] + O[x]^m // Normal, {m}];
PROG
(Axiom) [moebiusMu(n) for n in 1..100]
(Magma) [ MoebiusMu(n) : n in [1..100]];
(PARI) a=n->if(n<1, 0, moebius(n));
(PARI) {a(n) = if( n<1, 0, direuler( p=2, n, 1 - X)[n])};
(PARI) list(n)=my(v=vector(n, i, 1)); forprime(p=2, sqrtint(n), forstep(i=p, n, p, v[i]*=-1); forstep(i=p^2, n, p^2, v[i]=0)); forprime(p=sqrtint(n)+1, n, forstep(i=p, n, p, v[i]*=-1)); v \\ Charles R Greathouse IV, Apr 27 2012 (Haskell)
import Math.NumberTheory.Primes.Factorisation (factorise)
a008683 = mu . snd . unzip . factorise where
mu [] = 1; mu (1:es) = - mu es; mu (_:es) = 0
(Sage)
@cached_function
def mu(n):
if n < 2: return n
return -sum(mu(d) for d in divisors(n)[:-1])
# Changing the sign of the sum gives the number of ordered factorizations of n A074206. (Python)
from sympy import mobius
print([mobius(i) for i in range(1, 101)]) # Indranil Ghosh, Mar 18 2017
CROSSREFS
Cf. A000010, A001221, A008966, A007423, A080847, A002321 (partial sums), A069158, A055615, A129360, A140579, A140664, A140254, A143104, A152902, A206706, A063524, A007427, A007428, A124010, A073776, A074206, A132971, A156552.
Kalmár's [Kalmar's] problem: number of ordered factorizations of n.
+10
222
0, 1, 1, 1, 2, 1, 3, 1, 4, 2, 3, 1, 8, 1, 3, 3, 8, 1, 8, 1, 8, 3, 3, 1, 20, 2, 3, 4, 8, 1, 13, 1, 16, 3, 3, 3, 26, 1, 3, 3, 20, 1, 13, 1, 8, 8, 3, 1, 48, 2, 8, 3, 8, 1, 20, 3, 20, 3, 3, 1, 44, 1, 3, 8, 32, 3, 13, 1, 8, 3, 13, 1, 76, 1, 3, 8, 8, 3, 13, 1, 48, 8, 3, 1, 44, 3, 3, 3, 20, 1, 44, 3, 8, 3, 3, 3, 112
COMMENTS
a(0)=0, a(1)=1; thereafter a(n) is the number of ordered factorizations of n as a product of integers greater than 1.
Kalmár (1931) seems to be the earliest reference that mentions this sequence (as opposed to A002033). - N. J. A. Sloane, May 05 2016 a(n) is the permanent of the n-1 X n-1 matrix A with (i,j) entry = 1 if j|i+1 and = 0 otherwise. This is because ordered factorizations correspond to nonzero elementary products in the permanent. For example, with n=6, 3*2 -> 1,3,6 [partial products] -> 6,3,1 [reverse list] -> (6,3)(3,1) [partition into pairs with offset 1] -> (5,3)(2,1) [decrement first entry] -> (5,3)(2,1)(1,2)(3,4)(4,5) [append pairs (i,i+1) to get a permutation] -> elementary product A(1,2)A(2,1)A(3,4)A(4,5)A(5,3). - David Callan, Oct 19 2005 This sequence is important in describing the amount of energy in all wave structures in the Universe according to harmonics theory. - Ray Tomes (ray(AT)tomes.biz), Jul 22 2007
a(n) appears to be the number of permutation matrices contributing to the Moebius function. See A008683 for more information. Also a(n) appears to be the Moebius transform of A067824. Furthermore it appears that except for the first term a(n)= A067824(n)*(1/2). Are there other sequences such that when the Moebius transform is applied, the new sequence is also a constant factor times the starting sequence? - Mats Granvik, Jan 01 2009 Numbers divisible by n distinct primes appear to have ordered factorization values that can be found in an n-dimensional summatory Pascal triangle. For example, the ordered factorization values for numbers divisible by two distinct primes can be found in table A059576. - Mats Granvik, Sep 06 2009 Inverse Mobius transform of A174725 and also except for the first term, inverse Mobius transform of A174726. - Mats Granvik, Mar 28 2010 a(n) is a lower bound on the worst-case number of solutions to the probed partial digest problem for n fragments of DNA; see the Newberg & Naor reference, below. - Lee A. Newberg, Aug 02 2011 All integers greater than 1 are perfect numbers over this sequence (for definition of A-perfect numbers, see comment to A175522). - Vladimir Shevelev, Aug 03 2011 Also the number of strict chains of divisors from n to 1. For example, the a(n) chains for n = 1, 2, 4, 6, 8, 12, 30 are:
1 2/1 4/1 6/1 8/1 12/1 30/1
4/2/1 6/2/1 8/2/1 12/2/1 30/2/1
6/3/1 8/4/1 12/3/1 30/3/1
8/4/2/1 12/4/1 30/5/1
12/6/1 30/6/1
12/4/2/1 30/10/1
12/6/2/1 30/15/1
12/6/3/1 30/6/2/1
30/6/3/1
30/10/2/1
30/10/5/1
30/15/3/1
30/15/5/1
(End)
a(n) is also the number of ways to tile a strip of length log(n) with tiles having lengths {log(k) : k>=2}. - David Bevan, Jan 07 2025
REFERENCES
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 126, see #27.
R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 141.
Kalmár, Laszlo, A "factorisatio numerorum" problemajarol [Hungarian], Matemat. Fizik. Lapok, 38 (1931), 1-15.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 124.
FORMULA
With different offset: a(n) = sum of all a(i) such that i divides n and i < n. - Clark Kimberlinga(p^k) = 2^(k-1) if k>0 and p is a prime.
Dirichlet g.f.: 1/(2-zeta(s)). - Herbert S. Wilf, Apr 29 2003
If p,q,r,... are distinct primes, then a(p*q)=3, a(p^2*q)=8, a(p*q*r)=13, a(p^3*q)=20, etc. - Vladimir Shevelev, Aug 03 2011 [corrected by Charles R Greathouse IV, Jun 02 2012] a(0) = 0, a(1) = 1; a(n) = [x^n] Sum_{k=1..n-1} a(k)*x^k/(1 - x^k). - Ilya Gutkovskiy, Dec 11 2017 If p,q are distinct primes, and n,m>0 then we have:
a(p^n*q^m) = Sum_{k=0..min(n,m)} 2^(n+m-k-1)*binomial(n,k)*binomial(m,k);
More generally: let tau[k](n) denote the number of ordered factorizations of n as a product of k terms, also named the k-th Piltz function (see A007425), then we have for n>1: a(n) = Sum_{j=1..bigomega(n)} Sum_{k=1..j} (-1)^(j-k)*binomial(j,k)*tau[k](n), or
a(n) = Sum_{j=1..bigomega(n)} Sum_{k=0..j-1} (-1)^k*binomial(j,k)*tau[j-k](n). (End)
EXAMPLE
G.f. = x + x^2 + x^3 + 2*x^4 + x^5 + 3*x^6 + x^7 + 4*x^8 + 2*x^9 + 3*x^10 + ...
Number of ordered factorizations of 8 is 4: 8 = 2*4 = 4*2 = 2*2*2.
MAPLE
a := array(1..150): for k from 1 to 150 do a[k] := 0 od: a[1] := 1: for j from 2 to 150 do for m from 1 to j-1 do if j mod m = 0 then a[j] := a[j]+a[m] fi: od: od: for k from 1 to 150 do printf(`%d, `, a[k]) od: # James A. Sellers, Dec 07 2000 A074206:= proc(n) option remember; if n > 1 then `+`(op(apply( A074206, numtheory[divisors](n)[1..-2]))) else n fi end: # M. F. Hasler, Oct 12 2018
MATHEMATICA
a[0] = 0; a[1] = 1; a[n_] := a[n] = a /@ Most[Divisors[n]] // Total; a /@ Range[20000] (* N. J. A. Sloane, May 04 2016, based on program in A002033 *) ccc[n_]:=Switch[n, 0, {}, 1, {{1}}, _, Join@@Table[Prepend[#, n]&/@ccc[d], {d, Most[Divisors[n]]}]]; Table[Length[ccc[n]], {n, 0, 100}] (* Gus Wiseman, Aug 25 2020 *)
PROG
(Haskell)
a074206 n | n <= 1 = n
| otherwise = 1 + (sum $ map (a074206 . (div n)) $
tail $ a027751_row n)
(PARI) A=vector(100); A[1]=1; for(n=2, #A, A[n]=1+sumdiv(n, d, A[d])); A/=2; A[1]=1; concat(0, A) \\ Charles R Greathouse IV, Nov 20 2012 (PARI) {a(n) = if( n<2, n>0, my(A = divisors(n)); sum(k=1, #A-1, a(A[k])))}; /* Michael Somos, Dec 26 2016 */ (PARI) A74206=[1]; A074206(n)={if(#A74206<n, A74206=concat(A74206, vector(n*3\/2-#A74206)), n&& A74206[n], return(A74206[n])); A74206[n]=sumdiv(n, i, if(i<4, i<n, i<n, A074206(i)))} \\ Use memoization for computing many values. - M. F. Hasler, Oct 12 2018 (PARI) first(n) = {my(res = vector(n, i, 1)); for(i = 2, n, for(j = 2, n \ i, res[i*j] += res[i])); concat(0, res)} \\ David A. Corneth, Oct 13 2018 (PARI) first(n) = {my(res = vector(n, i, 1)); for(i = 2, n, d = divisors(i); res[i] += sum(j = 1, #d-1, res[d[j]])); concat(0, res)} \\ somewhat faster than progs above for finding first terms of n. \\ David A. Corneth, Oct 12 2018 (PARI) a(n)={if(!n, 0, my(sig=factor(n)[, 2], m=vecsum(sig)); sum(k=0, m, prod(i=1, #sig, binomial(sig[i]+k-1, k-1))*sum(r=k, m, binomial(r, k)*(-1)^(r-k))))} \\ Andrew Howroyd, Aug 30 2020 (SageMath)
@cached_function
def minus_mu(n):
if n < 2: return n
return sum(minus_mu(d) for d in divisors(n)[:-1])
# Note that changing the sign of the sum gives the Möbius function A008683. print([minus_mu(n) for n in (0..96)]) # Peter Luschny, Dec 26 2016 (Python)
from math import prod
from functools import lru_cache
from sympy import divisors, factorint, prime
@lru_cache(maxsize=None)
def A074206(n): return sum( A074206(d) for d in divisors(prod(prime(i+1)**e for i, e in enumerate(sorted(factorint(n).values(), reverse=True))), generator=True, proper=True)) if n > 1 else n # Chai Wah Wu, Sep 16 2022
CROSSREFS
Apart from initial term, same as A002033. A124433 has these as unsigned row sums.
A001222 counts prime factors with multiplicity.
A008480 counts ordered prime factorizations.
A067824 counts strict chains of divisors starting with n.
A122651 counts strict chains of divisors summing to n.
A253249 counts strict chains of divisors.
Cf. A000005, A025487, A046523, A059576, A122408, A124010, A153881 (Dirichlet inverse), A167865, A174725, A174726, A175522, A181819, A320390, A334997, A337105, A361665.
EXTENSIONS
Originally this sequence was merged with A002033, the number of perfect partitions. Herbert S. Wilf suggested that it warrants an entry of its own.
Number of partitions of n into an odd number of parts.
+10
206
0, 1, 1, 2, 2, 4, 5, 8, 10, 16, 20, 29, 37, 52, 66, 90, 113, 151, 190, 248, 310, 400, 497, 632, 782, 985, 1212, 1512, 1851, 2291, 2793, 3431, 4163, 5084, 6142, 7456, 8972, 10836, 12989, 15613, 18646, 22316, 26561, 31659, 37556, 44601, 52743, 62416, 73593, 86809, 102064, 120025, 140736
COMMENTS
Number of partitions of n in which greatest part is odd.
Number of partitions of n+1 into an even number of parts, the least being 1. Example: a(5)=4 because we have [5,1], [3,1,1,1], [2,1,1] and [1,1,1,1,1,1].
Also number of partitions of n+1 such that the largest part is even and occurs only once. Example: a(5)=4 because we have [6], [4,2], [4,1,1] and [2,1,1,1,1]. - Emeric Deutsch, Apr 05 2006 Also the number of partitions of n such that the number of odd parts and the number of even parts have opposite parities. Example: a(8)=10 is a count of these partitions: 8, 611, 521, 431, 422, 41111, 332, 32111, 22211, 2111111. - Clark Kimberling, Feb 01 2014, corrected Jan 06 2021 In Chaves 2011 see page 38 equation (3.20). - Michael Somos, Dec 28 2014 Suppose that c(0) = 1, that c(1), c(2), ... are indeterminates, that d(0) = 1, and that d(n) = -c(n) - c(n-1)*d(1) - ... - c(0)*d(n-1). When d(n) is expanded as a polynomial in c(1), c(2),..,c(n), the terms are of the form H*c(i_1)*c(i_2)*...*c(i_k). Let P(n) = [c(i_1), c(i_2), ..., c(i_k)], a partition of n. Then H is negative if P has an odd number of parts, and H is positive if P has an even number of parts. That is, d(n) has A027193(n) negative coefficients, A027187(n) positive coefficients, and A000041 terms. The maximal coefficient in d(n), in absolute value, is A102462(n). - Clark Kimberling, Dec 15 2016
REFERENCES
N. J. Fine, Basic Hypergeometric Series and Applications, Amer. Math. Soc., 1988; p. 39, Example 7.
FORMULA
G.f.: Sum(k>=1, x^(2*k-1)/Product(j=1..2*k-1, 1-x^j ) ). - Emeric Deutsch, Apr 05 2006 G.f.: - Sum(k>=1, (-x)^(k^2)) / Product(k>=1, 1-x^k ). - Joerg Arndt, Feb 02 2014 G.f.: Sum(k>=1, x^(k*(2*k-1)) / Product(j=1..2*k, 1-x^j)). - Michael Somos, Dec 28 2014
EXAMPLE
G.f. = x + x^2 + 2*x^3 + 2*x^4 + 4*x^5 + 5*x^6 + 8*x^7 + 10*x^8 + 16*x^9 + 20*x^10 + ...
The a(1) = 1 through a(8) = 10 partitions into an odd number of parts are the following. The Heinz numbers of these partitions are given by A026424. (1) (2) (3) (4) (5) (6) (7) (8)
(111) (211) (221) (222) (322) (332)
(311) (321) (331) (422)
(11111) (411) (421) (431)
(21111) (511) (521)
(22111) (611)
(31111) (22211)
(1111111) (32111)
(41111)
(2111111)
The a(1) = 1 through a(8) = 10 partitions whose greatest part is odd are the following. The Heinz numbers of these partitions are given by A244991. (1) (11) (3) (31) (5) (33) (7) (53)
(111) (1111) (32) (51) (52) (71)
(311) (321) (322) (332)
(11111) (3111) (331) (521)
(111111) (511) (3221)
(3211) (3311)
(31111) (5111)
(1111111) (32111)
(311111)
(11111111)
(End)
MAPLE
g:=sum(x^(2*k)/product(1-x^j, j=1..2*k-1), k=1..40): gser:=series(g, x=0, 50): seq(coeff(gser, x, n), n=1..45); # Emeric Deutsch, Apr 05 2006
MATHEMATICA
nn=40; CoefficientList[Series[ Sum[x^(2j+1)Product[1/(1- x^i), {i, 1, 2j+1}], {j, 0, nn}], {x, 0, nn}], x] (* Geoffrey Critzer, Dec 01 2012 *) a[ n_] := If[ n < 0, 0, Length@Select[ IntegerPartitions[ n], OddQ[ Length@#] &]]; (* Michael Somos, Dec 28 2014 *) a[ n_] := If[ n < 1, 0, Length@Select[ IntegerPartitions[ n], OddQ[ First@#] &]]; (* Michael Somos, Dec 28 2014 *) a[ n_] := If[ n < 0, 0, Length@Select[ IntegerPartitions[ n + 1], #[[-1]] == 1 && EvenQ[ Length@#] &]]; (* Michael Somos, Dec 28 2014 *) a[ n_] := If[ n < 1, 0, Length@Select[ IntegerPartitions[ n + 1], EvenQ[ First@#] && (Length[#] < 2 || #[[1]] != #[[2]]) &]]; (* Michael Somos, Dec 28 2014 *)
PROG
(PARI) {a(n) = if( n<1, 0, polcoeff( sum( k=1, n, if( k%2, x^k / prod( j=1, k, 1 - x^j, 1 + x * O(x^(n-k)) ))), n))}; /* Michael Somos, Jul 24 2012 */ (PARI) q='q+O('q^66); concat([0], Vec( (1/eta(q)-eta(q)/eta(q^2))/2 ) ) \\ Joerg Arndt, Mar 23 2014
CROSSREFS
The even-length version is A027187. The case of odd maximum as well as length is A340385. Other cases of odd length:
- A024429 counts set partitions of odd length. - A067659 counts strict partitions of odd length. - A089677 counts ordered set partitions of odd length. - A166444 counts compositions of odd length. - A174726 counts ordered factorizations of odd length. - A332304 counts strict compositions of odd length. - A339890 counts factorizations of odd length. A026804 counts partitions whose least part is odd.
A072233 counts partitions by sum and length.
A101707 counts partitions of odd positive rank.
Number of partitions of n into an even number of parts.
+10
185
1, 0, 1, 1, 3, 3, 6, 7, 12, 14, 22, 27, 40, 49, 69, 86, 118, 146, 195, 242, 317, 392, 505, 623, 793, 973, 1224, 1498, 1867, 2274, 2811, 3411, 4186, 5059, 6168, 7427, 9005, 10801, 13026, 15572, 18692, 22267, 26613, 31602, 37619, 44533, 52815, 62338, 73680, 86716, 102162, 119918
COMMENTS
For n > 0, also the number of partitions of n whose greatest part is even. [Edited by Gus Wiseman, Jan 05 2021] Number of partitions of n+1 into an odd number of parts, the least being 1.
Also the number of partitions of n such that the number of even parts has the same parity as the number of odd parts; see Comments at A027193. - Clark Kimberling, Feb 01 2014, corrected Jan 06 2021 Suppose that c(0) = 1, that c(1), c(2), ... are indeterminates, that d(0) = 1, and that d(n) = -c(n) - c(n-1)*d(1) - ... - c(0)*d(n-1). When d(n) is expanded as a polynomial in c(1), c(2),..,c(n), the terms are of the form H*c(i_1)*c(i_2)*...*c(i_k). Let P(n) = [c(i_1), c(i_2), ..., c(i_k)], a partition of n. Then H is negative if P has an odd number of parts, and H is positive if P has an even number of parts. That is, d(n) has A027193(n) negative coefficients, A027187(n) positive coefficients, and A000041 terms. The maximal coefficient in d(n), in absolute value, is A102462(n). - Clark Kimberling, Dec 15 2016
REFERENCES
N. J. Fine, Basic Hypergeometric Series and Applications, Amer. Math. Soc., 1988; See p. 8, (7.323) and p. 39, Example 7.
LINKS
N. J. Fine, Problem 4314, Amer. Math. Monthly, Vol. 57, 1950, 421-423.
FORMULA
a(n) = p(n) - p(n-1) + p(n-4) - p(n-9) + ... where p(n) is the number of unrestricted partitions of n, A000041. [Fine] - David Callan, Mar 14 2004 G.f.: A(q) = Sum_{n >= 0} a(n) q^n = 1 + q^2 + q^3 + 3 q^4 + 3 q^5 + 6 q^6 + ...
= Sum_{n >= 0} q^(2n)/(q; q)_{2n}
= ((Product_{k >= 1} 1/(1-q^k) + (Product_{k >= 1} 1/(1+q^k))/2.
Also, let B(q) = Sum_{n >= 0} A027193(n) q^n = q + q^2 + 2 q^3 + 2 q^4 + 4 q^5 + 5 q^6 + ... Then B(q) = Sum_{n >= 0} q^(2n+1)/(q; q)_{2n+1} = ((Product_{k >= 1} 1/(1-q^k) - (Product_{k >= 1} 1/(1+q^k))/2.
Also we have the following identity involving 2 X 2 matrices:
Product_{k >= 1} [ 1/(1-q^2k) q^k/(1-q^2k / q^k/(1-q^2k) 1/(1-q^2k) ]
= [ A(q) B(q) / B(q) A(q) ]. (End)
Expansion of (1 + phi(-q)) / (2 * f(-q)) where phi(), f() are Ramanujan theta functions. - Michael Somos, Aug 19 2006 G.f.: (Sum_{k>=0} (-1)^k * x^(k^2)) / (Product_{k>0} (1 - x^k)). - Michael Somos, Aug 19 2006
EXAMPLE
G.f. = 1 + x^2 + x^3 + 3*x^4 + 3*x^5 + 6*x^6 + 7*x^7 + 12*x^8 + 14*x^9 + 22*x^10 + ...
The a(2) = 1 through a(8) = 12 partitions into an even number of parts are the following. The Heinz numbers of these partitions are given by A028260. (11) (21) (22) (32) (33) (43) (44)
(31) (41) (42) (52) (53)
(1111) (2111) (51) (61) (62)
(2211) (2221) (71)
(3111) (3211) (2222)
(111111) (4111) (3221)
(211111) (3311)
(4211)
(5111)
(221111)
(311111)
(11111111)
The a(2) = 1 through a(8) = 12 partitions whose greatest part is even are the following. The Heinz numbers of these partitions are given by A244990. (2) (21) (4) (41) (6) (43) (8)
(22) (221) (42) (61) (44)
(211) (2111) (222) (421) (62)
(411) (2221) (422)
(2211) (4111) (431)
(21111) (22111) (611)
(211111) (2222)
(4211)
(22211)
(41111)
(221111)
(2111111)
(End)
MATHEMATICA
f[n_] := Length[Select[IntegerPartitions[n], IntegerQ[First[#]/2] &]]; Table[f[n], {n, 1, 30}] (* Clark Kimberling, Mar 13 2012 *) a[ n_] := SeriesCoefficient[ (1 + EllipticTheta[ 4, 0, x]) / (2 QPochhammer[ x]), {x, 0, n}]; (* Michael Somos, May 06 2015 *) a[ n_] := If[ n < 0, 0, Length@Select[ IntegerPartitions[n], EvenQ[Length @ #] &]]; (* Michael Somos, May 06 2015 *)
PROG
(PARI) {a(n) = my(A); if( n<0, 0, A = x * O(x^n); polcoeff( sum( k=0, sqrtint(n), (-x)^k^2, A) / eta(x + A), n))}; /* Michael Somos, Aug 19 2006 */ (PARI) q='q+O('q^66); Vec( (1/eta(q)+eta(q)/eta(q^2))/2 ) \\ Joerg Arndt, Mar 23 2014
CROSSREFS
The Heinz numbers of these partitions are A028260. The case of even sum as well as length is A236913 (the even bisection). Other cases of even length:
- A024430 counts set partitions of even length. - A034008 counts compositions of even length. - A052841 counts ordered set partitions of even length. - A174725 counts ordered factorizations of even length. - A332305 counts strict compositions of even length - A339846 counts factorizations of even length. A026805 counts partitions whose least part is even.
A072233 counts partitions by sum and length.
A101708 counts partitions of even positive rank.
Number of odd-length factorizations of n into factors > 1.
+10
78
0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 2, 1, 4, 1, 1, 1, 4, 1, 1, 1, 3, 1, 2, 1, 2, 2, 1, 1, 6, 1, 2, 1, 2, 1, 3, 1, 3, 1, 1, 1, 5, 1, 1, 2, 5, 1, 2, 1, 2, 1, 2, 1, 8, 1, 1, 2, 2, 1, 2, 1, 6, 2, 1, 1, 5, 1, 1, 1
EXAMPLE
The a(n) factorizations for n = 24, 48, 60, 72, 96, 120:
24 48 60 72 96 120
2*2*6 2*3*8 2*5*6 2*4*9 2*6*8 3*5*8
2*3*4 2*4*6 3*4*5 2*6*6 3*4*8 4*5*6
3*4*4 2*2*15 3*3*8 4*4*6 2*2*30
2*2*12 2*3*10 3*4*6 2*2*24 2*3*20
2*2*2*2*3 2*2*18 2*3*16 2*4*15
2*3*12 2*4*12 2*5*12
2*2*2*3*3 2*2*2*2*6 2*6*10
2*2*2*3*4 3*4*10
2*2*2*3*5
MAPLE
g:= proc(n, k, t) option remember; `if`(n>k, 0, t)+
`if`(isprime(n), 0, add(`if`(d>k, 0, g(n/d, d, 1-t)),
d=numtheory[divisors](n) minus {1, n}))
end:
a:= n-> `if`(n<2, 0, g(n$2, 1)):
MATHEMATICA
facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];
Table[Length[Select[facs[n], OddQ@Length[#]&]], {n, 100}]
CROSSREFS
The case of set partitions (or n squarefree) is A024429. The case of partitions (or prime powers) is A027193. The remaining (even-length) factorizations are counted by A339846. A160786 counts odd-length partitions of odd numbers, ranked by A300272.
A316439 counts factorizations by product and length.
A340101 counts factorizations into odd factors.
A340102 counts odd-length factorizations into odd factors.
Number of even-length factorizations of n into factors > 1.
+10
77
1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 2, 0, 1, 1, 3, 0, 2, 0, 2, 1, 1, 0, 4, 1, 1, 1, 2, 0, 3, 0, 3, 1, 1, 1, 5, 0, 1, 1, 4, 0, 3, 0, 2, 2, 1, 0, 6, 1, 2, 1, 2, 0, 4, 1, 4, 1, 1, 0, 6, 0, 1, 2, 6, 1, 3, 0, 2, 1, 3, 0, 8, 0, 1, 2, 2, 1, 3, 0, 6, 3, 1, 0, 6, 1, 1, 1, 4, 0, 6, 1, 2, 1, 1, 1, 10, 0, 2, 2, 5, 0, 3, 0, 4, 3
EXAMPLE
The a(n) factorizations for n = 12, 16, 24, 36, 48, 72, 96, 120:
2*6 2*8 3*8 4*9 6*8 8*9 2*48 2*60
3*4 4*4 4*6 6*6 2*24 2*36 3*32 3*40
2*2*2*2 2*12 2*18 3*16 3*24 4*24 4*30
2*2*2*3 3*12 4*12 4*18 6*16 5*24
2*2*3*3 2*2*2*6 6*12 8*12 6*20
2*2*3*4 2*2*2*9 2*2*3*8 8*15
2*2*3*6 2*2*4*6 10*12
2*3*3*4 2*3*4*4 2*2*5*6
2*2*2*12 2*3*4*5
2*2*2*2*2*3 2*2*2*15
2*2*3*10
MAPLE
g:= proc(n, k, t) option remember; `if`(n>k, 0, t)+
`if`(isprime(n), 0, add(`if`(d>k, 0, g(n/d, d, 1-t)),
d=numtheory[divisors](n) minus {1, n}))
end:
a:= n-> `if`(n=1, 1, g(n$2, 0)):
MATHEMATICA
facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];
Table[Length[Select[facs[n], EvenQ@Length[#]&]], {n, 100}]
PROG
(PARI) A339846(n, m=n, e=1) = if(1==n, e, sumdiv(n, d, if((d>1)&&(d<=m), A339846(n/d, d, 1-e)))); \\ Antti Karttunen, Oct 22 2023
CROSSREFS
The case of set partitions (or n squarefree) is A024430. The case of partitions (or prime powers) is A027187. The odd-length factorizations are counted by A339890. A316439 counts factorizations by product and length.
A340102 counts odd-length factorizations into odd factors.
Number of partitions of n into distinct parts such that number of parts is even.
+10
53
1, 0, 0, 1, 1, 2, 2, 3, 3, 4, 5, 6, 7, 9, 11, 13, 16, 19, 23, 27, 32, 38, 45, 52, 61, 71, 83, 96, 111, 128, 148, 170, 195, 224, 256, 292, 334, 380, 432, 491, 556, 630, 713, 805, 908, 1024, 1152, 1295, 1455, 1632, 1829, 2049, 2291, 2560, 2859, 3189, 3554, 3959, 4404
REFERENCES
B. C. Berndt, Ramanujan's Notebooks Part III, Springer-Verlag, see p. 18 Entry 9 Corollary (2).
FORMULA
G.f.: A(q) = Sum_{n >= 0} a(n) q^n = 1 + q^3 + q^4 + 2 q^5 + 2 q^6 + 3 q^7 + ... = Sum_{n >= 0} q^(n(2n+1))/(q; q)_{2n} [ Bill Gosper, Jun 25 2005] Also, let B(q) = Sum_{n >= 0} A067659(n) q^n = q + q^2 + q^3 + q^4 + q^5 + 2 q^6 + ... Then B(q) = Sum_{n >= 0} q^((n+1)(2n+1))/(q; q)_{2n+1}. Also we have the following identity involving 2 X 2 matrices:
Prod_{k >= 1} [ 1, q^k; q^k, 1 ] = [ A(q), B(q); B(q), A(q) ] [ Bill Gosper, Jun 25 2005] Expansion of (1 + phi(-x)) / (2*chi(-x)) in powers of x where phi(), chi() are Ramanujan theta functions. - Michael Somos, Feb 14 2006 G.f.: A(x) = (1/2)*((Product_{n >= 0} 1 + x^n) + (Product_{n >= 0} 1 - x^n)).
Let B(x) denote the g.f. of A067659. Then A(x)^2 - B(x)^2 = A(x^2) - B(x^2) = Product_{n >= 1} 1 - x^(2*n) = Sum_{n in Z} (-1)^n*x^(n*(3*n+1)).
A(x) + B(x) is the g.f. of A000009. 1/(A(x) - B(x)) is the g.f. of A000041. (A(x) + B(x))/(A(x) - B(x)) is the g.f. of A015128. A(x)/(A(x) + B(x)) = Sum_{n >= 0} (-1)^n*x^n^2 = (1 + theta_3(-x))/2.
B(x)/(A(x) - B(x)) is the g.f. of A014968. A(x)/(A(x^2) - B(x^2)) is the g.f. of A027187. B(x)/(A(x^2) - B(x^2)) is the g.f. of A027193. (End)
EXAMPLE
G.f. = 1 + x^3 + x^4 + 2*x^5 + 2*x^6 + 3*x^7 + 3*x^8 + 4*x^9 + 5*x^10 + ...
The a(3) = 1 through a(14) = 11 partitions (A-D = 10..13):
21 31 32 42 43 53 54 64 65 75 76 86
41 51 52 62 63 73 74 84 85 95
61 71 72 82 83 93 94 A4
81 91 92 A2 A3 B3
4321 A1 B1 B2 C2
5321 5421 C1 D1
6321 5431 5432
6421 6431
7321 6521
7421
8321
(End)
MAPLE
b:= proc(n, i, t) option remember; `if`(n>i*(i+1)/2, 0,
`if`(n=0, t, add(b(n-i*j, i-1, abs(t-j)), j=0..min(n/i, 1))))
end:
a:= n-> b(n$2, 1):
MATHEMATICA
b[n_, i_, t_] := b[n, i, t] = If[n > i*(i + 1)/2, 0, If[n == 0, t, Sum[b[n - i*j, i - 1, Abs[t - j]], {j, 0, Min[n/i, 1]}]]]; a[n_] := b[n, n, 1]; Table[a[n], {n, 0, 80}] (* Jean-François Alcover, Jan 16 2015, after Alois P. Heinz *) a[ n_] := SeriesCoefficient[ (QPochhammer[ -x, x] + QPochhammer[ x]) / 2, {x, 0, n}]; (* Michael Somos, May 06 2015 *) Table[Length[Select[IntegerPartitions[n], UnsameQ@@#&&EvenQ[Length[#]]&]], {n, 0, 30}] (* Gus Wiseman, Jan 08 2021 *)
PROG
(PARI) {a(n) = my(A); if( n<0, 0, A = x * O(x^n); polcoeff( (eta(x^2 + A) / eta(x + A) + eta(x + A)) / 2, n))}; /* Michael Somos, Feb 14 2006 */ (PARI) N=66; q='q+O('q^N); S=1+2*sqrtint(N);
gf=sum(n=0, S, (n%2==0) * q^(n*(n+1)/2) / prod(k=1, n, 1-q^k ) );
CROSSREFS
Numbers with these strict partitions as binary indices are A001969. The Heinz numbers of these partitions are A030229. Other cases of even length:
- A024430 counts set partitions of even length. - A034008 counts compositions of even length. - A052841 counts ordered set partitions of even length. - A174725 counts ordered factorizations of even length. - A332305 counts strict compositions of even length - A339846 counts factorizations of even length. A008289 counts strict partitions by sum and length.
A026805 counts partitions whose least part is even.
Number of ordered factorizations of n with integer alternating product.
+10
26
1, 1, 1, 2, 1, 1, 1, 3, 2, 1, 1, 4, 1, 1, 1, 7, 1, 4, 1, 4, 1, 1, 1, 6, 2, 1, 3, 4, 1, 1, 1, 11, 1, 1, 1, 18, 1, 1, 1, 6, 1, 1, 1, 4, 4, 1, 1, 20, 2, 4, 1, 4, 1, 6, 1, 6, 1, 1, 1, 8, 1, 1, 4, 26, 1, 1, 1, 4, 1, 1, 1, 35, 1, 1, 4, 4, 1, 1, 1, 20, 7, 1, 1, 8, 1, 1, 1, 6, 1, 8, 1, 4, 1, 1, 1, 32, 1, 4, 4, 18
COMMENTS
An ordered factorization of n is a sequence of positive integers > 1 with product n.
We define the alternating product of a sequence (y_1,...,y_k) to be Product_i y_i^((-1)^(i-1)).
EXAMPLE
The ordered factorizations for n = 4, 8, 12, 16, 24, 32, 36:
4 8 12 16 24 32 36
2*2 4*2 6*2 4*4 12*2 8*4 6*6
2*2*2 2*2*3 8*2 2*2*6 16*2 12*3
3*2*2 2*2*4 3*2*4 2*2*8 18*2
2*4*2 4*2*3 2*4*4 2*2*9
4*2*2 6*2*2 4*2*4 2*3*6
2*2*2*2 4*4*2 2*6*3
8*2*2 3*2*6
2*2*4*2 3*3*4
4*2*2*2 3*6*2
2*2*2*2*2 4*3*3
6*2*3
6*3*2
9*2*2
2*2*3*3
2*3*3*2
3*2*2*3
3*3*2*2
MATHEMATICA
facs[n_]:=If[n<=1, {{}}, Join@@Table[Map[Prepend[#, d]&, Select[facs[n/d], Min@@#>=d&]], {d, Rest[Divisors[n]]}]];
altprod[q_]:=Product[q[[i]]^(-1)^(i-1), {i, Length[q]}];
Table[Length[Select[Join@@Permutations/@facs[n], IntegerQ[altprod[#]]&]], {n, 100}]
PROG
(PARI) A347463(n, m=n, ap=1, e=0) = if(1==n, if(e%2, 1==denominator(ap), 1==numerator(ap)), sumdiv(n, d, if(d>1, A347463(n/d, d, ap * d^((-1)^e), 1-e)))); \\ Antti Karttunen, Jul 28 2024
CROSSREFS
The restriction to powers of 2 is A116406. A046099 counts factorizations with no alternating permutations.
A103919 counts partitions by sum and alternating sum (reverse: A344612).
A119620 counts partitions with alternating product 1, ranked by A028982.
A273013 counts ordered factorizations of n^2 with alternating product 1.
A347438 counts factorizations with alternating product 1.
A347460 counts possible alternating products of factorizations.
Cf. A025047, A038548, A138364, A347440, A347441, A347453, A347454, A347456, A347458, A347459, A347464, A347705, A347708.
Search completed in 0.030 seconds
|