A212804 -id:A212804 - cp's OEIS frontend

A337452 Number of relatively prime strict integer partitions of n with no 1's.

0, 0, 0, 0, 0, 1, 0, 2, 1, 3, 2, 6, 3, 9, 7, 11, 11, 20, 15, 28, 24, 35, 36, 55, 47, 73, 71, 95, 96, 136, 123, 180, 177, 226, 235, 305, 299, 403, 406, 503, 523, 668, 662, 852, 873, 1052, 1115, 1370, 1391, 1720, 1784, 2125, 2252, 2701, 2786, 3348, 3520, 4116

Offset: 0

Gus Wiseman, Aug 31 2020

nonn

			The a(5) = 1 through a(16) = 11 partitions (A = 10, B = 11, C = 12, D = 13):
  32  43  53  54   73   65   75   76   95    87    97
      52      72   532  74   543  85   B3    B4    B5
              432       83   732  94   653   D2    D3
                        92        A3   743   654   754
                        542       B2   752   753   763
                        632       643  932   762   853
                                  652  5432  843   943
                                  742        852   952
                                  832        942   B32
                                             A32   6532
                                             6432  7432

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..300

A078374 is the version allowing 1's.
A302698 is the non-strict version.
A332004 is the ordered version allowing 1's.
A337450 is the ordered non-strict version.
A337451 is the ordered version.
A337485 is the pairwise coprime version.
A000837 counts relatively prime partitions.
A078374 counts relatively prime strict partitions.
A002865 counts partitions with no 1's.
A212804 counts compositions with no 1's.
A291166 appears to rank relatively prime compositions.
A337561 counts pairwise coprime strict compositions.
Cf. A007359, A101268, A289509, A337485, A337563.

Table[Length[Select[IntegerPartitions[n],UnsameQ@@#&&!MemberQ[#,1]&&GCD@@#==1&]],{n,0,15}]

A337450 Number of relatively prime compositions of n with no 1's.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 0, 7, 5, 17, 17, 54, 51, 143, 168, 358, 482, 986, 1313, 2583, 3663, 6698, 9921, 17710, 26489, 46352, 70928, 121137, 188220, 317810, 497322, 832039, 1313501, 2177282, 3459041, 5702808, 9094377, 14930351, 23895672, 39084070, 62721578

Offset: 0

Gus Wiseman, Aug 31 2020

nonn

A composition of n is a finite sequence of positive integers summing to n.

			The a(5) = 2 through a(10) = 17 compositions (empty column indicated by dot):
  (2,3)  .  (2,5)    (3,5)    (2,7)      (3,7)
  (3,2)     (3,4)    (5,3)    (4,5)      (7,3)
            (4,3)    (2,3,3)  (5,4)      (2,3,5)
            (5,2)    (3,2,3)  (7,2)      (2,5,3)
            (2,2,3)  (3,3,2)  (2,2,5)    (3,2,5)
            (2,3,2)           (2,3,4)    (3,3,4)
            (3,2,2)           (2,4,3)    (3,4,3)
                              (2,5,2)    (3,5,2)
                              (3,2,4)    (4,3,3)
                              (3,4,2)    (5,2,3)
                              (4,2,3)    (5,3,2)
                              (4,3,2)    (2,2,3,3)
                              (5,2,2)    (2,3,2,3)
                              (2,2,2,3)  (2,3,3,2)
                              (2,2,3,2)  (3,2,2,3)
                              (2,3,2,2)  (3,2,3,2)
                              (3,2,2,2)  (3,3,2,2)

Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 171 terms from Fausto A. C. Cariboni)

A000740 is the version allowing 1's.
2*A055684(n) is the case of length 2.
A302697 ranks the unordered case.
A302698 is the unordered version.
A337451 is the strict version.
A337452 is the unordered strict version.
A000837 counts relatively prime partitions.
A002865 counts partitions with no 1's.
A101268 counts singleton or pairwise coprime compositions.
A212804 counts compositions with no 1's.
A291166 appears to rank relatively prime compositions.
A337462 counts pairwise coprime compositions.
Cf. A000010, A007359, A023023, A101268, A178472, A289509, A302568, A337485.

b:= proc(n, g) option remember; `if`(n=0,
     `if`(g=1, 1, 0), add(b(n-j, igcd(g, j)), j=2..n))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..42);

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],!MemberQ[#,1]&&GCD@@#==1&]],{n,0,15}]

A337451 Number of relatively prime strict compositions of n with no 1's.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 0, 4, 2, 10, 8, 20, 14, 34, 52, 72, 90, 146, 172, 244, 390, 502, 680, 956, 1218, 1686, 2104, 3436, 4078, 5786, 7200, 10108, 12626, 17346, 20876, 32836, 38686, 53674, 67144, 91528, 113426, 152810, 189124, 245884, 343350, 428494, 552548, 719156

Offset: 0

Gus Wiseman, Aug 31 2020

nonn

A strict composition of n is a finite sequence of distinct positive integers summing to n.

			The a(5) = 2 through a(10) = 8 compositions (empty column indicated by dot):
  (2,3)  .  (2,5)  (3,5)  (2,7)    (3,7)
  (3,2)     (3,4)  (5,3)  (4,5)    (7,3)
            (4,3)         (5,4)    (2,3,5)
            (5,2)         (7,2)    (2,5,3)
                          (2,3,4)  (3,2,5)
                          (2,4,3)  (3,5,2)
                          (3,2,4)  (5,2,3)
                          (3,4,2)  (5,3,2)
                          (4,2,3)
                          (4,3,2)

Fausto A. C. Cariboni, Table of n, a(n) for n = 0..350

A032022 does not require relative primality.
A302698 is the unordered non-strict version.
A332004 is the version allowing 1's.
A337450 is the non-strict version.
A337452 is the unordered version.
A000837 counts relatively prime partitions.
A032020 counts strict compositions.
A078374 counts strict relatively prime partitions.
A002865 counts partitions with no 1's.
A212804 counts compositions with no 1's.
A291166 appears to rank relatively prime compositions.
A337462 counts pairwise coprime compositions.
A337561 counts strict pairwise coprime compositions.
Cf. A000010, A007359, A101268, A178472, A216652, A289509, A337562, A337563.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],UnsameQ@@#&&!MemberQ[#,1]&&GCD@@#==1&]],{n,0,15}]

