Search: a028310 -id:a028310
|
|
|
|
1, 2, 5, 12, 28, 65, 151, 351, 816, 1897, 4410, 10252, 23833, 55405, 128801, 299426, 696081, 1618192, 3761840, 8745217, 20330163, 47261895, 109870576, 255418101, 593775046, 1380359512, 3208946545, 7459895657, 17342153393, 40315615410, 93722435101
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (1 - x + x^2) / (1 - 3*x + 2*x^2 - x^3).
G.f.: 1 / (1 - 2*x / (1 - x / (2 + x / (1 - 2*x / (1 + x))))).
a(n) = 3*a(n-1) + 2*a(n-2) - a(n-3).
a(n) satisfies 1 = f(a(n-2), a(n-1), a(n)) where f(u, v, w) = u^3 - 5*v^3 + w^3 + u*v * (7*v -4*u) + u*w * (3*u + 2*w) + v*w * (11*v - 6*w) - 9*u*v*w.
|
|
EXAMPLE
|
G.f. = 1 + 2*x + 5*x^2 + 12*x^3 + 28*x^4 + 65*x^5 + 151*x^6 + 351*x^7 + 816*x^8 + ...
|
|
MATHEMATICA
|
CoefficientList[Series[(1-x+x^2)/(1-3*x+2*x^2-x^3), {x, 0, 50}], x] (* G. C. Greubel, Aug 12 2018 *)
|
|
PROG
|
(PARI) {a(n) = if( n<0, n = -1-n; polcoeff( (1 - x + x^2) / (1 - 2*x + 3*x^2 - x^3) + x * O(x^n), n), polcoeff( (1 - x + x^2) / (1 - 3*x + 2*x^2 - x^3) + x * O(x^n), n))}
(PARI) x='x+O('x^50); Vec((1-x+x^2)/(1-3*x+2*x^2-x^3)) \\ G. C. Greubel, Aug 12 2018
(Magma) m:=25; R<x>:=PowerSeriesRing(Integers(), m); Coefficients(R!((1-x+x^2)/(1-3*x+2*x^2-x^3))); // G. C. Greubel, Aug 12 2018
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
|
|
1, -1, 0, 2, -2, -5, 14, 5, -72, 68, 278, -726, -520, 4691, -3514, -21758, 50374, 56185, -374566, 194596, 1962618, -3956504, -6258320, 33057877, -8974630, -190822072, 330170022, 710487590, -3088268200, 18008739, 19398384974, -28292606291, -81631282280, 298546543220, 84094857302, -2028216574806, 2428288153424, 9450205225145
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
LINKS
|
|
|
FORMULA
|
Given g.f. A(x) then B(x) = x * A(x) satisfies B(x) = (1 - B(x)) * (x + B(x) * (B(x) - x)). - Michael Somos, Apr 05 2012
Conjecture: 6*n*(n+1)*a(n) -n*(n-14)*a(n-1) +2*n*(14*n-19)*a(n-2) -4*(n-2)*(17*n-48)*a(n-3) +6*(2*n-5)*(n-4)*a(n-4)=0. - R. J. Mathar, Nov 15 2012
Recurrence (of order 3): 3*n*(n+1)*(19*n-27)*a(n) = -2*n*(38*n^2 - 73*n + 9)*a(n-1) - 20*(19*n^3 - 65*n^2 + 66*n - 18)*a(n-2) + 2*(n-3)*(2*n-3)*(19*n-8)*a(n-3). - Vaclav Kotesovec, Jan 22 2014
Lim sup n->infinity |a(n)|^(1/n) = sqrt(20/9 + 1/27*(272376 - 12312 * sqrt(57))^(1/3) + 2/9*(1261 + 57 * sqrt(57))^(1/3)) = 2.637962913244886521522... - Vaclav Kotesovec, Jan 22 2014
|
|
EXAMPLE
|
1 - x + 2*x^3 - 2*x^4 - 5*x^5 + 14*x^6 + 5*x^7 - 72*x^8 + 68*x^9 + ...
|
|
MATHEMATICA
|
CoefficientList[1/x*InverseSeries[Series[x*(1-x+x^2) /(1-x)^2, {x, 0, 20}], x], x] (* Vaclav Kotesovec, Jan 22 2014 *)
|
|
PROG
|
(PARI) {a(n) = if( n<0, 0, polcoeff( serreverse( x * ((1 - x + x^2) / (1 - x)^2 + x * O(x^n))) / x, n))} /* Michael Somos, Apr 05 2012 */
(PARI) {a(n) = local(B); if( n<0, 0, B = O(x); for( k=0, n, B = (1 - B) * (x + B * (B - x))); polcoeff( B / x, n))} /* Michael Somos, Apr 05 2012 */
|
|
CROSSREFS
|
|
|
KEYWORD
|
sign,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A342385
|
|
Triangle T(n,k) read by rows (n >= 0, 0 <= k <= n): first column is A001477 and column k > 0 is k*A028310.
|
|
+20
1
|
|
|
0, 1, 1, 2, 1, 2, 3, 2, 2, 3, 4, 3, 4, 3, 4, 5, 4, 6, 6, 4, 5, 6, 5, 8, 9, 8, 5, 6, 7, 6, 10, 12, 12, 10, 6, 7, 8, 7, 12, 15, 16, 15, 12, 7, 8, 9, 8, 14, 18, 20, 20, 18, 14, 8, 9, 10, 9, 16, 21, 24, 25, 24, 21, 16, 9, 10, 11, 10, 18, 24, 28, 30, 30, 28, 24, 18, 10, 11
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
A000290(n) is a subsequence via (2*n+1)-th rows.
|
|
LINKS
|
|
|
FORMULA
|
T(n,0) = T(n,n) = n.
T(n,k) = k*(n-k), for 0 < k < n. (End)
|
|
EXAMPLE
|
Triangle begins:
n\k| 0 1 2 3 4 5 6 7 8 9 ...
---+-------------------------------------------
0 | 0;
1 | 1, 1;
2 | 2, 1, 2;
3 | 3, 2, 2, 3;
4 | 4, 3, 4, 3, 4;
5 | 5, 4, 6, 6, 4, 5;
6 | 6, 5, 8, 9, 8, 5, 6;
7 | 7, 6, 10, 12, 12, 10, 6, 7;
8 | 8, 7, 12, 15, 16, 15, 12, 7, 8;
9 | 9, 8, 14, 18, 20, 20, 18, 14, 8, 9;
...
|
|
MATHEMATICA
|
With[{rowmax=10}, Table[If[0<k<n, k(n-k), n], {n, 0, rowmax}, {k, 0, n}]] (* Paolo Xausa, Nov 15 2023 *)
|
|
CROSSREFS
|
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A000070
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
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
|
|
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.
|
|
LINKS
|
|
|
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.
|
|
KEYWORD
|
nonn,easy,nice
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A000124
|
|
Central polygonal numbers (the Lazy Caterer's sequence): n(n+1)/2 + 1; or, maximal number of pieces formed when slicing a pancake with n cuts.
(Formerly M1041 N0391)
|
|
+10
426
|
|
|
1, 2, 4, 7, 11, 16, 22, 29, 37, 46, 56, 67, 79, 92, 106, 121, 137, 154, 172, 191, 211, 232, 254, 277, 301, 326, 352, 379, 407, 436, 466, 497, 529, 562, 596, 631, 667, 704, 742, 781, 821, 862, 904, 947, 991, 1036, 1082, 1129, 1177, 1226, 1276, 1327, 1379
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
These are Hogben's central polygonal numbers with the (two-dimensional) symbol
2
.P
1 n
The first line cuts the pancake into 2 pieces. For n > 1, the n-th line crosses every earlier line (avoids parallelism) and also avoids every previous line intersection, thus increasing the number of pieces by n. For 16 lines, for example, the number of pieces is 2 + 2 + 3 + 4 + 5 + ... + 16 = 137. These are the triangular numbers plus 1 (cf. A000217).
m = (n-1)(n-2)/2 + 1 is also the smallest number of edges such that all graphs with n nodes and m edges are connected. - Keith Briggs, May 14 2004
Also maximal number of grandchildren of a binary vector of length n+2. E.g., a binary vector of length 6 can produce at most 11 different vectors when 2 bits are deleted.
This is also the order dimension of the (strong) Bruhat order on the finite Coxeter group B_{n+1}. - Nathan Reading (reading(AT)math.umn.edu), Mar 07 2002
Number of 132- and 321-avoiding permutations of {1,2,...,n+1}. - Emeric Deutsch, Mar 14 2002
For n >= 1 a(n) is the number of terms in the expansion of (x+y)*(x^2+y^2)*(x^3+y^3)*...*(x^n+y^n). - Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 28 2003
Also the number of terms in (1)(x+1)(x^2+x+1)...(x^n+...+x+1); see A000140.
Narayana transform (analog of the binomial transform) of vector [1, 1, 0, 0, 0, ...] = A000124; using the infinite lower Narayana triangle of A001263 (as a matrix), N; then N * [1, 1, 0, 0, 0, ...] = A000124. - Gary W. Adamson, Apr 28 2005
Number of interval subsets of {1, 2, 3, ..., n} (cf. A002662). - Jose Luis Arregui (arregui(AT)unizar.es), Jun 27 2006
Define a number of straight lines in the plane to be in general arrangement when (1) no two lines are parallel, (2) there is no point common to three lines. Then these are the maximal numbers of regions defined by n straight lines in general arrangement in the plane. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
Note that a(n) = a(n-1) + A000027(n-1). This has the following geometrical interpretation: Suppose there are already n-1 lines in general arrangement, thus defining the maximal number of regions in the plane obtainable by n-1 lines and now one more line is added in general arrangement. Then it will cut each of the n-1 lines and acquire intersection points which are in general arrangement. (See the comments on A000027 for general arrangement with points.) These points on the new line define the maximal number of regions in 1-space definable by n-1 points, hence this is A000027(n-1), where for A000027 an offset of 0 is assumed, that is, A000027(n-1) = (n+1)-1 = n. Each of these regions acts as a dividing wall, thereby creating as many new regions in addition to the a(n-1) regions already there, hence a(n) = a(n-1) + A000027(n-1). Cf. the comments on A000125 for an analogous interpretation. - Peter C. Heinig (algorithms(AT)gmx.de), Oct 19 2006
When constructing a zonohedron, one zone at a time, out of (up to) 3-d non-intersecting parallelepipeds, the n-th element of this sequence is the number of edges in the n-th zone added with the n-th "layer" of parallelepipeds. (Verified up to 10-zone zonohedron, the enneacontahedron.) E.g., adding the 10th zone to the enneacontahedron requires 46 parallel edges (edges in the 10th zone) by looking directly at a 5-valence vertex and counting visible vertices. - Shel Kaphan, Feb 16 2006
Binomial transform of (1, 1, 1, 0, 0, 0, ...) and inverse binomial transform of A072863: (1, 3, 9, 26, 72, 192, ...). - Gary W. Adamson, Oct 15 2007
If Y is a 2-subset of an n-set X then, for n >= 3, a(n-3) is the number of (n-2)-subsets of X which do not have exactly one element in common with Y. - Milan Janjic, Dec 28 2007
It appears that a(n) is the number of distinct values among the fractions F(i+1)/F(j+1) as j ranges from 1 to n and, for each fixed j, i ranges from 1 to j, where F(i) denotes the i-th Fibonacci number. - John W. Layman, Dec 02 2008
a(n) is the number of subsets of {1,2,...,n} that contain at most two elements. - Geoffrey Critzer, Mar 10 2009
For n >= 2, a(n) gives the number of sets of subsets A_1, A_2, ..., A_n of n = {1, 2, ..., n} such that Meet_{i = 1..n} A_i is empty and Sum_{j in [n]} (|Meet{i = 1..n, i != j} A_i|) is a maximum. - Srikanth K S, Oct 22 2009
The numbers along the left edge of Floyd's triangle. - Paul Muljadi, Jan 25 2010
Let A be the Hessenberg matrix of order n, defined by: A[1,j] = A[i,i]:=1, A[i,i-1] = -1, and A[i,j] = 0 otherwise. Then, for n >= 1, a(n-1) = (-1)^(n-1)*coeff(charpoly(A,x),x). - Milan Janjic, Jan 24 2010
Also the number of deck entries of Euler's ship. See the Meijer-Nepveu link. - Johannes W. Meijer, Jun 21 2010
(1 + x^2 + x^3 + x^4 + x^5 + ...)*(1 + 2x + 3x^2 + 4x^3 + 5x^4 + ...) = (1 + 2x + 4x^2 + 7x^3 + 11x^4 + ...). - Gary W. Adamson, Jul 27 2010
The number of length n binary words that have no 0-digits between any pair of consecutive 1-digits. - Jeffrey Liese, Dec 23 2010
Let b(0) = b(1) = 1; b(n) = max(b(n-1)+n-1, b(n-2)+n-2) then a(n) = b(n+1). - Yalcin Aktar, Jul 28 2011
Also number of distinct sums of 1 through n where each of those can be + or -. E.g., {1+2,1-2,-1+2,-1-2} = {3,-1,1,-3} and a(2) = 4. - Toby Gottfried, Nov 17 2011
This sequence is complete because the sum of the first n terms is always greater than or equal to a(n+1)-1. Consequently, any nonnegative number can be written as a sum of distinct terms of this sequence. See A204009, A072638. - Frank M Jackson, Jan 09 2012
The sequence is the number of distinct sums of subsets of the nonnegative integers, and its first differences are the positive integers. See A208531 for similar results for the squares. - John W. Layman, Feb 28 2012
Apparently the number of Dyck paths of semilength n+1 in which the sum of the first and second ascents add to n+1. - David Scambler, Apr 22 2013
Without 1 and 2, a(n) equals the terminus of the n-th partial sum of sequence 1, 1, 2. Explanation: 1st partial sums of 1, 1, 2 are 1, 2, 4; 2nd partial sums are 1, 3, 7; 3rd partial sums are 1, 4, 11; 4th partial sums are 1, 5, 16, etc. - Bob Selcoe, Jul 04 2013
Equivalently, numbers of the form 2*m^2+m+1, where m = 0, -1, 1, -2, 2, -3, 3, ... . - Bruno Berselli, Apr 08 2014
For n >= 2: quasi-triangular numbers; the almost-triangular numbers being A000096(n), n >= 2. Note that 2 is simultaneously almost-triangular and quasi-triangular. - Daniel Forgues, Apr 21 2015
n points in general position determine "n choose 2" lines, so A055503(n) <= a(n(n-1)/2). If n > 3, the lines are not in general position and so A055503(n) < a(n(n-1)/2). - Jonathan Sondow, Dec 01 2015
The digital root is period 9 (1, 2, 4, 7, 2, 7, 4, 2, 1), also the digital roots of centered 10-gonal numbers (A062786), for n > 0, A133292. - Peter M. Chema, Sep 15 2016
For n >= 0, a(n) is the number of weakly unimodal sequences of length n over the alphabet {1, 2}. - Armend Shabani, Mar 10 2017
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) < e(j) != e(k). [Martinez and Savage, 2.4]
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) < e(j) and e(i) < e(k). [Martinez and Savage, 2.4]
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) >= e(j) != e(k). [Martinez and Savage, 2.4]
(End)
The odd prime factors != 7 occur in an interval of p successive terms either never or exactly twice, while 7 always occurs only once. If a prime factor p appears in a(n) and a(m) within such an interval, then n + m == -1 (mod p). When 7 divides a(n), then 2*n == -1 (mod 7). a(n) is never divisible by the prime numbers given in A003625.
While all prime factors p != 7 can occur to any power, a(n) is never divisible by 7^2. The prime factors are given in A045373. The prime terms of this sequence are given in A055469.
(End)
a(n-1) is the greatest sum of arch lengths for the top arches of a semi-meander with n arches. An arch length is the number of arches covered + 1.
/\ The top arch has a length of 3. /\ The top arch has a length of 3.
/ \ Both bottom arches have a //\\ The middle arch has a length of 2.
//\/\\ length of 1. ///\\\ The bottom arch has a length of 1.
Example: for n = 4, a(4-1) = a(3) = 7 /\
//\\
/\ ///\\\ 1 + 3 + 2 + 1 = 7. (End)
a(n+1) is the a(n)-th smallest positive integer that has not yet appeared in the sequence. - Matthew Malone, Aug 26 2021
For n> 0, let the n-dimensional cube {0,1}^n be, provided with the Hamming distance, d. Given an element x in {0,1}^n, a(n) is the number of elements y in {0,1}^n such that d(x, y) <= 2. Example: n = 4. (0,0,0,0), (1,0,0,0), (0,1,0,0), (0,0,1,0), (0,0,0,1), (0,0,1,1), (0,1,0,1), (0,1,1,0), (1,0,0,1), (1,0,1,0), (1,1,0,0) are at distance <= 2 from (0,0,0,0), so a(4) = 11. - Yosu Yurramendi, Dec 10 2021
a(n) is the sum of the first three entries of row n of Pascal's triangle. - Daniel T. Martin, Apr 13 2022
a(n-1) is the number of Grassmannian permutations that avoid a pattern, sigma, where sigma is a pattern of size 3 with exactly one descent. For example, sigma is one of the patterns, {132, 213, 231, 312}. - Jessica A. Tomasko, Sep 14 2022
a(n+4) is the number of ways to tile an equilateral triangle of side length 2*n with smaller equilateral triangles of side length n and side length 1. For example, with n=2, there are 22 ways to tile an equilateral triangle of side length 4 with smaller ones of sides 2 and 1, including the one tiling with sixteen triangles of sides 1 and the one tiling with four triangles of sides 2. - Ahmed ElKhatib and Greg Dresden, Aug 19 2024
|
|
REFERENCES
|
Robert B. Banks, Slicing Pizzas, Racing Turtles and Further Adventures in Applied Mathematics, Princeton Univ. Press, 1999. See p. 24.
Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 72, Problem 2.
Henry Ernest Dudeney, Amusements in Mathematics, Nelson, London, 1917, page 177.
Derrick Niederman, Number Freak, From 1 to 200 The Hidden Language of Numbers Revealed, A Perigee Book, NY, 2009, p. 83.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
Alain M. Robert, A Course in p-adic Analysis, Springer-Verlag, 2000; p. 213.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane, On single-deletion-correcting codes, in Codes and Designs (Columbus, OH, 2000), 273-291, Ohio State Univ. Math. Res. Inst. Publ., 10, de Gruyter, Berlin, 2002.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
David Wells, The Penguin Dictionary of Curious and Interesting Numbers. Penguin Books, NY, 1986, Revised edition 1987. See p. 98.
William Allen Whitworth, DCC Exercises in Choice and Chance, Stechert, NY, 1945, p. 30.
Akiva M. Yaglom and Isaak M. Yaglom, Challenging Mathematical Problems with Elementary Solutions. Vol. I. Combinatorial Analysis and Probability Theory. New York: Dover Publications, Inc., 1987, p. 13, #44 (First published: San Francisco: Holden-Day, Inc., 1964).
|
|
LINKS
|
M. F. Hasler, Interactive illustration of A000124. [Sep 06 2017: The user can choose the slices to make, but the program can suggest a set of n slices which should yield the maximum number of pieces. For n slices this obviously requires 2n endpoints, or 2n+1 if they are equally spaced, so if there are not enough "blobs", their number is accordingly increased. This is the distinction between "draw" (done when you change the slices or number of blobs by hand) and "suggest" (propose a new set of slices).]
Rodica Simion and Frank W. Schmidt, Restricted permutations, European J. Combin., 6, 383-406, 1985; see Example 3.5.
|
|
FORMULA
|
G.f.: (1 - x + x^2)/(1 - x)^3. - Simon Plouffe in his 1992 dissertation
G.f.: (1 - x^6)/((1 - x)^2*(1 - x^2)*(1 - x^3)). a(n) = a(-1 - n) for all n in Z. - Michael Somos, Sep 04 2006
Euler transform of length 6 sequence [ 2, 1, 1, 0, 0, -1]. - Michael Somos, Sep 04 2006
a(n+3) = 3*a(n+2) - 3*a(n+1) + a(n) and a(1) = 1, a(2) = 2, a(3) = 4. - Artur Jasinski, Oct 21 2008
a(n) = a(n-1) + n. E.g.f.:(1 + x + x^2/2)*exp(x). - Geoffrey Critzer, Mar 10 2009
a(n) = Sum_{k = 0..n + 1} binomial(n+1, 2(k - n)). - Paul Barry, Aug 29 2004
a(n) = binomial(n+2, 1) - 2*binomial(n+1, 1) + binomial(n+2, 2). - Zerinvary Lajos, May 12 2006
a(n) = Sum_{l_1 = 0..n + 1} Sum_{l_2 = 0..n}...Sum_{l_i = 0..n - i}...Sum_{l_n = 0..1} delta(l_1, l_2, ..., l_i, ..., l_n) where delta(l_1, l_2, ..., l_i, ..., l_n) = 0 if any l_i != l_(i+1) and l_(i+1) != 0 and delta(l_1, l_2, ..., l_i, ..., l_n) = 1 otherwise. (End)
a(n) = 2*a(n-1) - a(n-2) + 1. - Eric Werley, Jun 27 2011
E.g.f.: exp(x)*(1+x+(x^2)/2) = Q(0); Q(k) = 1+x/(1-x/(2+x-4/(2+x*(k+1)/Q(k+1)))); (continued fraction). - Sergei N. Gladkovskii, Nov 21 2011
Dirichlet g.f.: (zeta(s-2) + zeta(s-1) + 2*zeta(s))/2.
Sum_{n >= 0} 1/a(n) = 2*Pi*tanh(sqrt(7)*Pi/2)/sqrt(7) = A226985. (End)
a(n) = 2*a(n-1) - binomial(n-1, 2) and a(0) = 1. - Armend Shabani, Mar 10 2017
a(n) = (Sum_{i=n-2..n+2} A000217(i))/5.
a(n) = (Sum_{i=n-2..n+2} A002378(i))/10.
a(n) = (Sum_{i=n..n+2} A002061(i)+1)/6.
a(n) = (Sum_{i=n-1..n+2} A000290(i)+2)/8.
(End)
Product_{n>=0} (1 + 1/a(n)) = cosh(sqrt(15)*Pi/2)*sech(sqrt(7)*Pi/2).
Product_{n>=1} (1 - 1/a(n)) = 2*Pi*sech(sqrt(7)*Pi/2). (End)
a((n^2-3n+6)/2) + a((n^2-n+4)/2) = a(n^2-2n+6)/2. - Charlie Marion, Feb 14 2023
|
|
EXAMPLE
|
a(3) = 7 because the 132- and 321-avoiding permutations of {1, 2, 3, 4} are 1234, 2134, 3124, 2314, 4123, 3412, 2341.
G.f. = 1 + 2*x + 4*x^2 + 7*x^3 + 11*x^4 + 16*x^5 + 22*x^6 + 29*x^7 + ...
|
|
MAPLE
|
|
|
MATHEMATICA
|
Table[PolygonalNumber[n] + 1, {n, 0, 52}] (* Michael De Vlieger, Jun 30 2016, Version 10.4 *)
|
|
PROG
|
(PARI) {a(n) = (n^2 + n) / 2 + 1}; /* Michael Somos, Sep 04 2006 */
(Haskell)
a000124 = (+ 1) . a000217
(Python)
def a(n): return n*(n+1)//2 + 1
|
|
CROSSREFS
|
Cf. A000096 (Maximal number of pieces that can be obtained by cutting an annulus with n cuts, for n >= 1).
Cf. A002061, A002522, A016028, A055503, A072863, A144328, A177862, A263883, A000127, A005408, A006261, A016813, A058331, A080856, A086514, A161701, A161702, A161703, A161704, A161706, A161707, A161708, A161710, A161711, A161712, A161713, A161715, A051601, A228918.
Cf. A055469 Quasi-triangular primes.
|
|
KEYWORD
|
nonn,core,easy,nice,changed
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A215703
|
|
A(n,k) is the n-th derivative of f_k at x=1, and f_k is the k-th of all functions that are representable as x^x^...^x with m>=1 x's and parentheses inserted in all possible ways; square array A(n,k), n>=0, k>=1, read by antidiagonals.
|
|
+10
58
|
|
|
1, 1, 1, 1, 1, 0, 1, 1, 2, 0, 1, 1, 4, 3, 0, 1, 1, 2, 12, 8, 0, 1, 1, 6, 9, 52, 10, 0, 1, 1, 4, 27, 32, 240, 54, 0, 1, 1, 2, 18, 156, 180, 1188, -42, 0, 1, 1, 2, 15, 100, 1110, 954, 6804, 944, 0, 1, 1, 8, 9, 80, 650, 8322, 6524, 38960, -5112, 0, 1, 1, 6, 48, 56, 590, 4908, 70098, 45016, 253296, 47160, 0
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,9
|
|
COMMENTS
|
A000081(m) distinct functions are representable as x^x^...^x with m>=1 x's and parentheses inserted in all possible ways. Some functions are representable in more than one way, the number of valid parenthesizations is A000108(m-1). The f_k are ordered, such that the number m of x's in f_k is a nondecreasing function of k. The exact ordering is defined by the algorithm below.
The list of functions f_1, f_2, ... begins:
| f_k : m : function (tree) : representation(s) : sequence |
+-----+---+------------------+--------------------------+----------+
| f_2 | 2 | x -> x^x | x^x | A005727 |
| f_3 | 3 | x -> x^(x*x) | (x^x)^x | A215524 |
| f_4 | 3 | x -> x^(x^x) | x^(x^x) | A179230 |
| f_5 | 4 | x -> x^(x*x*x) | ((x^x)^x)^x | A215704 |
| f_6 | 4 | x -> x^(x^x*x) | (x^x)^(x^x), (x^(x^x))^x | A215522 |
| f_7 | 4 | x -> x^(x^(x*x)) | x^((x^x)^x) | A215705 |
| f_8 | 4 | x -> x^(x^(x^x)) | x^(x^(x^x)) | A179405 |
|
|
LINKS
|
|
|
EXAMPLE
|
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 1, 1, 1, 1, 1, ...
0, 2, 4, 2, 6, 4, 2, 2, ...
0, 3, 12, 9, 27, 18, 15, 9, ...
0, 8, 52, 32, 156, 100, 80, 56, ...
0, 10, 240, 180, 1110, 650, 590, 360, ...
0, 54, 1188, 954, 8322, 4908, 5034, 2934, ...
0, -42, 6804, 6524, 70098, 41090, 47110, 26054, ...
|
|
MAPLE
|
T:= proc(n) T(n):=`if`(n=1, [x], map(h-> x^h, g(n-1$2))) end:
g:= proc(n, i) option remember; `if`(i=1, [x^n], [seq(seq(
seq(mul(T(i)[w[t]-t+1], t=1..j)*v, v=g(n-i*j, i-1)), w=
combinat[choose]([$1..nops(T(i))+j-1], j)), j=0..n/i)])
end:
f:= proc() local i, l; i, l:= 0, []; proc(n) while n>
nops(l) do i:= i+1; l:= [l[], T(i)[]] od; l[n] end
end():
A:= (n, k)-> n!*coeff(series(subs(x=x+1, f(k)), x, n+1), x, n):
seq(seq(A(n, 1+d-n), n=0..d), d=0..12);
|
|
MATHEMATICA
|
T[n_] := If[n == 1, {x}, Map[x^#&, g[n - 1, n - 1]]];
g[n_, i_] := g[n, i] = If[i == 1, {x^n}, Flatten @ Table[ Table[ Table[ Product[T[i][[w[[t]] - t + 1]], {t, 1, j}]*v, {v, g[n - i*j, i - 1]}], {w, Subsets[ Range[ Length[T[i]] + j - 1], {j}]}], {j, 0, n/i}]];
f[n_] := Module[{i = 0, l = {}}, While[n > Length[l], i++; l = Join[l, T[i]]]; l[[n]]];
A[n_, k_] := n! * SeriesCoefficient[f[k] /. x -> x+1, {x, 0, n}];
|
|
CROSSREFS
|
Columns k=1-17, 37 give: A019590, A005727, A215524, A179230, A215704, A215522, A215705, A179405, A215706, A215707, A215708, A215709, A215691, A215710, A215643, A215629, A179505, A211205.
Rows n=0+1, 2-10 give: A000012, A215841, A215842, A215834, A215835, A215836, A215837, A215838, A215839, A215840.
Cf. A000081, A000108, A033917, A211192, A214569, A214570, A214571, A216041, A216281, A216349, A216350, A216351, A216368, A222379, A222380, A277537, A306679, A306710, A306726.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A336811
|
|
Irregular triangle read by rows T(n,k) in which the length of row n equals the partition number A000041(n-1) and every column k gives the positive integers A000027, with n >= 1 and k >= 1.
|
|
+10
50
|
|
|
1, 2, 3, 1, 4, 2, 1, 5, 3, 2, 1, 1, 6, 4, 3, 2, 2, 1, 1, 7, 5, 4, 3, 3, 2, 2, 1, 1, 1, 1, 8, 6, 5, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 9, 7, 6, 5, 5, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 10, 8, 7, 6, 6, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
In other words: row n lists A028310(n-1) blocks where the m-th block consists of A187219(m) copies of n - m + [m=1], with n >= 1 and m >= 1, where [] is the Iverson bracket. [Corrected by Paolo Xausa, Feb 10 2023]
All divisors of all terms in row n are also all parts in the last section of the set of partitions of n.
Thus all divisors of all terms of the first n rows of triangle are also all parts of all partitions of n. In other words: all divisors of the first A000070(n-1) terms of the sequence are also all parts of all partitions of n. - Omar E. Pol, Jun 19 2021
The number of k's in row n is equal to A002865(n-k), 1 <= k <= n.
The number of terms >= k in row n is equal to A000041(n-k), 1 <= k <= n.
The number of k's in the first n rows (or in the first A000070(n-1) terms of the sequence) is equal to A000041(n-k), 1 <= k <= n.
The number of terms >= k in the first n rows (or in the first A000070(n-1) terms of the sequence) is equal to A000070(n-k), 1 <= k <= n.
First n rows of triangle (or first A000070(n-1) terms of the sequence) in nonincreasing order give the n-th row of A176206. (End)
|
|
LINKS
|
|
|
EXAMPLE
|
Triangle begins:
1;
2;
3, 1;
4, 2, 1;
5, 3, 2, 1, 1;
6, 4, 3, 2, 2, 1, 1;
7, 5, 4, 3, 3, 2, 2, 1, 1, 1, 1;
8, 6, 5, 4, 4, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1;
9, 7, 6, 5, 5, 4, 4, 3, 3, 3, 3, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1;
...
For n = 6, by definition the length of row 6 is A000041(6-1) = A000041(5) = 7, so the row 6 of triangle has seven terms. Since every column lists the positive integers A000027 so the row 6 is [6, 4, 3, 2, 2, 1, 1].
Then we have that the divisors of the numbers of the 6th row are:
.
6th row of the triangle ----------> 6 4 3 2 2 1 1
3 2 1 1 1
2 1
1
.
There are seven 1's, four 2's, two 3's, one 4 and one 6.
In total there are 7 + 4 + 2 + 1 + 1 = 15 divisors.
On the other hand the last section of the set of the partitions of 6 can be represented in several ways, five of them as shown below:
._ _ _ _ _ _
|_ _ _ | 6 6 6 6
|_ _ _|_ | 3 3 3 3 3 3 3 3
|_ _ | | 4 2 4 2 4 2 4 2
|_ _|_ _|_ | 2 2 2 2 2 2 2 2 2 2 2 2
| | 1 1 1 1
| | 1 1 1 1
| | 1 1 1 1
| | 1 1 1 1
| | 1 1 1 1
| | 1 1 1 1
|_| 1 1 1 1
.
Figure 1. Figure 2. Figure 3. Figure 4. Figure 5.
.
In every figure there are seven 1's, four 2's, two 3's, one 4 and one 6, as shown also the 6th row of A182703.
In total there are 7 + 4 + 2 + 1 + 1 = A138137(6) = 15 parts in every figure.
Figure 5 is an arrangement that shows the correspondence between divisors and parts since the columns give the divisors of the terms of 6th row of triangle.
Finally we can see that all divisors of all numbers in the 6th row of the triangle are the same positive integers as all parts in the last section of the set of the partitions of 6.
|
|
MATHEMATICA
|
A336811[row_]:=Flatten[Table[ConstantArray[row-m, PartitionsP[m]-PartitionsP[m-1]], {m, 0, row-1}]];
|
|
PROG
|
(PARI) f(n) = numbpart(n-1);
T(n, k) = {if (k > f(n), error("invalid k")); if (k==1, return (n)); my(s=0); while (k <= f(n-1), s++; n--; ); 1+s; }
tabf(nn) = {for (n=1, nn, for (k=1, f(n), print1(T(n, k), ", "); ); print; ); } \\ Michel Marcus, Jan 13 2021
|
|
CROSSREFS
|
Cf. A000007, A000041, A027750, A028310, A002865, A133735, A135010, A138121, A138137, A182703, A187219, A207378, A221529, A336812, A339278, A340035, A340061, A346741.
|
|
KEYWORD
|
nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A048645
|
|
Integers with one or two 1-bits in their binary expansion.
|
|
+10
34
|
|
|
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 16, 17, 18, 20, 24, 32, 33, 34, 36, 40, 48, 64, 65, 66, 68, 72, 80, 96, 128, 129, 130, 132, 136, 144, 160, 192, 256, 257, 258, 260, 264, 272, 288, 320, 384, 512, 513, 514, 516, 520, 528, 544, 576, 640, 768, 1024, 1025, 1026, 1028, 1032
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
COMMENTS
|
Apart from initial 1, sums of two not necessarily distinct powers of 2.
4 does not divide C(2s-1,s) (= A001700[ s ]) if and only if s=a(n).
Possible number of sides of a regular polygon such that there exists a triangulation where each triangle is isosceles. - Sen-peng Eu, May 07 2008
Also numbers n such that n!/2^(n-2) is an integer. - Michel Lagneau, Mar 28 2011
Numbers with binary weight 1 or 2. - Omar E. Pol, Feb 22 2015
|
|
LINKS
|
|
|
FORMULA
|
a(0) = 1, a(n) = (2^(trinv(n-1)-1) + 2^((n-1)-((trinv(n-1)*(trinv(n-1)-1))/2))), i.e., 2^A003056(n) + 2^A002262(n-1) (the latter sequence contains the definition of trinv).
Let Theta = Sum_{k >= 0} x^(2^k). Then Sum_{n>=1} x^a(n) = (Theta^2 + Theta + x)/2. - N. J. A. Sloane, Jun 23 2009
|
|
EXAMPLE
|
Also, written as a triangle T(j,k), k >= 1, in which row lengths are the terms of A028310:
1;
2;
3, 4;
5, 6, 8;
9, 10, 12, 16;
17, 18, 20, 24, 32;
33, 34, 36, 40, 48, 64;
65, 66, 68, 72, 80, 96, 128;
...
It appears that column 1 is A094373.
It appears that the right border gives A000079.
It appears that the first differences in every row that contains at least two terms give the first h-1 powers of 2, where h is the length of the row.
(End)
|
|
MAPLE
|
lincom:=proc(a, b, n) local i, j, s, m; s:={}; for i from 0 to n do for j from 0 to n do m:=a^i+b^j; if m<=n then s:={op(s), m} fi od; od; lprint(sort([op(s)])); end: lincom(2, 2, 1000); # Zerinvary Lajos, Feb 24 2007
|
|
MATHEMATICA
|
|
|
PROG
|
(Haskell)
import Data.List (insert)
a048645 n k = a048645_tabl !! (n-1) !! (k-1)
a048645_row n = a048645_tabl !! (n-1)
a048645_tabl = iterate (\xs -> insert (2 * head xs + 1) $ map ((* 2)) xs) [1]
a048645_list = concat a048645_tabl
(PARI) isok(n) = my(hw = hammingweight(n)); (hw == 1) || (hw == 2); \\ Michel Marcus, Mar 06 2016
(PARI) a(n) = if(n <= 2, return(n), n-=2); my(c = (sqrtint(8*n + 1) - 1) \ 2); 1 << c + 1 << (n - binomial(c + 1, 2)) \\ David A. Corneth, Jan 02 2019
(PARI) nxt(n) = msb = 1 << logint(n, 2); if(n == msb, n + 1, t = n - msb; n + t) \\ David A. Corneth, Jan 02 2019
(Python)
def ok(n): return 1 <= bin(n)[2:].count('1') <= 2
(Python)
from itertools import count, islice
def agen(): # generator of terms
for d in count(0):
msb = 2**d
yield msb
for lsb in range(d):
yield msb + 2**lsb
|
|
CROSSREFS
|
Cf. A018900, A048623, A046097, A169707, A147562, A162795, A003056, A002262, A094373, A028310, A179951.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|
|
A227349
|
|
Product of lengths of runs of 1-bits in binary representation of n.
|
|
+10
29
|
|
|
1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 2, 2, 2, 3, 4, 1, 1, 1, 2, 1, 1, 2, 3, 2, 2, 2, 4, 3, 3, 4, 5, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 2, 2, 2, 3, 4, 2, 2, 2, 4, 2, 2, 4, 6, 3, 3, 3, 6, 4, 4, 5, 6, 1, 1, 1, 2, 1, 1, 2, 3, 1, 1, 1, 2, 2, 2, 3, 4, 1, 1, 1, 2, 1, 1, 2, 3, 2, 2, 2, 4, 3, 3, 4, 5, 2, 2, 2, 4, 2, 2, 4, 6, 2, 2, 2, 4, 4, 4, 6, 8, 3, 3, 3, 6, 3, 3, 6, 9, 4
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,4
|
|
COMMENTS
|
This is the Run Length Transform of S(n) = {0, 1, 2, 3, 4, 5, 6, ...}. The Run Length Transform of a sequence {S(n), n >= 0} is defined to be the sequence {T(n), n >= 0} given by T(n) = Product_i S(i), where i runs through the lengths of runs of 1's in the binary expansion of n. E.g., 19 is 10011 in binary, which has two runs of 1's, of lengths 1 and 2. So T(19) = S(1)*S(2). T(0) = 1 (the empty product). - N. J. A. Sloane, Sep 05 2014
|
|
LINKS
|
|
|
FORMULA
|
(End)
|
|
EXAMPLE
|
a(0) = 1, as zero has no runs of 1's, and an empty product is 1.
a(1) = 1, as 1 is "1" in binary, and the length of that only 1-run is 1.
a(2) = 1, as 2 is "10" in binary, and again there is only one run of 1-bits, of length 1.
a(3) = 2, as 3 is "11" in binary, and there is one run of two 1-bits.
a(55) = 6, as 55 is "110111" in binary, and 2 * 3 = 6.
a(119) = 9, as 119 is "1110111" in binary, and 3 * 3 = 9.
Written as an irregular triangle in which row lengths is A011782:
1;
1;
1,2;
1,1,2,3;
1,1,1,2,2,2,3,4;
1,1,1,2,1,1,2,3,2,2,2,4,3,3,4,5;
1,1,1,2,1,1,2,3,1,1,1,2,2,2,3,4,2,2,2,4,2,2,4,6,3,3,3,6,4,4,5,6;
...
Right border gives A028310: 1 together with the positive integers.
(End)
Also, the sequence can be written as an irregular tetrahedron T(s, r, k) as shown below:
1;
..
1;
..
1;
2;
....
1,1;
2;
3;
........
1,1,1,2;
2,2;
3;
4;
................
1,1,1,2,1,1,2,3;
2,2,2,4;
3,3;
4;
5;
................................
1,1,1,2,1,1,2,3,1,1,1,2,2,2,3,4;
2,2,2,4,2,2,4,6;
3,3,3,6;
4,4;
5;
6;
...
Apart from the initial 1, we have that T(s, r, k) = T(s+1, r, k).
(End)
|
|
MAPLE
|
a:= proc(n) local i, m, r; m, r:= n, 1;
while m>0 do
while irem(m, 2, 'h')=0 do m:=h od;
for i from 0 while irem(m, 2, 'h')=1 do m:=h od;
r:= r*i
od; r
end:
ans:=[];
for n from 0 to 100 do lis:=[]; t1:=convert(n, base, 2); L1:=nops(t1); out1:=1; c:=0;
for i from 1 to L1 do
if out1 = 1 and t1[i] = 1 then out1:=0; c:=c+1;
elif out1 = 0 and t1[i] = 1 then c:=c+1;
elif out1 = 1 and t1[i] = 0 then c:=c;
elif out1 = 0 and t1[i] = 0 then lis:=[c, op(lis)]; out1:=1; c:=0;
fi;
if i = L1 and c>0 then lis:=[c, op(lis)]; fi;
od:
a:=mul(i, i in lis);
ans:=[op(ans), a];
od:
|
|
MATHEMATICA
|
onBitRunLenProd[n_] := Times @@ Length /@ Select[Split @ IntegerDigits[n, 2], #[[1]] == 1 & ]; Array[onBitRunLenProd, 100, 0] (* Jean-François Alcover, Mar 02 2016 *)
|
|
PROG
|
(Python)
from operator import mul
from functools import reduce
from re import split
return reduce(mul, (len(d) for d in split('0+', bin(n)[2:]) if d)) if n > 0 else 1 # Chai Wah Wu, Sep 07 2014
A227349_list = lambda len: RLT(lambda n: n, len)
(Scheme)
(define (A227349 n) (apply * (bisect (reverse (binexp->runcount1list n)) (- 1 (modulo n 2)))))
(define (bisect lista parity) (let loop ((lista lista) (i 0) (z (list))) (cond ((null? lista) (reverse! z)) ((eq? i parity) (loop (cdr lista) (modulo (1+ i) 2) (cons (car lista) z))) (else (loop (cdr lista) (modulo (1+ i) 2) z)))))
(define (binexp->runcount1list n) (if (zero? n) (list) (let loop ((n n) (rc (list)) (count 0) (prev-bit (modulo n 2))) (if (zero? n) (cons count rc) (if (eq? (modulo n 2) prev-bit) (loop (floor->exact (/ n 2)) rc (1+ count) (modulo n 2)) (loop (floor->exact (/ n 2)) (cons count rc) 1 (modulo n 2)))))))
|
|
CROSSREFS
|
Cf. A000120 (sum of lengths of runs of 1-bits), A167489, A227350, A227193, A278222, A245562, A284562, A284569, A283972, A284582, A284583.
Differs from similar A284580 for the first time at n=119, where a(119) = 9, while A284580(119) = 5.
|
|
KEYWORD
|
nonn,base
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|
|
A005183
|
|
a(n) = n*2^(n-1) + 1.
(Formerly M1434)
|
|
+10
28
|
|
|
1, 2, 5, 13, 33, 81, 193, 449, 1025, 2305, 5121, 11265, 24577, 53249, 114689, 245761, 524289, 1114113, 2359297, 4980737, 10485761, 22020097, 46137345, 96468993, 201326593, 419430401, 872415233, 1811939329, 3758096385, 7784628225, 16106127361, 33285996545
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
a(n-1) is the number of permutations of length n which avoid the patterns 132, 4312. - Lara Pudwell, Jan 21 2006
Number of sequences (e(1), ..., e(n+1)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) <= e(j) >= e(k) and e(i) != e(k). [Martinez and Savage, 2.11] - Eric M. Schmidt, Jul 17 2017
Indices of records in A066099. Also, indices of "cusps" in the graph of A030303 giving positions of 1's in the binary Champernowne word A030190. - M. F. Hasler, Oct 12 2020
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
LINKS
|
Jean-Luc Baril, Pamela E. Harris, and José L. Ramírez, Flattened Catalan Words, arXiv:2405.05357 [math.CO], 2024. See p. 16.
V. Jelinek, T. Mansour, and M. Shattuck, On multiple pattern avoiding set partitions, Adv. Appl. Math. 50 (2) (2013) 292-326, Example 4.16, H_{1223} and Example 4.17 L_{1232} and propositions 4.20 and 4.22, all shifted with an additional leading a(0)=1.
L. Pudwell, Pattern-avoiding ascent sequences, Slides from a talk, 2015 Joint Mathematics Meetings, AMS Special Session on Enumerative Combinatorics, January 11, 2015.
|
|
FORMULA
|
Main diagonal of the array defined by T(0, j)=j+1 j>=0, T(i, 0)=i+1 i>=0, T(i, j)=T(i-1, j-1)+T(i-1, j)-1. - Benoit Cloitre, Jun 17 2003
G.f.: (1 -3*x +3*x^2)/((1-x)*(1-2*x)^2). - Lara Pudwell, Jan 21 2006
|
|
MAPLE
|
A005183 := (1-3*z+3*z**2)/(1-z)/(1-2*z)**2; # Generating function conjectured by Simon Plouffe in his 1992 dissertation.
|
|
MATHEMATICA
|
LinearRecurrence[{5, -8, 4}, {1, 2, 5}, 30] (* Harvey P. Dale, Jul 29 2015 *)
|
|
PROG
|
(Sage) [2^(n-1)*n+1 for n in (0..35)] # G. C. Greubel, May 31 2019
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
Search completed in 0.057 seconds
|