|
|
A024786
|
|
Number of 2's in all partitions of n.
|
|
42
|
|
|
0, 1, 1, 3, 4, 8, 11, 19, 26, 41, 56, 83, 112, 160, 213, 295, 389, 526, 686, 911, 1176, 1538, 1968, 2540, 3223, 4115, 5181, 6551, 8191, 10269, 12756, 15873, 19598, 24222, 29741, 36532, 44624, 54509, 66261, 80524, 97446, 117862, 142029, 171036, 205290, 246211
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,4
|
|
COMMENTS
|
Also number of partitions of n-1 with a distinguished part different from all the others. [Comment corrected by Emeric Deutsch, Aug 13 2008]
In general the number of times that j appears in the partitions of n equals Sum_{k<n, k = n (mod j)} P(k). In particular this gives a formula for a(n), A024787, ..., A024794, for j = 2,...,10; it generalizes the formula given for A000070 for j=1. - Jose Luis Arregui (arregui(AT)posta.unizar.es), Apr 05 2002
a(n) is also the difference between the sum of second largest and the sum of third largest elements in all partitions of n. More generally, the number of occurrences of k in all partitions of n equals the difference between the sum of k-th largest and the sum of (k+1)st largest elements in all partitions of n. And more generally, the sum of the number of occurrences of k, k+1, k+2..k+m in all partitions of n equals the difference between the sum of k-th largest and the sum of (k+m+1)st largest elements in all partitions of n. - Omar E. Pol, Oct 25 2012
Number of singletons in all partitions of n-1. A singleton in a partition is a part that occurs exactly once. Example: a(5) = 4 because in the partitions of 4, namely [1,1,1,1], [1,1,2'], [2,2], [1',3'], [4'] we have 4 singletons (marked by '). - Emeric Deutsch, Sep 12 2016
a(n) is also the number of non-isomorphic vertex-transitive cover graphs of lattice quotients of essential lattice congruences of the weak order on the symmetric group S_{n-1}. See Table 1 in the Hoang/Mütze reference in the Links section. - Torsten Muetze, Nov 28 2019
Assuming a partition is in weakly decreasing order, a(n) is also the number of times -1 occurs in the differences of the partitions of n+1. - George Beck, Mar 28 2023
|
|
REFERENCES
|
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 184.
|
|
LINKS
|
|
|
FORMULA
|
a(n) = Sum_{k<n, k = n (mod 2)} P(k), P(k) = number of partitions of k as in A000041, P(0) = 1. - Jose Luis Arregui (arregui(AT)posta.unizar.es), Apr 05 2002
G.f.: x^2/((1-x)*(1-x^2)^2))*Product_{j>=3} 1/(1-x^j) from Riordan reference second term, last eq.
a(n) ~ exp(Pi*sqrt(2*n/3)) / (2^(5/2) * Pi * sqrt(n)) * (1 - 25*Pi/(24*sqrt(6*n)) + (25/48 + 433*Pi^2/6912)/n). - Vaclav Kotesovec, Mar 07 2016, extended Nov 05 2016
G.f.: x^2/((1 - x)*(1 - x^2)) * Sum_{n >= 0} x^(2*n)/( Product_{k = 1..n} 1 - x^k ); that is, convolution of A004526 (partitions into 2 parts, or, modulo offset differences, partitions into parts <= 2) and A002865 (partitions into parts >= 2). - Peter Bala, Jan 17 2021
|
|
EXAMPLE
|
For n = 7 we have:
--------------------------------------
. Number
Partitions of 7 of 2's
--------------------------------------
7 .............................. 0
4 + 3 .......................... 0
5 + 2 .......................... 1
3 + 2 + 2 ...................... 2
6 + 1 .......................... 0
3 + 3 + 1 ...................... 0
4 + 2 + 1 ...................... 1
2 + 2 + 2 + 1 .................. 3
5 + 1 + 1 ...................... 0
3 + 2 + 1 + 1 .................. 1
4 + 1 + 1 + 1 .................. 0
2 + 2 + 1 + 1 + 1 .............. 2
3 + 1 + 1 + 1 + 1 .............. 0
2 + 1 + 1 + 1 + 1 + 1 .......... 1
1 + 1 + 1 + 1 + 1 + 1 + 1 ...... 0
------------------------------------
. 24 - 13 = 11
.
The difference between the sum of the second column and the sum of the third column of the set of partitions of 7 is 24 - 13 = 11 and equals the number of 2's in all partitions of 7, so a(7) = 11.
(End)
|
|
MAPLE
|
b:= proc(n, i) option remember; local f, g;
if n=0 or i=1 then [1, 0]
else f:= b(n, i-1); g:= `if`(i>n, [0$2], b(n-i, i));
[f[1]+g[1], f[2]+g[2]+`if`(i=2, g[1], 0)]
fi
end:
a:= n-> b(n, n)[2]:
|
|
MATHEMATICA
|
Table[ Count[ Flatten[ IntegerPartitions[n]], 2], {n, 1, 50} ]
(* Second program: *)
b[n_, i_] := b[n, i] = Module[{f, g}, If[n==0 || i==1, {1, 0}, f = b[n, i - 1]; g = If[i>n, {0, 0}, b[n-i, i]]; {f[[1]] + g[[1]], f[[2]] + g[[2]] + If[i == 2, g[[1]], 0]}]]; a[n_] := b[n, n][[2]]; Table[a[n], {n, 1, 50}] (* Jean-François Alcover, Sep 22 2015, after Alois P. Heinz *)
Table[Sum[(1 + (-1)^k)/2 * PartitionsP[n-k], {k, 2, n}], {n, 1, 50}] (* Vaclav Kotesovec, Aug 27 2017 *)
|
|
PROG
|
(Python)
from sympy import npartitions
def A024786(n): return sum(npartitions(n-(k<<1)) for k in range(1, (n>>1)+1)) # Chai Wah Wu, Oct 25 2023
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|