A034691 -id:A034691 - cp's OEIS frontend

A140585 Total number of all hierarchical orderings for all set partitions of n.

1, 4, 20, 129, 1012, 9341, 99213, 1191392, 15958404, 235939211, 3817327362, 67103292438, 1273789853650, 25973844914959, 566329335460917, 13150556885604115, 324045146807055210, 8446201774570017379, 232198473069120178475, 6715304449424099384968

Offset: 1

Thomas Wieder, May 17 2008

nonn

			We are considering all set partitions of the n-set {1,2,3,...,n}.
For each such set partition we examine all possible hierarchical arrangements of the subsets. A hierarchy is a distribution of elements (sets in the present case) onto levels.
A distribution onto levels is "hierarchical" if a level L+1 contains at most as many elements as level L. Thus for n=4 the arrangement {1,2}:{3}{4} is not allowed.
Let the colon ":" separate two consecutive levels L and L+1.
n=2 --> 1+3=4
{1,2} {1}{2}
{1}:{2}
{2}:{1}
-----------------------
n=3 --> 1+9+10=20
1*1 3*3=9 1*10
{1,2,3} {1,2}{3} {1}{2}{3}
{1,3}{2}
{2,3}{1} {1}{2}:{3}
{3}{1}:{2}
{1,2}:{3} {2}{3}:{1}
{1,3}:{2}
{2,3}:{1} {1}:{2}:{3}
{3}:{1}:{2}
{3}:{1,2} {2}:{3}:{1}
{2}:{1,3} {1}:{3}:{2}
{1}:{2,3} {2}:{1}:{3}
{3}:{2}:{1}
-----------------------
n=4 --> 1+12+9+60+47=129
1*1 4*3=12 3*3=9 6*10=60 1*47
{1,2,3,4} {1,2,3}{4} {1,2}{3,4} {1,2}{3}{4} {1}{2}{3}{4}
{1,2,4}{3} {1,3}{2,4} {1,2}{3}:{4}
{1,3,4}{2} {1,4}{2,3} {1,2}{4}:{3} {1}{2}:{3}:{4}
{2,3,4}{1} {1}{2}:{3,4} {1}{3}:{2}:{4}
{1,2}:{3,4} {1,2}:{3}:{4} {1}{4}:{2}:{3}
{1,2,3}:{4} {1,3}:{2,4} {1,2}:{4}:{3} {1}{2}:{4}:{3}
{1,2,4}:{3} {1,4}:{2,3} {1}:{2}:{3,4} {1}{3}:{4}:{2}
{1,3,4}:{2} {3,4}:{1,2} {2}:{1}:{3,4} {1}{4}:{3}:{2}
{2,3,4}:{1} {2,4}:{1,3} {1}:{3,4}:{2}
{2,3}:{1,4} {2}:{3,4}:{1} {2}{3}:{1}:{4}
{4}:{1,2,3} {2}{4}:{1}:{3}
{3}:{1,2,4} likewise for: {2}{3}:{4}:{1}
{2}:{1,3,4} {3,4}{1}{2} {2}{4}:{3}:{1}
{1}:{2,3,4} {2,4}{1}{3}
{2,3}{1}{4} {3}{4}:{1}:{2}
{1,4}{2}{3} {3}{4}:{2}:{1}
{1,3}{2}{4}
{1}{2}:{3}{4}
{1}{3}:{2}{4}
{1}{4}:{2}{3}
{2}{3}:{1}{4}
{2}{4}:{1}{3}
{3}{4}:{1}{2}
{2}{3}{4}:{1}
{1}{3}{4}:{2}
{1}{2}{4}:{3}
{1}{2}{3}:{4}
{1}:{2}:{3}:{4}
+23 permutations

Vaclav Kotesovec, Table of n, a(n) for n = 1..420 (first 160 terms from Alois P. Heinz)
Thomas Wieder, The number of certain rankings and hierarchies formed from labeled or unlabeled elements and sets, Applied Mathematical Sciences, vol. 3, 2009, no. 55, 2707 - 2724. [_Thomas Wieder_, Nov 14 2009]

