9
\$\begingroup\$

\$\left\{ n \atop k \right\}\$ or \$S(n, k)\$ is a way of referring to the Stirling numbers of the second kind, the number of ways to partition a set of \$n\$ items into \$k\$ non-empty subsets. For example, to partition \$\{1,2,3,4\}\$ into \$2\$ non-empty subsets, we have

$$\begin{matrix} \{\{1\},\{2,3,4\}\} & \{\{2\},\{1,3,4\}\} & \{\{3\},\{1,2,4\}\} & \{\{4\},\{1,2,3\}\} \\ \{\{1,2\},\{3,4\}\} & \{\{1,3\},\{2,4\}\} & \{\{1,4\},\{2,3\}\} \end{matrix}$$

So \$\left\{ 4 \atop 2 \right\} = S(4,2) = 7\$

Here, we'll only be considering the sequence \$\left\{ n \atop 3 \right\} = S(n, 3)\$, or the ways to partition \$n\$ items into \$3\$ non-empty subsets. This is A000392. There is also the related sequence which ignores the three leading zeros (so is \$1, 6, 25, 90, 301, ...\$)\${}^*\$.

This is a standard challenge, where you can choose which of the two related sequences to handle (leading zeros or not). Regardless of which sequence you choose, you should do one of the following:

  • Take an integer \$n\$ and output the \$n\$th element of the sequence. This can be \$0\$ or \$1\$ indexed, your choice, and \$n\$'s minimum value will reflect this.
  • Take a positive integer \$n\$ and output the first \$n\$ elements of the sequence
  • Take no input and infinitely output the sequence

This is so the shortest code in bytes wins.

\${}^*\$: I'm allowing either sequence, as handling the leading zeros can "fail" for some algorithms that have to compute empty sums


Test cases

If you ignore the leading zeros, the first 20 elements are

1, 6, 25, 90, 301, 966, 3025, 9330, 28501, 86526, 261625, 788970, 2375101, 7141686, 21457825, 64439010, 193448101, 580606446, 1742343625, 5228079450

Otherwise, the first 20 elements are

0, 0, 0, 1, 6, 25, 90, 301, 966, 3025, 9330, 28501, 86526, 261625, 788970, 2375101, 7141686, 21457825, 64439010, 193448101
\$\endgroup\$

20 Answers 20

11
\$\begingroup\$

Jelly, 6 bytes

3Ḋ*)SI

Try it online!

-1 byte thanks to Jonathan Allan

1-indexed sequence without leading zeros. Uses the formula \$\sum_{k=1}^{n} 3^k - 2^k\$.

Explanation

3Ḋ*)SI Main monadic link
   )   For each k in the range [1..n]:
3Ḋ       Remove the first element from the range [1..3]
  *      Raise each to the power of k
    S  Sum (producing [sum(2^k), sum(3^k)])
     I Increments
\$\endgroup\$
2
  • 2
    \$\begingroup\$ With some rearrangement you can do this in 6 bytes like so: 3Ḋ*)SI \$\endgroup\$ – Jonathan Allan Jul 21 at 20:45
  • 2
    \$\begingroup\$ @JonathanAllan Smart idea, thanks! \$\endgroup\$ – xigoi Jul 21 at 20:46
8
\$\begingroup\$

R, 23 bytes

3^(n=scan()+2)/2-2^n+.5

Try it online!

Outputs without the leading zeros, 0-indexed.

Uses formula from OEIS page: $$ a(n) = 9 \cdot 3^n/2 - 4 \cdot 2^n + 1/2 $$

\$\endgroup\$
1
8
\$\begingroup\$

Jelly, 7 bytes

cþæ*2FS

Try it online!

Now that xigoi has outgolfed me, I thought I'd share my answer.

This outputs the \$n\$ term of the sequence without leading zeroes.

How it works

We generate the matrix

