A003114 -id:A003114 - cp's OEIS frontend

A342096 Number of integer partitions of n with no adjacent parts having quotient >= 2.

1, 2, 2, 3, 3, 4, 4, 6, 6, 8, 9, 11, 13, 17, 19, 24, 29, 35, 42, 51, 61, 75, 90, 108, 130, 158, 189, 227, 272, 325, 389, 464, 553, 659, 782, 929, 1102, 1306, 1545, 1824, 2153, 2538, 2989, 3514, 4127, 4842, 5673, 6642, 7766, 9068, 10583, 12335, 14361, 16705

Offset: 1

Gus Wiseman, Mar 02 2021

nonn

The decapitation of such a partition (delete the greatest part) is term-wise greater than its negated first-differences.

			The a(1) = 1 through a(10) = 8 partitions:
  1  2   3    4     5      6       7        8         9          A
     11  111  22    32     33      43       44        54         55
              1111  11111  222     322      53        333        64
                           111111  1111111  332       432        433
                                            2222      3222       532
                                            11111111  111111111  3322
                                                                 22222
                                                                 1111111111

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..250

The case of equality (all adjacent parts having quotient 2) is A154402.
The multiplicative version is A342083 or A342084.
The version allowing quotients of 2 exactly is A342094.
The strict case allowing quotients of 2 exactly is A342095.
The strict case is A342097.
The reciprocal version is A342098.
A000009 counts strict partitions.
A000929 counts partitions with no adjacent parts having quotient < 2.
A003114 counts partitions with adjacent parts differing by more than 1.
A034296 counts partitions with adjacent parts differing by at most 1.
Cf. A027193, A001055, A001227, A003242, A167606, A342085, A342191.

