A068911 -id:A068911 - cp's OEIS frontend

A048675 If n = p_i^e_i * ... * p_k^e_k, p_i < ... < p_k primes (with p_i = prime(i)), then a(n) = (1/2) * (e_i * 2^i + ... + e_k * 2^k).

0, 1, 2, 2, 4, 3, 8, 3, 4, 5, 16, 4, 32, 9, 6, 4, 64, 5, 128, 6, 10, 17, 256, 5, 8, 33, 6, 10, 512, 7, 1024, 5, 18, 65, 12, 6, 2048, 129, 34, 7, 4096, 11, 8192, 18, 8, 257, 16384, 6, 16, 9, 66, 34, 32768, 7, 20, 11, 130, 513, 65536, 8, 131072, 1025, 12, 6, 36, 19

Offset: 1

Antti Karttunen, Jul 14 1999

nonn

The original motivation for this sequence was to encode the prime factorization of n in the binary representation of a(n), each such representation being unique as long as this map is restricted to A005117 (squarefree numbers, resulting a permutation of nonnegative integers A048672) or any of its subsequence, resulting an injective function like A048623 and A048639.
However, also the restriction to A260443 (not all terms of which are squarefree) results a permutation of nonnegative integers, namely A001477, the identity permutation.
When a polynomial with nonnegative integer coefficients is encoded with the prime factorization of n (e.g., as in A206296, A260443), then a(n) gives the evaluation of that polynomial at x=2.
The primitive completely additive integer sequence that satisfies a(n) = a(A225546(n)), n >= 1. By primitive, we mean that if b is another such sequence, then there is an integer k such that b(n) = k * a(n) for all n >= 1. - Peter Munn, Feb 03 2020
If the binary rank of an integer partition y is given by Sum_i 2^(y_i-1), and the Heinz number is Product_i prime(y_i), then a(n) is the binary rank of the integer partition with Heinz number n. Note the function taking a set s to Sum_i 2^(s_i-1) is the inverse of A048793 (binary indices), and the function taking a multiset m to Product_i prime(m_i) is the inverse of A112798 (prime indices). - Gus Wiseman, May 22 2024

			From _Gus Wiseman_, May 22 2024: (Start)
The A018819(7) = 6 cases of binary rank 7 are the following, together with their prime indices:
   30: {1,2,3}
   40: {1,1,1,3}
   54: {1,2,2,2}
   72: {1,1,1,2,2}
   96: {1,1,1,1,1,2}
  128: {1,1,1,1,1,1,1}
(End)

Antti Karttunen, Table of n, a(n) for n = 1..1024
Hans Havermann, Factorization of the first 10000 terms, in format [[primes], [exponents]]

Row 2 of A104244.
Similar logarithmic functions: A001414, A056239, A090880, A289506, A293447.
Left inverse of the following sequences: A000079, A019565, A038754, A068911, A134683, A260443, A332824.
A003961, A028234, A032742, A055396, A064989, A067029, A225546, A297845 are used to express relationship between terms of this sequence.
Cf. also A048623, A048676, A099884, A277896 and tables A277905, A285325.
Cf. A297108 (Möbius transform), A332813 and A332823 [= a(n) mod 3].
Pairs of sequences (f,g) that satisfy a(f(n)) = g(n), possibly with offset change: (A000203,A331750), (A005940,A087808), (A007913,A248663), (A007947,A087207), (A097248,A048675), (A206296,A000129), (A248692,A056239), (A283477,A005187), (A284003,A006068), (A285101,A028362), (A285102,A068052), (A293214,A001065), (A318834,A051953), (A319991,A293897), (A319992,A293898), (A320017,A318674), (A329352,A069359), (A332461,A156552), (A332462,A156552), (A332825,A000010) and apparently (A163511,A135529).
See comments/formulas in A277333, A331591, A331740 giving their relationship to this sequence.
The formula section details how the sequence maps the terms of A329050, A329332.
A277892, A322812, A322869, A324573, A324575 give properties of the n-th term of this sequence.
The term k appears A018819(k) times.
The inverse transformation is A019565 (Heinz number of binary indices).
The version for distinct prime indices is A087207.
Numbers k such that a(k) is prime are A277319, counts A372688.
Grouping by image gives A277905.
A014499 lists binary indices of prime numbers.
A061395 gives greatest prime index, least A055396.
A112798 lists prime indices, length A001222, reverse A296150, sum A056239.
Binary indices:
- listed A048793, sum A029931
- reversed A272020
- opposite A371572, sum A230877
- length A000120, complement A023416
- min A001511, opposite A000012
- max A070939, opposite A070940
- complement A368494, sum A359400
- opposite complement A371571, sum A359359
Cf. A000720, A035100, A071814, A096111, A225620, A243055, A304818, A355536, A358136, A372890.
Cf. A087207, A097248.

nthprime := proc(n) local i; if(isprime(n)) then for i from 1 to 1000000 do if(ithprime(i) = n) then RETURN(i); fi; od; else RETURN(0); fi; end; # nthprime(2) = 1, nthprime(3) = 2, nthprime(5) = 3, etc. - this is also A049084.
A048675 := proc(n) local s,d; s := 0; for d in ifactors(n)[ 2 ] do s := s + d[ 2 ]*(2^(nthprime(d[ 1 ])-1)); od; RETURN(s); end;
# simpler alternative
f:= n -> add(2^(numtheory:-pi(t[1])-1)*t[2], t=ifactors(n)[2]):
map(f, [$1..100]); # Robert Israel, Oct 10 2016

