cp's OEIS Frontend

Dimensions of the homogeneous parts of the free Lie algebra with one generator in 1,2,3, etc. (Lie analog of the partition numbers).

This sequence is the Lie analog of the partition sequence (which gives the dimensions of the homogeneous polynomials with one generator in each degree) or similarly, of the partitions into distinct (or odd numbers) (which gives the dimensions of the homogeneous parts of the exterior algebra with one generator in each dimension).

The number of cycles of length n of rectangle shapes in the process of repeatedly cutting a square off the end of the rectangle. For example, the one cycle of length 1 is the golden rectangle. - David Pasino (davepasino(AT)yahoo.com), Jan 29 2009

In music, the number of distinct rhythms, at a given tempo, produced by a continuous repetition of measures with identical patterns of 1's and 0's (where 0 means no beat, and 1 means one beat), where each measure allows for n possible beats of uniform character, and when counted under these two conditions: (i) the starting and ending times for the measure are unknown or irrelevant and (ii) identical rhythms that can be produced by using a measure with fewer than n possible beats are excluded from the count. - Richard R. Forberg, Apr 22 2013

Richard R. Forberg's comment does not hold for n=1 because a(1)=1 but there are the two possible rhythms: "0" and "1". - Herbert Kociemba, Oct 24 2016

The comment does hold for n=1 as the rhythm "0" can be produced by using a measure of 0 beats and so is properly excluded from a(1)=1 by condition (ii) of the comment. - Travis Scott, May 28 2022

a(n) is also the number of Lyndon compositions (aperiodic necklaces of positive integers) with sum n. - Gus Wiseman, Dec 19 2017

Mobius transform of A008965. - Jianing Song, Nov 13 2021

a(n) is the number of cycles of length n for the map x->1 - abs(2*x-1) applied on rationals 0Michel Marcus, Jul 16 2025

After initial terms, first differs from A291292 at a(6) = 1352, A291292(8) = 1353.

Joe Keane (jgk(AT)jgk.org) observes that this sequence (beginning at 3) is "size of raises in pot-limit poker, one blind, maximum raising".

It appears that this sequence is the BinomialMean transform of A001653 (see A075271). - John W. Layman, Oct 03 2002

Number of (s(0), s(1), ..., s(2n+1)) such that 0 < s(i) < 8 and |s(i) - s(i-1)| = 1 for i = 1,2,...,2n+1, s(0) = 3, s(2n+1) = 4. - Herbert Kociemba, Jun 12 2004

Equals the INVERT transform of (1, 2, 5, 13, 34, 89, ...). - Gary W. Adamson, May 01 2009

a(n) is the number of compositions of n when there are 3 types of ones. - Milan Janjic, Aug 13 2010

a(n)/a(n-1) tends to (4 + sqrt(8))/2 = 3.414213.... Gary W. Adamson, Jul 30 2013

a(n) is the first subdiagonal of array A228405. - Richard R. Forberg, Sep 02 2013

Number of words of length n over {0,1,2,3,4} in which binary subwords appear in the form 10...0. - Milan Janjic, Jan 25 2017

From Gus Wiseman, Mar 05 2020: (Start)

Also the number of unimodal sequences of length n + 1 covering an initial interval of positive integers, where a sequence of integers is unimodal if it is the concatenation of a weakly increasing and a weakly decreasing sequence. For example, the a(0) = 1 through a(2) = 10 sequences are:

(1) (1,1) (1,1,1)

(1,2) (1,1,2)

(2,1) (1,2,1)

(1,2,2)

(1,2,3)

(1,3,2)

(2,1,1)

(2,2,1)

(2,3,1)

(3,2,1)

Missing are: (2,1,2), (2,1,3), (3,1,2).

Conjecture: Also the number of ordered set partitions of {1..n + 1} where no element of any block is greater than any element of a non-adjacent consecutive block. For example, the a(0) = 1 through a(2) = 10 ordered set partitions are:

{{1}} {{1,2}} {{1,2,3}}

{{1},{2}} {{1},{2,3}}

{{2},{1}} {{1,2},{3}}

{{1,3},{2}}

{{2},{1,3}}

{{2,3},{1}}

{{3},{1,2}}

{{1},{2},{3}}

{{1},{3},{2}}

{{2},{1},{3}}

Cf. A000670, A056242, A332673, A332872. (End)

a(n-1) is the number of hexagonal directed-column convex polyominoes having area n (see Baril et al. at page 4). - Stefano Spezia, Oct 14 2023

Triangle T(n,k), 0 <= k <= n, read by rows given by [0,1,0,2,0,3,0,4,0,5,0,6,0,7,0,...] DELTA [1,1,2,2,3,3,4,4,5,5,6,6,...] where DELTA is the operator defined in A084938; another version of A019538.

See also A019538: version with n > 0 and k > 0. - Philippe Deléham, Nov 03 2008

From Peter Bala, Jul 21 2014: (Start)

T(n,k) gives the number of (k-1)-dimensional faces in the interior of the first barycentric subdivision of the standard (n-1)-dimensional simplex. For example, the barycentric subdivision of the 1-simplex is o--o--o, with 1 interior vertex and 2 interior edges, giving T(2,1) = 1 and T(2,2) = 2.

This triangle is used when calculating the face vectors of the barycentric subdivision of a simplicial complex. Let S be an n-dimensional simplicial complex and write f_k for the number of k-dimensional faces of S, with the usual convention that f_(-1) = 1, so that F := (f_(-1), f_0, f_1,...,f_n) is the f-vector of S. If M(n) denotes the square matrix formed from the first n+1 rows and n+1 columns of the present triangle, then the vector F*M(n) is the f-vector of the first barycentric subdivision of the simplicial complex S (Brenti and Welker, Lemma 2.1). For example, the rows of Pascal's triangle A007318 (but with row and column indexing starting at -1) are the f-vectors for the standard n-simplexes. It follows that A007318*A131689, which equals A028246, is the array of f-vectors of the first barycentric subdivision of standard n-simplexes. (End)

This triangle T(n, k) appears in the o.g.f. G(n, x) = Sum_{m>=0} S(n, m)*x^m with S(n, m) = Sum_{j=0..m} j^n for n >= 1 as G(n, x) = Sum_{k=1..n} (x^k/(1 - x)^(k+2))*T(n, k). See also the Eulerian triangle A008292 with a Mar 31 2017 comment for a rewritten form. For the e.g.f. see A028246 with a Mar 13 2017 comment. - Wolfdieter Lang, Mar 31 2017

T(n,k) = the number of alignments of length k of n strings each of length 1. See Slowinski. An example is given below. Cf. A122193 (alignments of strings of length 2) and A299041 (alignments of strings of length 3). - Peter Bala, Feb 04 2018

The row polynomials R(n,x) are the Fubini polynomials. - Emanuele Munarini, Dec 05 2020

From Gus Wiseman, Feb 18 2022: (Start)

Also the number of patterns of length n with k distinct parts (or with maximum part k), where we define a pattern to be a finite sequence covering an initial interval of positive integers. For example, row n = 3 counts the following patterns:

(1,1,1) (1,2,2) (1,2,3)

(2,1,2) (1,3,2)

(2,2,1) (2,1,3)

(1,1,2) (2,3,1)

(1,2,1) (3,1,2)

(2,1,1) (3,2,1)

(End)

Regard A048994 as a lower-triangular matrix and divide each term A048994(n,k) by n!, then this is the matrix inverse. Because Sum_{k=0..n} (A048994(n,k) * x^n / n!) = A007318(x,n), Sum_{k=0..n} (A131689(n,k) * A007318(x,k)) = x^n. - Natalia L. Skirrow, Mar 23 2023

T(n,k) is the number of ordered partitions of [n] into k blocks. - Alois P. Heinz, Feb 21 2025

0, and terms of A065609 that are not in A121016.

Number of terms with d binary digits is A001037(d).

Take the binary representation of a(n), reverse it, add 1 to each digit. The result is the decimal representation of A102659(n).

From Gus Wiseman, Apr 19 2020: (Start)

Also numbers k such that the k-th composition in standard order (row k of A066099) is a Lyndon word. For example, the sequence of all Lyndon words begins:

0: () 52: (1,2,3) 118: (1,1,2,1,2)

1: (1) 56: (1,1,4) 120: (1,1,1,4)

2: (2) 58: (1,1,2,2) 122: (1,1,1,2,2)

4: (3) 60: (1,1,1,3) 124: (1,1,1,1,3)

6: (1,2) 62: (1,1,1,1,2) 126: (1,1,1,1,1,2)

8: (4) 64: (7) 128: (8)

12: (1,3) 72: (3,4) 144: (3,5)

14: (1,1,2) 80: (2,5) 160: (2,6)

16: (5) 84: (2,2,3) 164: (2,3,3)

20: (2,3) 96: (1,6) 168: (2,2,4)

24: (1,4) 98: (1,4,2) 192: (1,7)

26: (1,2,2) 100: (1,3,3) 194: (1,5,2)

28: (1,1,3) 104: (1,2,4) 196: (1,4,3)

30: (1,1,1,2) 106: (1,2,2,2) 200: (1,3,4)

32: (6) 108: (1,2,1,3) 202: (1,3,2,2)

40: (2,4) 112: (1,1,5) 208: (1,2,5)

48: (1,5) 114: (1,1,3,2) 210: (1,2,3,2)

50: (1,3,2) 116: (1,1,2,3) 212: (1,2,2,3)

(End)

Original name: a(n) = number of necklaces of n beads with up to n unlabeled colors.

The Moebius transform of this sequence is A060223.

A Lyndon word is primitive (not a power of another word) and is earlier in lexicographic order than any of its cyclic shifts.

Any binary word has a unique factorization as a product of nonincreasing Lyndon words (see Lothaire). a(n) = number of factors in Lyndon factorization of binary expansion of n.

It appears that a(n) = k for the first time when n = 2^(k-1)+1.

We define the Lyndon product of two or more finite sequences to be the lexicographically maximal sequence obtainable by shuffling the sequences together. For example, the Lyndon product of (231) with (213) is (232131), the product of (221) with (213) is (222131), and the product of (122) with (2121) is (2122121). A Lyndon word is a finite sequence that is prime with respect to the Lyndon product. Equivalently, a Lyndon word is a finite sequence that is lexicographically strictly less than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into Lyndon words, and if these factors are arranged in lexicographically decreasing order, their concatenation is equal to their Lyndon product. - Gus Wiseman, Nov 12 2019

A sequence of integers is unimodal if it is the concatenation of a weakly increasing and a weakly decreasing sequence.

The co-Lyndon product of two or more finite sequences is defined to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (231) and (213) is (212313), the product of (221) and (213) is (212213), and the product of (122) and (2121) is (1212122). A co-Lyndon word is a finite sequence that is prime with respect to the co-Lyndon product. Equivalently, a co-Lyndon word is a finite sequence that is lexicographically strictly greater than all of its cyclic rotations. Every finite sequence has a unique (orderless) factorization into co-Lyndon words, and if these factors are arranged in a certain order, their concatenation is equal to their co-Lyndon product. For example, (1001) has sorted co-Lyndon factorization (1)(100).

Also the length of the Lyndon factorization of the inverted binary expansion of n, where the inverted digits are 1 minus the binary digits.

A composition of n is a finite sequence of positive integers summing to n. The k-th composition in standard order (row k of A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.