Third Stirling numbers of the second kind

Question

\$\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 sequence 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 code-golf 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

xigoi · Accepted Answer · 2021-07-21 20:51:18Z

12

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

edited Jul 21, 2021 at 20:51

answered Jul 21, 2021 at 20:29

xigoi

7,3312 gold badges13 silver badges23 bronze badges

2

\$\begingroup\$ With some rearrangement you can do this in 6 bytes like so: 3Ḋ*)SI \$\endgroup\$
– Jonathan Allan
Commented Jul 21, 2021 at 20:45
2

\$\begingroup\$ @JonathanAllan Smart idea, thanks! \$\endgroup\$
– xigoi
Commented Jul 21, 2021 at 20:46

Add a comment |

pajonk · Accepted Answer · 2021-07-21 19:21:41Z

9

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 $$

answered Jul 21, 2021 at 19:21

pajonk

18.3k3 gold badges25 silver badges74 bronze badges

2

\$\begingroup\$ Nice. Here's another 23-byter but I can't beat you... \$\endgroup\$
– Dominic van Essen
Commented Jul 21, 2021 at 22:59

Add a comment |

caird coinheringaahin g · Accepted Answer · 2021-07-22 10:46:58Z

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

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\$. — Nitrodon, Commented Jul 22, 2021 at 15:09

Nitrodon · Accepted Answer · 2021-07-21 19:07:06Z

7

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.

answered Jul 21, 2021 at 19:07

Nitrodon

10.8k2 gold badges19 silver badges33 bronze badges

Add a comment |

xnor · Accepted Answer · 2021-07-21 18:30:45Z

6

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

edited Jul 21, 2021 at 18:30

answered Jul 21, 2021 at 18:09

xnor

147k26 gold badges279 silver badges652 bronze badges

Add a comment |

Adám · Accepted Answer · 2021-07-21 18:43:50Z

6

APL (Dyalog Unicode), 14 bytes

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

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

Try it online!

answered Jul 21, 2021 at 18:43

Adám

31.1k3 gold badges124 silver badges287 bronze badges

Add a comment |

Nick Kennedy · Accepted Answer · 2021-07-21 19:52:21Z

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

Jonathan Allan · Accepted Answer · 2021-07-21 20:51:18Z

6

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

edited Jul 21, 2021 at 20:51

answered Jul 21, 2021 at 20:25

Jonathan Allan

110k7 gold badges65 silver badges282 bronze badges

\$\begingroup\$ What formula is this based on? \$\endgroup\$
– xigoi
Commented Jul 22, 2021 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
Commented Jul 22, 2021 at 19:17

Add a comment |

user · Accepted Answer · 2021-07-21 22:25:35Z

6

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

edited Jul 21, 2021 at 22:25

answered Jul 21, 2021 at 18:59

user

3872 gold badges21 silver badges68 bronze badges

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
Commented Jul 21, 2021 at 22:24
\$\begingroup\$ @DominicvanEssen It doesn't, I'll mention that in the answer. \$\endgroup\$
– user
Commented Jul 21, 2021 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
Commented Jul 21, 2021 at 22:34

Add a comment |

ZaMoC · Accepted Answer · 2021-07-21 21:06:01Z

5

Wolfram Language (Mathematica), 15 bytes

#~StirlingS2~3&

Try it online!

answered Jul 21, 2021 at 21:06

ZaMoC

24.9k2 gold badges30 silver badges81 bronze badges

Add a comment |

user · Accepted Answer · 2021-07-21 22:42:41Z

5

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.

edited Jul 21, 2021 at 22:42

answered Jul 21, 2021 at 22:37

user

3872 gold badges21 silver badges68 bronze badges

Add a comment |

d01 · Accepted Answer · 2023-01-16 06:44:27Z

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)

@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) — d01, Commented Jul 22, 2021 at 0:42

Noodle9 · Accepted Answer · 2021-07-21 20:04:44Z

4

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\$.

edited Jul 21, 2021 at 20:04

answered Jul 21, 2021 at 19:59

Noodle9

20.3k3 gold badges21 silver badges46 bronze badges

Add a comment |

chunes · Accepted Answer · 2021-07-22 01:49:44Z

4

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.

answered Jul 22, 2021 at 1:49

chunes

26.8k3 gold badges24 silver badges53 bronze badges

1

\$\begingroup\$ now this is a mathematica level threat \$\endgroup\$
– Razetime
Commented Jul 22, 2021 at 6:25

Add a comment |

ovs · Accepted Answer · 2021-07-23 11:19:38Z

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 +/∊+.×⍨∘.!⍨⍳⎕

lyxal · Accepted Answer · 2021-07-31 06:39:25Z

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

ovs · Accepted Answer · 2021-08-25 09:39:00Z

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 subtraction

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)

AnttiP · Accepted Answer · 2022-02-18 17:27:37Z