Cf. A005651, A075729, A034691, A083355, A109186, A000670.

A140585 := proc(n::integer) local k, Result; Result:=0: for k from 1 to n do Result:=Result+stirling2(n,k)*A005651(k); end do; lprint(Result); end proc;
E.g.f.: series(1/mul(1-(exp(x)-1)^k/k!,k=1..10),x=0,10). # Thomas Wieder, Sep 04 2008
# second Maple program:
with(numtheory): b:= proc(k) option remember; add(d/d!^(k/d), d=divisors(k)) end: c:= proc(n) option remember; `if`(n=0, 1, add((n-1)!/ (n-k)!* b(k)* c(n-k), k=1..n)) end: a:= n-> add(Stirling2(n, k) *c(k), k=1..n): seq(a(n), n=1..30); # Alois P. Heinz, Oct 10 2008

Table[n!*SeriesCoefficient[1/Product[(1-(E^x-1)^k/k!),{k,1,n}],{x,0,n}],{n,1,20}] (* Vaclav Kotesovec, Sep 03 2014 *)

Stirling transform of A005651 = Sum of multinomial coefficients: a(n) = Sum_{i=1..n} S2(n,k) A005651(k).
E.g.f.: 1/Product_{k>=1} (1 - (exp(x)-1)^k/k!). - Thomas Wieder, Sep 04 2008
a(n) ~ c * n! / (log(2))^n, where c = 1/(2*log(2)) * Product_{k>=2} 1/(1-1/k!) = A247551 / (2*log(2)) = 1.82463230250447246267598544320244231645906135137... . - Vaclav Kotesovec, Sep 04 2014, updated Jan 21 2017

More terms from Alois P. Heinz, Oct 10 2008

A256142 G.f.: Product_{j>=1} (1+x^j)^(3^j).

Original entry on oeis.org

1, 3, 12, 55, 225, 927, 3729, 14787, 57888, 224220, 860022, 3270744, 12343899, 46264257, 172305837, 638039136, 2350109736, 8613851832, 31428857611, 114187160631, 413222547846, 1489829356657, 5352683946903, 19167988920930, 68427472477338, 243559693397025

Offset: 0

Vaclav Kotesovec, Mar 16 2015

nonn

In general, if g.f. = Product_{j>=1} (1+x^j)^(k^j), then a(n) ~ k^n * exp(2*sqrt(n) - 1/2 - c(k)) / (2 * sqrt(Pi) * n^(3/4)), where c(k) = Sum_{m>=2} (-1)^m/(m*(k^(m-1)-1)).

Vaclav Kotesovec, Table of n, a(n) for n = 0..1000
Vaclav Kotesovec, Asymptotics of sequence A034691
Vaclav Kotesovec, A method of finding the asymptotics of q-series based on the convolution of generating functions, arXiv:1509.08708 [math.CO], Sep 30 2015, p. 27.

Cf. A102866, A144067, A144074.

Column k=3 of A292804.

nmax=30; CoefficientList[Series[Product[(1+x^k)^(3^k),{k,1,nmax}],{x,0,nmax}],x]

a(n) ~ 3^n * exp(2*sqrt(n) - 1/2 - c) / (2 * sqrt(Pi) * n^(3/4)), where c = Sum_{m>=2} (-1)^m/(m*(3^(m-1)-1)) = 0.215985336303958581708278160877115129... .

A335482 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (2,3,1).

Original entry on oeis.org

41, 81, 83, 89, 105, 145, 161, 163, 165, 166, 167, 169, 177, 179, 185, 209, 211, 217, 233, 289, 290, 291, 297, 305, 321, 323, 325, 326, 327, 329, 331, 332, 333, 334, 335, 337, 339, 345, 353, 355, 357, 358, 359, 361, 369, 371, 377, 401, 417, 419, 421, 422, 423