a[1] = 0; a[n_] := Total[ #[[2]]*2^(PrimePi[#[[1]]]-1)& /@ FactorInteger[n] ]; Array[a, 100] (* Jean-François Alcover, Mar 15 2016 *)

a(n) = my(f = factor(n)); sum(k=1, #f~, f[k,2]*2^primepi(f[k,1]))/2; \\ Michel Marcus, Oct 10 2016

\\ The following program reconstructs terms (e.g. for checking purposes) from the factorization file prepared by Hans Havermann:
v048675sigs = readvec("a048675.txt");
A048675(n) = if(n<=2,n-1,my(prsig=v048675sigs[n],ps=prsig[1],es=prsig[2]); prod(i=1,#ps,ps[i]^es[i])); \\ Antti Karttunen, Feb 02 2020

from sympy import factorint, primepi
def a(n):
    if n==1: return 0
    f=factorint(n)
    return sum([f[i]*2**(primepi(i) - 1) for i in f])
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jun 19 2017

a(1) = 0, a(n) = 1/2 * (e1*2^i1 + e2*2^i2 + ... + ez*2^iz) if n = p_{i1}^e1*p_{i2}^e2*...*p_{iz}^ez, where p_i is the i-th prime. (e.g. p_1 = 2, p_2 = 3).
Totally additive with a(p^e) = e * 2^(PrimePi(p)-1), where PrimePi(n) = A000720(n). [Missing factor e added to the comment by Antti Karttunen, Jul 29 2015]
From Antti Karttunen, Jul 29 2015: (Start)
a(1) = 0; for n > 1, a(n) = 2^(A055396(n)-1) + a(A032742(n)). [Where A055396(n) gives the index of the smallest prime dividing n and A032742(n) gives the largest proper divisor of n.]
a(1) = 0; for n > 1, a(n) = (A067029(n) * (2^(A055396(n)-1))) + a(A028234(n)).
Other identities. For all n >= 0:
a(A019565(n)) = n.
a(A260443(n)) = n.
a(A206296(n)) = A000129(n).
a(A005940(n+1)) = A087808(n).
a(A007913(n)) = A248663(n).
a(A007947(n)) = A087207(n).
a(A283477(n)) = A005187(n).
a(A284003(n)) = A006068(n).
a(A285101(n)) = A028362(1+n).
a(A285102(n)) = A068052(n).
Also, it seems that a(A163511(n)) = A135529(n) for n >= 1. (End)
a(1) = 0, a(2n) = 1+a(n), a(2n+1) = 2*a(A064989(2n+1)). - Antti Karttunen, Oct 11 2016
From Peter Munn, Jan 31 2020: (Start)
a(n^2) = a(A003961(n)) = 2 * a(n).
a(A297845(n,k)) = a(n) * a(k).
a(n) = a(A225546(n)).
a(A329332(n,k)) = n * k.
a(A329050(n,k)) = 2^(n+k).
(End)
From Antti Karttunen, Feb 02-25 2020, Feb 01 2021: (Start)
a(n) = Sum_{d|n} A297108(d) = Sum_{d|A225546(n)} A297108(d).
a(n) = a(A097248(n)).
For n >= 2:
A001221(a(n)) = A322812(n), A001222(a(n)) = A277892(n).
A000203(a(n)) = A324573(n), A033879(a(n)) = A324575(n).
For n >= 1, A331750(n) = a(A000203(n)).
For n >= 1, the following chains hold:
A293447(n) >= a(n) >= A331740(n) >= A331591(n).
a(n) >= A087207(n) >= A248663(n).
(End)
a(n) = A087207(A097248(n)). - Flávio V. Fernandes, Jul 16 2025

Entry revised by Antti Karttunen, Jul 29 2015

More linking formulas added by Antti Karttunen, Apr 18 2017

A038754 a(2n) = 3^n, a(2n+1) = 2*3^n.

Original entry on oeis.org

1, 2, 3, 6, 9, 18, 27, 54, 81, 162, 243, 486, 729, 1458, 2187, 4374, 6561, 13122, 19683, 39366, 59049, 118098, 177147, 354294, 531441, 1062882, 1594323, 3188646, 4782969, 9565938, 14348907, 28697814, 43046721, 86093442, 129140163, 258280326, 387420489

Offset: 0

Henry Bottomley, May 03 2000

In general, for the recurrence a(n) = a(n-1)*a(n-2)/a(n-3), all terms are integers iff a(0) divides a(2) and first three terms are positive integers, since a(2n+k) = a(k)*(a(2)/a(0))^n for all nonnegative integers n and k.
Equals eigensequence of triangle A070909; (1, 1, 2, 3, 6, 9, 18, ...) shifts to the left with multiplication by triangle A070909. - Gary W. Adamson, May 15 2010
The a(n) represent all paths of length (n+1), n >= 0, starting at the initial node on the path graph P_5, see the second Maple program. - Johannes W. Meijer, May 29 2010
a(n) is the difference between numbers of multiple of 3 evil (A001969) and odious (A000069) numbers in interval [0, 2^(n+1)). - Vladimir Shevelev, May 16 2012
A "half-geometric progression": to obtain a term (beginning with the third one) we multiply the before previous one by 3. - Vladimir Shevelev, May 21 2012
Pisano periods: 1, 2, 1, 4, 8, 2, 12, 4, 1, 8, 10, 4, 6, 12, 8, 8, 32, 2, 36, 8, ... . - R. J. Mathar, Aug 10 2012
Numbers k such that the k-th cyclotomic polynomial has a root mod 3. - Eric M. Schmidt, Jul 31 2013
Range of row n of the circular Pascal array of order 6. - Shaun V. Ault, Jun 05 2014
Also, the number of walks of length n on the graph 0--1--2--3--4 starting at vertex 1. - Sean A. Irvine, Jun 03 2025

			In the interval [0,2^5) we have 11 multiples of 3 numbers, from which 10 are evil and only one (21) is odious. Thus a(4) = 10 - 1 = 9. - _Vladimir Shevelev_, May 16 2012

Indranil Ghosh, Table of n, a(n) for n = 0..1500 (first 401 terms from T. D. Noe)
S. V. Ault and C. Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics, Vol. 332 (2014), pp. 45-54.
Paul Barry, Three Études on a sequence transformation pipeline, arXiv:1803.06408 [math.CO], 2018.
Nachum Dershowitz, Between Broadway and the Hudson, arXiv:2006.06516 [math.CO], 2020.
Sean A. Irvine, Walks on Graphs.
Richard L. Ollerton and Anthony G. Shannon, Some properties of generalized Pascal squares and triangles, Fib. Q., 36 (1998), 98-109. See pages 106-7.
Vladimir Shevelev, On monotonic strengthening of Newman-like phenomenon on (2m+1)-multiples in base 2m, arXiv:0710.3177 [math.NT], 2007.
M. B. Wells, Elements of Combinatorial Computing, Pergamon, Oxford, 1971. [Annotated scanned copy of pages 237-240]
Index entries for linear recurrences with constant coefficients, signature (0,3).

Cf. A000045, A000069, A000079, A000120, A000244, A001969, A006720, A006721.
Cf. A006722, A006723, A008776, A028495, A030436, A037124, A048328, A061551.
Cf. A068911, A070909, A087503, A124302, A128588, A133464, A140730, A140740.
Cf. A178381, A182751, A182752, A182753, A182754, A182755, A182756, A182757.
Fifth row of the array A094718.

import Data.List (transpose)
a038754 n = a038754_list !! n
a038754_list = concat $ transpose [a000244_list, a008776_list]
-- Reinhard Zumkeller, Oct 19 2015

[n le 2 select n else 3*Self(n-2): n in [1..40]]; // Vincenzo Librandi, Aug 18 2016

a[0]:=0:a[1]:=1:for n from 2 to 50 do a[n]:=3*a[n-2]+2 od: seq(a[n]+1, n=0..34); # Zerinvary Lajos, Mar 20 2008
with(GraphTheory): P:=5: G:=PathGraph(P): A:= AdjacencyMatrix(G): nmax:=35; for n from 1 to nmax do B(n):=A^n; a(n):=add(B(n)[1,k],k=1..P) od: seq(a(n),n=1..nmax); # Johannes W. Meijer, May 29 2010

LinearRecurrence[{0,3},{1,2},40] (* Harvey P. Dale, Jan 26 2014 *)
CoefficientList[Series[(1+2x)/(1-3x^2), {x, 0, 40}], x] (* Vincenzo Librandi, Aug 18 2016 *)
Module[{nn=20,c},c=3^Range[0,nn];Riffle[c,2c]] (* Harvey P. Dale, Aug 21 2021 *)

PARI
```
a(n)=(1/6)*(5-(-1)^n)*3^floor(n/2)
```
PARI
```
a(n)=3^(n>>1)<
				
```

[2^(n%2)*3^((n-(n%2))/2) for n in range(61)] # G. C. Greubel, Oct 10 2022

a(n) = a(n-1)*a(n-2)/a(n-3) with a(0)=1, a(1)=2, a(2)=3.
a(2*n) = (3/2)*a(2*n-1) = 3^n, a(2*n+1) = 2*a(2*n) = 2*3^n.
From Benoit Cloitre, Apr 27 2003: (Start)
a(1)=1, a(n)= 2*a(n-1) if a(n-1) is odd, or a(n)= (3/2)*a(n-1) if a(n-1) is even.
a(n) = (1/6)*(5-(-1)^n)*3^floor(n/2).
a(2*n) = a(2*n-1) + a(2*n-2) + a(2*n-3).
a(2*n+1) = a(2*n) + a(2*n-1). (End)
G.f.: (1+2*x)/(1-3*x^2). - Paul Barry, Aug 25 2003
From Reinhard Zumkeller, Sep 11 2003: (Start)
a(n) = (1 + n mod 2) * 3^floor(n/2).
a(n) = A087503(n) - A087503(n-1). (End)
a(n) = sqrt(3)*(2+sqrt(3))*(sqrt(3))^n/6 - sqrt(3)*(2-sqrt(3))*(-sqrt(3))^n/6. - Paul Barry, Sep 16 2003
From Reinhard Zumkeller, May 26 2008: (Start)
a(n) = A140740(n+2,2).
a(n+1) = a(n) + a(n - n mod 2). (End)
If p(i) = Fibonacci(i-3) and if A is the Hessenberg matrix of order n defined by A(i,j) = p(j-i+1), (i<=j), A(i,j)=-1, (i=j+1), and A(i,j)=0 otherwise. Then, for n>=1, a(n-1) = (-1)^n det A. - Milan Janjic, May 08 2010
a(n) = A182751(n) for n >= 2. - Jaroslav Krizek, Nov 27 2010
a(n) = Sum_{i=0..2^(n+1), i==0 (mod 3)} (-1)^A000120(i). - Vladimir Shevelev, May 16 2012
a(0)=1, a(1)=2, for n>=3, a(n)=3*a(n-2). - Vladimir Shevelev, May 21 2012
Sum_(n>=0) 1/a(n) = 9/4. - Alexander R. Povolotsky, Aug 24 2012
a(n) = sqrt(3*a(n-1)^2 + (-3)^(n-1)). - Richard R. Forberg, Sep 04 2013
a(n) = 2^((1-(-1)^n)/2)*3^((2*n-1+(-1)^n)/4). - Luce ETIENNE, Aug 11 2014
From Reinhard Zumkeller, Oct 19 2015: (Start)
a(2*n) = A000244(n), a(2*n+1) = A008776(n).
For n > 0: a(n+1) = a(n) + if a(n) odd then min{a(n), a(n-1)} else max{a(n), a(n-1)}, see also A128588. (End)
E.g.f.: (7*cosh(sqrt(3)*x) + 4*sqrt(3)*sinh(sqrt(3)*x) - 4)/3. - Stefano Spezia, Feb 17 2022
Sum_{n>=0} (-1)^n/a(n) = 3/4. - Amiram Eldar, Dec 02 2022

A008967 Coefficients of Gaussian polynomials q_binomial(n-2, 2). Also triangle of distribution of rank sums: Wilcoxon's statistic. Irregular triangle read by rows.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 2, 2, 3, 2, 2, 1, 1, 1, 1, 2, 2, 3, 3, 3, 2, 2, 1, 1, 1, 1, 2, 2, 3, 3, 4, 3, 3, 2, 2, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 4, 4, 3, 3, 2, 2, 1, 1, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 5, 4, 4, 3, 3, 2, 2, 1, 1

Offset: 4

N. J. A. Sloane

Rows are numbers of dominoes with k spots where each half-domino has zero to n spots (in standard domino set: n=6, there are 28 dominoes and row is 1,1,2,2,3,3,4,3,3,2,2,1,1). - Henry Bottomley, Aug 23 2000
The Gaussian polynomial (or Gaussian binomial) [n,2]q is an example of a q-binomial coefficient (see the link) and may be defined for n >= 2 by [n,2]_q = ([n]_q * [n-1]_q)/([1]_q * [2]_q), where [n]_q := q^n - 1. The first few values are: [2,2]_q = 1; [3,2]_q = 1 + q + q^2; [4,2]_q = 1 + q + 2q^2 + q^3 + q^4. - _Peter Bala, Sep 23 2007
These numbers appear in the solution of Cayley's counting problem on covariants as N(p,2,w) = [x^p,q^w] Phi(q,x) with the o.g.f. Phi(q,x) = 1/((1-x)(1-qx)(1-q^2x)) given by Peter Bala in the formula section. See the Hawkins reference, p. 264, were also references are given. - Wolfdieter Lang, Nov 30 2012
The entry a(p,w), p >= 0, w = 0,1,...,2*p, of this irregular triangle is the number of nonnegative solutions of m_0 + m_1 + m_2 = p and 1*m_1 + 2*m_2 = w. See the Hawkins reference p. 264, (4.8). N(p,2,w) there is a(p,w). See also the Cayley reference p. 110, 35. with m = 2, Theta = p and q = w. - Wolfdieter Lang, Dec 01 2012
From Gus Wiseman, Sep 20 2023: (Start)
Also the number of unordered pairs of distinct positive integers up to n with sum k. For example, row n = 9 counts the following pairs:
  12  13  14  15  16  17  18  19  29  39  49  59  69  79  89
          23  24  25  26  27  28  38  48  58  68  78
                  34  35  36  37  47  57  67
                          45  46  56
Allowing repeated parts (x,x) gives A004737.
For strict partitions instead of just pairs we have A053632.
(End)

			1;
1,1,1;
1,1,2,1,1;
1,1,2,2,2,1,1;
1,1,2,2,3,2,2,1,1;
1,1,2,2,3,3,3,2,2,1,1;
...
Partitions: row p=2 and column w=2 has entry 2 because the 2 solutions of the two equations mentioned in a comment above are: m_0 = 0, m_1 = 2, m_2 = 0 and m_0 = 1, m_1 = 0, m_2 = 1. - _Wolfdieter Lang_, Dec 01 2012

G. E. Andrews, The Theory of Partitions, Addison-Wesley, 1976, p. 242.
F. N. David, M. G. Kendall and D. E. Barton, Symmetric Function and Allied Tables, Cambridge, 1966, p. 236.
T. Hawkins, Emergence of the Theory of Lie Groups, Springer 2000, ch. 7.4, p. 260-5.

John Tyler Rascoe, Rows n = 4..103, flattened
A. Cayley, A Second Memoir Upon Quantics, Phil. Trans. R. Soc. London, 146 (1856) 101-126.
Eric Weisstein's World of Mathematics, q-Binomial Coefficient.
Index entries for sequences related to dominoes

Cf. A008968, A047971, A106822.
A version with zeros is A219238.
This is the case of A365541 counting only length-2 subsets.
Cf. A000009, A004526, A004737, A053632, A068911, A167762, A238628, A365544.

qBinom := proc(n,m,q)
        mul((1-q^(n-i))/(1-q^(i+1)),i=0..m-1) ;
        factor(%) ;
        expand(%) ;
end proc:
A008967 := proc(n,k)
        coeftayl( qBinom(n,2,q),q=0,k ) ;
end proc:
seq(seq( A008967(n,k),k=0..2*n-4),n=2..10) ; # assumes offset 2. R. J. Mathar, Oct 13 2011

rmax = 11; f[r_] := Product[(x^i - x^(r+1))/(1-x^i), {i, 1, r-2}]/  x^((r-1)*(r-2)/2); row[r_] := CoefficientList[ Series[ f[r], {x, 0, 2rmax}], x]; Flatten[ Table[ row[r], {r, 2, rmax}]] (* Jean-François Alcover, Oct 13 2011, after given formula *)
T[n_, k_] := SeriesCoefficient[QBinomial[n - 2, 2, q], {q, 0, k}];
Table[T[n, k], {n, 4, 13}, {k, 0, 2 n - 8}] // Flatten (* Jean-François Alcover, Aug 20 2019 *)
Table[Length[Select[Subsets[Range[n],{2}],Total[#]==k&]],{n,2,15},{k,3,2n-1}] (* Gus Wiseman, Sep 20 2023 *)

print(flatten([q_binomial(n-2, 2).list() for n in (4..13)])) # Peter Luschny, Oct 23 2019

Let f(r) = Product( (x^i-x^(r+1))/(1-x^i), i = 1..r-2) / x^((r-1)*(r-2)/2); then expanding f(r) in powers of x and taking coefficients gives the successive rows of this triangle (with a different offset).
Expanding (q^n - 1)(q^(n+1) - 1)/((q - 1)(q^2 - 1)) in powers of q and taking coefficients gives the n-th row of the triangle. Ordinary generating function: 1/((1-x)(1-qx)(1-q^2x)) = 1 + x(1 + q + q^2) + x^2(1 + q + 2q^2 + q^3 + q^4) + .... - Peter Bala, Sep 23 2007
For n >= 2, let a(n,i) denote the i-th entry of the (n-1)-st row of this triangle; for every 0 <= i <= n-2, a(n,i) = a(n,2(n-2)-i) = ceiling((i+1)/2). - Christian Barrientos, Aug 08 2019

More terms from Christian Barrientos, Aug 08 2019

A028495 Expansion of g.f. (1-x^2)/(1-x-2*x^2+x^3).

Original entry on oeis.org

1, 1, 2, 3, 6, 10, 19, 33, 61, 108, 197, 352, 638, 1145, 2069, 3721, 6714, 12087, 21794, 39254, 70755, 127469, 229725, 413908, 745889, 1343980, 2421850, 4363921, 7863641, 14169633, 25532994, 46008619, 82904974, 149389218, 269190547, 485064009, 874055885

Offset: 0

N. J. A. Sloane

Form the graph with matrix A = [0,1,1; 1,0,0; 1,0,1] (P_3 with a loop at an extremity). Then A028495 counts closed walks of length n at the degree 3 vertex. - Paul Barry, Oct 02 2004
Equals INVERT transform of (1, 1, 0, 1, 0, 1, 0, 1, ...). - Gary W. Adamson, Apr 28 2009
From Johannes W. Meijer, May 29 2010: (Start)
a(n) is the number of ways White can force checkmate in exactly (n+1) moves, n>=0, ignoring the fifty-move and the triple repetition rules, in the following chess position: White Ka1, Ra8, Bc1, Nb8, pawns a6, a7, b2, c6, d2, f6 and h6; Black Kc8, pawns b3, c7, d3, f7 and h7. (After Noam D. Elkies, see link; diagram 5).
Counts all paths of length n, n>=0, starting at the initial node on the path graph P_6, see the second Maple program. (End)
a(n) is the number of length n-1 binary words such that each maximal block of 1's has odd length.  a(4) = 6 because we have: 000, 001, 010, 100, 101, 111. - Geoffrey Critzer, Nov 17 2012
a(n) is the number of compositions of n where increments can only appear at every second position, starting with the second and third part, see example. Also, a(n) is the number of compositions of n where there is no fall between every second pair of parts, starting with the first and second part; see example. - Joerg Arndt, May 21 2013
a(n) is the top left entry of the n-th power of the 3 X 3 matrix [1, 1, 0; 1, 0, 1; 0, 1, 0] or of the 3 X 3 matrix [1, 0, 1; 0, 0, 1; 1, 1, 0]. - R. J. Mathar, Feb 03 2014
Range of row n of the circular Pascal array of order 7. - Shaun V. Ault, Jun 05 2014
a(n) is the number of compositions of n into parts from {1,2,4,6,8,10,...}. Example: a(4)= 6 because we have 4, 22, 211, 121, 112, and 1111. - Emeric Deutsch, Aug 17 2016
In general, a(n,m) = (2^n/(m+1))*Sum_{r=1..m} (1-(-1)^r)*cos(Pi*r/(m+1))^n*(1+cos(Pi*r/(m+1))) gives the number of paths of length n starting at the initial node on the path graph P_m. Here we have m=6. - Herbert Kociemba, Sep 15 2020
a(n-1) is the number of triangular dcc-polyominoes having area n (see Baril et al. at page 11). - Stefano Spezia, Oct 14 2023
a(n) is the number of permutations p of [n] with p(j)Alois P. Heinz, Mar 29 2024

			G.f. = 1 + x + 2*x^2 + 3*x^3 + 6*x^4 + 10*x^5 + 19*x^6 + 33*x^7 + 61*x^8 + ...
From _Joerg Arndt_, May 21 2013: (Start)
There are a(6)=19 compositions of 6 where increments can only appear at every second position:
  01:  [ 1 1 1 1 1 1 ]
  02:  [ 1 1 1 1 2 ]
  03:  [ 1 1 2 1 1 ]
  04:  [ 1 1 2 2 ]
  05:  [ 1 1 3 1 ]
  06:  [ 1 1 4 ]
  07:  [ 2 1 1 1 1 ]
  08:  [ 2 1 2 1 ]
  09:  [ 2 1 3 ]
  10:  [ 2 2 1 1 ]
  11:  [ 2 2 2 ]
  12:  [ 3 1 1 1 ]
  13:  [ 3 1 2 ]
  14:  [ 3 2 1 ]
  15:  [ 3 3 ]
  16:  [ 4 1 1 ]
  17:  [ 4 2 ]
  18:  [ 5 1 ]
  19:  [ 6 ]
There are a(6)=19 compositions of 6 where there is no fall between every second pair of parts, starting with the first and second part:
  01:  [ 1 1 1 1 1 1 ]
  02:  [ 1 1 1 1 2 ]
  03:  [ 1 1 1 2 1 ]
  04:  [ 1 1 1 3 ]
  05:  [ 1 1 2 2 ]
  06:  [ 1 1 4 ]
  07:  [ 1 2 1 1 1 ]
  08:  [ 1 2 1 2 ]
  09:  [ 1 2 3 ]
  10:  [ 1 3 1 1 ]
  11:  [ 1 3 2 ]
  12:  [ 1 4 1 ]
  13:  [ 1 5 ]
  14:  [ 2 2 1 1 ]
  15:  [ 2 2 2 ]
  16:  [ 2 3 1 ]
  17:  [ 2 4 ]
  18:  [ 3 3 ]
  19:  [ 6 ]
(End)
19 = (1, 0, 1, 0, 1, 1) dot (1, 1, 2, 3, 6, 10) = (1 + 0 + 2 + 0 + 6 + 10). Cf. comment of Apr 28 2009. - _Gary W. Adamson_, Aug 10 2016

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
S. V. Ault and C. Kicey, Counting paths in corridors using circular Pascal arrays, Discrete Mathematics (2014).
Jean-Luc Baril, José L. Ramírez, and Fabio A. Velandia, Bijections between Directed-Column Convex Polyominoes and Restricted Compositions, September 29, 2023.
Alexandru Chirvasitu, Tara Hudson, and Aparna Upadhyay, Recursive sequences attached to modular representations of finite groups, arXiv:2105.04732 [math.RT], 2021. See (1) p. 27.
Johann Cigler, Some remarks and conjectures related to lattice paths in strips along the x-axis, arXiv:1501.04750 [math.CO], 2015.
Johann Cigler, Recurrences for certain sequences of binomial sums in terms of (generalized) Fibonacci and Lucas polynomials, arXiv:2212.02118 [math.NT], 2022.
Nachum Dershowitz, Between Broadway and the Hudson, arXiv:2006.06516 [math.CO], 2020.
Tomislav Došlić, Mate Puljiz, Stjepan Šebek, and Josip Žubrinić, On a variant of Flory model, arXiv:2210.12411 [math.CO], 2022.
Noam D. Elkies, New Directions in Enumerative Chess Problems, The Electronic Journal of Combinatorics, 11 (2), 2004-2005; arXiv:math/0508645 [math.CO], 2005. - _Johannes W. Meijer_, May 29 2010
Jia Huang, Partially Palindromic Compositions, J. Int. Seq. (2023) Vol. 26, Art. 23.4.1. See pp. 4, 14.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1056
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 1057
Mohammed L. Nadji, Moussa Ahmia, Daniel F. Checa, and José L. Ramírez, Arndt Compositions with Restricted Parts, Palindromes, and Colored Variants, J. Int. Seq. (2025) Vol. 28, Issue 3, Article 25.3.6. See pp. 9, 15.
László Németh and Dragan Stevanović, Graph solution of system of recurrence equations, Research Gate, 2023. See Table 2 at p. 6.
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
Index entries for linear recurrences with constant coefficients, signature (1,2,-1).

Cf. A052534, A052547, A096976, A276053, A068911, A078038, A094790, A000045, A038754, A028495, A030436, A061551, A178381.

Cf. A006053, A052975, A060557, A094718.

spec := [S,{S=Sequence(Union(Prod(Sequence(Prod(Z,Z)),Z,Z),Z))},unlabeled ]: seq(combstruct[count ](spec,size=n), n=0..20);
with(GraphTheory): P:=6: G:= PathGraph(P): A:=AdjacencyMatrix(G): nmax:=34; for n from 0 to nmax do B(n):=A^n; a(n):=add(B(n)[1,k], k=1..P) od: seq(a(n), n=0..nmax); # Johannes W. Meijer, May 29 2010
a := (-1)^(3/7) - (-1)^(4/7):
b := (-1)^(5/7) - (-1)^(2/7):
c := (-1)^(1/7) - (-1)^(6/7):
f := n -> (a^n * (2 + a) + b^n * (2 + b) + c^n * (2 + c))/7:
seq(simplify(f(n)), n=0..36); # Peter Luschny, Sep 16 2020

LinearRecurrence[{1, 2, -1}, {1, 1, 2}, 60] (* Vladimir Joseph Stephan Orlovsky, Feb 11 2012 *)
CoefficientList[Series[(1-x^2)/(1-x-2x^2+x^3),{x,0,40}],x] (* Harvey P. Dale, Dec 23 2018 *)
a[n_,m_]:= 2^(n+1)/(m+1) Module[{x=(Pi r)/(m+1)},Sum[Cos[x]^n (1+Cos[x]),{r,1,m,2}]]
Table[a[n,6],{n,0,40}]//Round (* Herbert Kociemba, Sep 15 2020 *) (* Herbert Kociemba, Sep 14 2020 *)

{a(n) = if( n<0, n = -1-n; polcoeff( (1 - x^2) / (1 - 2*x - x^2 + x^3) + x * O(x^n), n), polcoeff( (1 - x^2) / (1 - x - 2*x^2 + x^3) + x * O(x^n), n))} /* Michael Somos, Apr 05 2012 */

a(n)=([0,1,0;0,0,1;-1,2,1]^n*[1;1;2])[1,1] \\ Charles R Greathouse IV, Aug 25 2016

Recurrence: {a(0)=1, a(1)=1, a(2)=2, a(n)-2*a(n+1)-a(n+2)+a(n+3)=0}.
a(n) = Sum_(1/7*(1+2*_alpha)*_alpha^(-1-n), _alpha=RootOf(_Z^3-2*_Z^2-_Z+1)).
a(n) = A094718(6, n). - N. J. A. Sloane, Jun 12 2004
a(n) = a(n-1) + Sum_{k=1..floor(n/2)} a(n-2*k). - Floor van Lamoen, Oct 29 2005
a(n) = 5*a(n-2) - 6*a(n-4) + a(n-6). - Floor van Lamoen, Nov 02 2005
a(n) = A006053(n+2) - A006053(n). - R. J. Mathar, Nov 16 2007
a(2*n) = A052975(n), a(2*n+1) = A060557(n). - Johannes W. Meijer, May 29 2010
G.f.: 1 / (1 - x / (1 - x / (1 + x / (1 + x / (1 - x))))). - Michael Somos, Apr 05 2012
a(-1 - n) = A052534(n). - Michael Somos, Apr 05 2012
a(n) = (2^n/7)*Sum_{r=1..6} (1-(-1)^r)*cos(Pi*r/7)^n*(1+cos(Pi*r/7)). - Herbert Kociemba, Sep 15 2020

More terms from James Sellers, Jun 05 2000

A238628 Number of partitions p of n such that n - max(p) is a part of p.

Original entry on oeis.org

0, 1, 1, 3, 2, 5, 3, 8, 4, 11, 5, 16, 6, 21, 7, 29, 8, 38, 9, 51, 10, 66, 11, 88, 12, 113, 13, 148, 14, 190, 15, 246, 16, 313, 17, 402, 18, 508, 19, 646, 20, 812, 21, 1023, 22, 1277, 23, 1598, 24, 1982, 25, 2461, 26, 3036, 27, 3745, 28, 4593, 29, 5633

Offset: 1

Clark Kimberling, Mar 02 2014

Also the number of integer partitions of n that are of length 2 or contain n/2. The first condition alone is A004526, complement A058984. The second condition alone is A035363, complement A086543, ranks A344415. - Gus Wiseman, Oct 07 2023

			a(6) counts these partitions:  51, 42, 33, 321, 3111.

Cf. A238479.
The strict case is A365659, complement A365826.
The complement is counted by A365825.
These partitions are ranked by A366318.
A000041 counts integer partitions, strict A000009.
A140106 counts strict partitions of length 2, complement A365827.
A182616 counts partitions of 2n that do not contain n, strict A365828.
Cf. A004526, A005408, A008967, A035363, A058984, A068911, A086543.

Table[Count[IntegerPartitions[n], p_ /; MemberQ[p, n - Max[p]]], {n, 50}]

a(n) = my(res = floor(n/2)); if(!bitand(n, 1), res+=(numbpart(n/2)-1)); res

from sympy.utilities.iterables import partitions
def A238628(n): return sum(1 for p in partitions(n) if n-max(p,default=0) in p) # Chai Wah Wu, Sep 21 2023

A365541 Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} containing two distinct elements summing to k = 3..2n-1.

Original entry on oeis.org

1, 2, 2, 2, 4, 4, 7, 4, 4, 8, 8, 14, 14, 14, 8, 8, 16, 16, 28, 28, 37, 28, 28, 16, 16, 32, 32, 56, 56, 74, 74, 74, 56, 56, 32, 32, 64, 64, 112, 112, 148, 148, 175, 148, 148, 112, 112, 64, 64, 128, 128, 224, 224, 296, 296, 350, 350, 350, 296, 296, 224, 224, 128, 128

Offset: 2

Gus Wiseman, Sep 15 2023

Rows are palindromic.

			Triangle begins:
    1
    2    2    2
    4    4    7    4    4
    8    8   14   14   14    8    8
   16   16   28   28   37   28   28   16   16
   32   32   56   56   74   74   74   56   56   32   32
Row n = 4 counts the following subsets:
  {1,2}      {1,3}      {1,4}      {2,4}      {3,4}
  {1,2,3}    {1,2,3}    {2,3}      {1,2,4}    {1,3,4}
  {1,2,4}    {1,3,4}    {1,2,3}    {2,3,4}    {2,3,4}
  {1,2,3,4}  {1,2,3,4}  {1,2,4}    {1,2,3,4}  {1,2,3,4}
                        {1,3,4}
                        {2,3,4}
                        {1,2,3,4}

Row lengths are A005408.
The case counting only length-2 subsets is A008967.
Column k = n + 1 appears to be A167762.
The version for all subsets (instead of just pairs) is A365381.
Column k = n is A365544.
A000009 counts subsets summing to n.
A007865/A085489/A151897 count certain types of sum-free subsets.
A046663 counts partitions with no submultiset summing to k, strict A365663.
A093971/A088809/A364534 count certain types of sum-full subsets.
A365543 counts partitions with a submultiset summing to k, strict A365661.
Cf. A068911, A095944, A238628, A288728, A326083, A364272, A365376, A365377.

Table[Length[Select[Subsets[Range[n]], MemberQ[Total/@Subsets[#,{2}],k]&]], {n,2,11}, {k,3,2n-1}]

A124302 Number of set partitions with at most 3 blocks; number of Dyck paths of height at most 4; dimension of space of symmetric polynomials in 3 noncommuting variables.

Original entry on oeis.org

1, 1, 2, 5, 14, 41, 122, 365, 1094, 3281, 9842, 29525, 88574, 265721, 797162, 2391485, 7174454, 21523361, 64570082, 193710245, 581130734, 1743392201, 5230176602, 15690529805, 47071589414, 141214768241, 423644304722, 1270932914165, 3812798742494, 11438396227481

Offset: 0

Mike Zabrocki, Oct 25 2006

Row sums of triangle in A056241. - Philippe Deléham, Oct 30 2006
Row sums of triangle in A147746. - Philippe Deléham, Dec 04 2008
Hankel transform is := [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, ...]. - Philippe Deléham, Dec 04 2008
Number of nonisomorphic graded posets with 0 and 1 and uniform Hasse graph of rank n with no 3-element antichain. (Uniform used in the sense of Retakh, Serconek and Wilson.  Graded used in Stanley's sense that every maximal chain has the same length n.) - David Nacin, Feb 26 2012
Number of Dyck paths of length 2n and height at most 4. - Ira M. Gessel, Aug 06 2012

			There are 15 set partitions of {1,2,3,4}, only {{1},{2},{3},{4}} has more than 3 blocks, so a(4) = 14.
G.f. = 1 + x + 2*x^2 + 5*x^3 + 14*x^4 + 41*x^5 + 122*x^6 + 365*x^7 + ...

R. Stanley, Enumerative combinatorics, Vol. 1, Cambridge University Press, Cambridge, 1997, pp. 96-100.

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Per Alexandersson and Frether Getachew, An involution on derangements, arXiv:2105.08455 [math.CO], 2021.
N. Bergeron, C. Reutenauer, M. Rosas and M. Zabrocki, Invariants and Coinvariants of the Symmetric Group in Noncommuting Variables, arXiv:math/0502082 [math.CO], 2005; Canad. J. Math. 60 (2008), no. 2, 266-296.
Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, arXiv:1907.08142 [cs.DS], 2019.
S. Felsner and D. Heldt, Lattice Path Enumeration and Toeplitz Matrices, J. Int. Seq. 18 (2015) # 15.1.3.
Daniel Heldt, On the mixing time of the face flip-and up/down Markov chain for some families of graphs, Dissertation, Mathematik und Naturwissenschaften der Technischen Universitat Berlin zur Erlangung des akademischen Grades Doktor der Naturwissenschaften, 2016.
M. Hyatt and J. Remmel, The classification of 231-avoiding permutations by descents and maximum drop, arXiv preprint arXiv:1208.1052 [math.CO], 2012. - From _N. J. A. Sloane_, Dec 24 2012
V. Jelinek, T. Mansour, and M. Shattuck, On multiple pattern avoiding set partitions, Adv. Appl. Math. 50 (2) (2013) 292-326, - From _N. J. A. Sloane_, Jan 01 2013
Sergey Kitaev, Jeffrey Remmel and Mark Tiefenbruck, Marked mesh patterns in 132-avoiding permutations I, arXiv:1201.6243 [math.CO], 2012-2014 (Corollary 3, case k=4, pages 10-11). - From _N. J. A. Sloane_, May 09 2012
Sergey Kitaev, Jeffrey Remmel, and Mark Tiefenbruck, Quadrant Marked Mesh Patterns in 132-Avoiding Permutations II, Electronic Journal of Combinatorial Number Theory, Volume 15 #A16. (arXiv:1302.2274)
László Németh and László Szalay, Sequences Involving Square Zig-Zag Shapes, J. Int. Seq., Vol. 24 (2021), Article 21.5.2.
V. Retakh, S. Serconek, and R. Wilson, Hilbert Series of Algebras Associated to Directed Graphs and Order Homology, arXiv:1010.6295 [math.RA], 2010-2011.
Santiago Rojas-Rojas, Camila Muñoz, Edgar Barriga, Pablo Solano, Aldo Delgado, and Carla Hermann-Avigliano, Analytic Evolution for Complex Coupled Tight-Binding Models: Applications to Quantum Light Manipulation, arXiv:2310.12366 [quant-ph], 2023. See p. 12.
M. Rosas and B. Sagan, Symmetric Functions in Noncommuting Variables, Transactions of the American Mathematical Society, 358 (2006), no. 1, 215-232.
Index entries for linear recurrences with constant coefficients, signature (4,-3).

Cf. A056272, A123183, A001519, A000110, A008277, A038754, A048328, A068911, A211216.

Essentially the same as A007051.

I:=[1, 1, 2]; [n le 3 select I[n] else  4*Self(n-1) - 3*Self(n-2): n in [1..30]]; // Vincenzo Librandi, Dec 25 2012

a:= proc(n); if n<3 then [1,1,2][n+1]; else 4*a(n-1)-3*a(n-2); fi; end:
# Mike Zabrocki, Oct 25 2006
with(GraphTheory): G:=PathGraph(5): A:= AdjacencyMatrix(G): nmax:=27; for n from 0 to 2*nmax do B(n):=A^n; b(n):=B(n)[1,1]; od: for n from 0 to nmax do a(n):=b(2*n) od: seq(a(n),n=0..nmax);
# Johannes W. Meijer, May 29 2010

a=Exp[x]-1; Range[0, 20]! CoefficientList[Series[1+a+a^2/2+a^3/6, {x,0,20}],x]
Join[{1}, LinearRecurrence[{4, -3}, {1, 2}, 20]] (* David Nacin, Feb 26 2012 *)
CoefficientList[Series[1 / (1 - x / (1 - x / (1 - x / (1 - x)))), {x, 0, 30}], x] (* Vincenzo Librandi, Dec 25 2012 *)
Table[Sum[StirlingS2[n,k],{k,0,3}],{n,0,30}] (* Robert A. Russell, Mar 29 2018 *)

{a(n) = if( n<1, n==0, (3^(n-1) + 1) / 2)}; /* Michael Somos, Apr 03 2014 */

def a(n, adict={0:1, 1:1, 2:2}):
    if n in adict:
        return adict[n]
    adict[n]=4*a(n-1) - 3*a(n-2)
    return adict[n] # David Nacin, Mar 04 2012

O.g.f.: (q^2 - 3*q + 1)/(3*q^2 - 4*q + 1) = Sum_{k=0..3} (q^k/Product_{i=1..k} (1-i*q)).
a(n) = 4*a(n-1) - 3*a(n-2); a(0) = 1, a(1) = 1, a(2) = 2, a(n) = Sum_{k=1..3} A008277(n,k).
Inverse binomial transform of A007581. - Philippe Deléham, Oct 30 2006
a(n) = Sum_{k=0..n} A056241(n,k), n >= 1. - Philippe Deléham, Oct 30 2006
a(0) = 1, a(n) = (3^(n-1) + 1)/2 for n >= 1, see A007051. - Philippe Deléham, Oct 30 2006
E.g.f.: (2 + 3*exp(x) + exp(3x))/6.
G.f.: 1 / (1 - x / (1 - x / (1 - x / (1 - x)))). - Michael Somos, May 03 2012
G.f.: 1 + x + 3*x^2*U(0)/2 where U(k) = 1 + 2/(3*3^k + 3*3^k/(1 - 18*x*3^k/ (9*x*3^k - 1/U(k+1)))); (continued fraction, 4-step). - Sergei N. Gladkovskii, Nov 01 2012
G.f.: 1+x*G(0) where G(k) = 1 + 2*x/( 1-2*x - x*(1-2*x)/(x + (1-2*x)*2/G(k+1) )); (recursively defined continued fraction). - Sergei N. Gladkovskii, Dec 10 2012
a(n) = Sum_{k=0..3} Stirling2(n,k). - Robert A. Russell, Mar 29 2018
G.f.: Sum_{j=0..k} A248925(k,j)*x^j / Product_{j=1..k} 1-j*x with k=3. - Robert A. Russell, Apr 25 2018

A367216 Number of subsets of {1..n} whose cardinality is equal to the sum of some subset.

Original entry on oeis.org

1, 2, 3, 5, 10, 20, 40, 82, 169, 348, 716, 1471, 3016, 6171, 12605, 25710, 52370, 106539, 216470, 439310, 890550, 1803415, 3648557, 7375141, 14896184, 30065129, 60639954, 122231740, 246239551, 495790161, 997747182, 2006969629, 4035274292, 8110185100, 16293958314, 32724456982

Offset: 0

Gus Wiseman, Nov 12 2023

nonn

			The a(0) = 1 through a(4) = 10 subsets:
  {}  {}   {}     {}       {}
      {1}  {1}    {1}      {1}
           {1,2}  {1,2}    {1,2}
                  {2,3}    {2,3}
                  {1,2,3}  {2,4}
                           {1,2,3}
                           {1,2,4}
                           {1,3,4}
                           {2,3,4}
                           {1,2,3,4}

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
               sum-full   sum-free   comb-full  comb-free
              -------------------------------------------
  partitions:  A367212    A367213    A367218    A367219
  strict:      A367214    A367215    A367220    A367221
  subsets:     A367216*   A367217    A367222    A367223
  ranks:       A367224    A367225    A367226    A367227
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A002865 counts partitions whose length is a part, complement A229816.
A007865/A085489/A151897 count certain types of sum-free subsets.
A088809/A093971/A364534 count certain types of sum-full subsets.
A237668 counts sum-full partitions, ranks A364532.
A240855 counts strict partitions whose length is a part, complement A240861.
A364272 counts sum-full strict partitions, sum-free A364349.
A365046 counts combination-full subsets, differences of A364914.
Triangles:
A365381 counts sets with a subset summing to k, without A366320.
A365541 counts sets containing two distinct elements summing to k.
Cf. A068911, A095944, A103580, A288728, A326080, A326083, A365376, A365544.

Table[Length[Select[Subsets[Range[n]], MemberQ[Total/@Subsets[#], Length[#]]&]], {n,0,10}]

a(n) = 2^n - A367217(n). - Chai Wah Wu, Nov 14 2023

a(16)-a(28) from Chai Wah Wu, Nov 14 2023

a(29)-a(35) from Max Alekseyev, Feb 25 2025

A367217 Number of subsets of {1..n} whose cardinality is not equal to the sum of any subset.

Original entry on oeis.org

0, 0, 1, 3, 6, 12, 24, 46, 87, 164, 308, 577, 1080, 2021, 3779, 7058, 13166, 24533, 45674, 84978, 158026, 293737, 545747, 1013467, 1881032, 3489303, 6468910, 11985988, 22195905, 41080751, 75994642, 140514019, 259693004, 479749492, 885910870, 1635281386

Offset: 0

Gus Wiseman, Nov 12 2023

nonn

			The a(2) = 1 through a(5) = 12 subsets:
  {2}  {2}    {2}    {2}
       {3}    {3}    {3}
       {1,3}  {4}    {4}
              {1,3}  {5}
              {1,4}  {1,3}
              {3,4}  {1,4}
                     {1,5}
                     {3,4}
                     {3,5}
                     {4,5}
                     {1,4,5}
                     {2,4,5}

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
               sum-full   sum-free   comb-full  comb-free
              -------------------------------------------
  partitions:  A367212    A367213    A367218    A367219
  strict:      A367214    A367215    A367220    A367221
  subsets:     A367216    A367217*   A367222    A367223
  ranks:       A367224    A367225    A367226    A367227
A000009 counts subsets summing to n.
A000124 counts distinct possible sums of subsets of {1..n}.
A229816 counts partitions whose length is not a part, complement A002865.
A007865/A085489/A151897 count certain types of sum-free subsets.
A088809/A093971/A364534 count certain types of sum-full subsets.
A124506 appears to count combination-free subsets, differences of A326083.
A237667 counts sum-free partitions, ranks A364531.
Triangles:
A046663 counts partitions of n without a subset-sum k, strict A365663.
A365381 counts sets with a subset summing to k, without A366320.
A365541 counts sets containing two distinct elements summing to k.
Cf. A068911, A103580, A240861, A288728, A326080, A326083, A364346, A364349, A365046, A365376, A365377.

Table[Length[Select[Subsets[Range[n]], FreeQ[Total/@Subsets[#], Length[#]]&]], {n,0,15}]

a(n) = 2^n - A367216(n). - Chai Wah Wu, Nov 14 2023

a(16)-a(28) from Chai Wah Wu, Nov 14 2023

a(29)-a(35) from Max Alekseyev, Feb 25 2025

A367219 Number of integer partitions of n whose length cannot be written as a nonnegative linear combination of the distinct parts.

Original entry on oeis.org

0, 0, 1, 1, 1, 1, 3, 2, 4, 4, 7, 6, 11, 9, 16, 16, 23, 22, 35, 33, 48, 50, 69, 70, 99, 99, 136, 142, 187, 194, 261, 267, 346, 367, 468, 489, 626, 650, 824, 870, 1081, 1135, 1421, 1485, 1833, 1942, 2374, 2501, 3062, 3220, 3915, 4145, 4987, 5274, 6363, 6709, 8027

Offset: 0

Gus Wiseman, Nov 14 2023

nonn

			3 cannot be written as a nonnegative linear combination of 2 and 5, so (5,2,2) is counted under a(9).
The a(2) = 1 through a(10) = 7 partitions:
  (2)  (3)  (4)  (5)  (6)      (7)    (8)      (9)      (10)
                      (3,3)    (4,3)  (4,4)    (5,4)    (5,5)
                      (2,2,2)         (5,3)    (6,3)    (6,4)
                                      (4,2,2)  (5,2,2)  (7,3)
                                                        (4,4,2)
                                                        (6,2,2)
                                                        (2,2,2,2,2)

The following sequences count and rank integer partitions and finite sets according to whether their length is a subset-sum or linear combination of the parts. The current sequence is starred.
               sum-full   sum-free   comb-full  comb-free
              -------------------------------------------
  partitions:  A367212    A367213    A367218    A367219*
  strict:      A367214    A367215    A367220    A367221
  subsets:     A367216    A367217    A367222    A367223
  ranks:       A367224    A367225    A367226    A367227
A000041 counts integer partitions, strict A000009.
A002865 counts partitions whose length is a part, complement A229816.
A008284 counts partitions by length, strict A008289.
A124506 appears to count combination-free subsets, differences of A326083.
A365046 counts combination-full subsets, differences of A364914.
Cf. A068911, A088314, A116861, A364345, A364350, A365073, A365312, A365380.

combs[n_,y_]:=With[{s=Table[{k,i},{k,y},{i,0,Floor[n/k]}]},Select[Tuples[s],Total[Times@@@#]==n&]];
Table[Length[Select[IntegerPartitions[n],combs[Length[#],Union[#]]=={}&]],{n,0,15}]

a(31)-a(56) from Chai Wah Wu, Nov 15 2023

cp's OEIS Frontend

A048675 If n = p_i^e_i * ... * p_k^e_k, p_i < ... < p_k primes (with p_i = prime(i)), then a(n) = (1/2) * (e_i * 2^i + ... + e_k * 2^k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A038754 a(2n) = 3^n, a(2n+1) = 2*3^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

A008967 Coefficients of Gaussian polynomials q_binomial(n-2, 2). Also triangle of distribution of rank sums: Wilcoxon's statistic. Irregular triangle read by rows.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

SageMath

Formula

Extensions

A028495 Expansion of g.f. (1-x^2)/(1-x-2*x^2+x^3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A238628 Number of partitions p of n such that n - max(p) is a part of p.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Python

A365541 Irregular triangle read by rows where T(n,k) is the number of subsets of {1..n} containing two distinct elements summing to k = 3..2n-1.

Views

Author

Keywords

Comments