login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001399 Number of partitions of n into at most 3 parts; also partitions of n+3 in which the greatest part is 3; also multigraphs with 3 nodes and n edges.
(Formerly M0518 N0186)
85
1, 1, 2, 3, 4, 5, 7, 8, 10, 12, 14, 16, 19, 21, 24, 27, 30, 33, 37, 40, 44, 48, 52, 56, 61, 65, 70, 75, 80, 85, 91, 96, 102, 108, 114, 120, 127, 133, 140, 147, 154, 161, 169, 176, 184, 192, 200, 208, 217, 225, 234, 243, 252, 261, 271, 280, 290, 300, 310, 320, 331, 341 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,3

COMMENTS

Also number of tripods (trees with exactly 3 leaves) on n vertices. - Eric W. Weisstein, Mar 05 2011

Also number of partitions of n+3 into exactly 3 parts; number of partitions of n in which the greatest part is less than or equal to 3; and the number of nonnegative solutions to b+2c+3d=n.

Also a(n) gives number of partitions of n+6 into 3 distinct parts and number of partitions of 2n+9 into 3 distinct and odd parts, e.g. 15=11+3+1=9+5+1=7+5+3. - Jon Perry, Jan 07 2004

Also necklaces with n+3 beads 3 of which are red (so there are 2 possibilities with 5 beads).

More generally, the number of partitions of n into at most k parts is also the number of partitions of n+k into k positive parts, the number of partitions of n+k in which the greatest part is k, the number of partitions of n in which the greatest part is less than or equal to k, the number of partitions of n+k(k+1)/2 into exactly k distinct positive parts, the number of nonnegative solutions to b+2c+3d+...+kz=n and the number of nonnegative solutions to 2c+3d+...+kz<=n. - Henry Bottomley, Apr 17 2001

Also coefficient of q^n in the expansion of (m choose 3)_q as m goes to infinity. - Y. Kelly Itakura (yitkr(AT)mta.ca), Aug 21 2002

Write 1,2,3,4,... in a hexagonal spiral around 0, then a(n) for n>0 is formed by the folding points (including the initial 1). The spiral begins:

......16..15..14

....17..5...4...13

..18..6...0...3...12

19..7...1...2...11..26

..20..8...9...10..25

....21..22..23..24

a(p) is maximal number of hexagons in a polyhex with perimeter at most 2p + 6. - Winston C. Yang (winston(AT)cs.wisc.edu), Apr 30 2002

a(n-3) is the number of partitions of n into 3 distinct parts, where 0 is allowed as a part. E.g., at n=9, we can write 8+1+0, 7+2+0, 6+3+0, 4+5+0, 1+2+6, 1+3+5 and 2+3+4, which is a(6)=7. - Jon Perry, Jul 08 2003

a(n) gives number of partitions of n+6 into parts <=3 where each part is used at least once (subtract 6=1+2+3 from n). - Jon Perry, Jul 03 2004

This is also the number of partitions of n+3 into exactly 3 parts (there is a 1-to-1 correspondence between the number of partitions of n+3 in which the greatest part is 3 and the number of partitions of n+3 into exactly three parts). - Graeme McRae, Feb 07 2005

Apply the Riordan array (1/(1-x^3),x) to floor((n+2)/2). - Paul Barry, Apr 16 2005

Also, number of triangles that can be created with odd perimeter 3,5,7,9,11,... with all sides whole numbers. Note that triangles with even perimeter can be generated from the odd ones by increasing each side by 1. E.g., a(1) = 1 because perimeter 3 can make {1,1,1} 1 triangle. a(4) = 3 because perimeter 9 can make {1,4,4} {2,3,4} {3,3,3} 3 possible triangles. - Bruce Love (bruce_love(AT)ofs.edu.sg), Nov 20 2006

Also number of nonnegative solutions of the Diophantine equation x+2*y+3*z=n, cf. Polya/Szego reference.

From Vladimir Shevelev, Apr 23 2011: (Start)