Offset: 1

Gus Wiseman, Jun 18 2020

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.

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			The sequence of terms together with the corresponding compositions begins:
   41: (2,3,1)
   81: (2,4,1)
   83: (2,3,1,1)
   89: (2,1,3,1)
  105: (1,2,3,1)
  145: (3,4,1)
  161: (2,5,1)
  163: (2,4,1,1)
  165: (2,3,2,1)
  166: (2,3,1,2)
  167: (2,3,1,1,1)
  169: (2,2,3,1)
  177: (2,1,4,1)
  179: (2,1,3,1,1)
  185: (2,1,1,3,1)

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

The version counting permutations is A056986.
Patterns matching this pattern are counted by A335515 (by length).
Permutations of prime indices matching this pattern are counted by A335520.
These compositions are counted by A335514 (by sum).
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Permutations matching (1,3,2,4) are counted by A158009.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Other permutations:
- A335479 (1,2,3)
- A335480 (1,3,2)
- A335481 (2,1,3)
- A335482 (2,3,1)
- A335483 (3,1,2)
- A335484 (3,2,1)
Cf. A034691, A056986, A108917, A114994, A158005, A238279, A333224, A333257, A334968, A335456, A335458.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Select[Range[0,100],MatchQ[stc[#],{_,x_,_,y_,_,z_,_}/;z

A335485 Numbers k such that the k-th composition in standard order (A066099) is not weakly decreasing.

Original entry on oeis.org

6, 12, 13, 14, 20, 22, 24, 25, 26, 27, 28, 29, 30, 38, 40, 41, 44, 45, 46, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 70, 72, 76, 77, 78, 80, 81, 82, 83, 84, 86, 88, 89, 90, 91, 92, 93, 94, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106

Offset: 1

Gus Wiseman, Jun 18 2020

nonn

Also compositions matching the pattern (1,2).

A composition of n is a finite sequence of positive integers summing to n. 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 sequence of terms together with the corresponding compositions begins:
   6: (1,2)
  12: (1,3)
  13: (1,2,1)
  14: (1,1,2)
  20: (2,3)
  22: (2,1,2)
  24: (1,4)
  25: (1,3,1)
  26: (1,2,2)
  27: (1,2,1,1)
  28: (1,1,3)
  29: (1,1,2,1)
  30: (1,1,1,2)
  38: (3,1,2)
  40: (2,4)

Keiichi Shigechi, Noncommutative crossing partitions, arXiv:2211.10958 [math.CO], 2022.
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

The complement A114994 is the avoiding version.
The (2,1)-matching version is A335486.
Patterns matching this pattern are counted by A002051 (by length).
Permutations of prime indices matching this pattern are counted by A335447.
These compositions are counted by A056823 (by sum).
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Combinatory separations are counted by A269134.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Cf. A034691, A056986, A108917, A114994, A238279, A333224, A333257, A335456, A335458.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Select[Range[0,100],MatchQ[stc[#],{_,x_,_,y_,_}/;x

A095684 Triangle read by rows. There are 2^(m-1) rows of length m, for m = 1, 2, 3, ... The rows are in lexicographic order. The rows have the property that the first entry is 1, the second distinct entry (reading from left to right) is 2, the third distinct entry is 3, etc.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane, Jun 25 2004

Row k is the unique multiset that covers an initial interval of positive integers and has multiplicities equal to the parts of the k-th composition in standard order (graded reverse-lexicographic, A066099). This composition 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. For example, the 13th composition is (1,2,1), so row 13 is {1,2,2,3}. - Gus Wiseman, Apr 26 2020

			1, 11, 12, 111, 112, 122, 123, 1111, 1112, 1122, 1123, 1222, 1223, 1233, ...
The 8 strings of length 4 are 1111, 1112, 1122, 1123, 1222, 1223, 1233, 1234.
From _Gus Wiseman_, Apr 26 2020: (Start)
The triangle read by columns begins:
  1:{1}  2:{1,1}  4:{1,1,1}   8:{1,1,1,1}  16:{1,1,1,1,1}
         3:{1,2}  5:{1,1,2}   9:{1,1,1,2}  17:{1,1,1,1,2}
                  6:{1,2,2}  10:{1,1,2,2}  18:{1,1,1,2,2}
                  7:{1,2,3}  11:{1,1,2,3}  19:{1,1,1,2,3}
                             12:{1,2,2,2}  20:{1,1,2,2,2}
                             13:{1,2,2,3}  21:{1,1,2,2,3}
                             14:{1,2,3,3}  22:{1,1,2,3,3}
                             15:{1,2,3,4}  23:{1,1,2,3,4}
                                           24:{1,2,2,2,2}
                                           25:{1,2,2,2,3}
                                           26:{1,2,2,3,3}
                                           27:{1,2,2,3,4}
                                           28:{1,2,3,3,3}
                                           29:{1,2,3,3,4}
                                           30:{1,2,3,4,4}
                                           31:{1,2,3,4,5}
(End)

J. C. Kieffer, W. Szpankowski and E.-H. Yang, Problems on sequences: information theory and computer science interface, IEEE Trans. Inform. Theory, 50 (No. 7, 2004), 1385-1392.

See A096299 for another version.
The number of distinct parts in row n is A000120(n), also the maximum part.
Row sums are A029931.
Heinz numbers of rows are A057335.
Row lengths are A070939.
Row products are A284001.
The version for prime indices is A305936.
There are A333942(n) multiset partitions of row n.
Multisets of compositions are counted by A034691.
Combinatory separations of normal multisets are A269134.
All of the following pertain to compositions in standard order (A066099):
- Necklaces are A065609.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon words are A275692.
- Dealings are counted by A333939.
- Distinct parts are counted by A334028.
Cf. A318284, A333764, A333940, A334030.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
ptnToNorm[y_]:=Join@@Table[ConstantArray[i,y[[i]]],{i,Length[y]}];
Table[ptnToNorm[stc[n]],{n,15}] (* Gus Wiseman, Apr 26 2020 *)

A334029 Length of the co-Lyndon factorization of the k-th composition in standard order.

Original entry on oeis.org

0, 1, 1, 2, 1, 1, 2, 3, 1, 1, 2, 1, 2, 2, 3, 4, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 3, 2, 3, 3, 4, 5, 1, 1, 1, 1, 2, 1, 1, 1, 2, 2, 3, 1, 2, 2, 2, 1, 2, 2, 2, 2, 3, 2, 3, 2, 3, 3, 4, 3, 4, 4, 5, 6, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 1, 2, 2, 2, 2, 3, 1, 2

Offset: 0

Gus Wiseman, Apr 14 2020

nonn

We define the co-Lyndon product of two or more finite sequences to be the lexicographically minimal sequence obtainable by shuffling the sequences together. For example, the co-Lyndon product of (2,3,1) with (2,1,3) is (2,1,2,3,1,3), the product of (2,2,1) with (2,1,3) is (2,1,2,2,1,3), and the product of (1,2,2) with (2,1,2,1) is (1,2,1,2,1,2,2). 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, (1,0,0,1) has co-Lyndon factorization {(1),(1,0,0)}.

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.

			The 441st composition in standard order is (1,2,1,1,3,1), with co-Lyndon factorization {(1),(3,1),(2,1,1)}, so a(441) = 3.

The dual version is A329312.
The version for binary expansion is (also) A329312.
The version for reversed binary expansion is A329326.
Binary Lyndon/co-Lyndon words are counted by A001037.
Necklaces covering an initial interval are A019536.
Lyndon/co-Lyndon compositions are counted by A059966
Length of Lyndon factorization of binomial expansion is A211100.
Numbers whose prime signature is a necklace are A329138.
Length of Lyndon factorization of reversed binary expansion is A329313.
A list of all binary co-Lyndon words is A329318.
All of the following pertain to compositions in standard order (A066099):
- Length is A000120.
- Necklaces are A065609.
- Sum is A070939.
- Runs are counted by A124767.
- Rotational symmetries are counted by A138904.
- Strict compositions are A233564.
- Constant compositions are A272919.
- Lyndon compositions are A275692.
- Co-Lyndon compositions are A326774.
- Aperiodic compositions are A328594.
- Reversed co-necklaces are A328595.
- Rotational period is A333632.
- Co-necklaces are A333764.
- Co-Lyndon factorizations are counted by A333765.
- Lyndon factorizations are counted by A333940.
- Reversed necklaces are A333943.
- Co-necklaces are A334028.
Cf. A034691, A060223, A102659, A211097, A292884, A296372, A328596, A329358, A329359, A329362, A329400, A329401, A333939.

stc[n_]:=Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
colynQ[q_]:=Length[q]==0||Array[Union[{RotateRight[q,#1],q}]=={RotateRight[q,#1],q}&,Length[q]-1,1,And];
colynfac[q_]:=If[Length[q]==0,{},Function[i,Prepend[colynfac[Drop[q,i]],Take[q,i]]][Last[Select[Range[Length[q]],colynQ[Take[q,#1]]&]]]]
Table[Length[colynfac[stc[n]]],{n,0,100}]

A335467 Numbers k such that the k-th composition in standard order (A066099) avoids the pattern (1,2,1).

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 26, 28, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 47, 48, 50, 52, 56, 58, 60, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 78, 79, 80, 81

Offset: 1

Gus Wiseman, Jun 16 2020

nonn

A composition of n is a finite sequence of positive integers summing to n. 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.

We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).

			See A335466 for an example of the complement.

Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.
Gus Wiseman, Statistics, classes, and transformations of standard compositions

The complement A335466 is the matching version.
The (2,1,2)-avoiding version is A335469.
These compositions are counted by A335471.
Constant patterns are counted by A000005 and ranked by A272919.
Permutations are counted by A000142 and ranked by A333218.
Patterns are counted by A000670 and ranked by A333217.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Combinatory separations are counted by A269134 and ranked by A334030.
Patterns matched by standard compositions are counted by A335454.
Minimal patterns avoided by a standard composition are counted by A335465.
Cf. A001710, A034691, A056986, A108917, A114994, A238279, A333224, A333257, A335449, A335456, A335458.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Select[Range[0,100],!MatchQ[stc[#],{_,x_,_,y_,_,x_,_}/;x

A335472 Number of compositions of n matching the pattern (2,1,2).

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 3, 9, 25, 66, 165, 394, 914, 2068, 4607, 10093, 21818, 46592, 98498, 206452, 429670, 888818, 1829005, 3746802, 7645511, 15549306, 31534322, 63800562, 128823111, 259678348, 522715526, 1050957282, 2110953835, 4236623798, 8497083721, 17032615177

Offset: 0

Gus Wiseman, Jun 17 2020

nonn

Also the number of (1,2,2) or (2,2,1)-matching compositions.
We define a pattern to be a finite sequence covering an initial interval of positive integers. Patterns are counted by A000670 and ranked by A333217. A sequence S is said to match a pattern P if there is a not necessarily contiguous subsequence of S whose parts have the same relative order as P. For example, (3,1,1,3) matches (1,1,2), (2,1,1), and (2,1,2), but avoids (1,2,1), (1,2,2), and (2,2,1).
A composition of n is a finite sequence of positive integers summing to n.

			The a(5) = 1 through a(7) = 9 compositions:
  (212)  (1212)  (313)
         (2112)  (2122)
         (2121)  (2212)
                 (11212)
                 (12112)
                 (12121)
                 (21112)
                 (21121)
                 (21211)

Andrew Howroyd, Table of n, a(n) for n = 0..200
Wikipedia, Permutation pattern
Gus Wiseman, Sequences counting and ranking compositions by the patterns they match or avoid.

The version for prime indices is A335453.
These compositions are ranked by A335468.
The (1,2,1)-matching version is A335470.
The complement A335473 is the avoiding version.
The version for patterns is A335509.
Constant patterns are counted by A000005 and ranked by A272919.
Patterns are counted by A000670 and ranked by A333217.
Permutations are counted by A000142 and ranked by A333218.
Compositions are counted by A011782.
Non-unimodal compositions are counted by A115981 and ranked by A335373.
Combinatory separations are counted by A269134.
Patterns matched by compositions are counted by A335456.
Minimal patterns avoided by a standard composition are counted by A335465.
Compositions matching (1,2,3) are counted by A335514.
Cf. A261982, A034691, A056986, A106356, A238279, A333755.

Table[Length[Select[Join@@Permutations/@IntegerPartitions[n],MatchQ[#,{_,x_,_,y_,_,x_,_}/;x>y]&]],{n,0,10}]

a(n > 0) = 2^(n - 1) - A335473(n).

A381996 Number of non-isomorphic multisets of size n that can be partitioned into a set of sets.

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 6, 9, 13, 18, 25, 34, 47

Offset: 0

Gus Wiseman, Mar 31 2025

First differs from A382523 at a(12) = 47, A382523(12) = 45.

We call a multiset non-isomorphic iff it covers an initial interval of positive integers with weakly decreasing multiplicities. The size of a multiset is the number of elements, counting multiplicity.

			Differs from A382523 in counting the following under a(12):
  {1,1,1,1,1,1,2,2,3,3,4,5} with partition {{1},{1,2},{1,3},{1,4},{1,5},{1,2,3}}
  {1,1,1,1,2,2,2,2,3,3,3,3} with partition {{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Factorizations of this type are counted by A050326, distinct sums A381633.
Normal multiset partitions of this type are counted by A116539, distinct sums A381718.
The complement is counted by A292444.
Twice-partitions of this type are counted by A358914, distinct sums A279785.
For integer partitions we have A382077, ranks A382200, complement A382078, ranks A293243.
Weak version is A382214, complement A292432, distinct sums A382216, complement A382202.
For distinct sums we have A382523, complement A382430.
Normal multiset partitions: A034691, A035310, A116540, A255906.
Set systems: A050342, A296120, A318361.
Set multipartitions: A089259, A270995, A296119, A318360.
Cf. A000110, A000670, A007716, A050320, A255903, A317532, A326519, A381992, A382428, A382458, A382459.

strnorm[n_]:=Flatten[MapIndexed[Table[#2,{#1}]&,#]]& /@ IntegerPartitions[n];
sps[{}]:={{}};sps[set:{i_,_}] := Join@@Function[s,Prepend[#,s]& /@ sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort /@ (#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
Table[Length[Select[strnorm[n], Select[mps[#], UnsameQ@@#&&And@@UnsameQ@@@#&]!={}&]], {n,0,5}]

A382204 Number of normal multiset partitions of weight n into constant blocks with a common sum.

Original entry on oeis.org

1, 1, 2, 3, 4, 4, 7, 5, 8, 8, 10, 8, 15, 9, 14, 15, 17, 13, 22, 14, 25, 21, 23, 19, 34, 24, 29, 28, 37, 27, 45, 29, 44, 38, 43, 43, 59, 40, 51, 48, 69, 48, 71, 52, 73, 69, 72, 61, 93, 72, 91, 77, 99, 78, 105, 95, 119, 95, 113, 96, 146, 107, 126, 123, 151, 130

Offset: 0

Gus Wiseman, Mar 26 2025

nonn

We call a multiset or multiset partition normal iff it covers an initial interval of positive integers. The weight of a multiset partition is the sum of sizes of its blocks.

			The a(1) = 1 through a(6) = 7 multiset partitions:
  {1} {11}   {111}     {1111}       {11111}         {111111}
      {1}{1} {2}{11}   {11}{11}     {2}{11}{11}     {111}{111}
             {1}{1}{1} {2}{2}{11}   {2}{2}{2}{11}   {22}{1111}
                       {1}{1}{1}{1} {1}{1}{1}{1}{1} {11}{11}{11}
                                                    {2}{2}{11}{11}
                                                    {2}{2}{2}{2}{11}
                                                    {1}{1}{1}{1}{1}{1}
The a(1) = 1 through a(7) = 5 factorizations:
  2  4    8      16       32         64           128
     2*2  3*4    4*4      3*4*4      8*8          3*4*4*4
          2*2*2  3*3*4    3*3*3*4    9*16         3*3*3*4*4
                 2*2*2*2  2*2*2*2*2  4*4*4        3*3*3*3*3*4
                                     3*3*4*4      2*2*2*2*2*2*2
                                     3*3*3*3*4
                                     2*2*2*2*2*2

Christian Sievers, Table of n, a(n) for n = 0..25000

Without a common sum we have A055887.
Twice-partitions of this type are counted by A279789.
Without constant blocks we have A326518.
For distinct block-sums and strict blocks we have A381718.
Factorizations of this type are counted by A381995.
For distinct instead of equal block-sums we have A382203.
For strict instead of constant blocks we have A382429.
A000670 counts patterns, ranked by A055932 and A333217, necklace A019536.
A001055 count multiset partitions of prime indices, strict A045778.
A089259 counts set multipartitions of integer partitions.
A255906 counts normal multiset partitions, row sums of A317532.
A321469 counts multiset partitions with distinct block-sums, ranks A326535.
Normal multiset partitions: A035310, A304969, A356945.
Set multipartitions: A116540, A270995, A296119, A318360.
Set multipartitions with distinct sums: A279785, A381806, A381870.
Constant blocks with distinct sums: A381635, A381636, A381716.
Cf. A007716, A034691, A034729, A116539, A255903, A317583, A326520, A382216.

allnorm[n_Integer]:=Function[s,Array[Count[s,y_/;y<=#]+1&,n]]/@Subsets[Range[n-1]+1];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[mset_]:=Union[Sort[Sort/@(#/.x_Integer:>mset[[x]])]&/@sps[Range[Length[mset]]]];
Table[Length[Join@@(Select[mps[#],SameQ@@Total/@#&&And@@SameQ@@@#&]&/@allnorm[n])],{n,0,5}]

h(s,x)=my(t=0,p=1,k=1);while(s%k==0,p*=1/(1-x^(s/k))-1;t+=p;k+=1);t
lista(n)=Vec(1+sum(s=1,n,h(s,x+O(x*x^n)))) \\ Christian Sievers, Apr 05 2025

G.f.: 1 + Sum_{s>=1} Sum_{k=1..A055874(s)} Product_{v=1..k} (1/(1-x^(s/v)) - 1). - Christian Sievers, Apr 05 2025

Terms a(16) and beyond from Christian Sievers, Apr 04 2025

cp's OEIS Frontend

A140585 Total number of all hierarchical orderings for all set partitions of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A256142 G.f.: Product_{j>=1} (1+x^j)^(3^j).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A335482 Numbers k such that the k-th composition in standard order (A066099) matches the pattern (2,3,1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A335485 Numbers k such that the k-th composition in standard order (A066099) is not weakly decreasing.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A095684 Triangle read by rows. There are 2^(m-1) rows of length m, for m = 1, 2, 3, ... The rows are in lexicographic order. The rows have the property that the first entry is 1, the second distinct entry (reading from left to right) is 2, the third distinct entry is 3, etc.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A334029 Length of the co-Lyndon factorization of the k-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A335467 Numbers k such that the k-th composition in standard order (A066099) avoids the pattern (1,2,1).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A335472 Number of compositions of n matching the pattern (2,1,2).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs