Rearranging the sequence
ES6, 118 81 78 bytes
n=>[...[...Array(n).keys()].join``].map(c=>r/=(o[c]=-~o[c])/i++,o=[],i=r=1)&&r
Someone's bound to tell me there's a shorter way of concatenating the numbers up to n
.
Saved a cool 37 bytes by taking @edc65's idea and running it on steroids. (Save an extra byte by using '|' instead of &&
but that limits the result to 31 bits.)
Edit: Saved 3 further bytes again thanks to @edc65.
APL (Dyalog Extended), 13 bytes
×/2!/+\⎕D⍧⍕⍳⎕
Try it online!
A full program. Uses ⎕IO←0
.
How it works
×/2!/+\⎕D⍧⍕⍳⎕
⎕ ⍝ Take input from stdin (N)
⍳ ⍝ Generate range 0..N-1
⍕ ⍝ Stringify the entire array (S)
⍝ (The result has spaces between items)
⎕D ⍝ The character array '0123456789'
⍧ ⍝ Count occurrences of each digit in S
×/2!/+\ ⍝ Calculate multinomial:
+\ ⍝ Cumulative sum
2!/ ⍝ Binomial of consecutive pairs
×/ ⍝ Product
The multinomial calculation comes from the following fact:
$$ \frac{(a_1 + a_2 + \cdots + a_n)!}{a_1! a_2! \cdots a_n!} = \frac{(a_1 + a_2)!}{a_1! a_2!} \times \frac{(a_1 + a_2 + \cdots + a_n)!}{(a_1 + a_2)! a_3! \cdots a_n!} $$
$$ = \frac{(a_1 + a_2)!}{a_1! a_2!} \times \frac{(a_1 + a_2 + a_3)!}{(a_1 + a_2)! a_3!} \times \frac{(a_1 + a_2 + \cdots + a_n)!}{(a_1 + a_2 + a_3)! \cdots a_n!} $$
$$ = \cdots = \binom{a_1 + a_2}{a_1} \binom{a_1 + a_2 + a_3}{a_1 + a_2} \cdots \binom{a_1 + \cdots + a_n}{a_1 + \cdots + a_{n-1}} $$
MATL, 21 bytes
:qV0h!4Y2=sts:pw"@:p/
Try it online!
Explanation
:q % implicitly input N, and generate vector [0, 1, ..., N-1]
V % convert to string representation of numbers. Contains spaces,
% but no matter. Only characters '0', ..., '9' will be counted
0h % append 0 character (not '0'), so that string is never empty
! % convert string to column char array
4Y2 % string '0123456789' (row char array)
= % test all pairs for equality
s % sum each column. For N = 12 this gives [2, 4, 1, 1, ..., 1]
t % duplicate
s % compute sum. For N = 12 this gives 14
:p % factorial
w % swap. Now vector [2, 4, 1, 1, ..., 1] is on top
" % for each number in that vector
@:p % factorial
/ % divide
% implicitly end loop
% implicitly display