Also a(n-3), n >= 3, is the number of non-equivalent necklaces of 3 beads each of them painted by one of n colors.

The sequence {a(n-3), n >= 3} solves the so-called Reis problem about convex k-gons in case k=3 (see our comment to A032279).

a(n-3) (n >= 3) is an essentially unimprovable upper estimate for the number of distinct values of the permanent in (0,1)-circulants of order n with three 1's in every row. (End)

A001399(n) is the number of 3-tuples (w,x,y) having all terms in {0,...,n} and w = 2*x+3*y. - Clark Kimberling, Jun 04 2012

Also, for n >= 3, a(n-3) is the number of the distinct triangles in an n-gon, see the Ngaokrajan links. - Kival Ngaokrajang, Mar 16 2013

Also, a(n) is the total number of 5-curves coins patterns (5C4S type: 5-curves covering full 4 coins and symmetry) packing into fountain of coins base (n+3). See illustration in links. - Kival Ngaokrajang, Oct 16 2013

Also a(n) = half the number of minimal zero sequences for Z_n of length 3 [Ponomarenko] - N. J. A. Sloane, Feb 25 2014

REFERENCES

R. Ayoub, An Introduction to the Analytic Theory of Numbers, Amer. Math. Soc., 1963; Chapter III, Problem 33.

N. Benyahia Tani, Z. Yahi, S. Bouroubi, Ordered and non-ordered non-isometric convex quadrilaterals inscribed in a regular n-gon, Bulletin du Laboratoire Liforce, 01 (2014) 1 - 9; http://www.liforce.usthb.dz/IMG/pdf/bulletin2014.pdf

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 110, D(n); page 263, #18, P_n^{3}.

S. J. Cyvin et al., Polygonal Systems Including the Corannulene and Coronene Homologs: Novel Applications of Pólya's Theorem, Z. Naturforsch., 52a (1997), 867-873.

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 517.

H. Gupta et al., Tables of Partitions. Royal Society Mathematical Tables, Vol. 4, Cambridge Univ. Press, 1958, p. 2.

H. Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no.8, 964-999.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 88, (4.1.18).

G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers. 3rd ed., Oxford Univ. Press, 1954, p. 275.

Karl Hermann Struve, Fresnel's Interferenzerscheinungen: Theoretisch und Experimentell Bearbeitet, Dorpat, 1881 (Thesis). [Gives the Round(n^2/12) formula.]

J. H. Jordan, R. Walch and R. J. Wisner, Triangles with integer sides, Amer. Math. Monthly, 86 (1979), 686-689.

Gerzson Keri and Patric R. J. Ostergard, The Number of Inequivalent (2R+3,7)R Optimal Covering Codes, Journal of Integer Sequences, Vol. 9 (2006), Article 06.4.7.

J. H. van Lint, Combinatorial Seminar Eindhoven, Lecture Notes Math., 382 (1974), see pp. 33-34.

G. Polya and G. Szego, Problems and Theorems in Analysis I (Springer 1924, reprinted 1972), Part One, Chap. 1, Sect. 1, Problem 25.

Vadim Ponomarenko, Minimal zero sequences of finite cyclic groups, INTEGERS, 4 (2004), #A24.

V. Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.

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).

James Tanton, "Young students approach integer triangles", FOCUS 22 no. 5 (2002), 4 - 6.

W. C. Yang, Maximal and minimal polyhexes, manuscript, 2002.

LINKS

T. D. Noe, Table of n, a(n) for n=0..1000

Hamid Afshar, Branislav Cvetkovic, Sabine Ertl, Daniel Grumiller and Niklas Johansson, Conformal Chern-Simons holography-lock, stock and barrel, Arxiv preprint arXiv:1110.5644, 2011

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 352

M. B. Nathanson, Partitions with parts in a finite set

Kival Ngaokrajang, Distinct triangles in n-gon for n = 3..9, Distinct triangles in 45-gon

Kival Ngaokrajang, Illustration of 5-curves coins patterns

