Skip to main content
4 votes
Accepted

Reasoning about the Collatz conjecture, multiple infinitely growing trees that never overlap?

This is a construction you can perform for any function $f : X \to X$ from a set $X$ to itself called taking the backwards orbit $f^{-\infty}(x)$, also known as the basin of attraction of $x$. Here $X$...
Qiaochu Yuan's user avatar
4 votes
Accepted

Closed formula for probability of n-digit numbers containing three consecutive sixes

Here is an attempt at a systematic approach. Let $a(n)$ be the number of $n$-digit numbers with no leading zero and at least one 666 pattern $b(n)$ be the number of $n$-digit numbers possibly with a ...
Henry's user avatar
  • 159k
4 votes
Accepted

Closed form for the recurrence $S_n = 1 + S_{n-1} + \frac{2}{n} S_{n-2}$, where $S_1=1$ and $S_2=2$?

I went for a power series expansion and found $$\sum_{n=1}^\infty S_n x^n = \frac{1-e^{-2x}}{2(1-x)^3}~.$$ From here you can use the cauchy product to gain an explicit description of the sequence. $$...
M.E.W.'s user avatar
  • 188
3 votes
Accepted

Solving equations involving the floor and ceiling function

Let's look in general at the equation $$\tag{*} x=\left\lfloor\frac{\left\lceil ax\right\rceil}{a}\right\rfloor$$ for real positive $a$ (in the case of this question, we have $a=\frac{103}{64}$). The ...
Chris Lewis's user avatar
  • 2,568
2 votes

Closed formula for probability of n-digit numbers containing three consecutive sixes

The problem can be attacked by using Inclusion-Exclusion, with Stars and Bars used internally. First, briefly see this self-answer question which uses the methodology to attack a similar question, ...
user2661923's user avatar
  • 37.2k
1 vote

What is the correct term for maximal/minimal "thickness" of convex hull in ℝ³?

With the help of Mikhail I found document naming minimal/maximal "thickness" width/diameter in 1.3 Preliminaries. I updated the JSCAD app for this thread to provide a "width/diameter&...
HermannSW's user avatar
1 vote
Accepted

Remove two vertices such that there are no 3-cliques in the resulting graph

Assume, on the contrary, that there exists a graph $G$, $|V(G)|>1$ in which (i) any two triangles have at least one vertex in common; (ii) there are no $5$-cliques; (iii) for any two vertices of $V(...
kabenyuk's user avatar
  • 10.8k
1 vote

Simplify the following using logical equivalence, and prove equivalence: ~(~p ∧ q) ∧ (p ∨ q) ≡ p

That is called distributive law. $$p \vee (q\wedge r) \equiv (p\vee q) \wedge (p\vee r).$$
Yathi's user avatar
  • 2,470
1 vote
Accepted

Simplify the following using logical equivalence, and prove equivalence: ~(~p ∧ q) ∧ (p ∨ q) ≡ p

$\newcommand{\lsim}{\mathord{\sim}}$We are working with the expression $$\lsim((\lsim p) \wedge q) \wedge (p \vee q)$$ The first step uses $\lsim(A\wedge B)\equiv\lsim A\vee\lsim B$ and $\lsim(\lsim A)...
ultralegend5385's user avatar
1 vote

Number of lattices over a finite set

As suggested in the comments, there is no closed-form formula (yet) for the number of lattices over a finite set of $n$ elements. See this paper.
lafinur's user avatar
  • 3,452
1 vote

Closed formula for probability of n-digit numbers containing three consecutive sixes

Let us define $g(n)$ to be the number of $n$-digit numbers that contain at least 3 consecutive sixes. Then, to find a recursive pattern let us find $g(n+1)$ in terms of $g(n)$. Let us start by noting ...
Nic's user avatar
  • 774
1 vote

Closed formula for probability of n-digit numbers containing three consecutive sixes

My other answer used Inclusion-Exclusion to provide a very convoluted closed form formula. This answer provides a sanity-check against the other answer. Similar to my other answer, in this answer, I ...
user2661923's user avatar
  • 37.2k
1 vote

Finding a new MST for $G(V,E)$ after connecting a new vertex

This is exactly one step of Prim's algorithm. There we already have a minimum spanning tree of some subset of vertices $V'$ then we consider new vertex $v$ and it's incident edges along with the ...
spectralmath's user avatar
1 vote

Closed formula for probability of n-digit numbers containing three consecutive sixes

We use a generating function approach to derive a formula for the wanted sequence of probabilities. In order to do so we reformulate the problem a bit. We consider an alphabet $\mathcal{V}=\{0,1,2,3,4,...
Markus Scheuer's user avatar
1 vote

Simple paths in a graph

There are two paths from a to b, two paths from b to d, and one path from a to d. Therefore, 2 x 2 + 1 = 5.
Doug's user avatar
  • 2,584

Only top scored, non community-wiki answers of a minimum length are eligible