$$\left[\begin{matrix} \binom 1 1 & \binom 2 1 & \cdots & \binom n 1 \\ \binom 1 2 & \binom 2 2 & \cdots & \binom n 2 \\ \vdots & & \ddots & \vdots \\ \binom 1 n & \binom 2 n & \cdots & \binom n n \end{matrix}\right]^2 = \left[\begin{matrix} 1 & 2 & \cdots & n \\ 0 & 1 & \cdots & \frac {n(n-1)} 2 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{matrix}\right]^2 = \left[\begin{matrix} 1 & 4 & \cdots & \sum^n_{i=1} i \binom n i \\ 0 & 1 & \cdots & \sum^n_{i=1} \binom i 2\binom n i \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{matrix}\right]$$

We then calculate \$A^2\$ and get the sum of each element, by flattening and taking the total sum. As to why this works, I have no idea - I just discovered it after playing around with þæ* patterns in Jelly.

cþæ*2FS - Main link. Takes n on the left
 þ      - Generate an n x n matrix where each cell (i,j) is:
c       -   iCj (binomial choose)
  æ*2   - Matrix square
     FS - Flatten and sum
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Shouldn't the \$\binom 2 i\$ be \$\binom i 2\$? \$\endgroup\$ – att Jul 22 at 6:30
  • \$\begingroup\$ @att Yes, it should, typo fixed :) \$\endgroup\$ – caird coinheringaahing Jul 22 at 10:47
  • 1
    \$\begingroup\$ By a double counting argument, \$\sum_{i=k}^n \binom{i}{k} \binom{n}{i} = 2^{n-k} \binom{n}{k}\$. Using the binomial theorem, we can thus conclude that the sum of column \$n\$ is \$3^n - 2^n\$. \$\endgroup\$ – Nitrodon Jul 22 at 15:09
7
\$\begingroup\$

Alchemist, 76 bytes

_+0j->2c
b+0j->3d
0j+0_+0b->j
c+j+x->_+j
d+j->x+b+j
j+0c+0d->Out_x+Out_" "!b

Try it online!

Outputs nonzero values infinitely using the formula \$S(n, 3) = \sum_{k=1}^{n-2} (3^k - 2^k)\$.

On TIO, this computes up to the 13th element (2375101) before timing out.

\$\endgroup\$
6
\$\begingroup\$

Python 2, 24 bytes

lambda n:3**n/6-~-2**n/2

Try it online!

Formula from OEIS for \$n>0\$:

$$ f(n) = \frac{1}{2}(3^{n-1}-2^n+1)$$

\$\endgroup\$
6
\$\begingroup\$

APL (Dyalog Unicode), 14 bytes

Anonymous tacit prefix function using xnor's formula. 1-indexed.

2÷⍨1-2∘*-3*-∘1

Try it online!

\$\endgroup\$
6
\$\begingroup\$

Jelly, 12 bytes

3ẹ@þṗ¥ẠƇṢ€QL

Try it online!

A monadic link that takes \$n\$ as its argument and returns \$a(n)\$. This is longer and less efficient than the answers based on the OEIS formulae, but should work for any value of \$k\$ by varying the first number in the link from 3. Also, removing the L at the end yields the actual sets.

Explanation

3    ¥       | Using 3 as the left argument and n as the right argument:
    ṗ        | - Cartesian power of 3 and n (call this x)
 ẹ@þ         | - Find indices of each of 1 to 3 in each of x
      ẠƇ     | Keep only those lists where all are non-empty
        Ṣ€   | Sort each list
          Q  | Unique
           L | Length
\$\endgroup\$
6
\$\begingroup\$

Jelly, 9 bytes

Surely there is an eight or less out there...

1×Ɱ3$¡FQS

A full program that accepts a non-negative integer from STDIN and prints the result using the 0-indexed, no leading zeros option.

Try it online!

How?

1×Ɱ3$¡FQS - Main Link: no arguments
1         - start with x=1
     ¡    - repeat this (read from STDIN) times:
    $     -   last two links as a monad, x=f(x):
   3      -     three
 ×Ɱ       -     map (across y in [1..3]) with multiplication
      FQS - flatten, deduplicate, sum -> sum of the set of integers encountered
\$\endgroup\$
2
  • \$\begingroup\$ What formula is this based on? \$\endgroup\$ – xigoi Jul 22 at 17:37
  • 1
    \$\begingroup\$ @xigoi John W. Layman's conjecture on A000392. Also note the comment about it further down by Fred Daniel Kline. \$\endgroup\$ – Jonathan Allan Jul 22 at 19:17
