cp's OEIS Frontend

a(n+2) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = A000110(k) for k = 0, 1, ..., n. - Michael Somos, Oct 07 2003

Number of complete rhyming schemes.

Whereas the Bell number B(n) (A000110(n)) is the number of terms in the polynomial that expresses the n-th moment of a probability distribution as a function of the first n cumulants, these numbers give the number of terms in the corresponding expansion of the central moment as a function of the first n cumulants. - Michael Hardy (hardy(AT)math.umn.edu), Jan 26 2005

a(n) is the number of permutations on [n] for which the left-to-right maxima coincide with the descents (entries followed by a smaller number). For example, a(4) counts 2143, 3142, 3241, 4123. - David Callan, Jul 20 2005

From Gus Wiseman, Feb 10 2019: (Start)

Also the number of stable partitions of an n-cycle, where a stable partition of a graph is a set partition of the vertex set such that no edge has both ends in the same block. A bijective proof is given in David Callan's article. For example, the a(5) = 11 stable partitions are:

{{1},{2},{3},{4},{5}}

{{1},{2},{3,5},{4}}

{{1},{2,4},{3},{5}}

{{1},{2,5},{3},{4}}

{{1,3},{2},{4},{5}}

{{1,4},{2},{3},{5}}

{{1},{2,4},{3,5}}

{{1,3},{2,4},{5}}

{{1,3},{2,5},{4}}

{{1,4},{2},{3,5}}

{{1,4},{2,5},{3}}

(End)

Also number of partitions of {1, 2, ..., n-1} with singletons. E.g., a(4) = 4: {1|2|3, 12|3, 13|2, 1|23}. Also number of cyclical adjacencies partitions of {1, 2, ..., n-1}. E.g., a(4) = 4: {12|3, 13|2, 1|23, 123}. The two partitions can be mapped by a Kreweras bijection. - Yuchun Ji, Feb 22 2021

Also the k-th central moment of a Poisson random variable with mean 1. a(n) = E[(X-1)^n, X~Poisson(1)]. - Thomas Dybdahl Ahle, Dec 14 2022

Number of permutations of degree n with at most one fall; called "Grassmannian permutations" by Lascoux and Schützenberger. - Axel Kohnert (Axel.Kohnert(AT)uni-bayreuth.de)

Number of different permutations of a deck of n cards that can be produced by a single shuffle. [DeSario]

Number of Dyck paths of semilength n having at most one long ascent (i.e., ascent of length at least two). Example: a(4)=12 because among the 14 Dyck paths of semilength 4, the only paths that have more than one long ascent are UUDDUUDD and UUDUUDDD (each with two long ascents). Here U = (1, 1) and D = (1, -1). Also number of ordered trees with n edges having at most one branch node (i.e., vertex of outdegree at least two). - Emeric Deutsch, Feb 22 2004

Number of {12,1*2*,21*}-avoiding signed permutations in the hyperoctahedral group.

Number of 1342-avoiding circular permutations on [n+1].

2^n - n is the number of ways to partition {1, 2, ..., n} into arithmetic progressions, where in each partition all the progressions have the same common difference and have lengths at least 1. - Marty Getz (ffmpg1(AT)uaf.edu) and Dixon Jones (fndjj(AT)uaf.edu), May 21 2005

if b(0) = x and b(n) = b(n-1) + b(n-1)^2*x^(n-2) for n > 0, then b(n) is a polynomial of degree a(n). - Michael Somos, Nov 04 2006

The chromatic invariant of the Mobius ladder graph M_n for n >= 2. - Jonathan Vos Post, Aug 29 2008

Dimension sequence of the dual alternative operad (i.e., associative and satisfying the identity xyz + yxz + zxy + xzy + yzx + zyx = 0) over the field of characteristic 3. - Pasha Zusmanovich, Jun 09 2009

An elephant sequence, see A175654. For the corner squares six A[5] vectors, with decimal values between 26 and 176, lead to this sequence (without the first leading 1). For the central square these vectors lead to the companion sequence A168604. - Johannes W. Meijer, Aug 15 2010

a(n+1) is also the number of order-preserving and order-decreasing partial isometries (of an n-chain). - Abdullahi Umar, Jan 13 2011

A040001(n) = p(-1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, May 12 2012

A130103(n+1) = p(n+1) where p(x) is the unique degree-n polynomial such that p(k) = a(k) for k = 0, 1, ..., n. - Michael Somos, May 12 2012

The number of labeled graphs with n vertices whose vertex set can be partitioned into a clique and a set of isolated points. - Alex J. Best, Nov 20 2012

For n > 0, a(n) is a B_2 sequence. - Thomas Ordowski, Sep 23 2014

See coefficients of the linear terms of the polynomials of the table on p. 10 of the Getzler link. - Tom Copeland, Mar 24 2016

Consider n points lying on a circle, then for n>=2 a(n-1) is the maximum number of ways to connect two points with non-intersecting chords. - Anton Zakharov, Dec 31 2016

Also the number of cliques in the (n-1)-triangular honeycomb rook graph. - Eric W. Weisstein, Jul 14 2017

From Eric M. Schmidt, Jul 17 2017: (Start)

Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i) != e(j) < e(k). [Martinez and Savage, 2.7]

Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(i), e(j), e(k) pairwise distinct. [Martinez and Savage, 2.7]