A356844 Numbers k such that the k-th composition in standard order contains at least one 1. Numbers that are odd or whose binary expansion contains at least two adjacent 1's.

Original entry on oeis.org

1, 3, 5, 6, 7, 9, 11, 12, 13, 14, 15, 17, 19, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 33, 35, 37, 38, 39, 41, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 65, 67, 69, 70, 71, 73, 75, 76, 77, 78, 79, 81, 83, 85, 86, 87

Offset: 1

Gus Wiseman, Sep 02 2022

nonn

The k-th composition in standard order (graded reverse-lexicographic, 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.

			The terms, binary expansions, and standard compositions:
   1:       1  (1)
   3:      11  (1,1)
   5:     101  (2,1)
   6:     110  (1,2)
   7:     111  (1,1,1)
   9:    1001  (3,1)
  11:    1011  (2,1,1)
  12:    1100  (1,3)
  13:    1101  (1,2,1)
  14:    1110  (1,1,2)
  15:    1111  (1,1,1,1)
  17:   10001  (4,1)
  19:   10011  (3,1,1)
  21:   10101  (2,2,1)
  22:   10110  (2,1,2)
  23:   10111  (2,1,1,1)
  24:   11000  (1,4)
  25:   11001  (1,3,1)
  26:   11010  (1,2,2)
  27:   11011  (1,2,1,1)
  28:   11100  (1,1,3)
  29:   11101  (1,1,2,1)
  30:   11110  (1,1,1,2)
  31:   11111  (1,1,1,1,1)

Gus Wiseman, Statistics, classes, and transformations of standard compositions

See link for sequences related to standard compositions.
The case beginning with 1 is A004760, complement A004754.
The complement is A022340.
These compositions are counted by A099036, complement A212804.
The case covering an initial interval is A333217.
The gapless but non-initial version is A356843, unordered A356845.
Cf. A004780, A005408, A055932, A073492, A073493, A132747.

Select[Range[0,100],OddQ[#]||MatchQ[IntegerDigits[#,2],{_,1,1,_}]&]

Union of A005408 and A004780.

A374439 Triangle read by rows: the coefficients of the Lucas-Fibonacci polynomials. T(n, k) = T(n - 1, k) + T(n - 2, k - 2) with initial values T(n, k) = k + 1 for k < 2.

Original entry on oeis.org

1, 1, 2, 1, 2, 1, 1, 2, 2, 2, 1, 2, 3, 4, 1, 1, 2, 4, 6, 3, 2, 1, 2, 5, 8, 6, 6, 1, 1, 2, 6, 10, 10, 12, 4, 2, 1, 2, 7, 12, 15, 20, 10, 8, 1, 1, 2, 8, 14, 21, 30, 20, 20, 5, 2, 1, 2, 9, 16, 28, 42, 35, 40, 15, 10, 1, 1, 2, 10, 18, 36, 56, 56, 70, 35, 30, 6, 2

Offset: 0

Peter Luschny, Jul 22 2024

There are several versions of Lucas and Fibonacci polynomials in this database. Our naming follows the convention of calling polynomials after the values of the polynomials at x = 1. This assumes a regular sequence of polynomials, that is, a sequence of polynomials where degree(p(n)) = n. This view makes the coefficients of the polynomials (the terms of a row) a refinement of the values at the unity.
A remarkable property of the polynomials under consideration is that they are dual in this respect. This means they give the Lucas numbers at x = 1 and the Fibonacci numbers at x = -1 (except for the sign). See the example section.
The Pell numbers and the dual Pell numbers are also values of the polynomials, at the points x = -1/2 and x = 1/2 (up to the normalization factor 2^n). This suggests a harmonized terminology: To call 2^n*P(n, -1/2) = 1, 0, 1, 2, 5, ... the Pell numbers (A000129) and 2^n*P(n, 1/2) = 1, 4, 9, 22, ... the dual Pell numbers (A048654).
Based on our naming convention one could call A162515 (without the prepended 0) the Fibonacci polynomials. In the definition above only the initial values would change to: T(n, k) = k + 1 for k < 1. To extend this line of thought we introduce A374438 as the third triangle of this family.
The triangle is closely related to the qStirling2 numbers at q = -1. For the definition of these numbers see A333143. This relates the triangle to A065941 and A103631.

			Triangle starts:
  [ 0] [1]
  [ 1] [1, 2]
  [ 2] [1, 2, 1]
  [ 3] [1, 2, 2,  2]
  [ 4] [1, 2, 3,  4,  1]
  [ 5] [1, 2, 4,  6,  3,  2]
  [ 6] [1, 2, 5,  8,  6,  6,  1]
  [ 7] [1, 2, 6, 10, 10, 12,  4,  2]
  [ 8] [1, 2, 7, 12, 15, 20, 10,  8,  1]
  [ 9] [1, 2, 8, 14, 21, 30, 20, 20,  5,  2]
  [10] [1, 2, 9, 16, 28, 42, 35, 40, 15, 10, 1]
.
Table of interpolated sequences:
  |  n | A039834 & A000045 | A000032 |   A000129   |   A048654  |
  |  n |     -P(n,-1)      | P(n,1)  |2^n*P(n,-1/2)|2^n*P(n,1/2)|
  |    |     Fibonacci     |  Lucas  |     Pell    |    Pell*   |
  |  0 |        -1         |     1   |       1     |       1    |
  |  1 |         1         |     3   |       0     |       4    |
  |  2 |         0         |     4   |       1     |       9    |
  |  3 |         1         |     7   |       2     |      22    |
  |  4 |         1         |    11   |       5     |      53    |
  |  5 |         2         |    18   |      12     |     128    |
  |  6 |         3         |    29   |      29     |     309    |
  |  7 |         5         |    47   |      70     |     746    |
  |  8 |         8         |    76   |     169     |    1801    |
  |  9 |        13         |   123   |     408     |    4348    |

Paolo Xausa, Rows n = 0..150 of the triangle, flattened
Peter Luschny, Illustrating the polynomials.

Triangles related to Lucas polynomials: A034807, A114525, A122075, A061896, A352362.
Triangles related to Fibonacci polynomials: A162515, A053119, A168561, A049310, A374441.
Sums include: A000204 (Lucas numbers, row), A000045 & A212804 (even sums, Fibonacci numbers), A006355 (odd sums), A039834 (alternating sign row).
Type m^n*P(n, 1/m): A000129 & A048654 (Pell, m=2), A108300 & A003688 (m=3), A001077 & A048875 (m=4).
Adding and subtracting the values in a row of the table (plus halving the values obtained in this way): A022087, A055389, A118658, A052542, A163271, A371596, A324969, A212804, A077985, A069306, A215928.
Columns include: A040000 (k=1), A000027 (k=2), A005843 (k=3), A000217 (k=4), A002378 (k=5).
Diagonals include: A000034 (k=n), A029578 (k=n-1), abs(A131259) (k=n-2).
Cf. A029578 (subdiagonal), A124038 (row reversed triangle, signed).
Cf. A039961, A065941 (qStirling2), A103631, A108299, A131259. A133607, A194005, A333143, A374438 (m=3).

function T(n,k) // T = A374439
  if k lt 0 or k gt n then return 0;
  elif k le 1 then return k+1;
  else return T(n-1,k) + T(n-2,k-2);
  end if;
end function;
[T(n,k): k in [0..n], n in [0..12]]; // G. C. Greubel, Jan 23 2025

A374439 := (n, k) -> ifelse(k::odd, 2, 1)*binomial(n - irem(k, 2) - iquo(k, 2), iquo(k, 2)):
# Alternative, using the function qStirling2 from A333143:
T := (n, k) -> 2^irem(k, 2)*qStirling2(n, k, -1):
seq(seq(T(n, k), k = 0..n), n = 0..10);

A374439[n_, k_] := (# + 1)*Binomial[n - (k + #)/2, (k - #)/2] & [Mod[k, 2]];
Table[A374439[n, k], {n, 0, 10}, {k, 0, n}]//Flatten (* Paolo Xausa, Jul 24 2024 *)

from functools import cache
@cache
def T(n: int, k: int) -> int:
    if k > n: return 0
    if k < 2: return k + 1
    return T(n - 1, k) + T(n - 2, k - 2)

from math import comb as binomial
def T(n: int, k: int) -> int:
    o = k & 1
    return binomial(n - o - (k - o) // 2, (k - o) // 2) << o

def P(n, x):
    if n < 0: return P(n, x)
    return sum(T(n, k)*x**k for k in range(n + 1))
def sgn(x: int) -> int: return (x > 0) - (x < 0)
# Table of interpolated sequences
print("|  n | A039834 & A000045 | A000032 |   A000129   |   A048654  |")
print("|  n |     -P(n,-1)      | P(n,1)  |2^n*P(n,-1/2)|2^n*P(n,1/2)|")
print("|    |     Fibonacci     |  Lucas  |     Pell    |    Pell*   |")
f = "| {0:2d} | {1:9d}         |  {2:4d}   |   {3:5d}     |    {4:4d}    |"
for n in range(10): print(f.format(n, -P(n, -1), P(n, 1), int(2**n*P(n, -1/2)), int(2**n*P(n, 1/2))))

from sage.combinat.q_analogues import q_stirling_number2
def A374439(n,k): return (-1)^((k+1)//2)*2^(k%2)*q_stirling_number2(n+1, k+1, -1)
print(flatten([[A374439(n, k) for k in range(n+1)] for n in range(13)])) # G. C. Greubel, Jan 23 2025

T(n, k) = 2^k' * binomial(n - k' - (k - k') / 2, (k - k') / 2) where k' = 1 if k is odd and otherwise 0.
T(n, k) = (1 + (k mod 2))*qStirling2(n, k, -1), see A333143.
2^n*P(n, -1/2) = A000129(n - 1), Pell numbers, P(-1) = 1.
2^n*P(n, 1/2) = A048654(n), dual Pell numbers.
T(2*n, n) = (1/2)*(-1)^n*( (1+(-1)^n)*A005809(n/2) - 2*(1-(-1)^n)*A045721((n-1)/2) ). - G. C. Greubel, Jan 23 2025

A331783 Number of locally disjoint rooted semi-identity trees with n unlabeled vertices.

Original entry on oeis.org

1, 1, 2, 4, 8, 17, 37, 83, 191, 450, 1076, 2610, 6404, 15875, 39676, 99880, 253016, 644524, 1649918, 4242226

Offset: 1

Gus Wiseman, Jan 31 2020

Locally disjoint means no branch of any vertex overlaps a different (unequal) branch of the same vertex. In a semi-identity tree, all non-leaf branches of any given vertex are distinct.

			The a(1) = 1 through a(6) = 17 trees:
  o  (o)  (oo)   (ooo)    (oooo)     (ooooo)
          ((o))  ((oo))   ((ooo))    ((oooo))
                 (o(o))   (o(oo))    (o(ooo))
                 (((o)))  (oo(o))    (oo(oo))
                          (((oo)))   (ooo(o))
                          ((o(o)))   (((ooo)))
                          (o((o)))   ((o(oo)))
                          ((((o))))  ((oo(o)))
                                     (o((oo)))
                                     (o(o(o)))
                                     (oo((o)))
                                     ((((oo))))
                                     (((o(o))))
                                     ((o)((o)))
                                     ((o((o))))
                                     (o(((o))))
                                     (((((o)))))

The lone-child-avoiding case is A212804.
The identity tree version is A316471.
The Matula-Goebel numbers of these trees are given by A331682.
Identity trees are A004111.
Semi-identity trees are A306200.
Locally disjoint rooted trees are A316473.
Matula-Goebel numbers of locally disjoint semi-identity trees are A316494.
Cf. A000081, A306202, A316475, A316495, A316694, A331683, A331684, A331686.

disjunsQ[u_]:=Length[u]==1||UnsameQ@@DeleteCases[u,{}]&&Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
ldrsi[n_]:=If[n==1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[ldrsi/@c]]]/@IntegerPartitions[n-1],disjunsQ]];
Table[Length[ldrsi[n]],{n,10}]

A337697 Number of pairwise coprime compositions of n with no 1's, where a singleton is not considered coprime.

Original entry on oeis.org

0, 0, 0, 0, 0, 2, 0, 4, 2, 4, 8, 8, 14, 10, 16, 12, 30, 38, 46, 46, 48, 52, 62, 152, 96, 156, 112, 190, 256, 338, 420, 394, 326, 402, 734, 622, 1150, 802, 946, 898, 1730, 1946, 2524, 2200, 2328, 2308, 3356, 5816, 4772, 5350, 4890, 6282, 6316, 12092, 8902

Offset: 0

Gus Wiseman, Oct 06 2020

nonn

A composition of n is a finite sequence of positive integers summing to n. These compositions must be strict.

			The a(5) = 2 through a(12) = 14 compositions (empty column indicated by dot):
  (2,3)  .  (2,5)  (3,5)  (2,7)  (3,7)    (2,9)  (5,7)
  (3,2)     (3,4)  (5,3)  (4,5)  (7,3)    (3,8)  (7,5)
            (4,3)         (5,4)  (2,3,5)  (4,7)  (2,3,7)
            (5,2)         (7,2)  (2,5,3)  (5,6)  (2,7,3)
                                 (3,2,5)  (6,5)  (3,2,7)
                                 (3,5,2)  (7,4)  (3,4,5)
                                 (5,2,3)  (8,3)  (3,5,4)
                                 (5,3,2)  (9,2)  (3,7,2)
                                                 (4,3,5)
                                                 (4,5,3)
                                                 (5,3,4)
                                                 (5,4,3)
                                                 (7,2,3)
                                                 (7,3,2)

A022340 intersected with A333227 is a ranking sequence (using standard compositions A066099) for these compositions.
A212804 does not require coprimality, with unordered version A002865.
A337450 is the relatively prime instead of pairwise coprime version, with strict case A337451 and unordered version A302698.
A337462 allows 1's, with strict case A337561 (or A101268 with singletons), unordered version A327516 with Heinz numbers A302696, and 3-part case A337461.
A337485 is the unordered version (or A007359 with singletons considered coprime), with Heinz numbers A337984.
A337563 is the case of unordered triples.
Cf. A078374, A178472, A302568, A302697, A305713, A307719, A332004, A337562.

Table[Length[Join@@Permutations/@Select[IntegerPartitions[n],!MemberQ[#,1]&&CoprimeQ@@#&]],{n,0,30}]

For n > 1, the version where singletons are considered coprime is a(n) + 1.

A352744 Array read by ascending antidiagonals. Generalized Fibonacci numbers F(n, k) = (psi^k(phi - n) - phi^k(psi - n)) / (phi - psi) where phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5))/2. F(n, k) for n >= 0 and k >= 0.

Original entry on oeis.org

1, 1, 0, 1, 1, 1, 1, 2, 2, 1, 1, 3, 3, 3, 2, 1, 4, 4, 5, 5, 3, 1, 5, 5, 7, 8, 8, 5, 1, 6, 6, 9, 11, 13, 13, 8, 1, 7, 7, 11, 14, 18, 21, 21, 13, 1, 8, 8, 13, 17, 23, 29, 34, 34, 21, 1, 9, 9, 15, 20, 28, 37, 47, 55, 55, 34, 1, 10, 10, 17, 23, 33, 45, 60, 76, 89, 89, 55

Offset: 0

Peter Luschny, Apr 01 2022

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

			Array starts:
n\k 0, 1,  2,  3,  4,  5,  6,   7,   8,   9, ...
---------------------------------------------------------
[0] 1, 0,  1,  1,  2,  3,  5,   8,  13,  21, ... A212804
[1] 1, 1,  2,  3,  5,  8, 13,  21,  34,  55, ... A000045 (shifted once)
[2] 1, 2,  3,  5,  8, 13, 21,  34,  55,  89, ... A000045 (shifted twice)
[3] 1, 3,  4,  7, 11, 18, 29,  47,  76, 123, ... A000032 (shifted once)
[4] 1, 4,  5,  9, 14, 23, 37,  60,  97, 157, ... A000285
[5] 1, 5,  6, 11, 17, 28, 45,  73, 118, 191, ... A022095
[6] 1, 6,  7, 13, 20, 33, 53,  86, 139, 225, ... A022096
[7] 1, 7,  8, 15, 23, 38, 61,  99, 160, 259, ... A022097
[8] 1, 8,  9, 17, 26, 43, 69, 112, 181, 293, ... A022098
[9] 1, 9, 10, 19, 29, 48, 77, 125, 202, 327, ... A022099

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, sec. 6.6.
Donald Ervin Knuth, The Art of Computer Programming, Third Edition, Vol. 1, Fundamental Algorithms. Chapter 1.2.8 Fibonacci Numbers. Addison-Wesley, Reading, MA, 1997.

Alexander Bogomolny, Cassini's Identity.
Edsger W. Dijkstra, In honour of Fibonacci, in: F. L. Bauer, M. Broy, & E. W. Dijkstra (editors), Program Construction, 1979, Lecture Notes in Computer Science, Vol. 69.
Peter Luschny, The Fibonacci Function.

Rows: A212804, A000045, A000032, A000285, A022095, A022096, A022097, A022098, A022099.
Columns: A000012, A001477, A000027, A005408, A016789, A016885, A004770.
Diagonals: A088209 (main), A007502, A066982 (antidiagonal sums).
Cf. A352747, A353595 (alternative version), A354265 (generalized Lucas numbers).
Similar arrays based on the Catalan and the Bell numbers are A352680 and A352682.

# Time complexity is O(lg n).
function fibrec(n::Int)
    n == 0 && return (BigInt(0), BigInt(1))
    a, b = fibrec(div(n, 2))
    c = a * (b * 2 - a)
    d = a * a + b * b
    iseven(n) ? (c, d) : (d, c + d)
end
function Fibonacci(n::Int, k::Int)
    k == 0 && return BigInt(1)
    k  < 0 && return (-1)^k*Fibonacci(1 - n, -k)
    a, b = fibrec(k - 1)
    a + b*n
end
for n in -6:6
    println([Fibonacci(n, k) for k in -6:6])
end

f := n -> combinat:-fibonacci(n + 1): F := (n, k) -> (n-1)*f(k-1) + f(k):
seq(seq(F(n-k, k), k = 0..n), n = 0..9);
# The next implementation is for illustration only but is not recommended
# as it relies on floating point arithmetic.
phi := (1 + sqrt(5))/2: psi := (1 - sqrt(5))/2:
F := (n, k) -> (psi^k*(phi - n) - phi^k*(psi - n)) / (phi - psi):
for n from -6 to 6 do lprint(seq(simplify(F(n, k)), k = -6..6)) od;

Table[LinearRecurrence[{1, 1}, {1, n}, 10], {n, 0, 9}] // TableForm
F[ n_, k_] := (MatrixPower[{{0, 1}, {1, 1}}, k].{{1}, {n}})[[1, 1]]; (* Michael Somos, May 08 2022 *)
c := Pi/2 - I*ArcSinh[1/2]; (* Based on a remark from Bill Gosper. *)
F[n_, k_] := 2 (I (n-1) Sin[k c] + Sin[(k+1) c]) / (I^k Sqrt[5]);
Table[Simplify[F[n, k]], {n, -6, 6}, {k, -6, 6}] // TableForm (* Peter Luschny, May 10 2022 *)

F(n, k) = ([0, 1; 1, 1]^k*[1; n])[1, 1]

{F(n, k) = n*fibonacci(k) + fibonacci(k-1)}; /* Michael Somos, May 08 2022 */

F(n, k) = F(n, k-1) + F(n, k-2) for k >= 2, otherwise 1, n for k = 0, 1.
F(n, k) = (n-1)*f(k-1) + f(k) where f(n) = A000045(n+1), the Fibonacci numbers starting with f(0) = 1.
F(n, k) = ((phi^k*(n*phi + 1) - (-phi)^(-k)*((n - 1)*phi - 1)))/(2 + phi).
F(n, k) = [x^k] (1 + (n - 1)*x)/(1 - x - x^2) for k >= 0.
F(k, n) = [x^k] (F(0, n) + F(0, n-1)*x)/(1 - x)^2 for k >= 0.
F(n, k) = (k!/sqrt(5))*[x^k] ((n-psi)*exp(phi*x) - (n-phi)*exp(psi*x)) for k >= 0.
F(n, k) - F(n-1, k) = sign(k)^(n-1)*f(k) for all n, k in Z, where A000045 is extended to negative integers by f(-n) = (-1)^(n-1)*f(n) (CMath 6.107). - Peter Luschny, May 09 2022
F(n, k) = 2*((n-1)*i*sin(k*c) + sin((k+1)*c))/(i^k*sqrt(5)) where c = Pi/2 - i*arcsinh(1/2), for all n, k in Z. Based on a remark from Bill Gosper. - Peter Luschny, May 10 2022

A108623 G.f. satisfies x = A(x)*(1-A(x))/(1-A(x)-(A(x))^2).

Original entry on oeis.org

1, 0, -1, -1, 1, 4, 3, -8, -23, -10, 67, 153, 9, -586, -1081, 439, 5249, 7734, -7941, -47501, -53791, 105314, 430119, 343044, -1249799, -3866556, -1730017, 13996097, 34243897, 1947204, -150962373, -296101864, 121857185, 1582561870

Offset: 1

Christian G. Bower, Jun 12 2005

sign

Row sums of inverse of Riordan array (1/(1-x-x^2), x*(1-x)/(1-x-x^2)) (Cf. A053538). - Paul Barry, Nov 01 2006

			G.f. = x - x^3 - x^4 + x^5 + 4*x^6 + 3*x^7 - 8*x^8 - 23*x^9 - 10*x^10 + ...

Vincenzo Librandi, Table of n, a(n) for n = 1..1000

Except for signs, same as A108624.

Cf. A039978, A105523, A212804.

R:=PowerSeriesRing(Rationals(), 41);
Coefficients(R!( (1+x-Sqrt(1-2*x+5*x^2))/(2*(1-x)) )); // G. C. Greubel, Oct 20 2023

# Using function CompInv from A357588.
CompInv(34, n -> ifelse(n=-1, 1, combinat:-fibonacci(n-2))); # Peter Luschny, Oct 05 2022

CoefficientList[Series[(1+x-Sqrt[1-2*x+5*x^2])/(2*x*(1-x)), {x, 0, 20}], x] (* Vaclav Kotesovec, Feb 08 2014 *)
a[ n_] := SeriesCoefficient[ (1 + x - Sqrt[1 - 2 x + 5 x^2]) / (2 (1 - x)), {x, 0, n}]; (* Michael Somos, May 19 2014 *)
a[ n_] := If[ n < 1, 0, SeriesCoefficient[ InverseSeries[ Series[ (x - x^2) / (1 - x - x^2), {x, 0, n}]], {x, 0, n}]]; (* Michael Somos, May 19 2014 *)

{a(n) = if( n<0, 0, polcoeff( (1 + x - sqrt(1 - 2*x + 5*x^2 + x^2 * O(x^n))) / (2 * (1 - x)), n))}; /* Michael Somos, May 19 2014 */

{b(n) = if( n<1, 0, polcoeff( serreverse( (x - x^2) / (1 - x - x^2) + x * O(x^n)), n))}; /* Michael Somos, May 19 2014 */

def A108623_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1+x-sqrt(1-2*x+5*x^2))/(2*(1-x)) ).list()
a=A108623_list(41); a[1:] # G. C. Greubel, Oct 20 2023

Binomial transform of A105523. - Paul Barry, Nov 01 2006
G.f.: (1+x-sqrt(1-2*x+5*x^2))/(2*(1-x)). - Paul Barry, Nov 01 2006
Conjecture: n*a(n) +3*(1-n)*a(n-1) +(7*n-18)*a(n-2) +5*(3-n)*a(n-3)=0. - R. J. Mathar, Nov 15 2011
Lim sup_{n->infinity} |a(n)|^(1/n) = sqrt(5). - Vaclav Kotesovec, Feb 08 2014
Series reversion of g.f. of A212804. - Michael Somos, May 19 2014
G.f.: x / (1 - x + x /(1 - x / (1 - x + x / (1 - x / ...)))). - Michael Somos, May 19 2014
0 = a(n)*(25*a(n+1) - 50*a(n+2) + 45*a(n+3) - 20*a(n+4)) + a(n+1)*(-20*a(n+1) + 34*a(n+2) - 44*a(n+3) + 25*a(n+4)) + a(n+2)*(12*a(n+2) - 2*a(n+3) - 6*a(n+4)) + a(n+3)*(a(n+4)) if n>=0. - Michael Somos, May 19 2014

A353427 Numbers k such that the k-th composition in standard order has all run-lengths > 1.

Original entry on oeis.org

0, 3, 7, 10, 15, 31, 36, 42, 43, 58, 63, 87, 122, 127, 136, 147, 170, 171, 175, 228, 234, 235, 250, 255, 292, 295, 343, 351, 471, 484, 490, 491, 506, 511, 528, 547, 586, 591, 676, 682, 683, 687, 698, 703, 904, 915, 938, 939, 943, 983, 996, 1002, 1003, 1018

Offset: 1

Gus Wiseman, May 16 2022

nonn

			The terms and corresponding compositions begin:
     0: ()
     3: (1,1)
     7: (1,1,1)
    10: (2,2)
    15: (1,1,1,1)
    31: (1,1,1,1,1)
    36: (3,3)
    42: (2,2,2)
    43: (2,2,1,1)
    58: (1,1,2,2)
    63: (1,1,1,1,1,1)
    87: (2,2,1,1,1)
   122: (1,1,1,2,2)
   127: (1,1,1,1,1,1,1)

The version for partitions is A001694, counted by A007690.
The version for parts instead of lengths is A022340, counted by A212804.
These compositions are counted by A114901.
A subset of A348612 (counted by A261983).
The case of all run-lengths = 2 is A351011.
The case of all run-lengths > 2 is counted by A353400.
A005811 counts runs in binary expansion.
A011782 counts compositions.
A066099 lists compositions in standard order, reverse A228351.
Statistics of standard compositions:
- Length is A000120, sum A070939.
- Runs are counted by A124767.
- Runs-resistance is A333628.
- Run-lengths are A333769.
Cf. A044813, A128695, A165413, A240085, A244164, A274174, A318928, A333489, A333755, A353402, A353432.

stc[n_]:=Differences[Prepend[Join@@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
Select[Range[0,100],!MemberQ[Length/@Split[stc[#]],1]&]

cp's OEIS Frontend

A337452 Number of relatively prime strict integer partitions of n with no 1's.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

A337450 Number of relatively prime compositions of n with no 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A337451 Number of relatively prime strict compositions of n with no 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A356844 Numbers k such that the k-th composition in standard order contains at least one 1. Numbers that are odd or whose binary expansion contains at least two adjacent 1's.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A374439 Triangle read by rows: the coefficients of the Lucas-Fibonacci polynomials. T(n, k) = T(n - 1, k) + T(n - 2, k - 2) with initial values T(n, k) = k + 1 for k < 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Python

Python

Python

SageMath

Formula

A331783 Number of locally disjoint rooted semi-identity trees with n unlabeled vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A337697 Number of pairwise coprime compositions of n with no 1's, where a singleton is not considered coprime.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A352744 Array read by ascending antidiagonals. Generalized Fibonacci numbers F(n, k) = (psi^k*(phi - n) - phi^k*(psi - n)) / (phi - psi) where phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5))/2. F(n, k) for n >= 0 and k >= 0.

Views

A352744 Array read by ascending antidiagonals. Generalized Fibonacci numbers F(n, k) = (psi^k(phi - n) - phi^k(psi - n)) / (phi - psi) where phi = (1 + sqrt(5))/2 and psi = (1 - sqrt(5))/2. F(n, k) for n >= 0 and k >= 0.