login
The number of odd partitions of consecutive odd integers.
34

%I #25 Apr 08 2021 08:23:22

%S 1,2,4,8,16,29,52,90,151,248,400,632,985,1512,2291,3431,5084,7456,

%T 10836,15613,22316,31659,44601,62416,86809,120025,165028,225710,

%U 307161,416006,560864,752877,1006426,1340012,1777365,2348821,3093095,4059416,5310255,6924691

%N The number of odd partitions of consecutive odd integers.

%C It seems that these are partitions of odd length and sum, ranked by A340931. The parts do not have to be odd. - _Gus Wiseman_, Apr 06 2021

%H Alois P. Heinz, <a href="/A160786/b160786.txt">Table of n, a(n) for n = 0..5000</a>

%H V. I. Arnold, <a href="http://pauli.uni-muenster.de/~munsteg/arnold.html">On teaching mathematics</a>

%F a(n) = A027193(2n+1).

%e From _Gus Wiseman_, Apr 06 2021: (Start)

%e The a(0) = 1 through a(4) = 16 partitions:

%e (1) (3) (5) (7) (9)

%e (111) (221) (322) (333)

%e (311) (331) (432)

%e (11111) (421) (441)

%e (511) (522)

%e (22111) (531)

%e (31111) (621)

%e (1111111) (711)

%e (22221)

%e (32211)

%e (33111)

%e (42111)

%e (51111)

%e (2211111)

%e (3111111)

%e (111111111)

%e (End)

%p b:= proc(n, i) option remember; `if`(n=0, [1, 0$3],

%p `if`(i<1, [0$4], b(n, i-1)+`if`(i>n, [0$4], (p->

%p `if`(irem(i, 2)=0, [p[3], p[4], p[1], p[2]],

%p [p[2], p[1], p[4], p[3]]))(b(n-i, i)))))

%p end:

%p a:= n-> b(2*n+1$2)[2]:

%p seq(a(n), n=0..40); # _Alois P. Heinz_, Feb 16 2014

%t b[n_, i_] := b[n, i] = If[n==0, {1, 0, 0, 0}, If[i<1, {0, 0, 0, 0}, b[n, i-1] + If[i>n, {0, 0, 0, 0}, Function[{p}, If[Mod[i, 2]==0, p[[{3, 4, 1, 2}]], p[[{2, 1, 4, 3}]]]][b[n-i, i]]]]]; a[n_] := b[2*n+1, 2*n+1][[2]]; Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Jul 01 2015, after _Alois P. Heinz_ *)

%t (* Slow but easy to read *)

%t a[n_] := Length@IntegerPartitions[2 n + 1, {1, 2 n + 1, 2}]

%t a /@ Range[0, 25]

%t (* _Leo C. Stein_, Nov 11 2020 *)

%t (* Faster, don't build the partitions themselves *)

%t (* Number of partitions of n into exactly k parts *)

%t P[0, 0] = 1;

%t P[n_, k_] := 0 /; ((k <= 0) || (n <= 0))

%t P[n_, k_] := P[n, k] = P[n - k, k] + P[n - 1, k - 1]

%t a[n_] := Sum[P[2 n + 1, k], {k, 1, 2 n + 1, 2}]

%t a /@ Range[0, 40]

%t (* _Leo C. Stein_, Nov 11 2020 *)

%o (Python)

%o # Could be memoized for speedup

%o def numoddpart(n, m=1):

%o """The number of partitions of n into an odd number of parts of size at least m"""

%o if n < m:

%o return 0

%o elif n == m:

%o return 1

%o else:

%o # 1 (namely n = n) and all partitions of the form

%o # k + even partitions that start with >= k

%o return 1 + sum([numevenpart(n - k, k) for k in range(m, n//3 + 1)])

%o def numevenpart(n, m=1):

%o """The number of partitions of n into an even number of parts of size at least m"""

%o if n < 2*m:

%o return 0

%o elif n == 2*m:

%o return 1

%o else:

%o return sum([numoddpart(n - k, k) for k in range(m, n//2 + 1)])

%o [numoddpart(n) for n in range(1, 70, 2)]

%o (Python)

%o # dict to memoize

%o ps = {(0,0): 1}

%o def p(n, k):

%o """Number of partitions of n into exactly k parts"""

%o if (n,k) in ps: return ps[(n,k)]

%o if (n<=0) or (k<=0): return 0

%o ps[(n,k)] = p(n-k,k) + p(n-1,k-1)

%o return ps[(n,k)]

%o def a(n): return sum([p(2*n+1, k) for k in range(1,2*n+3,2)])

%o [a(n) for n in range(0,41)]

%o # _Leo C. Stein_, Nov 11 2020

%Y Partitions with all odd parts are counted by A000009 and ranked by A066208.

%Y This is a bisection of A027193 (odd-length partitions), which is ranked by A026424.

%Y The case of all odd parts is counted by A078408 and ranked by A300272.

%Y The even version is A236913, ranked by A340784.

%Y A multiplicative version is A340102.

%Y These partitions are ranked by A340931.

%Y A047993 counts balanced partitions, ranked by A106529.

%Y A058695 counts partitions of odd numbers, ranked by A300063.

%Y A072233 counts partitions by sum and length.

%Y A236914 counts partition of type OO, ranked by A341448.

%Y A340385 counts partitions with odd length and maximum, ranked by A340386.

%Y Cf. A000700, A168659, A200750, A340604, A340607, A340854, A340855.

%K nonn

%O 0,2

%A Utpal Sarkar (doetoe(AT)gmail.com), May 26 2009