Number of sequences (e(1), ..., e(n)), 0 <= e(i) < i, such that there is no triple i < j < k with e(j) >= e(k) and e(i) != e(k) pairwise distinct. [Martinez and Savage, 2.7]

(End)

Number of F-equivalence classes of Łukasiewicz paths. Łukasiewicz paths are F-equivalent iff the positions of pattern F are identical in these paths. - Sergey Kirgizov, Apr 08 2018

From Gus Wiseman, Feb 10 2019: (Start)

Also the number of connected partitions of an n-cycle. For example, the a(1) = 1 through a(4) = 12 connected partitions are:

{{1}} {{12}} {{123}} {{1234}}

{{1}{2}} {{1}{23}} {{1}{234}}

{{12}{3}} {{12}{34}}

{{13}{2}} {{123}{4}}

{{1}{2}{3}} {{124}{3}}

{{134}{2}}

{{14}{23}}

{{1}{2}{34}}

{{1}{23}{4}}

{{12}{3}{4}}

{{14}{2}{3}}

{{1}{2}{3}{4}}

(End)

Number of subsets of n-set without the single-element subsets. - Yuchun Ji, Jul 16 2019

For every prime p, there are infinitely many terms of this sequence that are divisible by p (see IMO Compendium link and Doob reference). Corresponding indices n are: for p = 2, even numbers A299174; for p = 3, A047257; for p = 5, A349767. - Bernard Schott, Dec 10 2021

Primes are in A081296 and corresponding indices in A048744. - Bernard Schott, Dec 12 2021

The titular polynomials are defined recursively: p(n,x) = x*p(n-1,x) + 3n - 1, with p(0,x)=1. For an introduction to reductions of polynomials by substitutions such as x^2 -> x+1, see A192232 and A192744.

...

The list of examples at A192744 is extended here; the recurrence is given by p(n,x) = x*p(n-1,x) + v(n), with p(0,x)=1, and the reduction of p(n,x) by x^2 -> x+1 is represented by u1 + u2*x:

...

If v(n)= n, then u1=A001595, u2=A104161.

If v(n)= n-1, then u1=A001610, u2=A066982.

If v(n)= 3n-1, then u1=A171516, u2=A192951.

If v(n)= 3n-2, then u1=A192746, u2=A192952.

If v(n)= 2n-1, then u1=A111314, u2=A192953.

If v(n)= n^2, then u1=A192954, u2=A192955.

If v(n)= -1+n^2, then u1=A192956, u2=A192957.

If v(n)= 1+n^2, then u1=A192953, u2=A192389.

If v(n)= -2+n^2, then u1=A192958, u2=A192959.

If v(n)= 2+n^2, then u1=A192960, u2=A192961.

If v(n)= n+n^2, then u1=A192962, u2=A192963.

If v(n)= -n+n^2, then u1=A192964, u2=A192965.

If v(n)= n(n+1)/2, then u1=A030119, u2=A192966.

If v(n)= n(n-1)/2, then u1=A192967, u2=A192968.

If v(n)= n(n+3)/2, then u1=A192969, u2=A192970.

If v(n)= 2n^2, then u1=A192971, u2=A192972.

If v(n)= 1+2n^2, then u1=A192973, u2=A192974.

If v(n)= -1+2n^2, then u1=A192975, u2=A192976.

If v(n)= 1+n+n^2, then u1=A027181, u2=A192978.

If v(n)= 1-n+n^2, then u1=A192979, u2=A192980.

If v(n)= (n+1)^2, then u1=A001891, u2=A053808.

If v(n)= (n-1)^2, then u1=A192981, u2=A192982.

a(n)-1 counts ternary numbers with no 0 digit (A007931) and at least one 2 digit, where the total of ternary digits is <= n. E.g., a(4)-1 = 7: 2 12 21 22 112 121 211. - Frank Ellermann, Dec 02 2001

A107909(a(n-1)) = A000079(n-1) = 2^(n-1). - Reinhard Zumkeller, May 28 2005

a(n) is the permanent of the n X n 0-1 matrix whose (i,j) entry is 1 iff i=1 or j=n or |i-j|<=1. For example, a(5)=15 is per([[1, 1, 1, 1, 1], [1, 1, 1, 0, 1], [0, 1, 1, 1, 1], [0, 0, 1, 1, 1], [0, 0, 0, 1, 1]]). - David Callan, Jun 07 2006

Conjecture. Let S(1)={1} and, for n>1, let S(n) be the smallest set containing x+1 and 2x+1 for each element x in S(n-1). Then a(n) is the sum of the elements in S(n). (See A122554 for a sequence defined in this way.) - John W. Layman, Nov 21 2007