Andrew N. Norris, Higher derivatives and the inverse derivative of a tensor-valued function of a tensor, arXiv:0707.0115, Equation 3.28, p. 10

Jon Perry, More Partition Function

Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992.

Simon Plouffe, 1031 Generating Functions and Conjectures, Université du Québec à Montréal, 1992.

V. Shevelev,Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma) (Cf. Section 5)

James Tanton, Integer Triangles, Chapter 11 in “Mathematics Galore!” (MAA, 2012).

Eric Weisstein's World of Mathematics, Tripod

Index to sequences with linear recurrences with constant coefficients, signature (1, 1, 0, -1, -1, 1).

FORMULA

G.f.: 1/((1-x)*(1-x^2)*(1-x^3)).

a(n) = round( (n+3)^2/12 ). Note that this cannot be of the form (2i+1)/2, so ties never arise.

a(n) = A008284(n+3, 3), n >= 0.

a(n) = 1 + a(n-2) + a(n-3) - a(n-5). - Michael Somos, Sep 04 2006

a(-6 - n) = a(n). - Michael Somos, Sep 04 2006

a(6*n) = A003215(n), a(6*n + 1) = A000567(n + 1), a(6*n + 2) = A049450(n + 1), a(6*n + 3) = A033428(n + 1), a(6*n + 4) = A049451(n + 1), a(6*n + 5) = A045944(n + 1).

a(n) = a(n-1)+A008615(n+2) = a(n-2) + A008620(n) = a(n-3)+A008619(n) = A001840(n+1) - a(n-1) = A002620(n+2)- A001840(n) = A000601(n) - A000601(n-1). - Henry Bottomley, Apr 17 2001

P(n, 3) = 1/72(6*n^2-7-9*pcr{1, -1}(2, n)+8*pcr{2, -1, -1}(3, n)) (see Comtet).

Let m>0 and -3<=p<=2 be defined by n = 6*m+p-3 then for n > -3 a(n) = 3*m^2+p*m and for n=-3 a(n) = 3*m^2+p*m+1. - Floor van Lamoen (fvlamoen(AT)hotmail.com), Jul 23 2001

a(n)=17/72+(n+1)*(n+5)/12+(-1)^n/8+(2/9)*cos(2*n*Pi/3). - Benoit Cloitre, Feb 09 2003

a(n)=6*t(floor(n/6))+(n%6)*(floor(n/6)+1)+(n mod 6==0?1:0), where t(n)=n*(n+1)/2 a(n)=ceil(1/12*n^2+1/2*n)+(n mod 6==0?1:0). - Jon Perry, Jun 17 2003

a(n)=sum(i=0, floor(n/3), 1+ceil((n-3*i-1)/2)). - Jon Perry, Jun 27 2003

a(n)=sum{k=0..floor(n/3), floor((n-3k+2)/2)}; a(n)=sum{k=0..n, floor((k+2)/2)*(cos(2*Pi*(n-k)/3+Pi/3)/3+sqrt(3)sin(2*Pi*(n-k)/3+Pi/3)/3+1/3)}. - Paul Barry, Apr 16 2005

(m choose 3)_q=(q^m-1)*(q^(m-1)-1)*(q^(m-2)-1)/((q^3-1)*(q^2-1)*(q-1))

a(n)=sum{k=0..floor(n/2), floor((3+n-2k)/3)}. - Paul Barry, Nov 11 2003

A117220(n) = a(A003586(n)). - Reinhard Zumkeller, Mar 04 2006

a(n)= 3 * sum_{i=2...n+1} floor(i/2)-floor(i/3). - Thomas Wieder, Feb 11 2007

Identical to the number of points in and on the boundary of the integer grid of {I, J}, bounded by the three straight lines I = 0, I - J = 0 and I + 2J = n. Norris has given, up to a unitary offset of index 'n', floor( (n+3)^2+4 ) )/12, which is the same as floor( (n+3)^2+3 ) )/12 already posted above. - Jonathan Vos Post, Jul 03 2007