6
\$\begingroup\$

Jelly, 9 bytes

Port of xnor's answer, made/fixed and golfed with hyper-neutrino's and caird coinheringaahing's help.

’3*_2*$‘H

Try it online!

This doesn't handle leading zeroes.

’3*_2*$‘H
’         n-1
 3*       3^(n-1)
   _      From that, subtract
    2*$   2^n
       ‘  Increment that
        H Halve it
\$\endgroup\$
3
  • 2
    \$\begingroup\$ Does this correctly output the leading 3x zeros? I don't know Jelly to 'try it online' with the footer, but the explanation suggests that (counting from zero) the sequence would start: 1/6, 0, 0, ... \$\endgroup\$ – Dominic van Essen Jul 21 at 22:24
  • \$\begingroup\$ @DominicvanEssen It doesn't, I'll mention that in the answer. \$\endgroup\$ – user Jul 21 at 22:25
  • 1
    \$\begingroup\$ Ah. My reading of the question was that one needed to output all 3x zeros, or none of them... \$\endgroup\$ – Dominic van Essen Jul 21 at 22:34
5
\$\begingroup\$

Scala, 132 bytes

n=>(for{i<-1 to n-1
j<-i+1 to n-1
p<-1.to(n).permutations}yield{Set(p.slice(0,i),p.slice(i,j),p.slice(j,n))map(_.toSet)}).toSet.size

Try it online!

Is it short? No. Is it efficient? No. Is it clever? No. Why did I make it? I...don't know. I'll try golfing it later, if possible.

\$\endgroup\$
4
\$\begingroup\$

C (gcc), 34 bytes

f(n){n=n<3?0:5*f(n-1)-6*f(n-2)+1;}

Try it online!

Inputs \$0\$-based \$n\$.
Returns \$S(n,3)\$.
Uses the formula: \$a(n) = 5\cdot a(n-1) - 6\cdot a(n-2) + 1\$, for \$n > 2\$.

\$\endgroup\$
4
\$\begingroup\$

Wolfram Language (Mathematica), 15 bytes

#~StirlingS2~3&

Try it online!

\$\endgroup\$
4
\$\begingroup\$

Rattle, 24 bytes

|s>-s=3e~s<=2e~sg1-~+/R1

Try it Online!

This is a port of xnor's Python answer into Rattle using this formula:

$$ f(n) = \frac{1}{2}(3^{n-1}-2^n+1)$$

Explanation

|                          takes the user's input
 s                         saves the user's input (n) to memory slot 0
  >                        move pointer right
   -                       decrement user's input
    s                      save (n-1) to memory slot 1
     =3                    set the value on top of the stack to 3
       e~                  perform 3^(n-1)
         s                 save in memory slot 1
          <                move pointer left
           =2              set the value on top of the stack to 2
             e~            perform 2^(n)
               s           save in memory slot 0
                g1         get value from slot 1
                  -~       subtract value in slot 0
                    +      increment
                     /     divide by 2
                      R1   reformat as int (which is printed implicitly)
\$\endgroup\$
2
  • \$\begingroup\$ Can you not remove the R1? \$\endgroup\$ – caird coinheringaahing Jul 22 at 0:42
  • \$\begingroup\$ @cairdcoinheringaahing unfortunately it's needed for n = 0, it can be removed otherwise (I'm currently trying to golf it more to not need that) \$\endgroup\$ – Daniel H. Jul 22 at 0:42
4
\$\begingroup\$

Factor + math.extras, 18 bytes

[ 3 + 3 stirling ]

Ignoring leading zeroes. Zero-indexed. stirling is bugged in the build TIO uses. It was fixed about three years ago, so here's a picture of running it in the listener with a more recent build.

enter image description here

\$\endgroup\$
1
  • 1
    \$\begingroup\$ now this is a mathematica level threat \$\endgroup\$ – Razetime Jul 22 at 6:25
3
\$\begingroup\$

Vyxal sr, 6 bytes

ƛ23fe¯

