Number of complete rhyme schemes

Question

A rhyme scheme is the pattern of rhymes at the end of the lines in a poem. They are typically represented using letters, like ABAB. We consider two rhyme schemes identical if they are isomorphs, and therefore only report the lexicographically earliest. Equivalently, rhyme schemes are simply strings in standard order. The rhyme schemes of length 4 are:

AAAA, AAAB, AABA, AABB, AABC, ABAA, ABAB, ABAC, ABBA, ABBB, ABBC, ABCA, ABCB, ABCC, ABCD

A complete rhyme scheme is one where every line rhymes with at least one other line; that is, every letter in the string appears more than once. For length 4, these are:

AAAA, AABB, ABAB, ABBA

Now consider the sequence of the number of complete rhyme schemes for any length. With length 0, 2, or 3, there is exactly one way to do this (​, AA, and AAA respectively), and length 1 has no ways. As we see, length 4 gives 4 ways. The first 30 terms of this sequence are:

1, 0, 1, 1, 4, 11, 41, 162, 715, 3425, 17722, 98253, 580317, 3633280, 24011157, 166888165, 1216070380, 9264071767, 73600798037, 608476008122, 5224266196935, 46499892038437, 428369924118314, 4078345814329009, 40073660040755337, 405885209254049952, 4232705122975949401, 45398541400642806873, 500318506535417182516, 5660220898064517469939

This is A000296 in the OEIS. It is also the number of ways to partition a set into subsets of a size of at least 2.

Your task is to output this sequence.

The sequence should not be limited by the 26 letters in the alphabet; the letters can be abstracted such that the sequence continues infinitely. The complete rhyme schemes which use the digits 1-9 is OEIS A273978.

Rules

• As with standard sequence challenges, you may choose to either:
  • Take an input n and output the nth term of the sequence
  • Take an input nand output the first n terms
  • Output the sequence indefinitely, e.g. using a generator
• You may use 0- or 1-indexing
• You may use any standard I/O method
• Standard loopholes are forbidden
• This is code-golf, so the shortest code in bytes wins

Answer 1

Haskell, 48 bytes

(%1)
0%_=1
n%i|i<n=(i-1)%1+(n-i)/i*n%(i+1)|1>0=0

Try it online!

Uses this recursion I found:

$$ f(n)=g(n,1), $$ where $$ \begin{eqnarray} g(0,i) &=& 0\nonumber \\ g(n,i) &=& g(i-1,1) +\frac{n-i}{i} g(n,i+1) \text{, if } i< n \nonumber \\ g(n,i) &=& 0 \text{, otherwise} \end{eqnarray} $$

45 bytes

(%0)
0%_=1
n%i|i>n-2=0|j<-i+1=i%0+(n-j)/j*n%j

Try it online!

47 bytes

(%1)
0%_=1
n%i=sum[(i-1)%1+(n-i)/i*n%(i+1)|i<n]

Try it online!

45 bytes

f n=foldr(\j x->f(j-1)+n/j*x-x)(0**n)[1..n-1]

Try it online!

Some float inaccuracies show up.

Answer 2

Jelly, 13 bytes

1IS;ƊÄ$¡IIS+¬

Try it online!

1IS;ƊÄ$¡IIS+¬
1     $¡        Starting from [1], iterate an operation n times:

 IS               Sum the increments (i.e. last minus first),
   ;Ɗ             prepend this to the array,
     Ä            and take the cumulative sum.
                  e.g. [a,b,c,d] → [d-a, d, d+b, d+b+c, d+b+c+d]

        IIS     Increments, increments, sum.
           +¬   This erroneously gives a(0)=0, so add 1 if n=0.

This is a port of the Maple code contributed to the OEIS page by Peter Luschny. As far as I understand, it's similar to Neil's answer, but modifies Aitken's array to get the result directly.

Answer 3

JavaScript (Node.js), 42 bytes

Avoid another loop variable saves 7 8 bytes as suggested by att.

f=(n,i=n)=>i?--i&&f(n,i)*i/(n-i)+f(n+~i):1

Try it online!

$$ f(x) = \sum_{i=1}^{x-1} \binom{x-1}{i}\cdot f(x-1-i) $$

with special

$$ f(0) = 1 $$

For complete rhyme patterns with length n:

1. The first rhyme is A by definition
2. We choose i rhymes after it and fill it by A; 1 < i < n-1
3. For unfilled cells, it become a recursive question
4. So we count f(n-1-i)*combination(n-1,i) rhyme patterns.

Answer 4

MATL, 23 bytes

:Y@!"@Y>@=f@d0<fX=]N~vs

Input is 0-indexed. Try it at MATL Online!

Explanation

This uses the following characterization from OEIS:

a(n) is the number of permutations of [1, 2, ..., n] for which the positions of the left-to-right maxima coincide with the positions of entries that are followed by a smaller number.

:       % Implicit input: n. Range [1 2 ... n]
Y@      % All permutations. Gives a matrix where each permutation is a row
!       % Transpose. Now each permutation is a column
"       % For each column
  @Y>   %   Cumulative maximum of the column
  @=    %   Compare each entry with that of the column
  f     %   Indices of true entries, i.e. of left-to-right maxima (*)
  @d    %   consecutive differences of the column
  0<    %   True for negative values
  f     %   Indices of true entries, i.e. of descents (**)
  X=    %   Are (*) and (**) equal? Gives true or false
]       % End
N~      % Number of terms in the stack, negated. Gives 1 for n=0
v       % Concatenate all values into a column vector
s       % Sum. Implicit display

Answer 5

Wolfram Language (Mathematica), 27 bytes