a(n) = A026820(n,3) for n>2. - Reinhard Zumkeller, Jan 21 2010

Euler transform of length 3 sequence [ 1, 1, 1]. - Michael Somos, Feb 25 2012

a(n) = A005044(2*n + 3) = A005044(2*n + 6). - Michael Somos, Feb 25 2012

a(n) = A000212(n+3) - A002620(n+3). - Richard R. Forberg, Dec 08 2013

EXAMPLE

1 + x + 2*x^2 + 3*x^3 + 4*x^4 + 5*x^5 + 7*x^6 + 8*x^7 + 10*x^8 + 12*x^9 + ...

Recall that in a necklace the adjacent beads have distinct colors. Let we have n colors with labels 1,...,n. Two colorings of the beads are equivalent, if the cyclic sequences of the distances modulo n between labels of adjacent colors have the same period. In case n=4 all colorings are equivalent. E.g., for the colorings {1,2,3} and {1,2,4} we have the same period {1,1,2} of distances nodulo 4. So, a(n-3)=a(1)=1. If n=5, then we have two such periods {1,1,3} and {1,2,2} modulo 5. Thus a(2)=2. - Vladimir Shevelev, Apr 23 2011

MAPLE

[ seq(1+floor((n^2+6*n)/12), n=0..60) ];

A001399 := -1/(z+1)/(z**2+z+1)/(z-1)**3; [Simon Plouffe in his 1992 dissertation.]

for n from 1 to 20 do result:=0: for i from 2 to n+1 do result:=result+(floor(i/2)-floor(i/3)); od; result; od; # Thomas Wieder, Feb 11 2007

with(combstruct):ZL4:=[S, {S=Set(Cycle(Z, card<4))}, unlabeled]:seq(count(ZL4, size=n), n=0..61); # Zerinvary Lajos, Sep 24 2007

B:=[S, {S = Set(Sequence(Z, 1 <= card), card <=3)}, unlabelled]: seq(combstruct[count](B, size=n), n=0..61); # Zerinvary Lajos, Mar 21 2009

MATHEMATICA

CoefficientList[ Series[ 1/((1 - x)*(1 - x^2)*(1 - x^3)), {x, 0, 65} ], x ]

Table[ Length[ IntegerPartitions[n, 3]], {n, 0, 61} ] (* corrected by Jean-François Alcover, Aug 08 2012 *)

k = 3; Table[(Apply[Plus, Map[EulerPhi[ # ]Binomial[n/#, k/# ] &, Divisors[GCD[n, k]]]]/n + Binomial[If[OddQ[n], n - 1, n - If[OddQ[k], 2, 0]]/2, If[OddQ[k], k - 1, k]/2])/2, {n, k, 50}] - Robert A. Russell, Sep 27 2004

LinearRecurrence[{1, 1, 0, -1, -1, 1}, {1, 1, 2, 3, 4, 5}, 70] (* Harvey P. Dale, Jun 21 2012 *)

PROG

(PARI) {a(n) = round((n + 3)^2 / 12)} /* Michael Somos, Sep 04 2006 */

(Haskell)

a001399 = p [1, 2, 3] where

   p _      0 = 1

   p []     _ = 0

   p ks'@(k:ks) m = if m < k then 0 else p ks' (m - k) + p ks m

-- Reinhard Zumkeller, Feb 28 2013

CROSSREFS

Cf. A008724, A003082, A117485.

Cf. A026810, A026811, A026812, A026813, A026814, A026815, A026816, A000228, A036496.

Cf. A008619, A001400, A001401, A128012.

Cf. A069905, A008615.

Sequence in context: A034092 A211540 * A069905 A008761 A008760 A008759

Adjacent sequences:  A001396 A001397 A001398 * A001400 A001401 A001402

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Robert G. Wilson v, Dec 11 2000

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified July 23 01:55 EDT 2014. Contains 244849 sequences.