3

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

edited Feb 18, 2022 at 17:27

AnttiP

7,91815 silver badges61 bronze badges

answered Jul 21, 2021 at 21:07

xigoi

7,3312 gold badges13 silver badges23 bronze badges

Add a comment |

lyxal · Accepted Answer · 2021-07-22 01:46:25Z

2

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
```

answered Jul 22, 2021 at 1:46

lyxal

34.3k2 gold badges64 silver badges141 bronze badges

1

\$\begingroup\$ Vyxal really likes to abuse our “CL flags = different language” rules :D \$\endgroup\$
– xigoi
Commented Jul 22, 2021 at 10:04

Add a comment |

Neil · Accepted Answer · 2021-07-30 18:42:06Z

Charcoal, 12 bytes

ＩΣＥ⊕Ｎ⁻Ｘ³ιＸ²ι

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

    Ｎ           Input integer
   ⊕            Incremented
  Ｅ             Map over implicit range
      Ｘ³ι       Power of 3
     ⁻          Subtract
         Ｘ²ι    Power of 2
 Σ              Sum
Ｉ               Cast to string
                Implicitly print

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

Roman Czyborra · Accepted Answer · 2023-01-17 05:13:22Z

2

Haskell, 21 bytes

s n=div(3^n-3*2^n+3)6

$$\left\{n\atop3\right\}=\frac{3^n-3!\left\{n\atop2\right\}-3\left\{n\atop1\right\}}{3!}=\frac{3^n-3!\frac{2^n-2}{2!}-3}{3!}=\frac{3^n-3(2^n-2)-3}{3!}=\frac{3^n-3\cdot2^n+6-3}{6}=\frac{3^n-3\cdot2^n+3}6$$

Try it online!

edited Jan 17, 2023 at 5:13

answered Jan 16, 2023 at 9:56

Roman Czyborra

1,6388 silver badges16 bronze badges

Add a comment |

alephalpha · Accepted Answer · 2023-01-16 10:25:47Z

1

PARI/GP, 17 bytes

n->(2^n-3^n\3)\-2

With leading zeros.

Attempt This Online!

PARI/GP, 18 bytes

n->stirling(n,3,2)

With leading zeros.

Attempt This Online!

PARI/GP, 14 bytes

n->-3^n\-2-2^n

Attempt This Online!

This gives the sequence 0, 0, 1, 6, 25, 90, 301, 966, .... I'm not sure if this is allowed.

edited Jan 16, 2023 at 10:25

answered Jan 16, 2023 at 10:08

alephalpha

50k7 gold badges68 silver badges182 bronze badges

Add a comment |

Shaggy · Accepted Answer · 2023-01-16 13:10:17Z

0

Japt `-mx`, 9 bytes

3p°U -2pU

Try it

3p°U -2pU     :Implicit map of each U in [0,input)
3p            :3 raised to the power of
  °U          :  U, prefix incremented
     -        :Subtract
      2pU     :2 raised to the power of U
              :Implicit output of sum of resulting array

answered Jan 16, 2023 at 13:10

Shaggy

43.5k4 gold badges36 silver badges94 bronze badges

Add a comment |

Kip the Malamute · Accepted Answer · 2023-01-16 16:02:34Z

0

Pyt, 13 bytes

Đ1⇹«⇹⁻3⇹^⇹-⁺₂

Try it online!

Port of xnor's answer

answered Jan 16, 2023 at 16:02

Kip the Malamute

1,7672 silver badges13 bronze badges

Add a comment |

Third Stirling numbers of the second kind

Test cases

24 Answers 24

Jelly, 6 bytes

Explanation

R, 23 bytes

Jelly, 7 bytes

How it works

Alchemist, 76 bytes

Python 2, 24 bytes

APL (Dyalog Unicode), 14 bytes

Jelly, 12 bytes

Explanation

Jelly, 9 bytes

How?

Jelly, 9 bytes

Wolfram Language (Mathematica), 15 bytes

Scala, 132 bytes

Rattle, 24 bytes

Explanation

C (gcc), 34 bytes

Factor + math.extras, 18 bytes

APL (Dyalog Unicode), 14 bytes

Add++, 16 bytes

Explained

05AB1E, 8 bytes

Risky, 10 bytes

Explanation

Vyxal sr, 6 bytes

Explained

Charcoal, 12 bytes

Haskell, 21 bytes

PARI/GP, 17 bytes

PARI/GP, 18 bytes

PARI/GP, 14 bytes

Japt -mx, 9 bytes

Pyt, 13 bytes

Your Answer

Sign up or log in

Post as a guest

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

Related

Hot Network Questions

Factor + `math.extras`, 18 bytes

Vyxal `sr`, 6 bytes

Japt `-mx`, 9 bytes

Not the answer you're looking for? Browse other questions tagged
code-golf
math
sequence
set-partitions
or ask your own question.