Nest[#'&,E^(E^#-1-#)&,#]@0&

Try it online!

Uses the exponential generating function given on OEIS:

E.g.f.: exp(exp(x) - 1 - x).

---

alternative 27 bytes:

D[E^(E^x-1-x),{x,#}]/.x->0&

Try it online!

Answer 6

JavaScript (ES7), 90 bytes

Outputs the \$n\$-th term, 0-indexed.

f=(n,k=n)=>~k&&(h=j=>~j&&(F=n=>n?F(n-1)/n:1)(j)*F(k-j)*(-1)**j--*(-j)**n+h(j))(k)-f(n,k-1)

Try it online!

There's a floating-point rounding error for \$a(3)\$.

How?

This is based on the following formula from A000296:

$$a(n)=\sum_{k=0}^n{(-1)^{n-k}\times\sum_{j=0}^k\left((-1)^j\times\binom{k}{j}\times (1-j)^n\right)/k!}$$

which can be turned into:

$$a(n)=\sum_{k=0}^n{(-1)^{n-k}\times\sum_{j=0}^k(-1)^j\times (1-j)^n/j!/(k-j)!}$$

Answer 7

Charcoal, 28 bytes

≔¹η⊞υ¹ＦＮ«≦⁻⌊υη⊞υ⌈υＵＭυΣ✂υλ»Ｉη

Try it online! Link is to verbose version of code. 0-indexed, obviously, given that this is the number of complete rhyme schemes for a given length, so the input should be the length. Explanation:

≔¹η

Start with 1 complete rhyme scheme for a length of 0.

⊞υ¹

Start computing Bell numbers (A000110).

ＦＮ«

Loop length times.

≦⁻⌊υη

Subtract the current result from the current Bell number.

⊞υ⌈υＵＭυΣ✂υλ

Compute the next row of Aitken's array to obtain the next Bell number. (Actually computes the row reversed because it's golfier.)

»Ｉη

Output the final number of complete rhyme schemes.

Answer 8

Python 3, 78 74 bytes

Port of a Maxima function found in the prog section on OEIS.

-4 bytes thanks to xnor!

from math import*
f=lambda n:sum(comb(n-1,i)*f(i)for i in range(n-1))+0**n

Try it online!

Same length with more recursion:

f=lambda n,i=0:(n-i>1and comb(n-1,i)*f(i)+f(n,i+1))+0**n
f=lambda n,i=0:~i+n and(n<1or comb(n-1,i)*f(i)+f(n,i+1))

Answer 9

x86 32-bit machine code, 29 28 bytes

31 c0 99 e2 09 c3 52 e8 f6 ff ff ff 5a 59 42 51 f3 0f b8 ca 3b 0c 24 7c ed 59 40 c3

Try it online!

Following the fastcall calling convention, this takes the 0-indexed n in ECX and returns the nth value in EAX.

-1 with some rearrangement and changes.

Assembly:

.intel_syntax noprefix
.global f
f:
    xor eax, eax    # Set EAX to 0.
recursion:      # Starting here will add the value to EAX instead of replacing it.
    cdq             # Set EDX to 0 (as long as EAX hasn't overflowed).
    loop enterloop  # Calculate n-1 and jump if that's not 0 (n≠1).
    ret             # Return with 0 for n=1.

repeat: 
    push edx        # Push EDX onto the stack.
    call recursion  # Recursive call, using the number of different positions.
    pop edx         # Restore EDX from the stack.
    pop ecx         # Restore ECX from the stack.
enterloop:      # EDX will be a bitmask of positions different from the last.
    inc edx         # Add 1 to EDX.
    push ecx        # Push ECX (n-1) onto the stack.
    popcnt ecx, edx # Count the different positions, into ECX.
    cmp ecx, [esp]  # Compare that with the value of n-1 on top of the stack.
    jl repeat       # Continue the loop if fewer than n-1 different positions.
    pop ecx         # (Otherwise: all n-1 positions, or n=0) Take n-1 off the stack.
    inc eax         # Count 1 for the all-the-same rhyme scheme.
    ret             # Return.

Answer 10

Pari/GP, 38 bytes

n->n!*Vec(exp(exp(x+O(x^n++))-1-x))[n]

Try it online!

Answer 11

Python 3.8, 128 bytes

lambda n:round(sum((-1)**(n-k)*sum((-1)**j*comb(k,j)*(1-j)**n/perm(k)for j in range(k+1))for k in range(n+1)))
from math import*

Try it online!

Uses the same formula (unchanged) from A000296 that Arnauld uses in his JavaScript answer.

Answer 12

05AB1E, 14 bytes

1=λD¥OšηOD¥¥O,

Port of @Lynn's Jelly answer, but outputs the infinite sequence newline-delimited instead.

Try it online.

Explanation:

1              # Push 1
 =             # Print it with trailing newline (without popping)
               # (workaround for edge case a(0)=1)
  λ            # Start the recursive environment,
               # to output the infinite sequence
               # Starting with the a(0)=1 we've pushed
               #  (implicitly push the value of a(n-1))
   D           #  Duplicate this a(n-1)
    ¥          #  Pop and push a list of its forward differences
     O         #  Sum those
      š        #  Prepend it in front of the list
       η       #  Pop and push a list of its prefixes
        O      #  Sum those as well
         D     #  Duplicate it (which will be the result of this a(n))
          ¥    #  Pop and push a list of its forward differences
           ¥   #  Do it again
            O  #  Sum those
             , #  Pop and print it with trailing newline

Answer 13

Vyxal, 15 bytes

1w?(:¯∑p¦)¯¯∑1⟑

Try it Online!

A messy port of Lynn's answer, go upvote that!