| Displaying 1-8 of 8 results found.
page
1
Permutations of partitions listed in A080577 with partition lengths listed in A176208; the table has shape A058884.
+20
3
1, 2, 1, 3, 1, 2, 1, 2, 3, 1, 4, 1, 3, 1, 1, 2, 2, 1, 2, 1, 1, 2, 4, 2, 3, 1, 1, 5, 1, 4, 1, 1, 3, 2, 1, 3, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 3, 4, 2, 5, 2, 4, 1, 2, 3, 2, 2, 3, 1, 1, 1, 6, 1, 5, 1, 1, 4, 2, 1, 4, 1, 1, 1, 3, 3, 1, 3, 2, 1, 1, 3, 1, 1, 1, 1, 2, 2, 2, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1
COMMENTS
The permutations are selected by considering partial sums of A080577: 1
1 2 11
1 2 11 3 21 111
...
then prepending values from A176206 yielding 1
2 11
3 21 12 111
4 31 22 211 13 121 1111
...
Cases appearing in A080577 are excluded from {a(n)}.
EXAMPLE
Triangle begins:
{{1,2}},
{{1,3}, {1,2,1}},
{{2,3}, {1 4}, {1,3,1}, {1,2,2}, {1,2,1,1}},
Or more concisely:
{12},
{13, 121},
{23, 14, 131, 122, 1211},
{24, 231, 15, 141, 132, 1311, 1221, 12111},
...
PROG
(PARI) \\ here R(n) returns n-th row as vector of vectors.
L(n, k)={vecsort([Vecrev(p) | p<-partitions(k), p[#p] > n-k], , 4)}
R(n)={ concat(vector(n-1, k, [concat([n-k], p) | p<-L(n, k)])) }
EXTENSIONS
Offset corrected and a(50) and beyond from Andrew Howroyd, Apr 21 2023
An irregular table with shape sequence A058884 measuring the length of ordered partitions defined by A176207.
+20
2
2, 2, 3, 2, 2, 3, 3, 4, 2, 3, 2, 3, 3, 4, 4, 5, 2, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 5, 4, 5, 6, 2, 3, 2, 3, 3, 4, 3, 4, 5, 2, 3, 3, 4, 3, 4, 5, 4, 4, 5, 6, 5, 6, 7, 2, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 5, 4, 4, 5, 6, 2, 3, 3, 4, 3, 4, 5, 3, 4, 4, 5, 6, 4, 5, 5, 6, 7, 5, 6, 7, 8
EXAMPLE
A058884 begins -1 0 0 1 2 5 8 15 ..., counting
12
13 121
23 14 131 122 1211
...
so triangle T(n,k) begins:
2;
2, 3;
2, 2, 3, 3, 4;
2, 3, 2, 3, 3, 4, 4, 5;
2, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 5, 4, 5, 6;
...
PROG
(PARI)
L(n, k)={vecsort([Vecrev(p) | p<-partitions(k), p[#p] > n-k], , 4)}
row(n)={ concat(vector(n-1, k, [#p + 1 | p<-L(n, k)])) }
a(n) = Sum_{k=0..n} p(k) where p(k) = number of partitions of k ( A000041).
(Formerly M1054 N0396)
+10
435
1, 2, 4, 7, 12, 19, 30, 45, 67, 97, 139, 195, 272, 373, 508, 684, 915, 1212, 1597, 2087, 2714, 3506, 4508, 5763, 7338, 9296, 11732, 14742, 18460, 23025, 28629, 35471, 43820, 53963, 66273, 81156, 99133, 120770, 146785, 177970, 215308, 259891, 313065, 376326, 451501
COMMENTS
Also the total number of all different integers in all partitions of n + 1. E.g., a(3) = 7 because the partitions of 4 comprise the sets {1},{1, 2},{2},{1, 3},{4} of different integers and their total number is 7. - Thomas Wieder, Apr 10 2004 With offset 1, also the number of 1's in all partitions of n. For example, 3 = 2+1 = 1+1+1, a(3) = (zero 1's) + (one 1's) + (three 1's), so a(3) = 4. - Naohiro Nomoto, Jan 09 2002. See the Riordan reference p. 184, last formula, first term, for a proof based on Fine's identity given in Riordan, p. 182 (20). Also, number of partitions of n into parts when there are two kinds of parts of size one.
Also number of graphical forest partitions of 2n+2.
a(n) = count 2 for each partition of n and 1 for each decrement. E.g., the partitions of 4 are 4 (2), 31 (3), 22 (2), 211 (3) and 1111 (2). 2 + 3 + 2 + 3 + 2 = 12. This is related to the Ferrers representation. We can see that taking the Ferrers diagram for each partition of n and adding a new * to all available columns, we generate each partition of n+1, but with repeats ( A058884). - Jon Perry, Feb 06 2004 Also the number of 1-transitions among all integer partitions of n. A 1-transition is the removal of a digit "1" from a partition containing at least one "1" and subsequent addition of that "1" to another digit in that partition. This other digit may be a "1" also, but all digits of equal amount are considered as undistinquishable (unlabeled). E.g., for n=6 one has the partition [1113] for which the following two 1-transitions are possible: [1113] --> [123] and [1113] --> [114]. The 1-transitions of n form a partial order (poset). For n=6 one has 12 1-transitions: [111111] --> [11112], [11112] --> [1113], [11112] --> [1122], [1113] --> [114], [1113] --> [123], [1122] --> [123], [1122] --> [222], [123] --> [33], [123] --> [24], [114] --> [15], [114] --> [24], [15] --> [6]. - Thomas Wieder, Mar 08 2005 Also number of partitions of 2n+1 where one of the parts is greater than n (also where there are more than n parts) and of 2n+2 where one of the parts is greater than n+1 (or with more than n+1 parts). - Henry Bottomley, Aug 01 2005 Also the total number of 1's among all hook-lengths in all partitions of n. E.g., a(4)=7 because hooks of the partitions of n = 4 comprise the multisets {4,3,2,1}, {4,2,1,1}, {3,2,2,1}, {4,1,2,1}, {4,3,2,1} and their total number of 1's is 7. - T. Amdeberhan, Jun 03 2012 With offset 1, a(n) is also the difference between the sum of largest and the sum of second 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 a(0) = 1 and 2*a(n-1) >= a(n) for all n > 0. Hence a(n) is a complete sequence. - Frank M Jackson, Apr 08 2013 a(n) is the number of conjugacy classes in the order-preserving, order-decreasing and (order-preserving and order-decreasing) injective transformation semigroups. - Ugbene Ifeanyichukwu, Jun 03 2015 a(n) is also the number of unlabeled subgraphs of the n-cycle C_n. For example, for n = 3, there are 3 unlabeled subgraphs of the triangle C_3 with 0 edges, 2 with 1 edge, 1 with 2 edges, and 1 with 3 edges (C_3 itself), so a(3) = 3 + 2 + 1 + 1 = 7. - John P. McSorley, Nov 21 2016 a(n) is also the number of partitions of 2n with all parts either even or equal to 1. Proof: the number of such partitions of 2n with exactly 2k 1's is p(n-k), for k = 0,..,n. Summing over k gives the formula. - Leonard Chastkofsky, Jul 24 2018 a(n) is the total number of polygamma functions that appear in the expansion of the (n+1)st derivative of x! with respect to x. More specifically, a(n) is the number of times the string "PolyGamma" appears in the expansion of D[x!, {x, n + 1}] in Mathematica. For example, D[x!, {x, 3 + 1}] = Gamma[1 + x] PolyGamma[0, 1 + x]^4 + 6 Gamma[1 + x] PolyGamma[0, 1 + x]^2 PolyGamma[1, 1 + x] + 3 Gamma[1 + x] PolyGamma[1, 1 + x]^2 + 4 Gamma[1 + x] PolyGamma[0, 1 + x] PolyGamma[2, 1 + x] + Gamma[1 + x] PolyGamma[3, 1 + x], and we see that the string "PolyGamma" appears a total of a(3) = 7 times in this expansion. - John M. Campbell, Aug 11 2018 With offset 1, also the number of integer partitions of 2n that do not comprise the multiset of vertex-degrees of any multigraph (i.e., non-multigraphical partitions); see A209816 for multigraphical partitions. - Gus Wiseman, Oct 26 2018 Also a(n) is the number of partitions of 2n+1 with exactly one odd part.
Delete the odd part 2k+1, k=0, ..., n, to get a partition of 2n-2k into even parts. There are as many unrestricted partitions of n-k; now sum those numbers from 0 to n to get a(n). - George Beck, Jul 22 2019 In the Young's lattice, a(n) is the number of branches that connect the (n-1)-th layer to the n-th layer. - Shouvik Datta, Sep 19 2021 a(n) is the number of multiset partitions of the multiset {r^n, s^1}, equivalently, factorization patterns of any number m=p^n*q^1 where p and q are primes. - Joerg Arndt, Jan 01 2024 a(n) is the number of positive integers whose divisors are the parts of the partitions of n + 1. - Omar E. Pol, Nov 07 2024
REFERENCES
H. Gupta, An asymptotic formula in partitions. J. Indian Math. Soc., (N. S.) 10 (1946), 73-76.
H. Gupta et al., Tables of Partitions. Royal Society Mathematical Tables, Vol. 4, Cambridge Univ. Press, 1958, p. 90.
R. Honsberger, Mathematical Gems III, M.A.A., 1985, p. 6.
D. E. Knuth, The Art of Computer Programming, Vol. 4A, Table A-1, page 778. - N. J. A. Sloane, Dec 30 2018 A. M. Odlyzko, Asymptotic Enumeration Methods, p. 19
J. Riordan, Combinatorial Identities, Wiley, 1968, p. 199.
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).
Stanley, R. P., Exercise 1.26 in Enumerative Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press, p. 59, 1999.
FORMULA
Euler transform of [ 2, 1, 1, 1, 1, 1, 1, ...].
a(n) = (1/n)*Sum_{k=1..n} (sigma(k)+1)*a(n-k), n > 1, a(0) = 1. - Vladeta Jovovic, Aug 22 2002 G.f.: (1/(1 - x))*Product_{m >= 1} 1/(1 - x^m).
Gupta gives the asymptotic result a(n-1) ~ sqrt(6/Pi^2)* sqrt(n)*p(n), where p(n) is the partition function A000041(n). Let P(2,n) denote the set of partitions of n into parts k >= 2.
a(n-2) = Sum_{parts k in all partitions in P(2,n)} phi(k), where phi(k) is the Euler totient function (see A000010). Using this result and Mertens's theorem on the average order of the phi function, leads to the asymptotic result a(n-2) ~ (6/Pi^2)*n*(p(n) - p(n-1)) = (6/Pi^2)* A138880(n) as n -> infinity. (End) a(n) ~ exp(Pi*sqrt(2*n/3)) / (2^(3/2)*Pi*sqrt(n)) * (1 + 11*Pi/(24*sqrt(6*n)) + (73*Pi^2 - 1584)/(6912*n)). - Vaclav Kotesovec, Oct 26 2016 G.f.: exp(Sum_{k>=1} (sigma_1(k) + 1)*x^k/k). - Ilya Gutkovskiy, Aug 21 2018
EXAMPLE
G.f. = 1 + 2*x + 4*x^2 + 7*x^3 + 12*x^4 + 19*x^5 + 30*x^6 + 45*x^7 + 67*x^8 + ...
For n = 5 consider the partitions of n+1:
--------------------------------------
. Number
Partitions of 6 of 1's
--------------------------------------
6 .......................... 0
3 + 3 ...................... 0
4 + 2 ...................... 0
2 + 2 + 2 .................. 0
5 + 1 ...................... 1
3 + 2 + 1 .................. 1
4 + 1 + 1 .................. 2
2 + 2 + 1 + 1 .............. 2
3 + 1 + 1 + 1 .............. 3
2 + 1 + 1 + 1 + 1 .......... 4
1 + 1 + 1 + 1 + 1 + 1 ...... 6
------------------------------------
35-16 = 19
.
The difference between the sum of the first column and the sum of the second column of the set of partitions of 6 is 35 - 16 = 19 and equals the number of 1's in all partitions of 6, so the 6th term of this sequence is a(5) = 19.
(End)
With offset 1, the a(1) = 1 through a(6) = 19 partitions of 2*n whose greatest part is > n:
(2) (4) (6) (8) (A) (C)
(31) (42) (53) (64) (75)
(51) (62) (73) (84)
(411) (71) (82) (93)
(521) (91) (A2)
(611) (622) (B1)
(5111) (631) (732)
(721) (741)
(811) (822)
(6211) (831)
(7111) (921)
(61111) (A11)
(7221)
(7311)
(8211)
(9111)
(72111)
(81111)
(711111)
With offset 1, the a(1) = 1 through a(6) = 19 partitions of 2*n whose number of parts is > n:
(11) (211) (2211) (22211) (222211) (2222211)
(1111) (3111) (32111) (322111) (3222111)
(21111) (41111) (331111) (3321111)
(111111) (221111) (421111) (4221111)
(311111) (511111) (4311111)
(2111111) (2221111) (5211111)
(11111111) (3211111) (6111111)
(4111111) (22221111)
(22111111) (32211111)
(31111111) (33111111)
(211111111) (42111111)
(1111111111) (51111111)
(222111111)
(321111111)
(411111111)
(2211111111)
(3111111111)
(21111111111)
(111111111111)
(End)
The a(5) = 19 multiset partitions of the multiset {1^5, 2^1} are:
1: {{1, 1, 1, 1, 1, 2}}
2: {{1, 1, 1, 1, 1}, {2}}
3: {{1, 1, 1, 1, 2}, {1}}
4: {{1, 1, 1, 1}, {1, 2}}
5: {{1, 1, 1, 1}, {1}, {2}}
6: {{1, 1, 1, 2}, {1, 1}}
7: {{1, 1, 1, 2}, {1}, {1}}
8: {{1, 1, 1}, {1, 1, 2}}
9: {{1, 1, 1}, {1, 1}, {2}}
10: {{1, 1, 1}, {1, 2}, {1}}
11: {{1, 1, 1}, {1}, {1}, {2}}
12: {{1, 1, 2}, {1, 1}, {1}}
13: {{1, 1, 2}, {1}, {1}, {1}}
14: {{1, 1}, {1, 1}, {1, 2}}
15: {{1, 1}, {1, 1}, {1}, {2}}
16: {{1, 1}, {1, 2}, {1}, {1}}
17: {{1, 1}, {1}, {1}, {1}, {2}}
18: {{1, 2}, {1}, {1}, {1}, {1}}
19: {{1}, {1}, {1}, {1}, {1}, {2}}
(End)
MAPLE
with(combinat): a:=n->add(numbpart(j), j=0..n): seq(a(n), n=0..44); # Zerinvary Lajos, Aug 26 2008
MATHEMATICA
CoefficientList[ Series[1/(1 - x)*Product[1/(1 - x^k), {k, 75}], {x, 0, 45}], x] (* Robert G. Wilson v, Jul 13 2004 *) Table[ Count[ Flatten@ IntegerPartitions@ n, 1], {n, 45}] (* Robert G. Wilson v, Aug 06 2008 *) Join[{1}, Accumulate[PartitionsP[Range[50]]]+1] (* _Harvey P. Dale, Mar 12 2013 *)
a[ n_] := SeriesCoefficient[ 1 / (1 - x) / QPochhammer[ x], {x, 0, n}]; (* Michael Somos, Nov 09 2013 *)
PROG
(PARI) {a(n) = if( n<0, 0, polcoeff( 1 / prod(m=1, n, 1 - x^m, 1 + x * O(x^n)) / (1 - x), n))}; /* Michael Somos, Nov 08 2002 */ (PARI) x='x+O('x^66); Vec(1/((1-x)*eta(x))) /* Joerg Arndt, May 15 2011 */ (PARI) a(n) = sum(k=0, n, numbpart(k)); \\ Michel Marcus, Sep 16 2016 (Haskell)
a000070 = p a028310_list where
p _ 0 = 1
p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m
(Sage)
p = [number_of_partitions(n) for n in range(leng)]
return [add(p[:k+1]) for k in range(leng)]
(GAP) List([0..45], n->Sum([0..n], k->NrPartitions(k))); # Muniru A Asiru, Jul 25 2018 (Python)
from itertools import accumulate
def A000070iter(n):
L = [0]*n; L[0] = 1
def numpart(n):
S = 0; J = n-1; k = 2
while 0 <= J:
T = L[J]
S = S+T if (k//2)%2 else S-T
J -= k if (k)%2 else k//2
k += 1
return S
for j in range(1, n): L[j] = numpart(j)
return accumulate(L)
(Python) # Using function A365676Row. Compare also A365675. from itertools import accumulate
def A000070List(size: int) -> list[int]:
return [sum(accumulate(reversed(A365676Row(n)))) for n in range(size)]
CROSSREFS
Cf. A014153, A024786, A026794, A026905, A058884, A093694, A133735, A137633, A010815, A027293, A035363, A028310, A000712, A000990.
Triangle of generalized sum of divisors function, read by rows.
+10
15
1, 2, 1, 2, 2, 3, 5, 2, 1, 6, 4, 2, 11, 2, 5, 13, 4, 10, 17, 3, 1, 15, 22, 4, 2, 25, 27, 2, 5, 37, 29, 6, 10, 52, 37, 2, 20, 67, 44, 4, 1, 30, 97, 44, 4, 2, 52, 117, 55, 5, 5, 77, 154, 59, 2, 10, 117, 184, 68, 6, 20, 162, 235, 71, 2, 36, 227, 277, 81, 6, 1, 58, 309, 338
COMMENTS
Lengths of rows are 1 1 2 2 2 3 3 3 3 4 4 4 4 4 ... ( A003056).
FORMULA
G.f. for k-th diagonal (the k-th row of the sideways triangle shown in the example): Sum_{ m_1 < m_2 < ... < m_k} q^(m_1+m_2+...+m_k)/((1-q^m_1)*(1-q^m_2)*...*(1-q^m_k)) = Sum_n T(n, k)*q^n.
EXAMPLE
Triangle turned on its side begins:
1 2 2 3 2 4 2 4 3 4 2 6 ...
1 2 5 6 11 13 17 22 27 29 ...
1 2 5 10 15 25 37 ...
1 2 5 ...
MAPLE
b:= proc(n, i) option remember; `if`(n=0, 1, `if`(i<1, 0,
expand(b(n, i-1) +x*add(b(n-i*j, i-1), j=1..n/i))))
end:
T:= n->(p->seq(coeff(p, x, degree(p)-k), k=0..degree(p)-1))(b(n$2)):
MATHEMATICA
Reverse /@ Table[Length /@ Split[ Sort[Map[Length, Split /@ IntegerPartitions[n], {1}]]], {n, 24}] (* Wouter Meeussen, Apr 21 2012, updated by Jean-François Alcover, Jan 29 2014 *)
PROG
(Python)
from math import isqrt
from itertools import count, islice
from sympy.utilities.iterables import partitions
def A060177_gen(): # generator of terms return (sum(1 for p in partitions(n) if len(p)==k) for n in count(1) for k in range(isqrt((n<<3)+1)-1>>1, 0, -1))
Expansion of Sum_{n>=1} ((n-1) * q^(n*(n+1)/2) / Product_{k=1..n} (1 - q^k)).
+10
4
0, 0, 0, 1, 1, 2, 4, 5, 7, 10, 15, 18, 25, 31, 41, 53, 66, 81, 103, 125, 154, 190, 229, 276, 333, 399, 475, 568, 673, 794, 938, 1102, 1289, 1512, 1760, 2050, 2384, 2760, 3190, 3687, 4246, 4882, 5609, 6427, 7354, 8412, 9592, 10927, 12439, 14130, 16033, 18177, 20573, 23256, 26271
COMMENTS
Number of up-steps (== number of parts - 1) in all partitions of n into distinct parts (represented as increasing lists), see example. - Joerg Arndt, Sep 03 2014
EXAMPLE
a(8) = 7 because in the 6 partitions of 8 into distinct parts
1: [ 1 2 5 ]
2: [ 1 3 4 ]
3: [ 1 7 ]
4: [ 2 6 ]
5: [ 3 5 ]
6: [ 8 ]
there are 2+2+1+1+1+0 = 7 up-steps. - Joerg Arndt, Sep 03 2014
MAPLE
b:= proc(n, i) option remember; `if`(n=0, [1, 0], `if`(i<1, 0,
b(n, i-1)+`if`(i>n, 0, (p->p+[0, p[1]])(b(n-i, i-1)))))
end:
a:= n-> `if`(n=0, 0, (p-> p[2]-p[1])(b(n$2))):
MATHEMATICA
max=80; s=Sum[(n-1)*q^(n*(n+1)/2)/QPochhammer[q, q, n], {n, Sqrt[max+1]}]+ O[q]^max; CoefficientList[s, q] (* Jean-François Alcover, Jan 17 2016 *)
PROG
(PARI)
N=66; q='q+O('q^N);
gf=sum(n=1, N, (n-1)*q^(n*(n+1)/2) / prod(k=1, n, 1-q^k ) );
v=Vec(gf+'a0); v[1]-='a0; v /* include initial zeros */
CROSSREFS
Cf. A015723, Sum_{n>=0} (n * q^(n*(n+1)/2) / Product_{k=1..n} (1 - q^k)). Cf. A032020, Sum_{n>=0} (n! * q^(n*(n+1)/2) / Product_{k=1..n} (1 - q^k)). Cf. A032153, Sum_{n>=1} ((n-1)! * q^(n*(n+1)/2) / Product_{k=1..n} (1 - q^k)). Cf. A072576, Sum_{n>=0} ((n+1)! * q^(n*(n+1)/2) / Product_{k=1..n} (1 - q^k)). Cf. A058884 (up-steps in all partitions).
Number of multisets occurring as the peak heights multiset of a Dyck n-path.
+10
3
1, 1, 2, 4, 9, 20, 45, 98, 211, 445, 927, 1909, 3901, 7920, 16011, 32260, 64852, 130157, 260932, 522691, 1046489, 2094438, 4190798, 8384100, 16771453, 33547094, 67099568, 134205996, 268420714, 536852452, 1073718799, 2147455019, 4294931825, 8589890772
COMMENTS
We use the definition given by Callan and Deutsch (see reference). A Dyck n-path is a lattice path of n upsteps U (changing by (1,1)) and n downsteps D (changing by (1,-1)) that starts at the origin and never goes below the x-axis. A peak is an occurrence of U D and the peak height is the y-coordinate of the vertex between its U and D.
Also the number of nonempty multisets S of positive integers satisfying max(S) + |S| - 1 <= n <= sum(S).
FORMULA
G.f.: 1/(1-2*x) - (x/(1-x)) * Product_{m>=1} 1/(1-x^m).
EXAMPLE
For n=2 the possibilities are UDUD, UUDD giving us multisets of {1,1} and {2} respectively. There are two distinct multisets so a(2) = 2.
MAPLE
a:= proc(n) a(n):= `if`(n=0, 1, a(n-1)+2^(n-1)-combinat[numbpart](n-1)) end:
MATHEMATICA
Table[2^(n) - Sum[PartitionsP[k], {k, 0, n - 1}], {n, 1, 40}]
PROG
(Python)
#Returns all possible peak heights multisets
def peakheightsmultisets(n):
.#Making all possible paths
.allpaths=list()
.combinst=itertools.combinations(range(2*n), n)
.for tup in combinst:
..a=[]
..for i in range(2*n):
...if i in tup:
....a.append(1)
...else:
....a.append(-1)
..allpaths.append(tuple(a))
.#Now we take Dyck paths and form multisets as we go
.output=set()
.for x in allpaths:
..include=True
..peaklist=[]
..total=0
..for unit in x:
...if unit==-1 and lastunit==1:
....peaklist.append(total)
...total+=unit
...if total < 0:
....include=False
....break
...lastunit=unit
..if include:
...output.add(tuple(sorted(peaklist)))
.return output
(Python)
#Using peakheightsmultisets(n)
def a(n):
.return len(peakheightsmultisets(n))
Irregular triangle read by rows: T(n,k) = number of compositions of n with k inversions (n >= 0, 0 <= k <= floor(n^2/8)).
+10
2
1, 1, 2, 3, 1, 5, 2, 1, 7, 5, 3, 1, 11, 8, 7, 4, 2, 15, 15, 14, 10, 6, 3, 1, 22, 23, 26, 21, 17, 10, 6, 2, 1, 30, 37, 44, 42, 36, 27, 19, 11, 6, 3, 1, 42, 55, 73, 74, 73, 60, 50, 34, 24, 13, 8, 4, 2, 56, 83, 115, 128, 133, 123, 109, 87, 68, 48, 32, 20, 12, 6, 3, 1, 77, 118, 177, 209, 235, 230, 223, 192, 166, 129, 100, 70, 51, 31, 20, 11, 6, 2, 1
COMMENTS
Row sums are powers of 2.
The Heubach et al. reference has a table for n <= 12.
EXAMPLE
T(4,0) = 5: [4], [1,3], [2,2], [1,1,2], [1,1,1,1] - all partitions of 4.
T(5,2) = 3: [2,2,1], [3,1,1], [1,2,1,1].
T(6,4) = 2: [2,2,1,1], [2,1,1,1,1].
Triangle begins:
1
1
2
3 1
5 2 1
7 5 3 1
11 8 7 4 2
15 15 14 10 6 3 1
22 23 26 21 17 10 6 2 1
...
MAPLE
T:= proc(n) option remember; local b, p;
b:=proc(m, i, l)
if m=0 then p(i):= p(i)+1
else seq(b(m-h, i+nops(select(j->j<h, l)), [h, l[]]), h=1..m)
fi
end;
p:= proc() 0 end; forget(p);
b(n, 0, []); seq(p(i), i=0..floor(n^2/8))
end:
MATHEMATICA
T[n_] := T[n] = Module[{b, p}, b[m_, i_, l_List] := If[m == 0, p[i] = p[i] + 1, Table[b[m-h, i+Length[Select[ l, #<h&]], Join[{h}, l]], {h, 1, m}]]; Clear[p]; p[_]=0; b[n, 0, {}]; Table[p[i], {i, 0, Floor[n^2/8]}]]; Table[ T[n], {n, 0, 12}] // Flatten (* Jean-François Alcover, Jan 17 2016, after Alois P. Heinz *)
Irregular triangle read by rows: T(n, {j,k}) is the number of partitions of n that have exactly j parts equal to k; 1 <= j <= n, 1 <= k <= n.
+10
1
1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 2, 1, 1, 0, 1, 2, 1, 0, 0, 0, 2, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 2, 2, 1, 1, 0, 1, 3, 1, 1, 0, 0, 0, 2, 1, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 4, 2, 2, 1, 1, 0, 1, 4, 2, 1, 0, 0, 0, 0, 4, 1, 0, 0, 0, 0, 0, 3, 0
COMMENTS
If superfluous zeros are removed from the right side of each row, the row lengths = 1,2,1,3,1,1,4,2,... = A010766. Sum of each N X N block of rows = 1,2,4,7,12,19,... = A000070. The sum of the partitions of n that are over-counted in each block of N x N rows = A000070(n) - A000041(n) = A058884(n), n >= 1. Concatenation of first row from each N X N block = A116598. As noted by Joerg Arndt in A116598, the first row from each N X N block in reverse converges to A002865. Two sequences emerge from alternating second rows in reverse: for 2n, converges to even-indexed terms in A027336, and for 2n+1, converges to odd-indexed terms in A027336. Counting the rows in each N X N block where columns j=2 > 0 and j=3 through j=n are all zeros produces A008615(n), n > 0.
EXAMPLE
\ j 1 2 3 4 5
k
n
1: 1 1
2: 1 0 1
2 1 0
3: 1 1 0 1
2 1 0 0
3 1 0 0
4: 1 1 1 0 1
2 1 1 0 0
3 1 0 0 0
4 1 0 0 0
5: 1 2 1 1 0 1
2 2 1 0 0 0
3 2 0 0 0 0
4 1 0 0 0 0
5 1 0 0 0 0
.
.
.
MATHEMATICA
Array[With[{s = IntegerPartitions[#]}, Table[Count[Map[Count[#, k] &, s], j], {k, #}, {j, #}]] &, 7] // Flatten (* Michael De Vlieger, Feb 28 2018 *)
PROG
(Python) # See Stauduhar link.
Search completed in 0.012 seconds
|