Try it Online!

A port of xigoi's Jelly answer

Explained

ƛ23fe¯
ƛ      # over the range [1, input] (call each item n) 

 23f   #   the list [2, 3]
    e  #   ^ ** n
     ¯ #   deltas of ^
       # the s flag auto-sums the result
```
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Vyxal really likes to abuse our “CL flags = different language” rules :D \$\endgroup\$ – xigoi Jul 22 at 10:04
3
\$\begingroup\$

APL (Dyalog Unicode), 14 bytes

-/3 2⊥¨∘⊂1,⍴∘1

Try it online!

A function implementing the sum formula using base conversion:

$$ a(n) = \sum_{k=0}^n \left( 3^k-2^k \right) = \sum_{k=0}^n 3^k - \sum_{k=0}^n 2^k = (\underbrace{1 \cdots 1}_{n+1})_3 - (\underbrace{1 \cdots 1}_{n+1})_2 $$

           ⍴∘1   ⍝ a vector of n 1's
         1,      ⍝ prepend an additional 1
        ⊂        ⍝ enclose in a length 1 list
  3 2⊥¨          ⍝ for each of 2 and 3 decode the vector from that base
-/               ⍝ reduce the result by subtraction

If we use a full program instead of a function, this and a port of caird's Jelly answer are 13 bytes:

-/3 2⊥¨⊂1,⎕⍴1 and +/∊+.×⍨∘.!⍨⍳⎕

\$\endgroup\$
2
\$\begingroup\$

Risky, 10 bytes

+0?+1+_0+0__!2?-+_{0

Try it online!

1-indexed sequence without leading zeros. Uses the formula \$\sum_{k=0}^{n} 3^k - 2^k\$.

Explanation

+ sum
0       range
?           n
+         +
1           1
+     copy-last
_
0           0
+         +
0           0
_   map
_
!           3
2         ^
?           k
-     -
+       2^
_           [k,n]
{         index
0           0
\$\endgroup\$
1
\$\begingroup\$

05AB1E, 8 bytes

Same approach as my APL answer.

$>и32SβÆ

Try it online!

$          # push 1 and input n
 >         # increment n
  и        # a list of n+1 1's
   32S     # push list [3, 2]
      β    # for each of those numbers, convert the list of 1's from that base
       Æ   # reduce by reduction

The first three bytes could be >Å1 instead: Try it online!

A few alternatives from 8 to 11 bytes:

o3I<mα>;       port of xnor's answer          Try it online!
32SILδmOÆ      the sum formula                Try it online!
o<·3ILmOα      sum(3^k, k=1..n)-(2^n-1)*2     Try it online!
Î>FNo-3Nm+     sum using a for loop           Try it online!
LDδcDøδ*˜O     port of caird's answer         Try it online!
3Å0λ5*₂6*->    a(n)=5*a(n-1)-6*a(n-2)+1       Try it online! (infinite sequence)
\$\endgroup\$
1
\$\begingroup\$

Charcoal, 12 bytes

IΣE⊕N⁻X³ιX²ι

Try it online! Link is to verbose version of code. Uses @xigoi's Risky formulation of @Nitrodon's formula. Explanation:

    N           Input integer
   ⊕            Incremented
  E             Map over implicit range
      X³ι       Power of 3
     ⁻          Subtract
         X²ι    Power of 2
 Σ              Sum
I               Cast to string
                Implicitly print

I tried porting a couple of the other formulae too but they weighed in at 14 bytes.

\$\endgroup\$
1
\$\begingroup\$

Add++, 16 bytes

L,Rd3€^¦+$2€^¦+_

Try it online!

Frick you caird for making such a painful esolang (:p). Port of everyone's favourite Jelly answer by xigoi.

Explained

L,Rd3€^¦+$2€^¦+_
L,               # make a lambda that:
  Rd             #   pushes the range [1, input] twice and
    3€^          #   raises 3 to the power of each item,
       ¦+        #   summing that list (can't use s to sum here because frick you caird)
         $2€^¦+  #   do the same with 2
               _ #   subtract the two items. The i flag automatically runs the lambda and implicitly outputs the result
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.