Search: 254
|
| |
|
|
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)
|
|
+20
295
|
|
|
|
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
a(n) = A108561(n+3,2). - Reinhard Zumkeller, Jun 10 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 have no exactly one element in common with Y. - Milan Janjic, Dec 28 2007
Equals row sums of triangle A144328. - Gary W. Adamson, Sep 18 2008
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} so that $\cap_{i=1}^{n} A_i=\emptyset$ and the sum $\sum_{\forall j\in [n]}\left (|\cap_{i=1,i\ne j}^{n} A_i|\right )$ is 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 triangular numbers so far, for n > 0: a(n) = a(n-1) + Sum(A010054(a(k)): 0 <= k < n), see also A097602, A131073. - Reinhard Zumkeller, Nov 15 2012
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 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
a(n) = A014132(n,1) for n > 0. - Reinhard Zumkeller, Dec 12 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
a(n) = A228074(n+1,n). - Reinhard Zumkeller, Aug 15 2013
For n>3, a(n) is the number of length n binary words that have at least two 1's and at most two 0's. a(4) = 11 because we have: 0011, 0101, 0110, 0111, 1001, 1010, 1011, 1100, 1101, 1110, 1111. - Geoffrey Critzer, Jan 08 2014
For n > 0: A228446(a(n)) = 3. - Reinhard Zumkeller, Mar 12 2014
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
Partial sums of A028310. - J. Conrad, Oct 31 2016
|
|
|
REFERENCES
|
R. B. Banks, Slicing Pizzas, Racing Turtles and Further Adventures in Applied Mathematics, Princeton Univ. Press, 1999. See p. 24.
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 72, Problem 2.
H. E. Dudeney, Amusements in Mathematics, Nelson, London, 1917, page 177.
L. Hogben, Choice and Chance by Cardpack and Chessboard. Vol. 1, Chanticleer Press, NY, 1950, p. 22.
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.
A. 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).
W. A. Whitworth, DCC Exercises in Choice and Chance, Stechert, NY, 1945, p. 30.
A. M. Yaglom and I. 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
|
T. D. Noe, Table of n, a(n) for n = 0..1000
David Applegate and N. J. A. Sloane, The Gift Exchange Problem, arXiv:0907.0513 [math.CO], 2009.
J.-L. Baril, Classical sequences revisited with permutations avoiding dotted pattern, Electronic Journal of Combinatorics, 18 (2011), #P178.
J.-L. Baril, T. Mansour, A. Petrossian, Equivalence classes of permutations modulo excedances, preprint, Journal of Combinatorics, Volume 5 (2014) Number 4.
Jean-Luc Baril and Armen Petrossian, Equivalence classes of permutations modulo descents and left-to-right maxima, preprint, Pure Mathematics and Applications, Volume 25, Issue 1 (Sep 2015).
A. M. Baxter, L. K. Pudwell, Ascent sequences avoiding pairs of patterns, preprint, The Electronic Journal of Combinatorics, Volume 22, Issue 1 (2015) Paper #P1.58.
Christian Bean, A Claesson, H Ulfarsson, Simultaneous Avoidance of a Vincular and a Covincular Pattern of Length 3, arXiv preprint arXiv:1512.03226, 201
H. Bottomley, Illustration of initial terms
A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, arXiv:math/0112281 [math.CO], 2001.
A. Burstein and T. Mansour, Words restricted by 3-letter generalized multipermutation patterns, Annals. Combin., 7 (2003), 1-14.
Peter M. Chema, Illustration of first 22 terms as corners of a double square spiral with digital root.
David Coles, Triangle Puzzle.
K. Dilcher, K. B. Stolarsky, Nonlinear recurrences related to Chebyshev polynomials, The Ramanujan Journal, 2014, Online Oct. 2014, pp. 1-23. See Cor. 5.
I Dolinka, J East, RD Gray, Motzkin monoids and partial Brauer monoids, arXiv preprint arXiv:1512.02279, 2015. See Table 5.
Guo-Niu Han, Enumeration of Standard Puzzles [Cached copy]
Cheyne Homberger, Patterns in Permutations and Involutions: A Structural and Enumerative Approach, arXiv preprint 1410.2657 [math.CO], 2014.
C. Homberger, V. Vatter, On the effective and automatic enumeration of polynomial permutation classes, arXiv preprint arXiv:1308.4946 [math.CO], 2013-2015.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 386 [broken link?]
Milan Janjic, Two Enumerative Functions
Clark Kimberling, Complementary Equations, Journal of Integer Sequences, Vol. 10 (2007), Article 07.1.4.
Clark Kimberling and John E. Brown, Partial Complements and Transposable Dispersions, J. Integer Seqs., Vol. 7, 2004.
Kyu-Hwan Lee, Se-jin Oh, Catalan triangle numbers and binomial coefficients, arXiv:1601.06685 [math.CO], 2016.
D. Levin, L. Pudwell, M. Riehl, A. Sandberg, Pattern Avoidance on k-ary Heaps, Slides of Talk, 2014.
D. A. Lind, On a class of nonlinear binomial sums, Fib. Quart., 3 (1965), 292-298.
Jim Loy, Triangle Puzzle
T. Mansour, Permutations avoiding a set of patterns from S_3 and a pattern from S_4, arXiv:math/9909019 [math.CO], 1999.
J. W. Meijer and M. Nepveu, Euler's ship on the Pentagonal Sea, Acta Nova, Volume 4, No.1, December 2008. pp. 176-187.
Markus Moll, On a family of random noble means substitutions, Dr. Math. Dissertation, Universität Bielefeld, 2013.
Markus Moll, On a family of random noble means substitutions, arXiv:1312.5136 [math.DS], 2013.
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.
D. J. Price, Some unusual series occurring in n-dimensional geometry, Math. Gaz., 30 (1946), 149-150.
L. Pudwell, A. Baxter, Ascent sequences avoiding pairs of patterns, 2014.
N. Reading, On the structure of Bruhat Order, Ph.D. dissertation, University of Minnesota, April 2002.
N. Reading, Order Dimension, Strong Bruhat Order and Lattice Properties for Posets
N. Reading, Order Dimension, Strong Bruhat Order and Lattice Properties for Posets, Order, Vol. 19, no. 1 (2002), 73-100.
H. P. Robinson, Letter to N. J. A. Sloane, Aug 16 1971, with attachments
R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin., 6, 383-406, 1985; see Example 3.5.
N. J. A. Sloane, On single-deletion-correcting codes, 2002.
A. J. Turner, J. F. Miller, Recurrent Cartesian Genetic Programming Applied to Famous Mathematical Sequences, 2014.
Eric Weisstein's World of Mathematics, Circle Division by Lines
Eric Weisstein's World of Mathematics, Plane Division by Lines
Thomas Wieder, The number of certain k-combinations of an n-set, Applied Mathematics Electronic Notes, vol. 8 (2008).
Wikipedia, Floyd's triangle
Index entries for "core" sequences
Index entries for sequences related to centered polygonal numbers
Index entries for linear recurrences with constant coefficients, signature (3,-3,1).
|
|
|
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) = A000217(n) + 1.
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
Binomial(n+2,1)-2*binomial(n+1,1)+binomial(n+2,2). - Zerinvary Lajos, May 12 2006
a(n) = A086601(n)^(1/2). - Zerinvary Lajos, Apr 25 2008
From Thomas Wieder, Feb 25 2009: (Start)
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) = A034856(n+1) - A005843(n) = A000217(n) + A005408(n) - A005843(n). - Jaroslav Krizek, Sep 05 2009
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
a(n) = 1 + floor(n/2) + ceiling(n^2/2) = 1 + A004526(n) + A000982(n). - Wesley Ivan Hurt, Jun 14 2013
a(n) >= A263883(n) and a(n(n-1)/2) >= A055503(n). - Jonathan Sondow, Dec 01 2015
From Ilya Gutkovskiy, Jun 29 2016: (Start)
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) = (n+1)^2 - A000096(n). - Anton Zakharov, Jun 29 2016
a(n) = A101321(1,n). - R. J. Mathar, Jul 28 2016
|
|
|
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
|
A000124 := n-> n*(n+1)/2+1;
|
|
|
MATHEMATICA
|
FoldList[#1 + #2 &, 1, Range@ 50] (* Robert G. Wilson v, Feb 02 2011 *)
Accumulate[Range[0, 60]]+1 (* Harvey P. Dale, Mar 12 2013 *)
Select[Range[2000], IntegerQ[Sqrt[8 # - 7]] &] (* Vincenzo Librandi, Apr 16 2014 *)
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
-- Reinhard Zumkeller, Oct 04 2012, Nov 15 2011
(MAGMA) [n: n in [0..1500] | IsSquare(8*n-7)]; // Vincenzo Librandi, Apr 16 2014
|
|
|
CROSSREFS
|
Cf. A000096 Maximal number of pieces that can be obtained by cutting an annulus with n cuts, for n >= 1.
Slicing a cake: A000125, a bagel: A003600.
Partial sums =(A033547)/2, (A014206)/2.
The first 20 terms are also found in A025732 and A025739.
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.
Cf. A055469 Quasi-triangular primes.
|
|
|
KEYWORD
|
nonn,core,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A019538
|
|
Triangle of numbers T(n,k) = k!*Stirling2(n,k) read by rows (n >= 1, 1 <= k <= n).
|
|
+20
106
|
|
|
|
1, 1, 2, 1, 6, 6, 1, 14, 36, 24, 1, 30, 150, 240, 120, 1, 62, 540, 1560, 1800, 720, 1, 126, 1806, 8400, 16800, 15120, 5040, 1, 254, 5796, 40824, 126000, 191520, 141120, 40320, 1, 510, 18150, 186480, 834120, 1905120, 2328480, 1451520, 362880, 1, 1022, 55980
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
Number of ways n labeled objects can be distributed into k nonempty parcels. Also number of special terms in n variables with maximal degree k.
In older terminology these are called differences of 0. - Michael Somos, Oct 08 2003
Number of surjections (onto functions) from an n-element set to a k-element set.
Also coefficients (in ascending order) of so-called ordered Bell polynomials.
(k-1)!*Stirling2(n,k-1) is the number of chain topologies on an n-set having k open sets [Stephen].
Number of set compositions (ordered set partitions) of n items into k parts. Number of k dimensional 'faces' of the n dimensional permutohedron (see Simion, p. 162). - Mitch Harris, Jan 16 2007
Correction of comment before: Number of (n-k)-dimensional 'faces' of the permutohedron of order n (an (n-1)-dimensional polytope). - Tilman Piesk, Oct 29 2014
This array is related to the reciprocal of an e.g.f. as sketched in A133314. For example, the coefficient of the fourth order term in the Taylor series expansion of 1/(a(0) + a(1) x + a(2) x^2/2! + a(3) x^3/3! + ...) is a(0)^(-5) * {24 a(1)^4 - 36 a(1)^2 a(2) a(0) + [8 a(1) a(3) + 6 a(2)^2] a(0)^2 - a(4) a(0)^3}. The unsigned coefficients characterize the P3 permutohedron depicted on page 10 in the Loday link with 24 vertices (0-D faces), 36 edges (1-D faces), 6 squares (2-D faces), 8 hexagons (2-D faces) and 1 3-D permutohedron. Summing coefficients over like dimensions gives A019538 and A090582. Compare to A133437 for the associahedron. - Tom Copeland, Sep 29 2008, Oct 07 2008
Further to the comments of Tom Copeland above, the permutohedron of type A_3 can be taken as the truncated octahedron. Its dual is the tetrakis hexahedron, a simplicial polyhedron, with f-vector (1,14,36,24) giving the fourth row of this triangle. See the Wikipedia entry and [Fomin and Reading p. 21]. The corresponding h-vectors of permutohedra of type A give the rows of the triangle of Eulerian numbers A008292. See A145901 and A145902 for the array of f-vectors for type B and type D permutohedra respectively. - Peter Bala, Oct 26 2008
Subtriangle of triangle in A131689. - Philippe Deléham, Nov 03 2008
Since T(n,k) counts surjective functions and surjective functions are "consistent", T(n,k) satisfies a binomial identity, namely, T(n,x+y)=sum(C(n,j)*T(j,x)*T(n-j,y), j=0..n). For definition of consistent functions and a generalized binomial identity, see "Toy stories and combinatorial identities" in the link section below. - Dennis P. Walsh, Feb 24 2012
T(n,k) is the number of labeled forests on n+k vertices satisfying the following two conditions: (i) each forest consists of exactly k rooted trees with roots labeled 1, 2,...,k; (ii) every root has at least one child vertex. - Dennis P. Walsh, Feb 24 2012
The triangle is the inverse binomial transform of triangle A028246, deleting the left column and shifting up one row. - Gary W. Adamson, Mar 05 2012
See A074909 for associations among this array and the Bernoulli polynomials and their umbral compositional inverses. - Tom Copeland, Nov 14 2014
E.g.f. for the shifted signed polynomials is G(x,t) = (e^t-1)/[1+(1+x)(e^t-1)] = 1-(1+x)(e^t-1) + (1+x)^2(e^t-1)^2 - ... (see also A008292 and A074909), which has the infinitesimal generator g(x,u)d/du = [(1-x*u)(1-(1+x)u)]d/du, i.e., exp[t*g(x,u)d/du]u eval. at u=0 gives G(x,t), and dG(x,t)/dt=g(x,G(x,t)). The compositional inverse is log((1-xt)/(1-(1+x)t)). G(x,t) is a generating series associated to the generalized Hirzebruch genera. See the G. Rzadowski link for the relation of the derivatives of g(x,u) to solutions of the Riccatt differential equation, soliton solns. to the KdV equation, and the Eulerian and Bernoulli numbers. In addition A145271 connects products of derivatives of g(x,u) and the refined Eulerian numbers to the inverse of G(x,t), which gives the normalized, reverse face polynomials of the simplices (A135278, divided by n+1). See A028246 for the generator g(x,u)d/dx. - Tom Copeland, Nov 21 2014
For connections to toric varieties and Eulerian polynomials, see the Dolgachev and Lunts and the Stembridge links. - Tom Copeland, Dec 31 2015
See A008279 for a relation between the e.g.f.s enumerating the faces of permutahedra (this entry) and stellahedra. - Tom Copeland, Nov 14 2016
|
|
|
REFERENCES
|
A. T. Benjamin and J. J. Quinn, Proofs that really count: the art of combinatorial proof, M.A.A. 2003, p. 89, ex. 1; also p. 210.
Moussa Benoumhani, The number of topologies on a finite set, Preprint, 2005.
Miklos Bona, Combinatorics of Permutations, Chapman and Hall,2004, p.12.
G. Boole, A Treatise On The Calculus of Finite Differences, Dover Publications, 1960, p. 20.
H. T. Davis, Tables of the Mathematical Functions. Vols. 1 and 2, 2nd ed., 1963, Vol. 3 (with V. J. Fisher), 1962; Principia Press of Trinity Univ., San Antonio, TX, Vol. 2, p. 212.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, 1989, p. 155.
Kiran S. Kedlaya and Andrew V. Sutherland Computing L -Series of Hyperelliptic Curves in Algorithmic Number Theory Lecture Notes in Computer Science Volume 5011/2008
T. K. Petersen, Eulerian Numbers, Birkhauser, 2015, Section 5.6.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 33.
Mark Shattuck, Combinatorial proofs of some Stirling number formulas, Preprint (ResearchGate), 2014.
J. F. Steffensen, Interpolation, 2nd ed., Chelsea, NY, 1950, see p. 54.
A. H. Voigt, Theorie der Zahlenreihen und der Reihengleichungen, Goschen, Leipzig, 1911, p. 31.
E. Whittaker and G. Robinson, The Calculus of Observations, Blackie, London, 4th ed., 1949; p. 7.
|
|
|
LINKS
|
T. D. Noe, Rows n=1..100 of triangle, flattened
J. Fernando Barbero G., Jesús Salas, Eduardo J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. I. General Structure, arXiv:1307.2010 [math.CO], 2013.
J. F. Barbero G., J. Salas and E. J. S. Villaseñor, Bivariate Generating Functions for a Class of Linear Recurrences. II. Applications, arXiv preprint arXiv:1307.5624 [math.CO], 2013.
K. N. Boyadzhiev, A Series transformation formula and related polynomials, Int. J. Math. Math. Sc. 23 (2005), 3849-3866.
J. L. Chandon, J. LeMaire and J. Pouget, Dénombrement des quasi-ordres sur un ensemble fini, Math. Sci. Humaines, No. 62 (1978), 61-80.
T. Copeland, The Bernoulli polynomials and Hirzebruch's generalized Todd class
E. Delucchi, A. Pixton and L. Sabalka, Face vectors of subdivided simplicial complexes Discrete Math. 312 (2012), no. 2, 248--257. MR2852583 (2012j:05470). See p. 250. - N. J. A. Sloane, Apr 04 2014
I. Dolgachev and V. Lunts, A character formula for the representation of the Weyl group in the cohomology of the associated toric variety, Journal of Algebra, 168, 741-772, (1994).
S. Fomin, N. Reading, Root systems and generalized associahedra, Lecture notes for IAS/Park-City 2004. [From Peter Bala, Oct 26 2008]
M. Goebel, On the number of special permutation-invariant orbits and terms, in Applicable Algebra in Engin., Comm. and Comp. (AAECC 8), Volume 8, Number 6, 1997, pp. 505-509 (Lect. Notes Comp. Sci.)
M. Griffiths, I. Mezo, A generalization of Stirling Numbers of the Second Kind via a special multiset, JIS 13 (2010) #10.2.5
J. Gubeladze and J. Love, Vertex maps between simplices, cubes, and crosspolytopes, arXiv preprint arXiv:1304.3775 [math.CO], 2013.
Li Guo, Baxter algebras, Stirling numbers and partitions, arXiv:math/0402348 [math.AC], 2004.
M. Iida, On Triangle of numbers, Josai Mathematical Monographs, Vol. 5 (2012), 61-70;
Gábor Hetyei, The Stirling polynomial of a simplicial complex Discrete and Computational Geometry 35, Number 3, March 2006, pp 437-455. [From Peter Bala, Oct 28 2008]
Gábor Hetyei, Face enumeration using generalized binomial coefficients. Online draft version of the Hetyei paper referenced above. [From Peter Bala, Nov 10 2008]
Germain Kreweras, Une dualité élémentaire souvent utile dans les problèmes combinatoires, Mathématiques et Sciences Humaines 3 (1963): 31-41.
G. Kreweras, Les preordres totaux compatibles avec un ordre partiel, Math. Sci. Humaines No. 53 (1976), 5-30.
L. Liu, Y. Wang, A unified approach to polynomial sequences with only real zeros, arXiv:math/0509207 [math.CO], 2005-2006. [From Peter Bala, Oct 26 2008]
J. Loday, The Multiple Facets of the Associahedron [From Tom Copeland, Sep 29 2008]
MathOverflow, How many surjections are there from a set of size n? [From Tom Copeland, Sep 09 2015]
E. Mendelson, Races with Ties, Math. Mag. 55 (1982), 170-175.
T. S. Motzkin, Sorting numbers for cylinders and other classification numbers, in Combinatorics, Proc. Symp. Pure Math. 19, AMS, 1971, pp. 167-176. [Annotated, scanned copy]
OEIS Wiki, Sorting numbers
K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, Hierarchical Dobinski-type relations via substitution and the moment problem, arXiv:quant-ph/0312202, 2003.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260. [Annotated scanned copy]
G. Rzadkowski, Bernoulli numbers and solitons revisited, Journal of Nonlinear Mathematical Physics, 17:1, 121-126, DOI: 10.1142/S1402925110000635
R. Simion, Convex Polytopes and Enumeration, Adv. in Appl. Math. 18 (1997) pp. 149-180.
J. Stembridge, Some permuutation representations of Weyl groups associated with the cohomology of toric varieties, Adv. in Math., 106, 244-301, (1994).
D. Stephen, Topology on Finite Sets, American Mathematical Monthly, 75: 739 - 741, 1968.
S. M. Tanny, On some numbers related to the Bell numbers, Canad. Math. Bull. Vol. 17 (5), 733-738, 1975
A. H. Voigt, Theorie der Zahlenreihen und der Reihengleichungen, Goschen, Leipzig, 1911. [Annotated scans of pages 30-33 only]
D. P. Walsh, Toy stories and combinatorial identities
Wikipedia, Truncated octahedron [From Peter Bala, Oct 26 2008]
|
|
|
FORMULA
|
T(n, k) = k*(T(n-1, k-1)+T(n-1, k)) with T(0, 0) = 1 [or T(1, 1) = 1]. - Henry Bottomley, Mar 02 2001
E.g.f.: (y*(exp(x)-1) - exp(x))/(y*(exp(x)-1) - 1). - Vladeta Jovovic, Jan 30 2003
Equals [0, 1, 0, 2, 0, 3, 0, 4, 0, 5, ...] DELTA [1, 1, 2, 2, 3, 3, 4, 4, 5, 5, ...] where DELTA is Deléham's operator defined in A084938.
T(n, k) = Sum_{j=0..k} (-1)^(k-j)*j^n*binomial(k, j). - Mario Catalani (mario.catalani(AT)unito.it), Nov 28 2003. See Graham et al., eq. (6.19), p. 251. For a proof see Bert Seghers, Jun 29 2013.
Sum_{k=0..n} T(n, k)(-1)^(n-k) = 1, Sum_{k=0..n} T(n, k)(-1)^k = (-1)^n. - Mario Catalani (mario.catalani(AT)unito.it), Dec 11 2003
O.g.f. for n-th row: polylog(-n, x/(1+x))/(x+x^2). - Vladeta Jovovic, Jan 30 2005
E.g.f.: 1 / {1 + t[1-exp(x)]}. - Tom Copeland, Oct 13 2008
From Peter Bala, Oct 26 2008: (Start)
O.g.f. as a continued fraction: 1/(1 - x*t/(1 - (x + 1)*t/(1 - 2*x*t/(1 - 2*(x + 1)*t/(1 - ...))))) = 1 + x*t + (x + 2*x^2)*t^2 + (x + 6*x^2 + 6*x^3)*t^3 + ... .
The row polynomials R(n,x), which begin R(1,x) = x, R(2,x) = x + 2*x^2, R(3,x) = x + 6*x^2 + 6*x^3, satisfy the recurrence x*d/dx ((x + 1)*R(n,x)) = R(n+1,x). It follows that the zeros of R(n,x) are real and negative (apply Corollary 1.2 of [Liu and Wang]).
Since this is the triangle of f-vectors of the (simplicial complexes dual to the) type A permutohedra, whose h-vectors form the Eulerian number triangle A008292, the coefficients of the polynomial (x-1)^n*R(n,1/(x-1) give the n-th row of A008292. For example, from row 3 we have x^2 + 6*x + 6 = 1 + 4*y + y^2, where y = x + 1, producing [1,4,1] as the third row of A008292. The matrix product A008292 * A007318 gives the mirror image of this triangle (see A090582).
For n,k >= 0, T(n+1,k+1) = Sum_{j=0..k} (-1)^(k-j)*binomial(k,j)*[(j+1)^(n+1) - j^(n+1)]. The matrix product of Pascal's triangle A007318 with the current array gives (essentially) A047969. This triangle is also related to triangle A047969 by means of the S-transform of [Hetyei], a linear transformation of polynomials whose value on the basis monomials x^k is given by S(x^k) = binomial(x,k). The S-transform of the shifted n-th row polynomial Q(n,x) := R(n,x)/x is S(Q(n,x)) = (x+1)^n - x^n. For example, from row 3 we obtain S(1 + 6*x + 6*x^2) = 1 + 6*x + 6*x*(x-1)/2 = 1 + 3*x + 3*x^2 = (x+1)^3 - x^3. For fixed k, the values S(Q(n,k)) give the nonzero entries in column (k-1) of the triangle A047969 (the Hilbert transform of the Eulerian numbers). (End)
E.g.f.: (exp(x)-1)^k = sum T(n,k)x^n/n!. - Vladimir Kruchinin, Aug 10 2010
T(n,k) = Sum_{i=1...k} A(n,i)*Binomial(n-i,k-i) where A(n,i) is the number of n-permutations that have i ascending runs, A008292.
From Tom Copeland, Oct 11 2011: (Start)
With e.g.f.. A(x,t)= -1 + 1/(1+t*(1-exp(x)), the comp. inverse in x is
B(x,t)= log(((1+t)/t) - 1/(t(1+x))).
With h(x,t)= 1/(dB/dx)= (1+x)((1+t)(1+x)-1), the row polynomial P(n,t) is given by (h(x,t)*d/dx)^n x, eval. at x=0, A=exp(x*h(y,t)*d/dy) y, eval. at y=0, and dA/dx = h(A(x,t),t), with P(0,t)=0.
(A factor of -1/n! was removed by Copeland on Aug 25 2016). (End)
The term linear in x of [x*h(d/dx,t)]^n 1 gives the n-th row polynomial. (See A134685.) - Tom Copeland, Nov 07 2011
Row polynomials are given by D^n(1/(1-x*t)) evaluated at x = 0, where D is the operator (1+x)*d/dx. - Peter Bala, Nov 25 2011
T(n,x+y) = Sum_{j=0..n} binomial(n,j)*T(j,x)*T(n-j,y). - Dennis P. Walsh, Feb 24 2012
Let P be a Rota-Baxter operator of weight 1 satisfying the identity P(x)*P(y) = P(P(x)*y) + P(x*P(y)) + P(x*y). Then P(1)^2 = P(1) + 2*P^2(1). More generally, Guo shows that P(1)^n = Sum_{k=1..n} T(n,k)*P^k(1). - Peter Bala, Jun 08 2012
Sum_{i=1..n} (-1)^i*T(n,i)/i = 0, for n>1. - Leonid Bedratyuk, Aug 09 2012
T(n, k) = Sum_{j=0..k} (-1)^j*binomial(k, j)*(k-j)^n. [M. Catalani's re-indexed formula from Nov 28 2003] Proof: count the number of surjections of [n] onto [k] with the inclusion-exclusion principle, as an alternating sum of the number of functions from [n] to [k-j]. - Bert Seghers, Jun 29 2013
n-th row polynomial = 1/(1 + x)*( Sum_{k>=0} k^n*(x/(1 + x))^k ), valid for x in the open interval (-1/2, inf). See Tanny link. Cf. A145901. - Peter Bala, Jul 22 2014
T(n,k) = k * A141618(n,k-1) / binomial(n,k-1). - Tom Copeland, Oct 25 2014
Sum_{n=0..infinity} n^k*a^n = Sum_{i=1..k} (a / (1 - a))^i * T(k, i)/(1-a) for |a|<1. - David A. Corneth, Mar 09 2015
From Peter Bala, May 26 2015: (Start)
The row polynomials R(n,x) satisfy (1 + x)*R(n,x) = (-1)^n*x*R(n,-(1 + x)).
For a fixed integer k, the expansion of the function A(k,z) := exp( Sum_{n >= 1} R(n,k)*z^n/n ) has integer coefficients and satisfies the functional equation A(k,z)^(k + 1) = BINOMIAL(A(k,z))^k, where BINOMIAL(F(z))= 1/(1 - z)*F(z/(1 - z)) denotes the binomial transform of the o.g.f. F(z). Cf. A145901. For cases see A084784 (k = 1), A090352 (k = 2), A090355 (k = 3), A090357 (k = 4), A090362 (k = 5) and A084785 (k = -2 with z -> -z).
A(k,z)^(k + 1) = A(-(k + 1),-z)^k and hence BINOMIAL(A(k,z)) = A(-(k + 1),-z). (End)
From Tom Copeland, Oct 19 2016: (Start)
Let a(1) = 1 + x + B(1) = x + 1/2 and a(n) = B(n) = (B.)^n, where B(n) are the Bernoulli numbers defined by e^(B.t) = t / (e^t-1), then t / e^(a.t) = t / [(x + 1) * t + exp(B.t)] = (e^t - 1) /[ 1 + (x + 1) (e^t - 1)] = exp(p.(x)t), where (p.(x))^n = p_n(x) are the shifted, signed row polynomials of this array: p_0(x) = 0, p_1(x) = 1, p_2(x) = -(1 + 2 x), p_3(x) = 1 + 6 x + 6 x^2, ... and p_n(x) = n * b(n-1), where b(n) are the partition polynomials of A133314 evaluated with these a(n).
Sum_{n > 0} R(n,-1/2) x^n/n! = 2 * tanh(x/2), where R(n,x) = sum_{k = 1,..,n} T(n,k) x^(k-1) are the shifted row polynomials of this entry, so R(n,-1/2) = 4 * (2^(n+1)-1) B(n+1)/(n+1). (Cf. A000182.)
(End)
Also the Bernoulli numbers are given by B(n) = Sum_{k =1..n} (-1)^k T(n,k) / (k+1). - Tom Copeland, Nov 06 2016
|
|
|
EXAMPLE
|
The triangle T(n, k) begins:
n\k 1 2 3 4 5 6 7 8 9 10
1: 1
2: 1 2
3: 1 6 6
4: 1 14 36 24
5: 1 30 150 240 120
6: 1 62 540 1560 1800 720
7: 1 126 1806 8400 16800 15120 5040
8: 1 254 5796 40824 126000 191520 141120 40320
9: 1 510 18150 186480 834120 1905120 2328480 1451520 362880
10: 1 1022 55980 818520 5103000 16435440 29635200 30240000 16329600 3628800
... Reformatted and extended - Wolfdieter Lang, Oct 04 2014
---------------------------------------------------------------------------
T(4,1) = 1: {1234}. T(4,2) = 14: {1}{234} (4 ways), {12}{34} (6 ways), {123}{4} (4 ways). T(4,3) = 36: {12}{3}{4} (12 ways), {1}{23}{4} (12 ways), {1}{2}{34} (12 ways). T(4,4) = 1: {1}{2}{3}{4} (1 way).
|
|
|
MAPLE
|
with(combinat): A019538 := (n, k)->k!*stirling2(n, k);
|
|
|
MATHEMATICA
|
Table[k! StirlingS2[n, k], {n, 9}, {k, n}] // Flatten
|
|
|
PROG
|
(PARI) {T(n, k) = if( k<0 || k>n, 0, sum(i=0, k, (-1)^i * binomial(k, i) * (k-i)^n))}; /* Michael Somos, Oct 08 2003 */
(Haskell)
a019538 n k = a019538_tabl !! (n-1) !! (k-1)
a019538_row n = a019538_tabl !! (n-1)
a019538_tabl = iterate f [1] where
f xs = zipWith (*) [1..] $ zipWith (+) ([0] ++ xs) (xs ++ [0])
-- Reinhard Zumkeller, Dec 15 2013
(Sage) T(n, k) = factorial(k)*stirling_number2(n, k) # Danny Rorabaugh, Oct 10 2015
|
|
|
CROSSREFS
|
Row sums give A000670. Maximal terms in rows give A002869. Central terms T(2k-1,k) give A233734.
Diagonal is n! (A000142). 2nd diagonal is A001286. 3rd diagonal is A037960.
Cf. A000918, A000919, A001117, A001118, A008275, A008279, A048594, A059117, A059515, A074909, A084938.
Reflected version of A090582.
See also the two closely related triangles: A008277(n, k) = T(n, k)/k! (Stirling numbers of second kind) and A028246(n, k) = T(n, k)/k.
Cf. A033282 'faces' of the associahedron.
Cf. A008292, A047969, A145901, A145902. - Peter Bala, Oct 26 2008
Visible in the 3-D array in A249042.
Cf. A000182.
|
|
|
KEYWORD
|
nonn,tabl,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane, Manfred Goebel (goebel(AT)informatik.uni-tuebingen.de), Dec 11 1996
|
|
|
EXTENSIONS
|
Boole reference from Michael Somos, Oct 10 2003
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A000918
|
|
a(n) = 2^n - 2.
(Formerly M1599 N0625)
|
|
+20
96
|
|
|
|
-1, 0, 2, 6, 14, 30, 62, 126, 254, 510, 1022, 2046, 4094, 8190, 16382, 32766, 65534, 131070, 262142, 524286, 1048574, 2097150, 4194302, 8388606, 16777214, 33554430, 67108862, 134217726, 268435454, 536870910, 1073741822, 2147483646, 4294967294, 8589934590, 17179869182, 34359738366, 68719476734, 137438953470
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
For n > 3, a(n) is the expected number of tosses of a fair coin to get (n - 1) consecutive heads. - Pratik Poddar, Feb 04 2011
For n > 2, Sum_{k =1..a(n)} (-1)^binomial(n, k) = A064405(a(n)) + 1 = 0. - Benoit Cloitre, Oct 18 2002
For n > 0, the number of nonempty proper subsets of an n element set. - Ross La Haye, Feb 07 2004
Numbers n such that abs( Sum_{k=0..n} (-1)^binomial(n, k)*binomial(n + k, n - k) ) = 1. - Benoit Cloitre, Jul 03 2004
For n > 2 this formula also counts edge rooted forests in a cycle of length n. - Woong Kook (andrewk(AT)math.uri.edu), Sep 08 2004
For n >= 1, conjectured to be the number of integers from 0 to (10^n)-1 that lack 0, 1, 2, 3, 4, 5, 6 and 7 as a digit. - Alexandre Wajnberg, Apr 25 2005
Beginning with a(2) = 2, these are the partial sums of the subsequence of A000079 = 2^n beginning with A000079(1) = 2. Hence for n >= 2 a(n) is the smallest possible sum of exactly one prime, one two-almost prime, one three-almost prime, ... and one (n - 1)-almost prime. A060389 (partial sums of the primorials, A002110, beginning with A002110(1)=2) is the analog when all the almost primes must also be squarefree. - Rick L. Shepherd, May 20 2005
From the second term on (n >= 1), the binary representation of these numbers is a 0 preceded by (n - 1) 1's. This pattern (0)111...1110 is the "opposite" of the binary 2^n+1: 1000...0001 (cf. A000051). - Alexandre Wajnberg, May 31 2005
The numbers 2^n - 2 (n >= 2) give the positions of 0's in A110146. Also numbers n such that n^(n + 1) = 0 mod (n + 2). - Zak Seidov, Feb 20 2006
Partial sums of A155559. - Zerinvary Lajos, Oct 03 2007
Number of surjections from an n-element set onto a two-element set, with n >= 2. - Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Dec 15 2007
It appears that these are the numbers n such that 3*A135013(n) = n*(n + 1), thus answering Problem 2 on the Mathematical Olympiad Foundation of Japan, Final Round Problems, Feb 11 1993.
Let P(A) be the power set of an n-element set A and R be a relation on P(A) such that for all x, y of P(A), xRy if x is a proper subset of y or y is a proper subset of x and x and y are disjoint. Then a(n+1) = |R|. - Ross La Haye, Mar 19 2009
Apart the first term which is -1 the number of units of a(n) belongs to a periodic sequence: 0, 2, 6, 4. - Mohamed Bouhamida (bhmd95(AT)yahoo.fr), Sep 04 2009
The permutahedron Pi_n has 2^n - 2 facets [Pashkovich]. - Jonathan Vos Post, Dec 17 2009
First differences of A005803. - Reinhard Zumkeller, Oct 12 2011
For n >= 1, a(n + 1) is the smallest even number with bit sum n. Cf. A069532. - Jason Kimberley, Nov 01 2011
a(n) is the number of branches of a complete binary tree of n levels. - Denis Lorrain, Dec 16 2011
For n>=1, a(n) is the number of length-n words on alphabet {1,2,3} such that the gap(w)=1. For a word w the gap g(w) is the number of parts missing between the minimal and maximal elements of w. Generally for words on alphabet {1,2,...,m} with g(w)=g>0 the e.g.f. is: Sum_{k=g+2..m} (m - k + 1)*binomial((k - 2),g)*(exp(x) - 1)^(k - g). a(3)=6 because we have: 113, 131, 133, 311, 313, 331. Cf. A240506. See the Heubach/Mansour reference. - Geoffrey Critzer, Apr 13 2014
For n > 0, a(n) is the minimal number of internal nodes of a red-black tree of height 2*n-2. See the Oct 02 2015 comment under A027383. - Herbert Eberle, Oct 02 2015
Conjecture: For n>0, a(n) is the least m such that A007814(A000108(m)) = n-1. - L. Edson Jeffery, Nov 27 2015
|
|
|
REFERENCES
|
H. T. Davis, Tables of the Mathematical Functions. Vols. 1 and 2, 2nd ed., 1963, Vol. 3 (with V. J. Fisher), 1962; Principia Press of Trinity Univ., San Antonio, TX, Vol. 2, p. 212.
Ralph P. Grimaldi, Discrete and Combinatorial Mathematics: An Applied Introduction, Fifth Edition, Addison-Wesley, 2004, p. 134. [From Mohammad K. Azarian, October 27 2011]
S. Heubach and T. Mansour, Combinatorics of Compositions and Words, Chapman and Hall, 2009 page 86, Exercise 3.16.
Mathematical Olympiad Foundation of Japan, Final Round Problems, Feb 11 1993, Problem 2.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 33.
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).
A. H. Voigt, Theorie der Zahlenreihen und der Reihengleichungen, Goschen, Leipzig, 1911, p. 31.
|
|
|
LINKS
|
Vincenzo Librandi, Table of n, a(n) for n = 0..1000
O. Bagdasar, On some functions involving the lcm and gcd of integer tuples, Scientific Publications of the State University of Novi Pazar, Appl. Maths. Inform. and Mech., Vol. 6, 2 (2014), 91--100.
R. B. Campbell, The effect of inbreeding constraints and offspring distribution on time to the most recent common ancestor, Journal of Theoretical Biology, Volume 382, 7 October 2015, Pages 74-80.
Adam M. Goyt and Lara K. Pudwell, Avoiding colored partitions of two elements in the pattern sense, arXiv preprint arXiv:1203.3786 [math.CO], 2012. - From N. J. A. Sloane, Sep 17 2012
M. A. Hill, M. J. Hopkins and D. C. Ravenel, On the non-existence of elements of Kervaire invariant one [From N. J. A. Sloane, Sep 27 2010]
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 77
Milan Janjic, Enumerative Formulas for Some Functions on Finite Sets
M. Janjic and B. Petkovic, A Counting Function, arXiv 1301.4550 [math.CO], 2013.
Ross La Haye, Binary Relations on the Power Set of an n-Element Set, Journal of Integer Sequences, Vol. 12 (2009), Article 09.2.6.
T. Manneville, V. Pilaud, Compatibility fans for graphical nested complexes, arXiv preprint arXiv:1501.07152 [math.CO], 2015.
Kanstantsin Pashkovich, Symmetry in Extended Formulations of the Permutahedron, arXiv:0912.3446 [math.CO], 2009-2013. [Jonathan Vos Post, Dec 17 2009]
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260.
P. A. Piza, Kummer numbers, Mathematics Magazine, 21 (1947/1948), 257-260. [Annotated scanned copy]
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.
Pratik Poddar, Consecutive Heads Puzzle, Dec 2009
A. H. Voigt, Theorie der Zahlenreihen und der Reihengleichungen, Goschen, Leipzig, 1911. [Annotated scans of pages 30-33 only]
Eric Weisstein's World of Mathematics, Sphere Line Picking
Index entries for linear recurrences with constant coefficients, signature (3,-2)
|
|
|
FORMULA
|
a(n) = 2*A000225(n-1).
G.f.: 1/(1 - 2x) - 2/(1 - x), e.g.f.: (e^x - 1)^2 - 1. - Dan Fux (dan.fux(AT)OpenGaia.com or danfux(AT)OpenGaia.com), Apr 07 2001
For n >= 1, a(n) = A008970(n + 1, 2). - Philippe Deléham, Feb 21 2004
G.f.: (3*x - 1)/((2*x - 1)(x - 1)). - Simon Plouffe in his 1992 dissertation for the sequence without the leading -1
a(n) = 2a(n - 1) + 2. - Alexandre Wajnberg, Apr 25 2005
a(n) = A000079(n) - 2. - Omar E. Pol, Dec 16 2008
a(n) = A058896(n)/A052548(n). - Reinhard Zumkeller, Feb 14 2009
a(n) = A164874(n - 1, n - 1) for n > 1. - Reinhard Zumkeller, Aug 29 2009
a(n) = A173787(n,1); a(n) = A028399(2*n)/A052548(n), n > 0. - Reinhard Zumkeller, Feb 28 2010
a(n + 1) = A027383(2n - 1). - Jason Kimberley, Nov 02 2011
G.f.: U(0) -1 , where U(k) = 1 + x/(2^k + 2^k/(x - 1 - x^2*2^(k + 1)/(x*2^(k + 1) - (k + 1)/U(k + 1) ))); (continued fraction, 3rd kind, 4-step). - Sergei N. Gladkovskii, Dec 01 2012
a(n+1) = sum of row n in triangle A051601. - Reinhard Zumkeller, Aug 05 2013
a(n+1) = A127330(n,0). - Reinhard Zumkeller, Nov 16 2013
a(n) = Sum_{k=1..n-1} binomial(n, k) for n > 0. - Dan McCandless, Nov 14 2015
From Miquel Cerda, Aug 16 2016: (Start)
a(n) = A000225(n) - 1.
a(n) = A125128(n-1) - A000325(n).
a(n) = A095151(n) - A125128(n) - 1. (End)
|
|
|
MAPLE
|
seq(2^n-2, n=0..20) ;
[-1, seq(Stirling2(n, 2)*2, n=1..28)]; # Zerinvary Lajos, Dec 06 2006
ZL := [S, {S=Prod(B, B), B=Set(Z, 1 <= card)}, labeled]: [-1, seq(combstruct[count](ZL, size=n), n=1..28)]; # Zerinvary Lajos, Mar 13 2007
|
|
|
MATHEMATICA
|
Table[2^n - 2, {n, 0, 29}] (* Alonso del Arte, Dec 01 2012 *)
|
|
|
PROG
|
(Sage) [gaussian_binomial(n, 1, 2)-1 for n in xrange(0, 29)] # Zerinvary Lajos, May 31 2009
(PARI) a(n)=2^n-2 \\ Charles R Greathouse IV, Jun 16 2011
(MAGMA) [2^n - 2: n in [0..40]]; // Vincenzo Librandi, Jun 23 2011
(Haskell)
a000918 = (subtract 2) . (2 ^)
a000918_list = iterate ((subtract 2) . (* 2) . (+ 2)) (- 1)
-- Reinhard Zumkeller, Apr 23 2013
|
|
|
CROSSREFS
|
Row sums of triangle A026998.
Cf. A000919, A001117, A001118, A095121, A110146.
Cf. A033484, A000225, A000325, A095151, A125128.
|
|
|
KEYWORD
|
sign,easy,changed
|
|
|
AUTHOR
|
N. J. A. Sloane
|
|
|
EXTENSIONS
|
Maple programs fixed by Vaclav Kotesovec, Dec 13 2014
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A210000
|
|
Number of unimodular 2 X 2 matrices having all terms in {0,1,...,n}.
|
|
+20
96
|
|
|
|
0, 6, 14, 30, 46, 78, 94, 142, 174, 222, 254, 334, 366, 462, 510, 574, 638, 766, 814, 958, 1022, 1118, 1198, 1374, 1438, 1598, 1694, 1838, 1934, 2158, 2222, 2462, 2590, 2750, 2878, 3070, 3166, 3454, 3598, 3790, 3918, 4238, 4334, 4670, 4830
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
a(n) is the number of 2 X 2 matrices having all terms in {0,1,...,n} and inverses with all terms integers.
Most sequences in the following guide count 2 X 2 matrices having all terms contained in the domain shown in column 2 and determinant d or permanent p or sum s of terms as indicated in column 3.
A059306 ... {0,1,...,n} ..... d=0
A171503 ... {0,1,...,n} ..... d=1
A210000 ... {0,1,...,n} .... |d|=1
A209973 ... {0,1,...,n} ..... d=2
A209975 ... {0,1,...,n} ..... d=3
A209976 ... {0,1,...,n} ..... d=4
A209977 ... {0,1,...,n} ..... d=5
A210282 ... {0,1,...,n} ..... d=n
A210283 ... {0,1,...,n} ..... d=n-1
A210284 ... {0,1,...,n} ..... d=n+1
A210285 ... {0,1,...,n} ..... d=floor(n/2)
A210286 ... {0,1,...,n} ..... d=trace
A280588 ... {0,1,...,n} ..... d=s
A106634 ... {0,1,...,n} ..... p=n
A210288 ... {0,1,...,n} ..... p=trace
A210289 ... {0,1,...,n} ..... p=(trace)^2
A280934 ... {0,1,...,n} ..... p=s
A210290 ... {0,1,...,n} ..... d>=0
A183761 ... {0,1,...,n} ..... d>0
A210291 ... {0,1,...,n} ..... d>n
A210366 ... {0,1,...,n} ..... d>=n
A210367 ... {0,1,...,n} ..... d>=2n
A210368 ... {0,1,...,n} ..... d>=3n
A210369 ... {0,1,...,n} ..... d is even
A210370 ... {0,1,...,n} ..... d is odd
A210371 ... {0,1,...,n} ..... d is even and >=0
A210372 ... {0,1,...,n} ..... d is even and >0
A210373 ... {0,1,...,n} ..... d is odd and >0
A210374 ... {0,1,...,n} ..... s=n+2
A210375 ... {0,1,...,n} ..... s=n+3
A210376 ... {0,1,...,n} ..... s=n+4
A210377 ... {0,1,...,n} ..... s=n+5
A210378 ... {0,1,...,n} ..... t is even
A210379 ... {0,1,...,n} ..... t is odd
A211031 ... {0,1,...,n} ..... d is in [-n,n]
A211032 ... {0,1,...,n} ..... d is in (-n,n)
A211033 ... {0,1,...,n} ..... d=0 (mod 3)
A211034 ... {0,1,...,n} ..... d=1 (mod 3)
A209974 = (A209973)/4
A134506 ... {1,2,...,n} ..... d=0
A196227 ... {1,2,...,n} ..... d=1
A209979 ... {1,2,...,n} .... |d|=1
A197168 ... {1,2,...,n} ..... d=2
A210001 ... {1,2,...,n} ..... d=3
A210002 ... {1,2,...,n} ..... d=4
A210027 ... {1,2,...,n} ..... d=5
A209978 = (A196227)/2
A209980 = (A197168)/2
A211053 ... {1,2,...,n} ..... d=n
A211054 ... {1,2,...,n} ..... d=n-1
A211055 ... {1,2,...,n} ..... d=n+1
A055507 ... {1,2,...,n} ..... p=n
A211057 ... {1,2,...,n} ..... d is in [0,n]
A211058 ... {1,2,...,n} ..... d>=0
A211059 ... {1,2,...,n} ..... d>0
A211060 ... {1,2,...,n} ..... d>n
A211061 ... {1,2,...,n} ..... d>=n
A211062 ... {1,2,...,n} ..... d>=2n
A211063 ... {1,2,...,n} ..... d>=3n
A211064 ... {1,2,...,n} ..... d is even
A211065 ... {1,2,...,n} ..... d is odd
A211066 ... {1,2,...,n} ..... d is even and >=0
A211067 ... {1,2,...,n} ..... d is even and >0
A211068 ... {1,2,...,n} ..... d is odd and >0
A209981 ... {-n,....,n} ..... d=0
A209982 ... {-n,....,n} ..... d=1
A209984 ... {-n,....,n} ..... d=2
A209986 ... {-n,....,n} ..... d=3
A209988 ... {-n,....,n} ..... d=4
A209990 ... {-n,....,n} ..... d=5
A211140 ... {-n,....,n} ..... d=n
A211141 ... {-n,....,n} ..... d=n-1
A211142 ... {-n,....,n} ..... d=n+1
A211143 ... {-n,....,n} ..... d=n^2
A211140 ... {-n,....,n} ..... p=n
A211145 ... {-n,....,n} ..... p=trace
A211146 ... {-n,....,n} ..... d in [0,n]
A211147 ... {-n,....,n} ..... d>=0
A211148 ... {-n,....,n} ..... d>0
A211149 ... {-n,....,n} ..... d<0 or d>0
A211150 ... {-n,....,n} ..... d>n
A211151 ... {-n,....,n} ..... d>=n
A211152 ... {-n,....,n} ..... d>=2n
A211153 ... {-n,....,n} ..... d>=3n
A211154 ... {-n,....,n} ..... d is even
A211155 ... {-n,....,n} ..... d is odd
A211156 ... {-n,....,n} ..... d is even and >=0
A211157 ... {-n,....,n} ..... d is even and >0
A211158 ... {-n,....,n} ..... d is odd and >0
|
|
|
LINKS
|
Table of n, a(n) for n=0..44.
|
|
|
FORMULA
|
a(n) = 2*A171503(n).
|
|
|
EXAMPLE
|
a(2)=6 counts these matrices (using reduced matrix notation):
(1,0,0,1), determinant = 1, inverse = (1,0,0,1)
(1,0,1,1), determinant = 1, inverse = (1,0,-1,1)
(1,1,0,1), determinant = 1, inverse = (1,-1,0,1)
(0,1,1,0), determinant = -1, inverse = (0,1,1,0)
(0,1,1,1), determinant = -1, inverse = (-1,1,1,0)
(1,1,1,0), determinant = -1, inverse = (0,1,1,-1)
|
|
|
MATHEMATICA
|
a = 0; b = n; z1 = 50;
t[n_] := t[n] = Flatten[Table[w*z - x*y, {w, a, b}, {x, a, b}, {y, a, b}, {z, a, b}]]
c[n_, k_] := c[n, k] = Count[t[n], k]
Table[c[n, 0], {n, 0, z1}] (* A059306 *)
Table[c[n, 1], {n, 0, z1}] (* A171503 *)
2 % (* A210000 *)
Table[c[n, 2], {n, 0, z1}] (* A209973 *)
%/4 (* A209974 *)
Table[c[n, 3], {n, 0, z1}] (* A209975 *)
Table[c[n, 4], {n, 0, z1}] (* A209976 *)
Table[c[n, 5], {n, 0, z1}] (* A209977 *)
|
|
|
CROSSREFS
|
Cf. A171503.
See also the very useful list of cross-references in the Comments section.
|
|
|
KEYWORD
|
nonn,changed
|
|
|
AUTHOR
|
Clark Kimberling, Mar 16 2012
|
|
|
EXTENSIONS
|
A209982 added to list in comment by Chai Wah Wu, Nov 27 2016
|
|
|
STATUS
|
approved
|
| |
|
|
| |
| |
|
|
|
4, 6, 10, 14, 22, 26, 34, 38, 46, 58, 62, 74, 82, 86, 94, 106, 118, 122, 134, 142, 146, 158, 166, 178, 194, 202, 206, 214, 218, 226, 254, 262, 274, 278, 298, 302, 314, 326, 334, 346, 358, 362, 382, 386, 394, 398, 422, 446, 454, 458, 466, 478, 482, 502, 514, 526
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
Essentially the same as A001747.
Twice the prime numbers. - Omar E. Pol, May 14 2008
An alternative sequence that gives A100484 functionally: a(n) = Length[IntegerDigits[(2^Prime[n] - 1)*(2^Prime[n] + 1), 2]]. - Roger L. Bagula and Artur Jasinski, Nov 28 2008
Semiprimes of the form m*k such that m/(k-1) is prime. - Juri-Stepan Gerasimov, May 21 2010
Right edge of the triangle in A065342. - Reinhard Zumkeller, Jan 30 2012
Solutions of the differential equation n' = 1/2*(n+4), where n' is the arithmetic derivative of n. - Paolo P. Lava, Feb 02 2012
A253046(a(n)) > a(n). - Reinhard Zumkeller, Dec 26 2014
|
|
|
LINKS
|
Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Semiprime
|
|
|
FORMULA
|
a(n) = 2 * A000040(n).
a(n) = A001747(n+1).
n>1: A000005(a(n))=4; A000203(a(n))=3*A008864(n); A000010(a(n))=A006093(n); intersection of A001358 and A005843.
a(n) = A116366(n-1, n-1) for n>1. - Reinhard Zumkeller, Feb 06 2006
a(n) = A077017(n+1), n>1. - R. J. Mathar, Sep 02 2008
A078834(a(n)) = A000040(n). - Reinhard Zumkeller, Sep 19 2011
a(n) = A087112(n, 1). - Reinhard Zumkeller, Nov 25 2012
A000203(a(n)) = 3*n/2 + 3, n > 1. - Wesley Ivan Hurt, Sep 07 2013
|
|
|
MAPLE
|
A100484:=n->2*ithprime(n); seq(A100484(n), n=1..100); # Wesley Ivan Hurt, Mar 27 2014
|
|
|
MATHEMATICA
|
Prime[Range[22]]*2 (* Vladimir Joseph Stephan Orlovsky, Apr 29 2008 *)
|
|
|
PROG
|
(PARI) 2*primes(100) \\ Charles R Greathouse IV, Aug 21 2011
(Haskell)
a100484 n = a100484_list !! (n-1)
a100484_list = map (* 2) a000040_list
-- Reinhard Zumkeller, Jan 31 2012
(MAGMA) [2*p: p in PrimesUpTo(300)]; // Vincenzo Librandi, Mar 27 2014
|
|
|
CROSSREFS
|
Subsequence of A091376.
Cf. A046315, A152099, A179740.
Cf. A001748, A253046.
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
Reinhard Zumkeller, Nov 22 2004
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A191113
|
|
Increasing sequence generated by these rules: a(1)=1, and if x is in a then 3x-2 and 4x-2 are in a.
|
|
+20
80
|
|
|
|
1, 2, 4, 6, 10, 14, 16, 22, 28, 38, 40, 46, 54, 62, 64, 82, 86, 110, 112, 118, 136, 150, 158, 160, 182, 184, 190, 214, 244, 246, 254, 256, 326, 328, 334, 342, 352, 406, 438, 446, 448, 470, 472, 478, 542, 544, 550, 568, 598, 630, 638, 640, 726, 730, 734, 736, 758, 760, 766, 854, 974, 976, 982, 1000, 1014, 1022, 1024, 1054, 1216
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
This sequence represents a class of sequences generated by rules of the form "a(1)=1, and if x is in a then hx+i and jx+k are in a, where h,i,j,k are integers." If m>1, at least one of the numbers b(m)=(a(m)-i)/h and c(m)=(a(m)-k)/j is in the set N of natural numbers. Let d(n) be the n-th b(m) in N, and let e(n) be the n-th c(m) in N. Note that a is a subsequence of both d and e. Examples:
A191113: (h,i,j,k)=(3,-2,4,-2); d=A191146, e=A191149
A191114: (h,i,j,k)=(3,-2,4,-1); d=A191151, e=A191121
A191115: (h,i,j,k)=(3,-2,4,0); d=A191113, e=A191154
A191116: (h,i,j,k)=(3,-2,4,1); d=A191155 e=A191129
A191117: (h,i,j,k)=(3,-2,4,2); d=A191157, e=A191158
A191118: (h,i,j,k)=(3,-2,4,3); d=A191114, e=A191138
...
A191119: (h,i,j,k)=(3,-1,4,-3); d=A191120, e=A191163
A191120: (h,i,j,k)=(3,-1,4,-2); d=A191129, e=A191165
A191121: (h,i,j,k)=(3,-1,4,-1); d=A191166, e=A191167
A191122: (h,i,j,k)=(3,-1,4,0); d=A191168, e=A191169
A191123: (h,i,j,k)=(3,-1,4,1); d=A191170, e=A191171
A191124: (h,i,j,k)=(3,-1,4,2); d=A191172, e=A191173
A191125: (h,i,j,k)=(3,-1,4,3); d=A191174, e=A191175
...
A191126: (h,i,j,k)=(3,0,4,-3); d=A191128, e=A191177
A191127: (h,i,j,k)=(3,0,4,-2); d=A191178, e=A191179
A191128: (h,i,j,k)=(3,0,4,-1); d=A191180, e=A191181
A025613: (h,i,j,k)=(3,0,4,0); d=e=A025613
A191129: (h,i,j,k)=(3,0,4,1); d=A191182, e=A191183
A191130: (h,i,j,k)=(3,0,4,2); d=A191184, e=A191185
A191131: (h,i,j,k)=(3,0,4,3); d=A191186, e=A191187
...
A191132: (h,i,j,k)=(3,1,4,-3); d=A191135, e=A191189
A191133: (h,i,j,k)=(3,1,4,-2); d=A191190, e=A191191
A191134: (h,i,j,k)=(3,1,4,-1); d=A191192, e=A191193
A191135: (h,i,j,k)=(3,1,4,0); d=A191136, e=A191195
A191136: (h,i,j,k)=(3,1,4,1); d=A191196, e=A191197
A191137: (h,i,j,k)=(3,1,4,2); d=A191198, e=A191199
A191138: (h,i,j,k)=(3,1,4,3); d=A191200, e=A191201
...
A191139: (h,i,j,k)=(3,2,4,-3); d=A191143, e=A191119
A191140: (h,i,j,k)=(3,2,4,-2); d=A191204, e=A191205
A191141: (h,i,j,k)=(3,2,4,-1); d=A191206, e=A191207
A191142: (h,i,j,k)=(3,2,4,0); d=A191208, e=A191209
A191143: (h,i,j,k)=(3,2,4,1); d=A191210, e=A191136
A191144: (h,i,j,k)=(3,2,4,2); d=A191212, e=A191213
A191145: (h,i,j,k)=(3,2,4,3); d=e=A191145
...
Representative divisibility properties:
if s=A191116, then 2|(s+1), 4|(s+3), and 8|(s+3) for n>1; if s=A191117, then 10|(s+4) for n>1.
For lists of other "rules sequences" see A190803 (h=2 and j=3) and A191106 (h=j=3).
|
|
|
LINKS
|
Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
David Garth and Adam Gouge, Affinely Self-Generating Sets and Morphisms, Journal of Integer Sequences, Article 07.1.5, 10 (2007) 1-13.
|
|
|
FORMULA
|
a(1)=1, and if x is in a then 3x-2 and 4x-2 are in a; the terms of a are listed in without repetitions, in increasing order.
|
|
|
EXAMPLE
|
1 -> 2 -> 4,6 -> 10,14,16,22 ->
|
|
|
MAPLE
|
N:= 2000: # to get all terms <= N
S:= {}: agenda:= {1}:
while nops(agenda) > 0 do
S:= S union agenda;
agenda:= select(`<=`, map(t -> (3*t-2, 4*t-2), agenda) minus S, N)
od:
sort(convert(S, list)); # Robert Israel, Dec 22 2015
|
|
|
MATHEMATICA
|
h = 3; i = -2; j = 4; k = -2; f = 1; g = 8;
a = Union[Flatten[NestList[{h # + i, j # + k} &, f, g]]]
(* a=A191113; regarding g, see the Mathematica note at A190803 *)
b = (a + 2)/3; c = (a + 2)/4; r = Range[1, 900];
d = Intersection[b, r] (* A191146 *)
e = Intersection[c, r] (* A191149 *)
m = a/2 (* divisibility property *)
|
|
|
PROG
|
(Haskell)
import Data.Set (singleton, deleteFindMin, insert)
a191113 n = a191113_list !! (n-1)
a191113_list = 1 : f (singleton 2)
where f s = m : (f $ insert (3*m-2) $ insert (4*m-2) s')
where (m, s') = deleteFindMin s
-- Reinhard Zumkeller, Jun 01 2011
|
|
|
CROSSREFS
|
Cf. A190803, A191106.
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
Clark Kimberling, May 27 2011
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A024675
|
|
Average of two consecutive odd primes.
|
|
+20
73
|
|
|
|
4, 6, 9, 12, 15, 18, 21, 26, 30, 34, 39, 42, 45, 50, 56, 60, 64, 69, 72, 76, 81, 86, 93, 99, 102, 105, 108, 111, 120, 129, 134, 138, 144, 150, 154, 160, 165, 170, 176, 180, 186, 192, 195, 198, 205, 217, 225, 228, 231, 236, 240, 246, 254, 260, 266, 270, 274, 279, 282, 288, 300
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,1
|
|
|
COMMENTS
|
Sometimes called interprimes.
Where local maxima of A072681 occur: A072681(a(n))=A074927(n+1). - Reinhard Zumkeller, Mar 04 2009
Never prime, for that would contradict the definition. - Jon Perry, Dec 05 2012
A subset of A145025, obtained from that sequence by omitting the primes (which are barycenter of their neighboring primes). - M. F. Hasler, Jun 01 2013
|
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Interprime
|
|
|
FORMULA
|
a(n) = (prime(n+1)+prime(n+2))/2 = A001043(n+1)/2. - Omar E. Pol, Feb 02 2012
Conjecture: a(n) = ceiling(sqrt(prime(n+1)*prime(n+2))). - Thomas Ordowski, Mar 22 2013
Equals A145025 \ A006562 = A145025 \ A000040. - M. F. Hasler, Jun 01 2013
|
|
|
MAPLE
|
seq( ( (ithprime(x)+ithprime(x+1))/2 ), x=2..40);
|
|
|
MATHEMATICA
|
Plus @@@ Partition[Table[Prime[n], {n, 2, 100}], 2, 1]/2
ListConvolve[{1, 1}/2, Prime /@ Range[2, 70]] (* Jean-François Alcover, Jun 25 2013 *)
|
|
|
PROG
|
(PARI) for(X=2, 50, print((prime(X)+prime(X+1))/2)) \\ Hauke Worpel (thebigh(AT)outgun.com), May 08 2008
(PARI) first(n)=my(v=primes(n+2)); vector(n, i, v[i+1]+v[i+2])/2 \\ Charles R Greathouse IV, Jun 25 2013
|
|
|
CROSSREFS
|
Cf. A072568, A072569. Bisections give A058296, A079424.
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
Clark Kimberling
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A117816
|
|
Number of steps until the RADD sequence T(k+1) = n + R(T(k)), T(0) = 1, enters a cycle; -1 if no cycle is ever reached. (R=A004086: reverse digits)
|
|
+20
73
|
|
|
|
1, 1, 1, 1, 1, 1, 1, 1, 1, -1, 1, 2, 31, 15, -1, 721, 9, 1, 6, -1, 3, 5, 28, 29, 131, 23, 1, 31, 6, -1, 1, 19, 1, 53, 4, 406, 34, 254, 8, -1, 3, 245, 1, 3, 2, 422, 42, 308, 1, -1, 2, 2, 49, 1, 1371, 13, 1, 1, 2, -1, 78, 65, 1, 809, 1575, 5, 43, 31, 2, -1, 33, 2, 21, 192, 857, 91, 1, 2, 2, -1, 2, 491, 1, 2, 1, 81, 49, 1, 2, -1, 35, 197, 72, 1, 12, 79, 1, 6004, 1, -1, 52, 10264, 9, 28, 2, 2, 1, 427, 1, -1, 1, 1, 49, 167
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,12
|
|
|
COMMENTS
|
Comments following discussions with David Applegate, May 05 2006: (Start)
Certainly a(10) = -1 and probably a(n) is always -1 if n is a multiple of 10. Furthermore a(15) is almost certainly -1: T_15 has not reached a cycle in 10^7 terms (see A118532).
(End)
If n is a multiple of 10 the operation can never generate a trailing zero and so is reversible. So it loops only if it returns to the start, which is impossible. Hence a(10k) = -1. - Martin Fuller, May 12 2006
I suspect a(115) = 385592406, A117817(115) = 79560. Can someone confirm? - Martin Fuller, May 12 2006
The map f: x -> R(x)+n is injective, f(x)=f(y) <=> R(x)=R(y) <=> x=y, unless x or y only differ in trailing zeros. For n=10k, however, trailing zeros can never occur. (This also implies that the terms are of increasing length.) Thus, for n=10k, no number can occur twice in the orbit of 1 under f, i.e., a(10k)=-1. A sketch of proof for a(15)=-1 is given in A118532. As of today, no other n with a(n)=-1 seems to be known. - M. F. Hasler, May 06 2012
|
|
|
LINKS
|
Table of n, a(n) for n=1..114.
N. J. A. Sloane and others, Sequences of RADD type, OEIS wiki.
|
|
|
EXAMPLE
|
T_2 enters a cycle of length 81 after 1 step.
|
|
|
MATHEMATICA
|
ReverseNum[n_] := FromDigits[Reverse[IntegerDigits[n]]]; maxLen=10000; Table[z=1; lst={1}; While[z=ReverseNum[z]+n; !MemberQ[lst, z] && Length[lst]<maxLen, AppendTo[lst, z]]; If[Length[lst]<maxLen, Position[lst, z][[1, 1]]-1, -1], {n, 100}] (* T. D. Noe *)
|
|
|
PROG
|
(PARI) A117816(n, L=10^5, S=1)={ for(F=0, 1, my(u=Vecsmall(S)); while(L-- & #u<#u=vecsort(concat(u, Vecsmall(S=A004086(S)+n)), , 8), ); L || F=1; /* 1st run counts until repetition, now subtract cycle length */ F || L=1+#u); L-1}
|
|
|
CROSSREFS
|
For T_1, T_2, ..., T_16 (omitting T_9, which is uninteresting) see A117230, A117521, A118517, A117828, A117800, A118525, A118526, A118527, A117841, A118528, A118529, A118530, A118531, A118532, A118533.
Cf. A117817.
|
|
|
KEYWORD
|
sign,base
|
|
|
AUTHOR
|
N. J. A. Sloane, following discussions with Luc Stevens, May 04 2006
|
|
|
EXTENSIONS
|
a(21)-a(33) from Luc Stevens, May 08 2006
a(33) onwards from T. D. Noe, May 10 2006
Further terms from Martin Fuller, May 12 2006
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A259934
|
|
Infinite sequence starting with a(0)=0 such that A049820(a(k)) = a(k-1) for all k>=1, where A049820(n) = n - (number of divisors of n).
|
|
+20
63
|
|
|
|
0, 2, 6, 12, 18, 22, 30, 34, 42, 46, 54, 58, 62, 70, 78, 90, 94, 102, 106, 114, 118, 121, 125, 129, 144, 152, 162, 166, 174, 182, 190, 194, 210, 214, 222, 230, 236, 242, 250, 254, 270, 274, 282, 294, 298, 302, 310, 314, 330, 342, 346, 354, 358, 366, 374, 390, 394, 402, 410, 418, 426, 434, 442, 446, 462, 466, 474, 486, 494, 510, 522, 530, 546, 558, 562, 566, 574, 582, 590
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
Equivalently, satisfies the property: A000005(a(n)) = a(n)-a(n-1). The first differences a(n)-a(n-1) are given in A259935.
Falcao (2015) proved that such an infinite sequence exists. Numerical evidence suggests that it may be also unique -- is it? All terms below 10^10 are defined uniquely.
If the current definition does not uniquely define the sequence, the "lexicographically earliest" condition may be added to make the sequence well-defined.
From Vladimir Shevelev, Jul 21 2015: (Start)
If a(k), a(k+1), a(k+2) is an arithmetic progression, then a(k+1) is in A175304.
Indeed, by the definition of this sequence, a(n)-a(n-1) = d(a(n)), for all n>=1, where d(n) = A000005(n). Hence, have a(k+1) - a(k) = a(k+2) - a(k+1) = d(a(k+1)) = d(a(k+2)). So a(k+1) + d(a(k+2)) = a(k+2) and a(k+1) + d(a(k+1)) = a(k+2).
Therefore, d(a(k+1) + d(a(k+1))) = d(a(k+2))= d(a(k+1)), i.e., a(k+1) is in A175304. Thus, if there are infinitely many pairs of the same consecutive terms of A259935, then A175304 is infinite (see there my conjecture). (End)
From Antti Karttunen, Nov 27 2015: (Start)
If multiple apparently infinite branches would occur at some point of computing, then even if the "lexicographically earliest" condition were then added to the definition, it would not help us much (when computing the sequence), as we would still not know which of the said branches were truly infinite. [See also Max Alekseyev's latter Jul 9 2015 posting on SeqFan-list, where he notes the same thing.] Note that many of the derived sequences tacitly assume that the uniqueness-conjecture is true. See also comments at A262693 and A262896.
One sufficient (but not a necessary) condition for the uniqueness of this sequence is that the sequence A262509 has infinite number of terms. Please see further comments there.
The graph of sequence exhibits two markedly different slopes, depending on whether it is on the "fast lane" of A049820 (even numbers) or the "slow lane" [odd numbers, for example when traversing the 1356 odd terms from 123871 to 113569 at range a(9859) .. a(8504)]. See A263086/A263085 for the "average cumulative speed difference" between the lanes. In general, slow and fast lane stay separate, except when they terminate into one of the squares (A262514) that work as "exchange ramps", forcing the parity (and thus the speed) to change. In average, the odd squares are slightly better than the even squares in attracting lanes going towards smaller numbers (compare A263253 to A263252). The cumulative effect of this bias is that the odd terms are much rarer in this sequence than the even terms (compare A263278 to A262516).
(End)
|
|
|
LINKS
|
Robert Israel, Table of n, a(n) for n = 0..64800
M. Alekseyev et al., Apparently unique infinite sequences related to the sum of divisors, Discussion in SeqFan mailing list, 2015.
Michael De Vlieger, Poster illustrating A259934 and A263267
Falcao et al., Sequence and divisors, 2015. (in Russian)
|
|
|
FORMULA
|
From Antti Karttunen, Nov 27 2015: (Start)
Other identities and observations. For all n >= 0:
a(n) = A262679(A262896(n)).
A155043(a(n)) = A262694(a(n)) = A262904(a(n)) = n.
A261089(n) <= a(n) <= A262503(n). [A261103 and A262506 give the distances of a(n) to these bounds.]
(End)
|
|
|
MAPLE
|
N:= 10^4: # to get "guaranteed unique" terms <= N
S:= Vector(N, datatype=integer[1]):
for n from N+1 to 2*N do
k:= n - numtheory:-tau(n);
if k <= N then S[k]:= S[k]+1; B[k]:= n; fi;
od:
for n from N to 3 by -1 do
if S[n] >= 1 then
k:= n - numtheory:-tau(n);
S[k]:= S[k]+1; B[k]:= n;
fi
od:
A[0]:= 0: A[1]:= 2:
for n from 2 do
b:= B[A[n-1]];
if b > N or S[b] > 1 then break fi;
A[n]:= b;
od:
seq(A[i], i=0..n-1); # Robert Israel, Jul 09 2015
|
|
|
MATHEMATICA
|
NN = 10^4; (* to get "guaranteed unique" terms <= NN *)
Clear[A, B, S]; S[_]=0; For[n = NN+1, n <= 2*NN, n++, k = n-DivisorSigma[0, n]; If[k <= NN, S[k] = S[k]+1; B[k]=n]]; For[n=NN, n >= 3, n--, If[S[n] >= 1 , k = n-DivisorSigma[0, n]; S[k] = S[k]+1; B[k]=n]]; A[0]=0; A[1]=2; For[n=2, True, n++, b = B[A[n-1]]; If[b>NN || S[b]>1, Break[]]; A[n]=b]; Table[A[i], {i, 0, n-1}] (* Jean-François Alcover, Jul 22 2015, after Robert Israel *)
|
|
|
CROSSREFS
|
Cf. A000005, A049820, A060990, A259935 (first differences).
Topmost row of A263255. Cf. also irregular tables A263267 & A263265 and array A262898.
Cf. A262693 (characteristic function).
Cf. A155043, A262694, A262904 (left inverses).
Cf. A262514 (squares present), A263276 (their positions), A263277.
Cf. A262517 (odd terms).
Cf. A262509, A262510, A262897 (other subsequences).
Cf. also A175304, A260257, A262680.
Cf. A261089, A261103, A262503, A262506, A262516, A263279, A263280, A263085, A263086, A263253, A263257, A263278.
Cf. also A262679, A262896 (see the C++ program there).
No common terms with A045765 or A262903.
Positions of zeros in A262522, A262695, A262696, A262697, A263254.
Various metrics concerning finite side-trees: A262888, A262889, A262890.
Cf. also A262891, A262892 and A262895 (cf. its graph).
Cf. A260084, A260124 (variants).
Cf. also A179016 (a similar "beanstalk trunk sequence" but with more tractable and regular behavior).
|
|
|
KEYWORD
|
nonn,nice
|
|
|
AUTHOR
|
Max Alekseyev, Jul 09 2015
|
|
|
STATUS
|
approved
|
| |
|
|
| |
|
|
A003278
|
|
Szekeres's sequence: a(n)-1 in ternary = n-1 in binary; also: a(1) = 1, a(2) = 2, a(n) is smallest number k which avoids any 3-term arithmetic progression in a(1), a(2), ..., a(n-1), k.
(Formerly M0975)
|
|
+20
59
|
|
|
|
1, 2, 4, 5, 10, 11, 13, 14, 28, 29, 31, 32, 37, 38, 40, 41, 82, 83, 85, 86, 91, 92, 94, 95, 109, 110, 112, 113, 118, 119, 121, 122, 244, 245, 247, 248, 253, 254, 256, 257, 271, 272, 274, 275, 280, 281, 283, 284, 325, 326, 328, 329, 334, 335, 337, 338, 352, 353
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
That is, there are no three elements A, B and C such that B - A = C - B.
Difference sequence related to Gray code bit sequence (A001511). The difference patterns follows a similar repeating pattern (ABACABADABACABAE...), but each new value is the sum of the previous values, rather than simply 1 more than the maximum of the previous values. - Hal Burch (hburch(AT)cs.cmu.edu), Jan 12 2004
Sums of distinct powers of 3, translated by 1.
Positions of 0 in A189820; complement of A189822. - Clark Kimberling, May 26 2011
Also, Stanley sequence S(1): see OEIS index to Stanley sequences. - M. F. Hasler, Jan 18 2016
|
|
|
REFERENCES
|
S. R. Finch, Mathematical Constants, Cambridge, 2003, p. 164.
R. K. Guy, Unsolved Problems in Number Theory, E10.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
David W. Wilson, Table of n, a(n) for n = 1..10000 a(1..1024) from T. D. Noe
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
J.-P. Allouche and J. Shallit, The ring of k-regular sequences, Theoretical Computer Sci., 98 (1992), 163-197.
P. Erdős and P. Turan, On some sequences of integers, J. London Math. Soc., 11 (1936), 261-264.
Joseph Gerver, James Propp and Jamie Simpson, Greedily partitioning the natural numbers into sets free of arithmetic progressions Proc. Amer. Math. Soc. 102 (1988), no. 3, 765-772.
F. Iacobescu, Smarandache Partition Type and Other Sequences, Bull. Pure Appl. Sci. 16E, 237-240, 1997.
H. Ibstedt, A Few Smarandache Sequences, Smarandache Notions Journal, Vol. 8, No. 1-2-3, 1997, 170-183.
Gabor Korvin, Short note: Every large set of integers contains a three term arithmetic progression arXiv 1404.1557 [math.NT], Apr 6 2014.
F. Smarandache, Sequences of Numbers Involved in Unsolved Problems.
Eric Weisstein's World of Mathematics, Smarandache Sequences
Index entries for sequences related to binary expansion of n
Index entries related to non-averaging sequences
Index entries related to Stanley sequences
|
|
|
FORMULA
|
a(2k + 2) = a(2k + 1) + 1, a(2^k + 1) = 2*a(2^k).
a(n) = b(n+1) with b(0)=1, b(2n)=3b(n)-2, b(2n+1)=3b(n)-1. - Ralf Stephan, Aug 23 2003
G.f.: x/(1-x)^2 + x * sum(3^(k-1)*x^(2^k)/((1-x^(2^k))*(1-x)),k=1..infinity). - Ralf Stephan, Sep 10 2003, corrected by Robert Israel, May 25 2011
Conjecture: a(n) = (A191107(n) + 2)/3 = (A055246(n) + 5)/6. - L. Edson Jeffery, Nov 26 2015
|
|
|
EXAMPLE
|
G.f. = x + 2*x^2 + 4*x^3 + 5*x^4 + 10*x^5 + 11*x^6 + 13*x^7 + 14*x^8 + 28*x^9 + ...
|
|
|
MAPLE
|
a:= proc(n) local m, r, b; m, r, b:= n-1, 1, 1;
while m>0 do r:= r+b*irem(m, 2, 'm'); b:= b*3 od; r
end:
seq(a(n), n=1..100); # Alois P. Heinz, Aug 17 2013
|
|
|
MATHEMATICA
|
Take[ Sort[ Plus @@@ Subsets[ Table[3^n, {n, 0, 6}]]] + 1, 58] (* Robert G. Wilson v, Oct 23 2004 *)
a[1] = 0; h = 180;
Table[a[3 k - 2] = a[k], {k, 1, h}];
Table[a[3 k - 1] = a[k], {k, 1, h}];
Table[a[3 k] = 1, {k, 1, h}];
Table[a[n], {n, 1, h}] (*A189820*)
Flatten[Position[%, 0]] (*A003278*)
Flatten[Position[%%, 1]] (*A189822*)
(* A003278 from A189820, from Clark Kimberling, May 26 2011 *)
|
|
|
PROG
|
(Perl) $nxt = 1; @list = (); for ($cnt = 0; $cnt < 1500; $cnt++) { while (exists $legal{$nxt}) { $nxt++; } print "$nxt "; last if ($nxt >= 1000000); for ($i = 0; $i <= $#list; $i++) { $t = 2*$nxt - $list[$i]; $legal{$t} = -1; } $cnt++; push @list, $nxt; $nxt++; } # Hal Burch
(PARI) a(n)=1+sum(i=1, n-1, (1+3^valuation(i, 2))/2) \\ Ralf Stephan, Jan 21 2014
(Python)
def A003278(n):
....return int(format(n-1, 'b'), 3)+1 # Chai Wah Wu, Jan 04 2015
|
|
|
CROSSREFS
|
Equals 1 + A005836. Cf. A001511, A098871.
Row 0 of array in A093682.
Summary of increasing sequences avoiding arithmetic progressions of specified lengths (the second of each pair is obtained by adding 1 to the first):
3-term AP: A005836 (>=0), A003278 (>0);
4-term AP: A005839 (>=0), A005837 (>0);
5-term AP: A020654 (>=0), A020655 (>0);
6-term AP: A020656 (>=0), A005838 (>0);
7-term AP: A020657 (>=0), A020658 (>0);
8-term AP: A020659 (>=0), A020660 (>0);
9-term AP: A020661 (>=0), A020662 (>0);
10-term AP: A020663 (>=0), A020664 (>0).
See also A003002.
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
N. J. A. Sloane and Richard Stanley
|
|
|
STATUS
|
approved
|
| |
|
Search completed in 3.862 seconds
|
