A292444 -id:A292444 - cp's OEIS frontend

A298947 Number of integer partitions y of n such that exactly one permutation of y is a Lyndon word.

1, 1, 2, 3, 6, 7, 11, 12, 15, 19, 22, 22, 29, 32, 32, 38, 42, 44, 49, 51, 54, 63, 63, 64, 71, 79, 76, 84, 87, 90, 96, 101, 101, 113, 108, 115, 122, 131, 125, 134, 138, 144, 147, 155, 150, 169, 163, 168, 173, 185, 180, 194, 191, 200, 198, 211, 209, 227, 218, 224, 231, 246

Offset: 1

Gus Wiseman, Jan 30 2018

nonn

			The a(6) = 7 partitions are (6), (51), (42), (411), (3111), (2211), (21111). This list does not include (321) because there are two possible permutations that are Lyndon words, namely (123) and (132). The list does not include (33), (222), or (111111) because no permutation of these is a Lyndon word.

Cf. A000041, A000740, A001037, A032741, A059966, A144300, A167934, A293511, A292444, A298941.

with(combinat): with(numtheory):
g:= l-> (n-> `if`(n=0, 1, add(mobius(j)*multinomial(n/j,
        (l/j)[]), j=divisors(igcd(l[])))/n))(add(i, i=l)):
b:= (n, i, l)-> `if`(n=0 or i=1, `if`(g([l[], n])=1, 1, 0),
                 add(b(n-i*j, i-1, [l[], j]), j=0..n/i)):
a:= n-> b(n$2, []):
seq(a(n), n=1..30);  # Alois P. Heinz, Feb 09 2018

LyndonQ[q_]:=Array[OrderedQ[{q,RotateRight[q,#]}]&,Length[q]-1,1,And]&&Array[RotateRight[q,#]&,Length[q],1,UnsameQ];
Table[Length[Select[IntegerPartitions[n],Length[Select[Permutations[#],LyndonQ]]===1&]],{n,20}]
(* Second program: *)
multinomial[n_, k_List] := n!/Times @@ (k!);
g[l_List] := With[{n = Total[l]}, If[n == 0, 1, Sum[MoebiusMu[j]*multinomial[n/j, l/j], {j, Divisors[GCD @@ l]}]/n]];
b[n_, i_, l_List] := If[n == 0 || i == 1, If[g[Append[l, n]] == 1, 1, 0], Sum[b[n - i*j, i - 1, Append[l, j]], {j, 0, n/i}]];
a[n_] := b[n, n, {}];
Array[a, 30] (* Jean-François Alcover, May 20 2021, after Alois P. Heinz *)

a(23)-a(62) from Alois P. Heinz, Feb 09 2018

A321188 Number of set systems with no singletons whose multiset union is row n of A305936 (a multiset whose multiplicities are the prime indices of n).

Original entry on oeis.org

1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 4, 0, 1, 0, 0, 0, 0, 0, 3, 0, 0, 1, 0, 0, 0, 0, 11, 0, 0, 0, 4, 0, 0, 0, 1

Offset: 1

Gus Wiseman, Oct 29 2018

A set system is a finite set of finite nonempty sets.

A prime index of n is a number m such that prime(m) divides n. The multiset of prime indices of n is row n of A112798.

			The a(36) = 4 set systems with no singletons whose multiset union is {1,1,2,2,3,4}:
  {{1,2},{1,2,3,4}}
  {{1,2,3},{1,2,4}}
  {{1,2},{1,3},{2,4}}
  {{1,2},{1,4},{2,3}}

Cf. A000070, A000296, A000569, A050326, A056239, A112798, A283877, A292444, A305936, A306005, A318285, A318361, A320922, A320923, A320924.

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]]]];
hyp[m_]:=Select[mps[m],And[And@@UnsameQ@@@#,UnsameQ@@#,Min@@Length/@#>1]&];
nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]],{#1}]&,If[n==1,{},Flatten[Cases[FactorInteger[n]//Reverse,{p_,k_}:>Table[PrimePi[p],{k}]]]]];
Table[Length[hyp[nrmptn[n]]],{n,30}]

cp's OEIS Frontend

A298947 Number of integer partitions y of n such that exactly one permutation of y is a Lyndon word.

Views

Author

Keywords

Examples

Crossrefs

Programs

Maple

Mathematica

Extensions