a(n+1) indexes the corner blocks on the Fibonacci spiral built from blocks of unit area (using F(1) and F(2) as the sides of the first block). - Paul Barry, Mar 06 2008

The number of length n binary words with fewer than 2 0-digits between any pair of consecutive 1-digits. - Jeffrey Liese, Dec 23 2010

If b(n) = a(n+1) then b(0) = 1 and 2*b(n) >= b(n+1) for all n > 1 which is sufficient for b(n) to be a complete sequence. - Frank M Jackson, Mar 17 2013

From Gus Wiseman, Feb 10 2019: (Start)

Also the number of non-singleton subsets of {1, ..., n + 1} with no successive elements. For example, the a(5) = 15 subsets are:

{},

{1,3}, {1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,5}, {3,6}, {4,6},

{1,3,5}, {1,3,6}, {1,4,6}, {2,4,6}.

Also the number of binary sequences with all zeros or at least 2 ones and no adjacent ones. For example, the a(1) = 1 through a(4) = 8 sequences are:

(00) (000) (0000) (00000)

(101) (0101) (00101)

(1001) (01001)

(1010) (01010)

(10001)

(10010)

(10100)

(10101)

(End)

Row sums are the Bell numbers (A000110). T(n,0)=A000296(n). T(n,k) = binomial(n,k)*T(n-k,0). Sum(k*T(n,k),k=0..n) = A052889(n) = n*B(n-1), where B(q) are the Bell numbers (A000110).

Exponential Riordan array [exp(exp(x)-1-x),x]. - Paul Barry, Apr 23 2009

Sum_{k=0..n} T(n,k)*2^k = A000110(n+1) is the number of binary relations on an n-set that are both symmetric and transitive. - Geoffrey Critzer, Jul 25 2014

Also the number of set partitions of {1, ..., n} with k cyclical adjacencies (successive elements in the same block, where 1 is a successor of n). Unlike A250104, we count {{1}} as having 1 cyclical adjacency. - Gus Wiseman, Feb 13 2019

Let A006355(n+4)_0%20-%20A066982(n+1)_1%20(conjecture);%20(a(n))%20=%20em%5BK*%20%5Dseq(%20.25'i%20-%20.25'j%20-%20.25'k%20-%20.25i'%20+%20.25j'%20-%20.75k'%20-%20.25'ii'%20-%20.25'jj'%20-%20.25'kk'%20-%20.25'ij'%20-%20.25'ik'%20-%20.75'ji'%20+%20.25'jk'%20-%20.25'ki'%20-%20.75'kj'%20+%20.75e),%20apart%20from%20initial%20term.%20-%20_Creighton%20Dement">x indicate the sequence offset. Then a(n+2)_0 = A006355(n+4)_0 - A066982(n+1)_1 (conjecture); (a(n)) = em[K* ]seq( .25'i - .25'j - .25'k - .25i' + .25j' - .75k' - .25'ii' - .25'jj' - .25'kk' - .25'ij' - .25'ik' - .75'ji' + .25'jk' - .25'ki' - .75'kj' + .75e), apart from initial term. - _Creighton Dement, Nov 19 2004

The definition declares the Fibonacci numbers for all integers n and k. An alternative version is A353595.

The identity F(n, k) = (-1)^k*F(1 - n, -k) holds for all integers n, k. Proof:

F(n, k)*(2+phi) = (phi^k*(n*phi + 1) - (-phi)^(-k)*((n-1)*phi - 1))

= (-1)^k*(phi^(-k)*((1-n)*phi+1) - (-phi)^k*(-n*phi-1))

= (-1)^k*F(1-n, -k)*(2+phi).

This identity can be seen as an extension of Cassini's theorem of 1680 and of an identity given by Graham, Knuth and Patashnik in 'Concrete Mathematics' (6.106 and 6.107). The beginning of the full array with arguments in Z x Z can be found in the linked note.

The enumeration is the result of the simple form of the chosen definition. The classical positive Fibonacci numbers starting with 1, 1, 2, 3,... are in row n = 1 with offset 0. The nonnegative Fibonacci numbers starting 0, 1, 1, 2, 3,... are in row 0 with offset 1. They prolong towards -infinity with an index shifted by 1 compared to the enumeration used by Knuth. A characteristic of our enumeration is F(n, 0) = 1 for all integer n.

Fibonacci numbers vanish only for (n,k) in {(-1,2), (0,1), (1,-1), (2,-2)}. The zeros correspond to the identities (phi + 1)*psi^2 = (psi + 1)*phi^2, psi*phi = phi*psi, (phi - 1)*phi = (psi - 1)*psi and (phi - 2)*phi^2 = (psi - 2)*psi^2.

For divisibility properties see A352747.

For any fixed k, the sequence F(n, k) is a linear function of n. In other words, an arithmetic progression. This implies that F(n+1, k) = 2*F(n, k) - F(n-1, k) for all n in Z. Special case of this is Fibonacci(n+1) = 2 *Fibonacci(n) - Fibonacci(n-2). - Michael Somos, May 08 2022