16
\$\begingroup\$

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 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 , so the shortest code in bytes wins
Improve this question
\$\endgroup\$
5
  • \$\begingroup\$ Sandbox \$\endgroup\$ Commented Jan 5, 2022 at 17:32
  • \$\begingroup\$ With length 0, 2, or 2 ---> 3 \$\endgroup\$ Commented Jan 5, 2022 at 18:38
  • \$\begingroup\$ @kirjosieppo thanks for noticing that! By the way, in future, you can suggest an edit to fix that sort of thing. \$\endgroup\$ Commented Jan 5, 2022 at 19:24
  • \$\begingroup\$ You are actually listing the 31 first terms of the sequence. \$\endgroup\$ Commented Jan 5, 2022 at 20:34
  • \$\begingroup\$ @Arnauld hmm, zero-indexing... \$\endgroup\$ Commented Jan 5, 2022 at 20:41

13 Answers 13

Reset to default
9
+500
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
6
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ I prefer my approach for Charcoal because a) it doesn't have to special-case 0 and b) Charcoal sucks at differences and it's golfer to calculate Bell number differences as it goes... this takes "only" 10 bytes, whereas it costs 17 bytes just to extract the final result, although I was at least able to golf the extra sum of increments inside the loop to "only" cost a further 3 bytes. \$\endgroup\$ Commented Jan 6, 2022 at 9:50
5
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ Instead of summing from 1 to x-1 you could sum from 0 to x-2 then you could write f(i) instead of f(x-1-i). (I don't speak JavaScript, so I don't know whether it makes the code any shorter.) \$\endgroup\$ Commented Jan 6, 2022 at 7:27
  • \$\begingroup\$ @loopywalt I had tried many variance, but not so lucky. As the most byte costing part is calculate the combination (JS don't have built-in for combination number. It have to be multiplied manually during the loop), finger out stop condition, and make these codes be harmony with the special case for f(0). \$\endgroup\$ Commented Jan 6, 2022 at 7:33
  • \$\begingroup\$ 43 bytes \$\endgroup\$ Commented Jan 6, 2022 at 7:47
  • \$\begingroup\$ @att I'm not sure how f(i-1) part comes in your formula. But seems f=(n,i=n)=>i?--i&&f(n,i)*i/(n-i)+f(n+~i):1 also yield correct result (with 42 bytes) \$\endgroup\$ Commented Jan 6, 2022 at 8:15
5
\$\begingroup\$

MATL, 23 bytes

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

Input is 0-indexed. Try it at @=f@d0MATL 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
Improve this answer
\$\endgroup\$
4
\$\begingroup\$

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!

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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)!}$$

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
3
\$\begingroup\$

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))
Improve this answer
\$\endgroup\$
3
  • 1
    \$\begingroup\$ 75 bytes by flipping the index \$\endgroup\$ Commented Jan 5, 2022 at 21:53
  • 1
    \$\begingroup\$ 74 bytes new base case \$\endgroup\$ Commented Jan 5, 2022 at 21:55
  • 1
    \$\begingroup\$ The import can be shorter for 73 \$\endgroup\$ Commented Jan 6, 2022 at 7:47
3
\$\begingroup\$

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.
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Pari/GP, 38 bytes

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

Try it online!

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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.

Improve this answer
\$\endgroup\$
1
\$\begingroup\$

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
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

Vyxal, 15 bytes

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

Try it Online!

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

Improve this answer
\$\endgroup\$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.