Table[Length[Select[IntegerPartitions[n],And@@Thread[Differences[-#]

A342097 Number of strict integer partitions of n with no adjacent parts having quotient >= 2.

Original entry on oeis.org

1, 1, 1, 1, 2, 1, 2, 2, 3, 3, 3, 3, 4, 6, 6, 7, 8, 8, 9, 11, 13, 15, 18, 20, 24, 25, 29, 32, 39, 42, 48, 54, 63, 72, 81, 89, 102, 116, 132, 147, 165, 187, 210, 238, 264, 296, 329, 371, 414, 465, 516, 580, 644, 722, 803, 897, 994, 1108, 1229, 1367, 1512, 1678

Offset: 1

Gus Wiseman, Mar 02 2021

nonn

The decapitation of such a partition (delete the greatest part) is term-wise greater than its negated first-differences.

			The a(1) = 1 through a(16) = 7 partitions (A..G = 10..16):
  1  2  3  4  5   6  7   8   9    A    B   C    D    E     F     G
              32     43  53  54   64   65  75   76   86    87    97
                             432  532  74  543  85   95    96    A6
                                                643  653   654   754
                                                     743   753   853
                                                     5432  6432  6532
                                                                 7432

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..400

The case of equality (all adjacent parts having quotient 2) is A154402.
The multiplicative version is A342083 or A342084.
The non-strict version allowing quotients of 2 exactly is A342094.
The version allowing quotients of 2 exactly is A342095.
The non-strict version is A342096.
The reciprocal version is A342098.
A000009 counts strict partitions.
A000929 counts partitions with no adjacent parts having quotient < 2.
A003114 counts partitions with adjacent parts differing by more than 1.
A034296 counts partitions with adjacent parts differing by at most 1.
Cf. A027193, A001055, A001227, A003242, A167606, A337135, A342085.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&And@@Thread[Differences[-#]

A342095 Number of strict integer partitions of n with no adjacent parts having quotient > 2.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 3, 2, 4, 4, 6, 7, 6, 8, 10, 9, 13, 16, 17, 20, 25, 26, 29, 36, 40, 45, 55, 61, 69, 81, 90, 103, 119, 132, 154, 176, 196, 225, 254, 282, 323, 364, 403, 458, 519, 582, 655, 735, 822, 922, 1035, 1153, 1290, 1441, 1600, 1788, 1997, 2217, 2468

Offset: 1

Gus Wiseman, Mar 02 2021

nonn

The decapitation of such a partition (delete the greatest part) is term-wise greater than or equal to its negated first-differences.

			The a(1) = 1 through a(15) = 10 partitions (A..F = 10..15):
  1  2  3   4  5   6    7    8   9    A     B     C     D     E     F
        21     32  42   43   53  54   64    65    75    76    86    87
                   321  421      63   532   74    84    85    95    96
                                 432  4321  542   543   643   653   A5
                                            632   642   742   743   654
                                            5321  5421  6421  842   753
                                                  6321        5432  843
                                                              7421  6432
                                                                    8421
                                                                    54321

Fausto A. C. Cariboni, Table of n, a(n) for n = 1..400

The reciprocal version (no adjacent parts having quotient < 2) is A000929.
The case of equality (all adjacent parts having quotient 2) is A154402.
The multiplicative version is A342085 or A337135.
The non-strict version is A342094.
The non-strict version without quotients of 2 exactly is A342096.
The version without quotients of 2 exactly is A342097.
A000009 counts strict partitions.
A003114 counts partitions with adjacent parts differing by more than 1.
A034296 counts partitions with adjacent parts differing by at most 1.
Cf. A001055, A001227, A003242, A056239, A167606, A342083, A342084.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&And@@Thread[Differences[-#]<=Rest[#]]&]],{n,30}]

A168659 Number of partitions of n such that the number of parts is divisible by the greatest part. Also number of partitions of n such that the greatest part is divisible by the number of parts.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 6, 6, 8, 9, 14, 16, 22, 25, 33, 39, 51, 60, 79, 92, 116, 137, 174, 204, 254, 300, 368, 435, 530, 625, 760, 896, 1076, 1267, 1518, 1780, 2121, 2484, 2946, 3444, 4070, 4749, 5594, 6514, 7637, 8879, 10384, 12043, 14040, 16255

Offset: 1

Vladeta Jovovic, Dec 02 2009

nonn

			a(5)=3 because in the partitions [1,1,1,1,1], [1,1,1,2], [1,1,3] the number of parts is divisible by the greatest part; not true for the partitions [1,2,2],[2,3], [1,4], and [5]. - _Emeric Deutsch_, Dec 04 2009
From _Gus Wiseman_, Feb 08 2021: (Start)
The a(1) = 1 through a(10) = 9 partitions of the first type:
  1  11  21   22    311    321     322      332       333        4222
         111  1111  2111   2211    331      2222      4221       4321
                    11111  111111  2221     4211      4311       4411
                                   4111     221111    51111      52111
                                   211111   311111    222111     222211
                                   1111111  11111111  321111     322111
                                                      21111111   331111
                                                      111111111  22111111
                                                                 1111111111
The a(1) = 1 through a(11) = 14 partitions of the second type (A=10, B=11):
  1   2   3    4    5     6     7      8      9       A       B
          21   22   41    42    43     44     63      64      65
                    311   321   61     62     81      82      83
                                322    332    333     622     A1
                                331    611    621     631     632
                                4111   4211   4221    4222    641
                                              4311    4321    911
                                              51111   4411    4322
                                                      52111   4331
                                                              4421
                                                              8111
                                                              52211
                                                              53111
                                                              611111
(End)

Vaclav Kotesovec, Table of n, a(n) for n = 1..5000 (terms 1..301 from Vladeta Jovovic corrected by N. J. A. Sloane, Oct 05 2010, terms 302..1000 from Seiichi Manyama)

Cf. A168656, A168657, A079501, A168655.
Note: A-numbers of Heinz-number sequences are in parentheses below.
The case of equality is A047993 (A106529).
The Heinz numbers of these partitions are A340609/A340610.
If all parts (not just the greatest) are divisors we get A340693 (A340606).
The strict case in the second interpretation is A340828 (A340856).
A006141 = partitions whose length equals their minimum (A324522).
A067538 = partitions whose length/max divides their sum (A316413/A326836).
A200750 = partitions with length coprime to maximum (A340608).
Cf. A003114, A039900, A064173, A064174, A143773, A326837, A340653, A340830, A340851, A340853.
Row sums of A350879.

a := proc (n) local pn, ct, j: with(combinat): pn := partition(n): ct := 0: for j to numbpart(n) do if `mod`(nops(pn[j]), max(seq(pn[j][i], i = 1 .. nops(pn[j])))) = 0 then ct := ct+1 else end if end do: ct end proc: seq(a(n), n = 1 .. 50); # Emeric Deutsch, Dec 04 2009

Table[Length[Select[IntegerPartitions[n],Divisible[Length[#],Max[#]]&]],{n,30}] (* Gus Wiseman, Feb 08 2021 *)
nmax = 100; s = 0; Do[s += Normal[Series[Sum[x^((m+1)*k - 1) * Product[(1 - x^(m*k + j - 1))/(1 - x^j), {j, 1, k-1}], {k, 1, (1 + nmax)/(1 + m) + 1}], {x, 0, nmax}]], {m, 1, nmax}]; Rest[CoefficientList[s, x]] (* Vaclav Kotesovec, Oct 18 2024 *)

G.f.: Sum_{i>=1} Sum_{j>=1} x^((i+1)*j-1) * Product_{k=1..j-1} (1-x^(i*j+k-1))/(1-x^k). - Seiichi Manyama, Jan 24 2022

a(n) ~ c * exp(Pi*sqrt(2*n/3)) / n^(3/2), where c = 0.04628003... - Vaclav Kotesovec, Nov 16 2024

Extended by Emeric Deutsch, Dec 04 2009

A064173 Number of partitions of n with positive rank.

Original entry on oeis.org

0, 1, 1, 2, 3, 5, 6, 10, 13, 19, 25, 35, 45, 62, 80, 106, 136, 178, 225, 291, 366, 466, 583, 735, 912, 1140, 1407, 1743, 2140, 2634, 3214, 3932, 4776, 5807, 7022, 8495, 10225, 12313, 14762, 17696, 21136, 25236, 30030, 35722, 42367, 50216, 59368, 70138, 82665

Offset: 1

Vladeta Jovovic, Sep 19 2001

nonn

The rank of a partition is the largest summand minus the number of summands.
Also number of partitions of n with negative rank. - Omar E. Pol, Mar 05 2012
Column 1 of A208478. - Omar E. Pol, Mar 11 2012
Number of partitions p of n such that max(max(p), number of parts of p) is not a part of p. - Clark Kimberling, Feb 28 2014
The sequence enumerates the semigroup of partitions of positive rank for each number n. The semigroup is a subsemigroup of the monoid of partitions of nonnegative rank under the binary operation "*": Let A be the positive rank partition (a1,...,ak) where ak > k, and let B=(b1,...bj) with bj > j. Then let A*B be the partition (a1b1,...,a1bj,...,akb1,...,akbj), which has akbj > kj, thus having positive rank. For example, the partition (2,3,4) of 9 has rank 1, and its product with itself is (4,6,6,8,8,9,12,12,16) of 81, which has rank 7. A similar situation holds for partitions of negative rank--they are a subsemigroup of the monoid of nonpositive rank partitions. - Richard Locke Peterson, Jul 15 2018

			a(20) = p(18) - p(13) + p(5) = 385 - 101 + 7 = 291.
From _Gus Wiseman_, Feb 09 2021: (Start)
The a(2) = 1 through a(9) = 13 partitions of positive rank:
  (2)  (3)  (4)   (5)   (6)    (7)    (8)     (9)
            (31)  (32)  (33)   (43)   (44)    (54)
                  (41)  (42)   (52)   (53)    (63)
                        (51)   (61)   (62)    (72)
                        (411)  (421)  (71)    (81)
                               (511)  (422)   (432)
                                      (431)   (441)
                                      (521)   (522)
                                      (611)   (531)
                                      (5111)  (621)
                                              (711)
                                              (5211)
                                              (6111)
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..10000
F. J. Dyson, Some guesses in the theory of partitions, Eureka (Cambridge) 8 (1944), 10-15.
FindStat, St000145: The Dyson rank of a partition
Mircea Merca, Rank partition functions and truncated theta identities, arXiv:2006.07705 [math.CO], 2020.

Note: A-numbers of ranking sequences are in parentheses below.
The negative-rank version is also A064173 (A340788).
The case of odd positive rank is A101707 (A340604).
The case of even positive rank is A101708 (A340605).
These partitions are ranked by (A340787).
A063995/A105806 count partitions by rank.
A072233 counts partitions by sum and length.
A168659 counts partitions whose length is a multiple of the greatest part.
A200750 counts partitions whose length and greatest part are coprime.
- Rank -
A064174 counts partitions of nonnegative/nonpositive rank (A324562/A324521).
A101198 counts partitions of rank 1 (A325233).
A257541 gives the rank of the partition with Heinz number n.
A340601 counts partitions of even rank (A340602).
A340692 counts partitions of odd rank (A340603).
- Balance -
A047993 counts balanced partitions (A106529).
A340599 counts alt-balanced factorizations.
A340653 counts balanced factorizations.
Cf. A003114, A006141, A039900, A096401, A117193, A117409, A143773, A324516, A324518, A324520.

A064173 := proc(n)
    a := 0 ;
    for p in combinat[partition](n) do
        r := max(op(p))-nops(p) ;
        if r > 0 then
            a := a+1 ;
        end if;
    end do:
    a ;
end proc:
seq(A064173(n),n=0..40) ;# Emeric Deutsch, Dec 11 2004

Table[Count[IntegerPartitions[n], q_ /; First[q] > Length[q]], {n, 24}] (* Clark Kimberling, Feb 12 2014 *)
Table[Count[IntegerPartitions[n], p_ /; ! MemberQ[p, Max[Max[p], Length[p]]]], {n, 20}] (* Clark Kimberling, Feb 28 2014 *)
P = PartitionsP;
a[n_] := (P[n] - Sum[-(-1)^k (P[n - (3k^2 - k)/2] - P[n - (3k^2 + k)/2]), {k, 1, Floor[(1 + Sqrt[1 + 24n])/6]}])/2;
a /@ Range[48] (* Jean-François Alcover, Jan 11 2020, after Wouter Meeussen in A047993 *)

my(N=66, x='x+O('x^N)); concat(0, Vec(sum(k=1, N, x^k*prod(j=1, k, (1-x^(k+j-2))/(1-x^j))))) \\ Seiichi Manyama, Jan 25 2022

a(n) = (A000041(n) - A047993(n))/2.
a(n) = p(n-2) - p(n-7) + p(n-15) - ... - (-1)^k*p(n-(3*k^2+k)/2) + ..., where p() is A000041(). - Vladeta Jovovic, Aug 04 2004
G.f.: Product_{k>=1} (1/(1-q^k)) * Sum_{k>=1} ( (-1)^k * (-q^(3*k^2/2+k/2))) (conjectured). - Thomas Baruchel, May 12 2018
G.f.: Sum_{k>=1} x^k * Product_{j=1..k} (1-x^(k+j-2))/(1-x^j). - Seiichi Manyama, Jan 25 2022
a(n)+A064174(n) = A000041(n). - R. J. Mathar, Feb 22 2023

A025157 Number of partitions of n with distinct parts p(i) such that if i != j, then |p(i) - p(j)| >= 3.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 7, 8, 10, 11, 13, 15, 17, 19, 22, 25, 28, 32, 36, 41, 46, 52, 58, 66, 73, 82, 91, 102, 113, 126, 139, 155, 171, 190, 209, 232, 255, 282, 310, 342, 375, 413, 452, 497, 544, 596, 651, 713, 778, 850, 927, 1011, 1101, 1200, 1305, 1420, 1544, 1677, 1821, 1977, 2144, 2324, 2519, 2728

Offset: 0

Clark Kimberling

nonn

Also number of partitions of n into distinct parts in which the smallest part is greater than or equal to number of parts. - Vladeta Jovovic, Aug 06 2004

			a(12) = 6 because we have 12 = 11+1 = 10+2 = 9+3 = 8+4 = 7+4+1.

Alois P. Heinz, Table of n, a(n) for n = 0..10000
I. Martinjak and D. Svrtan, New Identities for the Polarized Partitions and Partitions with d-Distant Parts, J. Int. Seq. 17 (2014) # 14.11.4.

Cf. A003114, A096401, A263719.

Column k=3 of A194543.

b:= proc(n, i) option remember; `if`(n=0, 1, `if`(n>
      ceil(i*(i+3)/6), 0, b(n, i-1)+b(n-i, min(n-i, i-3))))
    end:
a:= n-> b(n$2):
seq(a(n), n=0..70);  # Alois P. Heinz, Jan 26 2022

nn=50; CoefficientList[Series[Sum[x^(j(3j-1)/2)Product[1/(1-x^i), {i, 1, j}], {j, 0, nn}], {x, 0, nn}], x] (* Geoffrey Critzer, Jul 21 2013 *)

my(N=99, x='x+O('x^N)); Vec(sum(k=0, N, x^(k*(3*k-1)/2)/prod(j=1, k, 1-x^j))) \\ Seiichi Manyama, Jan 13 2022

G.f.: sum(i>=1, x^(3*A000217(i)-2*i)/product(j=1..i, 1-x^j)). - Jon Perry, Jul 20 2004
G.f.: sum(n>=0, x^(n*(3*n-1)/2)/prod(k=1..n,1-x^k)). - Joerg Arndt, Jan 29 2011
a(n) ~ c^(1/4) * exp(2*sqrt(c*n)) / (2*n^(3/4)*r*sqrt(Pi*(1+3*r^2))), where r = A263719 = ((9+sqrt(93))/2)^(1/3)/3^(2/3) - (2/(3*(9+sqrt(93))))^(1/3) = 0.682327803828019327369483739711048256891188581898... is the root of the equation r^3 + r = 1 and c = 3*(log(r))^2/2 + polylog(2, 1-r) = 0.566433354765746647188050807325058683443823543741343518... . - Vaclav Kotesovec, Jan 02 2016

Prepended a(0)=1, Joerg Arndt, Jul 21 2013

A324521 Numbers > 1 where the maximum prime index is less than or equal to the number of prime factors counted with multiplicity.

Original entry on oeis.org

2, 4, 6, 8, 9, 12, 16, 18, 20, 24, 27, 30, 32, 36, 40, 45, 48, 50, 54, 56, 60, 64, 72, 75, 80, 81, 84, 90, 96, 100, 108, 112, 120, 125, 126, 128, 135, 140, 144, 150, 160, 162, 168, 176, 180, 189, 192, 196, 200, 210, 216, 224, 225, 240, 243, 250, 252, 256

Offset: 1

Gus Wiseman, Mar 06 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

Also Heinz numbers of integer partitions with nonnegative rank (A064174). The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

			The sequence of terms together with their prime indices begins:
   2: {1}
   4: {1,1}
   6: {1,2}
   8: {1,1,1}
   9: {2,2}
  12: {1,1,2}
  16: {1,1,1,1}
  18: {1,2,2}
  20: {1,1,3}
  24: {1,1,1,2}
  27: {2,2,2}
  30: {1,2,3}
  32: {1,1,1,1,1}
  36: {1,1,2,2}
  40: {1,1,1,3}
  45: {2,2,3}
  48: {1,1,1,1,2}

Matthieu Pluntz, Table of n, a(n) for n = 1..10929 (up to a(n) = 2^21)

Cf. A001222, A003114, A056239, A061395, A064174, A106529, A112798, A256617.

Cf. A324515, A324517, A324519, A324522, A324560, A324562.

with(numtheory):
q:= n-> is(pi(max(factorset(n)))<=bigomega(n)):
select(q, [$2..300])[];  # Alois P. Heinz, Mar 07 2019

Select[Range[2,100],PrimePi[FactorInteger[#][[-1,1]]]<=PrimeOmega[#]&]

isok(m) = (m>1) && (primepi(vecmax(factor(m)[, 1])) <= bigomega(m)); \\ Michel Marcus, Nov 14 2022

from sympy import factorint, primepi
def ok(n):
    f = factorint(n)
    return primepi(max(f)) <= sum(f.values())
print([k for k in range(2, 257) if ok(k)]) # Michael S. Branicky, Nov 15 2022

A061395(a(n)) <= A001222(a(n)).

A039900 Number of partitions satisfying 0 < cn(0,5) + cn(1,5) + cn(4,5).

Original entry on oeis.org

0, 1, 1, 2, 4, 6, 9, 13, 19, 27, 38, 52, 71, 95, 127, 167, 220, 285, 370, 474, 607, 770, 976, 1226, 1540, 1920, 2391, 2960, 3660, 4501, 5529, 6760, 8254, 10038, 12190, 14750, 17825, 21470, 25825, 30975, 37101, 44322, 52879, 62937, 74811, 88733, 105110, 124261

Offset: 0

Olivier Gérard

nonn

For a given partition cn(i,n) means the number of its parts equal to i modulo n.
Short: o < 0 + 1 + 4 (OMZAAp).
Number of partitions of n such that (greatest part) >= (multiplicity of greatest part), for n >= 1.  For example, a(6) counts these 9 partitions:  6, 51, 42, 411, 33, 321, 3111, 22111, 21111.  See the Mathematica program at A240057 for the sequence as a count of these partitions, along with counts of related partitions.  - Clark Kimberling, Apr 02 2014
The Heinz numbers of these integer partitions are given by A324561. - Gus Wiseman, Mar 09 2019
From Gus Wiseman, Mar 09 2019: (Start)
Also the number of integer partitions of n whose minimum part is less than or equal to the number of parts. The Heinz numbers of these integer partitions are given by A324560. For example, the a(1) = 1 through a(7) = 13 integer partitions are:
  (1)  (11)  (21)   (22)    (32)     (42)      (52)
             (111)  (31)    (41)     (51)      (61)
                    (211)   (221)    (222)     (322)
                    (1111)  (311)    (321)     (331)
                            (2111)   (411)     (421)
                            (11111)  (2211)    (511)
                                     (3111)    (2221)
                                     (21111)   (3211)
                                     (111111)  (4111)
                                               (22111)
                                               (31111)
                                               (211111)
                                               (1111111)
(End)

			From _Gus Wiseman_, Mar 09 2019: (Start)
The a(1) = 1 through a(7) = 13 integer partitions with at least one part equal to 0, 1, or 4 modulo 5:
  (1)  (11)  (21)   (4)     (5)      (6)       (43)
             (111)  (31)    (41)     (42)      (52)
                    (211)   (221)    (51)      (61)
                    (1111)  (311)    (321)     (331)
                            (2111)   (411)     (421)
                            (11111)  (2211)    (511)
                                     (3111)    (2221)
                                     (21111)   (3211)
                                     (111111)  (4111)
                                               (22111)
                                               (31111)
                                               (211111)
                                               (1111111)
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..10000

Cf. A003106, A003114, A039899.
Cf. A003114, A006141, A047993, A064174, A117144.
Cf. A324518, A324520, A324522, A324560, A324561.

b:= proc(n, i, t) option remember; `if`(n=0, t,
      `if`(i<1, 0, b(n, i-1, t)+ `if`(i>n, 0, b(n-i, i,
      `if`(irem(i, 5) in {2, 3}, t, 1)))))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..50);  # Alois P. Heinz, Apr 03 2014

Table[Count[IntegerPartitions[n], p_ /; Min[p] <= Length[p]], {n, 40}] (* Clark Kimberling, Feb 13 2014 *)
b[n_, i_, t_] := b[n, i, t] = If[n==0, t, If[i<1, 0, b[n, i-1, t] + If[i > n, 0, b[n-i, i, If[MemberQ[{2, 3}, Mod[i, 5]], t, 1]]]]]; a[n_] := b[n, n, 0]; Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Nov 16 2015, after Alois P. Heinz *)

my(N=66, x='x+O('x^N)); concat(0, Vec(sum(k=0, N, x^k*(1-x^k^2)/prod(j=1, k, 1-x^j)))) \\ Seiichi Manyama, Jan 13 2022

G.f.: Sum_{k>=0} x^k * (1-x^(k^2)) / Product_{j=1..k} (1-x^j). - Seiichi Manyama, Jan 13 2022

a(n) = A000041(n) - A003106(n). - Vaclav Kotesovec, Oct 20 2024

A040039 First differences of A033485; also A033485 with terms repeated.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 10, 10, 13, 13, 18, 18, 23, 23, 30, 30, 37, 37, 47, 47, 57, 57, 70, 70, 83, 83, 101, 101, 119, 119, 142, 142, 165, 165, 195, 195, 225, 225, 262, 262, 299, 299, 346, 346, 393, 393, 450, 450, 507, 507, 577, 577, 647, 647, 730, 730, 813, 813, 914, 914, 1015, 1015, 1134, 1134, 1253, 1253, 1395, 1395

Offset: 0

N. J. A. Sloane and J. H. Conway

Apparently a(n) = number of partitions (p_1, p_2, ..., p_k) of n+1, with p_1 >= p_2 >= ... >= p_k, such that for each i, p_i > p_{i+1}+...+p_k. - John McKay (mac(AT)mathstat.concordia.ca), Mar 06 2009
Comment from John McKay confirmed in paper by Bessenrodt, Olsson, and Sellers. Such partitions are called "strongly decreasing" partitions in the paper, see the function s(n) therein.
Also the number of unlabeled binary rooted trees with 2*n + 3 nodes in which the two branches directly under any given non-leaf node are either equal or at least one of them is a leaf. - Gus Wiseman, Oct 08 2018
From Gus Wiseman, Apr 06 2021: (Start)
This sequence counts both of the following essentially equivalent things:
1. Sets of distinct positive integers with maximum n + 1 in which all adjacent elements have quotients < 1/2. For example, the a(0) = 1 through a(8) = 7 subsets are:
  {1}  {2}  {3}    {4}    {5}    {6}    {7}      {8}      {9}
            {1,3}  {1,4}  {1,5}  {1,6}  {1,7}    {1,8}    {1,9}
                          {2,5}  {2,6}  {2,7}    {2,8}    {2,9}
                                        {3,7}    {3,8}    {3,9}
                                        {1,3,7}  {1,3,8}  {4,9}
                                                          {1,3,9}
                                                          {1,4,9}
2. Sets of distinct positive integers with maximum n + 1 whose first differences are term-wise greater than their decapitation (remove the maximum). For example, the set q = {1,4,9} has first differences (3,5), which are greater than (1,4), so q is counted under a(8). On the other hand, r = {1,5,9} has first differences (4,4), which are not greater than (1,5), so r is not counted under a(8).
Also the number of partitions of n + 1 into powers of 2 covering an initial interval of powers of 2. For example, the a(0) = 1 through a(8) = 7 partitions are:
  1  11  21   211   221    2211    421      4211      4221
         111  1111  2111   21111   2221     22211     22221
                    11111  111111  22111    221111    42111
                                   211111   2111111   222111
                                   1111111  11111111  2211111
                                                      21111111
                                                      111111111
(End)

			From _Joerg Arndt_, Dec 17 2012: (Start)
The a(19-1)=30 strongly decreasing partitions of 19 are (in lexicographic order)
[ 1]    [ 10 5 3 1 ]
[ 2]    [ 10 5 4 ]
[ 3]    [ 10 6 2 1 ]
[ 4]    [ 10 6 3 ]
[ 5]    [ 10 7 2 ]
[ 6]    [ 10 8 1 ]
[ 7]    [ 10 9 ]
[ 8]    [ 11 5 2 1 ]
[ 9]    [ 11 5 3 ]
[10]    [ 11 6 2 ]
[11]    [ 11 7 1 ]
[12]    [ 11 8 ]
[13]    [ 12 4 2 1 ]
[14]    [ 12 4 3 ]
[15]    [ 12 5 2 ]
[16]    [ 12 6 1 ]
[17]    [ 12 7 ]
[18]    [ 13 4 2 ]
[19]    [ 13 5 1 ]
[20]    [ 13 6 ]
[21]    [ 14 3 2 ]
[22]    [ 14 4 1 ]
[23]    [ 14 5 ]
[24]    [ 15 3 1 ]
[25]    [ 15 4 ]
[26]    [ 16 2 1 ]
[27]    [ 16 3 ]
[28]    [ 17 2 ]
[29]    [ 18 1 ]
[30]    [ 19 ]
The a(20-1)=30 strongly decreasing partitions of 20 are obtained by adding 1 to the first part in each partition in the list.
(End)
From _Gus Wiseman_, Oct 08 2018: (Start)
The a(-1) = 1 through a(4) = 3 semichiral binary rooted trees:
  o  (oo)  (o(oo))  ((oo)(oo))  (o((oo)(oo)))  ((o(oo))(o(oo)))
                    (o(o(oo)))  (o(o(o(oo))))  (o(o((oo)(oo))))
                                               (o(o(o(o(oo)))))
(End)

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..500 from Joerg Arndt)
Christine Bessenrodt, Jorn B. Olsson, and James A. Sellers, Unique path partitions: Characterization and Congruences, arXiv:1107.1156 [math.CO], 2011-2012.
J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013

Cf. A000123.
Cf. A088567, A089054.
Cf. A001190, A003238, A111299, A292050, A317712, A320222, A320230, A320271.
The equal case is A001511.
The reflected version is A045690.
The unequal (anti-run) version is A045691.
A000929 counts partitions with all adjacent parts x >= 2y.
A002843 counts compositions with all adjacent parts x <= 2y.
A018819 counts partitions into powers of 2.
A154402 counts partitions with all adjacent parts x = 2y.
A274199 counts compositions with all adjacent parts x < 2y.
A342094 counts partitions with all adjacent parts x <= 2y (strict: A342095).
A342096 counts partitions without adjacent x >= 2y (strict: A342097).
A342098 counts partitions with all adjacent parts x > 2y.
A342337 counts partitions with all adjacent parts x = y or x = 2y.
Cf. A000009, A003114, A003242, A224957, A342191, A342330.

# For example, the five partitions of 4, written in nonincreasing order, are
# [1,1,1,1], [2,1,1], [2,2], [3,1], [4].
# Only the last two satisfy the condition, and a(3)=2.
# The Maple program below verifies this for small values of n.
with(combinat); N:=8; a:=array(1..N); c:=array(1..N);
for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;
for s to np do r:=p[s]; r:=sort(r,`>`); nr:=nops(r); j:=1;
while jsum(r[k],k=j+1..nr) do j:=j+1;od; # gives A040039
#while j= sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A018819
if j=nr then t:=t+1;fi od; a[n]:=t; od;
# John McKay

T[n_, m_] := T[n, m] = Sum[Binomial[n-2k-1, n-2k-m] Sum[Binomial[m, i] T[k, i], {i, 1, k}], {k, 0, (n-m)/2}] + Binomial[n-1, n-m];
a[n_] := T[n+1, 1];
Table[a[n], {n, 0, 80}] (* Jean-François Alcover, Jul 27 2018, after Vladimir Kruchinin *)
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&And@@Table[#[[i-1]]/#[[i]]<1/2,{i,2,Length[#]}]&]],{n,15}] (* Gus Wiseman, Apr 06 2021 *)

T(n,m):=sum(binomial(n-2*k-1,n-2*k-m)*sum(binomial(m,i)*T(k,i),i,1,k),k,0,(n-m)/2)+binomial(n-1,n-m);
makelist(T(n+1,1),n,0,40); /* Vladimir Kruchinin, Mar 19 2015 */

/* compute as "A033485 with terms repeated" */
b(n) = if(n<2, 1, b(floor(n/2))+b(n-1));  /* A033485 */
a(n) = b(n\2+1); /* note different offsets */
for(n=0,99, print1(a(n),", ")); /* Joerg Arndt, Jan 21 2011 */

from itertools import islice
from collections import deque
def A040039_gen(): # generator of terms
    aqueue, f, b, a = deque([2]), True, 1, 2
    yield from (1, 1, 2, 2)
    while True:
        a += b
        yield from (a, a)
        aqueue.append(a)
        if f: b = aqueue.popleft()
        f = not f
A040039_list = list(islice(A040039_gen(),40)) # Chai Wah Wu, Jun 07 2022

Let T(x) be the g.f, then T(x) = 1 + x/(1-x)*T(x^2) = 1 + x/(1-x) * ( 1 + x^2/(1-x^2) * ( 1 + x^4/(1-x^4) * ( 1 + x^8/(1-x^8) *(...) ))). [Joerg Arndt, May 11 2010]
From Joerg Arndt, Oct 02 2013: (Start)
G.f.: sum(k>=1, x^(2^k-1) / prod(j=0..k-1, 1-x^(2^k) ) ) [Bessenrodt/Olsson/Sellers].
G.f.: 1/(2*x^2) * ( 1/prod(k>=0, 1 - x^(2^k) ) - (1 + x) ).
a(n) = 1/2 * A018819(n+2).
(End)
a(n) = T(n+1,1), where T(n,m)=sum(k..0,(n-m)/2, binomial(n-2*k-1,n-2*k-m)*sum(i=1..k, binomial(m,i)*T(k,i)))+binomial(n-1,n-m). - Vladimir Kruchinin, Mar 19 2015
Using offset 1: a(1) = 1; a(n even) = a(n-1); a(n odd) = a(n-1) + a((n-1)/2). - Gus Wiseman, Oct 08 2018

A324562 Numbers > 1 where the maximum prime index is greater than or equal to the number of prime factors counted with multiplicity.

Original entry on oeis.org

2, 3, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 19, 20, 21, 22, 23, 25, 26, 28, 29, 30, 31, 33, 34, 35, 37, 38, 39, 41, 42, 43, 44, 45, 46, 47, 49, 50, 51, 52, 53, 55, 56, 57, 58, 59, 61, 62, 63, 65, 66, 67, 68, 69, 70, 71, 73, 74, 75, 76, 77, 78, 79, 82, 83, 84, 85

Offset: 1

Gus Wiseman, Mar 06 2019

nonn

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

Also Heinz numbers of the integer partitions enumerated by A064174. The Heinz number of an integer partition (y_1, ..., y_k) is prime(y_1) * ... * prime(y_k).

			The sequence of terms together with their prime indices begins:
   2: {1}
   3: {2}
   5: {3}
   6: {1,2}
   7: {4}
   9: {2,2}
  10: {1,3}
  11: {5}
  13: {6}
  14: {1,4}
  15: {2,3}
  17: {7}
  19: {8}
  20: {1,1,3}
  21: {2,4}
  22: {1,5}
  23: {9}
  25: {3,3}
  26: {1,6}
  28: {1,1,4}

Amiram Eldar, Table of n, a(n) for n = 1..10000

Cf. A001222, A003114, A055396, A056239, A061395, A064174, A106529, A112798.

Cf. A324517, A324519, A324521, A324522, A324560, A324562.

with(numtheory):
q:= n-> is(pi(max(factorset(n)))>=bigomega(n)):
select(q, [$2..100])[];  # Alois P. Heinz, Mar 07 2019

Select[Range[2,100],PrimePi[FactorInteger[#][[-1,1]]]>=PrimeOmega[#]&]

A061395(a(n)) >= A001222(a(n)).

cp's OEIS Frontend

A342096 Number of integer partitions of n with no adjacent parts having quotient >= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A342097 Number of strict integer partitions of n with no adjacent parts having quotient >= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A342095 Number of strict integer partitions of n with no adjacent parts having quotient > 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A168659 Number of partitions of n such that the number of parts is divisible by the greatest part. Also number of partitions of n such that the greatest part is divisible by the number of parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A064173 Number of partitions of n with positive rank.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A025157 Number of partitions of n with distinct parts p(i) such that if i != j, then |p(i) - p(j)| >= 3.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A324521 Numbers > 1 where the maximum prime index is less than or equal to the number of prime factors counted with multiplicity.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple