/sci/ - Science & Math » Thread #14130151

88KiB, 425x1023, partitions_of_5.png

View Same Google iqdb SauceNAO

PERMUTATIONS AND COMBINATIONS

Anonymous Fri 21 Jan 01:35:26 2022 No.14130151 View Reply Original Report

Quoted By: >>14130510 >>14130522 >>14130660 >>14131033 >>14132808 >>14133629 >>14136938

I have such good feelings from combinatorics.
I'm pretty bad at it, but I'm also maybe the stupidest person who's ever gotten a math degree.

But I just fucking love ""advanced counting"".
There's something about it that feels so good to me. I also think it's undeservedly denigrated to "some subtopic" in "discrete" maths. Or a sidenote in graph theory. Or shit like that. But honestly dudes? I just really like combinatorics. It feels good and great and I like how it makes me feel.

Can people smarter than me talk about combinatorics?

Anonymous

View Same Google iqdb SauceNAO katyushaproblemliras-1.jpg, 1MiB, 1830x2590

Anonymous Fri 21 Jan 2022 02:37:20 No.14130332 Report

Quoted By: >>14130510 >>14131045 >>14132279 >>14133498 >>14141102

Not smarter than you but here's a problem I want to share. I think I took it from a book called combinatorial problems.
I enjoy combinatorics too but I'm also bad at it.

Anonymous

Anonymous Fri 21 Jan 2022 03:29:31 No.14130510 Report

Quoted By: >>14130576 >>14131031 >>14132315 >>14132439

>>14130151
I'm not even studying math but I love counting and combinatorics. Can't wait for my discrete math course next semester.
I'm just obsessed with the idea of Enumeration.
I try to teach my younger sister counting but unfortunately she doesn't seem to care that much.
I can't explain it either but I just wanted to tell you that I think I feel how you feel.
Hopefully I get to contribute somehow to the history of counting or whatever.

>>14130332
Not hard if you know fib.
$M_0 = M_1 = 1$
$M_n = M_{n-1} + 2M_{n-2}, n\geq2$
In other words we go from $n$ to $n+1$ (1 time) and $n+2$ (2 times).
So keeping a state $(M_{n-1}, M_n)$ we transition to $(M_n, M_{n+1}) = (M_n, M_n + 2M_{n-1})$ .
$\begin{bmatrix} M_n+1\\ M_n \end{bmatrix} = \begin{bmatrix} 1 & 2 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} M_n\\ M_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 2 \\ 1 & 0 \end{bmatrix}^n \begin{bmatrix} 1\\ 1 \end{bmatrix} $
We may be able to do diagonalization or some shit, I haven't studied linear algebra yet and I'm going to sleep now so I can't be bothered to search anything.
However we can compute the the result in $O(\log n)$ with binary exponentiation so my compsci ass is satisfied with the answer.

Anonymous

Anonymous Fri 21 Jan 2022 03:32:49 No.14130522 Report

Quoted By:

>>14130151
Go into a CS career OP. Being stupid and loving autistic things like different ways of counting would make you very successful

Anonymous

Anonymous Fri 21 Jan 2022 03:48:16 No.14130576 Report

Quoted By: >>14130617 >>14130652

>>14130510
Great job! that's the correct recursive formula and I think it's okay to be satisfied with that. What is fib by the way? Also what's this thing with states and matrices. I'd like to know more please.

Anonymous

Anonymous Fri 21 Jan 2022 04:02:35 No.14130617 Report

Quoted By: >>14130652 >>14130953

>>14130576
>What is fib by the way?
Fibonacci but I wanted to sound cool.
>Also what's this thing with states and matrices.
I like to think it that way to reach the recursive formula.
Probably a math-related resource would be better but I don't have any so here's errichto, he is nice at explaining things and making you understand them intuitively
https://www.youtube.com/watch?v=eMXNWcbw75E
You probably don't need to watch how he writes the code but he explains the states thing nicely. Thinking in states like that helps with many problems.

Anonymous

View Same Google iqdb SauceNAO states.jpg, 51KiB, 1467x486

Anonymous Fri 21 Jan 2022 04:20:50 No.14130652 Report

Quoted By: >>14130953

>>14130617
>>14130576
Well I just noticed that perhaps this 30 minute video isn't the best way to explain my thinking.
The intuition behind finding a nice matrix formula that to compute $M_n$ you only need $M_{n-1}$ and $M_{n-2}$ . So it makes sense to keep a states using only those, since all the previous values will be irrelevant.
That is why I choose to look only at those 2 values and I look at their transitions to the next state (see pic rel).
So a state is 2 numbers, you can think of it like a graph with 2 nodes and in each we keep track of the number of ways to reach it after $n$ 'moves/days'.
And to reach the next 'state/day' we will transfer the number in the vertex to some other vertex (according to pic).
The only thing left is how to build the matrix which does the transition.
If you recall that $c_{i j} = \sum_k a_{i k} \cdot b_{k j}$ when you do the matrix multiplication $C = A \cdot B$ then you can see how you can sort of 'build' the recursion formula for the states.

Anonymous

Anonymous Fri 21 Jan 2022 04:29:09 No.14130660 Report

Quoted By:

>>14130151
count the number of winnable games of klondike solitaire there are

Anonymous

View Same Google iqdb SauceNAO SPOILER_2021-07-30-18-46-16_000.png, 110KiB, 1714x350

Anonymous Fri 21 Jan 2022 07:31:38 No.14130953 Report

Quoted By:

>>14130617
>>14130652
I see, I see. That's very wise. Thank you so much for sharing. If you're interested, here's the closed formula for the answer by the way. A friend of mine got it by using generating functions.

Anonymous

Anonymous Fri 21 Jan 2022 08:27:16 No.14131031 Report

Quoted By: >>14132550

>>14130510
>We may be able to do diagonalization or some shit, I haven't studied linear algebra yet
product of eigenvalues = determinant = 1*0-2*1 = -2
sum of eigenvalues = trace = 1+0 = 1
Two numbers whose sum is 1 and product is -2: -1 and 2
closed formula is A*2^n + B*(-1)^n
plug in n = 0 and n = 1 and solve for A and B: A+B = 1, 2A-B = 1, so A = 2/3, B = 1/3
Final formula is (2/3)*2^n + (1/3)*(-1)^n.

Anonymous

Anonymous Fri 21 Jan 2022 08:28:17 No.14131033 Report

Quoted By:

>>14130151
Look into Project Euler. Lots of fun counting problems.

Anonymous

Anonymous Fri 21 Jan 2022 08:32:43 No.14131045 Report

Quoted By: >>14131049 >>14131839 >>14132519

>>14130332
We want the coefficient of t^n in (1+t+t^2+...)(1+t^2+t^4+...)^2. Using the geometric series, that infinite polynomial has the form [1/(1-t)][1/(1-t^2)] = 1/((1-t)^2(1+t)) = c0 + c1t + c2t^2 + ..., for some coefficients {cn}.
The idea is that we can calculate each coefficient one by one as we differentiate and plug in t = 0; if we denote our polynomial by p(t), we have cn = p^n(0)/n!.
Considering it as a rational function p^n(t) = qn(t)/rn(t), it's easy to see that rn(0) = 1. Alternatively, we could perform a partial fraction decomposition on p(t) which would make it easy to find a pattern when taking derivatives.
Typing all of this out on a mobile keyboard is frustrating so "exercise for the reader."

Anonymous

Anonymous Fri 21 Jan 2022 08:34:59 No.14131049 Report

Quoted By:

>>14131045
I forgot a ^2 on the second factor of the polynomial.

Anonymous

View Same Google iqdb SauceNAO combinatorial problems and exerc (...).jpg, 12KiB, 332x499

Anonymous Fri 21 Jan 2022 14:52:07 No.14131785 Report

Quoted By:

This book is really good. First third: problems. Second third: Hints. Third third: Solutions.

They immediately get much too difficult for my current understanding. But I hope someday I can work on them! It's on my shelf as an inspiration.

Anonymous

View Same Google iqdb SauceNAO erikaderangement.png, 837KiB, 1732x940

Anonymous Fri 21 Jan 2022 15:07:42 No.14131839 Report

Quoted By: >>14132466 >>14134507 >>14136490

>>14131045
I see, I see. This is all very nice.
I still need to check out that book by Wilf, Generatingfunctionology.
But thank you very much! You explained it pretty well I think.
Here's a different problem, quite a famous one at that. It can be solved with generating functions if you can get the recursion. Or it can be solved with PIE, principle of inclusion and exclusion. Maybe there are some other methods, I don't know. But either way, feel free to solve it or to skip it but I think it's a good problem.

Anonymous

Anonymous Fri 21 Jan 2022 17:28:00 No.14132279 Report

Quoted By: >>14132519 >>14132550

>>14130332
Let's call the number of Eti Topkek, Eti Jinn, and Eti Negro bought as a, b, c respectively. Let's also define d := b + c. Since 2d + a = n, we know that 2d can be any even number between [0, n], and that any such choice uniquely determines a. So therefore d ranges from $\left[0, \left\lfloor \frac{n}{2} \right\rfloor \right]$ . Furthermore, for each choice of d there are d+1 possible way to split those d 2 lira buys among b and c, since every possible b is between [0, d] and each choice of b uniquely determines c. So therefore, we get $\sum_{d = 0}^{\left\lfloor \frac{n}{2} \right\rfloor} (d+1) = \frac{\left\lfloor \frac{n}{2} \right\rfloor \left( \left\lfloor \frac{n}{2} \right\rfloor + 1 \right)}{2} + \left\lfloor \frac{n}{2} \right\rfloor + 1$

Anonymous

Anonymous Fri 21 Jan 2022 17:41:15 No.14132315 Report

Quoted By: >>14132472

>>14130510
How did you get the recurrence relation $M_n = M_{n-1} + 2M_{n-2}$ ?

Anonymous

Anonymous Fri 21 Jan 2022 17:57:13 No.14132351 Report

Quoted By: >>14133609

You roll six dice six times. What is the probability that the number six occurs exactly six times?

Anonymous

Anonymous Fri 21 Jan 2022 18:22:47 No.14132439 Report

Quoted By: >>14132472 >>14132550

>>14130510
This gives you that for 2 dollars, there are 3 ways of spending 2 dollars. Your recurrence relation is wrong.

Anonymous

Anonymous Fri 21 Jan 2022 18:28:58 No.14132466 Report

Quoted By: >>14132490 >>14132550 >>14134507

>>14131839
I guess you sort of spoiled the answer but it was really fun working the algebra.
Suppose $A_i$ is the set which has the ways of giving the papers such student $i$ gets their paper.
We see that if $S = \{i_1, i_2,\dots, i_m\}$ then
$\bigcap_{j\in S}A_j$ is the set of ways every student in $S$ getting their paper.
and $\bigcup_{j\in S}A_j$ is the set of at least one student in $S$ getting their paper.
notice that
$\left|\bigcap_{j\in S}A_j\right| = \left(n-|S|\right)!$
There are $n!$ ways of giving the papers without any condition.
Our answer is $n! - \left|\bigcup_{j\in\{1,\dots,n\}}A_j\right| = n! - \left(\sum_{\emptyset \neq J\subseteq\{1,\dots,n\}}(-1)^{|J|-1}|\left|\bigcap_{j\in J}A_j\right| \right) \\ = n! - \left(\sum_{\emptyset \neq J\subseteq\{1,\dots,n\}}(-1)^{|J|-1}\left(n - |J|\right)!\right) \\ = n! -\left(\sum_{k=1}^n\hspace{0.1cm}\sum_{J\subseteq\{1,\dots n\}:|J|=k}(-1)^{|J|-1}\left(n - |J|\right)!\right) \\ = n! - \sum_{k=1}^n \binom{n}{k} (-1)^{k-1}(n - k)! = n! - \sum_{k=1}^n (-1)^{k-1}\frac{n!}{k!} \\ = n!\left(1- \sum_{k=1}^n \frac{(-1)^{k-1}}{k!} \right) = n!\sum_{k=0}^n \frac{(-1)^{k-1}}{k!} $
I can't think of any more simplifications but I think the final term suffices.

Anonymous

Anonymous Fri 21 Jan 2022 18:30:24 No.14132472 Report

Quoted By: >>14132519

>>14132315
Suppose you are at your first day with $n$ coins. In that way there are 3 options each of which leads you to a different 'decision tree'. Because those 'decision trees' are disjoint you can sum the ways of each of your 3 different path.
The first path: getting the first lira (cost of 1, now you have $M_{n-1}$ ways of spending the rest)
The second path: getting the second lira (cost of 2, now you have $M_{n-2}$ ways of spending the rest)
The third path: getting the third lira (cost of 2, now you have $M_{n-2}$ ways of spending the rest)

>>14132439
but there are 3 ways to spend them. Name the coins 1, 2, 3 with corresponding costs 1, 2, 2.
Then the ways are (1->1)[2 days x1 coin each], (2)[1 day x2 coins], (3)[1 day x2 coins but the other lira that costs 2].

Anonymous

Anonymous Fri 21 Jan 2022 18:34:05 No.14132490 Report

Quoted By: >>14132550 >>14134507

>>14132466
oops I made a little mistake at the end. The correct steps would be
$ n!\left(1 - \sum_{k=1}^n \frac{(-1)^{k-1}}{k!}\right) = n!\left(- \sum_{k=0}^n \frac{(-1)^{k-1}}{k!}\right) = n!\sum_{k=0}^n \frac{(-1)^{k}}{k!}$

Anonymous

Anonymous Fri 21 Jan 2022 18:43:11 No.14132519 Report

Quoted By: >>14132611 >>14132650

>>14132472
>Suppose you are at your first day with nn coins. In that way there are 3 options each of which leads you to a different 'decision tree'. Because those 'decision trees' are disjoint you can sum the ways of each of your 3 different path.
>The first path: getting the first lira (cost of 1, now you have Mn?1Mn?1 ways of spending the rest)
>The second path: getting the second lira (cost of 2, now you have Mn?2Mn?2 ways of spending the rest)
>The third path: getting the third lira (cost of 2, now you have Mn?2Mn?2 ways of spending the rest)

This overcounts - for example, your first buy can be Jinn and your next buy can be negro, the rest of your decisions can be whatever, or your first buy can be negro, your second buy can be jinn. Both of these would count as different sequences, which is wrong
>but there are 3 ways to spend them. Name the coins 1, 2, 3 with corresponding costs 1, 2, 2.

>Then the ways are (1->1)[2 days x1 coin each], (2)[1 day x2 coins], (3)[1 day x2 coins but the other lira that costs 2].

Yeah idk what this anon was on because your method does yield the correct answer for 2 lira. However, even for the next iteration it breaks down due to this overcounting - it yields 5 possible options when there are actually 3.

>>14131045
>>14132279
Congrats on getting it correct

Anonymous

View Same Google iqdb SauceNAO tapiscombinatorics.png, 569KiB, 868x946

Anonymous Fri 21 Jan 2022 18:49:44 No.14132550 Report

Quoted By: >>14132611 >>14132904 >>14133738 >>14134507

>>14131031
Nice job mate!
That's correct. I haven't studied linear algebra yet so honestly I didn't understand a word of it but seeing it applied like this certainly made me more aware of how useful it is.
>>14132279
Hmmmm...Honestly I can't say you are wrong. I understand the beginning of your argument but I couldn't understand the later part. Could you check if it works for the other solution posted here.
>>14132439
Now I could be wrong but I think his recursion relation is correct. For 2 dollars, we do have 3 ways to spend our money. We can buy 2 TopKeks, that's one way. We can buy one Jinn, that's the second way. We can buy one Negro :DDDD, that's the third way.
>>14132466
>>14132490
Yeah I suppose I did give a bit of a spoiler but still, great job!
I'm really impressed honestly, and thank you very much giving me your time. I could post more problems but I think my problems might be too basic for you. However if you are interested I'd like to share more problems. But only if you want to see them.

Anonymous

Anonymous Fri 21 Jan 2022 19:00:38 No.14132611 Report

Quoted By: >>14132650

>>14132519
>This overcounts - for example, your first buy can be Jinn and your next buy can be negro, the rest of your decisions can be whatever, or your first buy can be negro, your second buy can be jinn. Both of these would count as different sequences, which is wrong
Since you buy them on different days they count as different ways.
I can see how you can modify the problem so it makes sense the way you are describing but I don't think it really fits with the current problem statement.

>>14132550
I wouldn't mind seeing more of your problems, I'm curious to see what other topics they cover.
I might not post more solutions if I believe the solution is too simple but I still have a lot more intuition to build even in 'simple' concepts.

Anonymous

View Same Google iqdb SauceNAO rosehipturkishl.png, 290KiB, 771x591

Anonymous Fri 21 Jan 2022 19:09:47 No.14132650 Report

Quoted By: >>14132725 >>14132732

>>14132611
>>14132519
Yeah, for this problem, which day you buy it matter so there's no overcounting. I apologize for not making it clear.
>>14132611
alright then. Here's a pretty simple one I suppose. I'm Turkish btw and kurds breed like rabbits. The question is a bit badly worded according to my friends so again, sorry. Just pay attention to the pairs part.

Anonymous

Anonymous Fri 21 Jan 2022 19:28:32 No.14132725 Report

Quoted By: >>14132732 >>14132873

>>14132650
Well that's way too simple but I don't have anything better to do so
Proof by induction:
Base cases $n = 0$ (after 0 months) obviously we have 1 pair, $n = 1$ (after 1 month) we still have 1 pair (the pair does not breed in the first month).
Suppose it is true for every number up to $n$ then in the next month every pair that is in the current month will be there (rabbits live forever), the number is $F_n$ .
Also every pair from those $F_n$ that can breed will breed and will produce exactly 1 other pair. How many pairs will do that? Every pair that was there 1 months before as well so finally $Answer_n = F_n + F_{n-1} \left [ = F_{n+1}\right ]$ .

Also what's with the anime girls and Turkish theme? I mean, I get the anime girls but are you Turkish by any chance?

Anonymous

Anonymous Fri 21 Jan 2022 19:29:54 No.14132732 Report

Quoted By: >>14132873

>>14132650
>>14132725
>I'm Turkish btw
Oh apparently I didn't read your post.
But my question remains, do you make these pics/problems?

Anonymous

Anonymous Fri 21 Jan 2022 19:45:11 No.14132808 Report

Quoted By:

>>14130151
I always get combinatorics problems correct but I never truly feel like I get it. Like it's just some few rules that I apply to specific wording and it just works. Same goes for conditional probability.

Anonymous

View Same Google iqdb SauceNAO rukiririaluffi2nobg.png, 333KiB, 700x900

Anonymous Fri 21 Jan 2022 20:00:05 No.14132873 Report

Quoted By: >>14133014

>>14132732
>>14132725
I make these pics. I do edit these problems but no I didn't write them myself. I take them from various books. I'm not too good at photoshopping either but editing books into hands is relatively easy and so is putting text on a whiteboard.

Anonymous

Anonymous Fri 21 Jan 2022 20:08:15 No.14132904 Report

Quoted By:

>>14132550
>Could you check if it works for the other solution posted here.

I checked with the generating function solution, it's consistent.

>Since you buy them on different days they count as different ways.
I can see how you can modify the problem so it makes sense the way you are describing but I don't think it really fits with the current problem statement.

It's ambiguous problem wording in whether the order of spending is counted in the way of spending money. The question of what combinations we can have (my interpretation) is a different question than what ordered sequences of buys we can do (your interpretation). Considering the person who used generating functions used the same interpretation I did, I would say my interpretation is the most common sense one.

Anonymous

Anonymous Fri 21 Jan 2022 20:44:12 No.14133014 Report

Quoted By: >>14133282

>>14132873
Do you mind the problem you consider the hardest/most advanced?

Anonymous

Anonymous Fri 21 Jan 2022 21:02:33 No.14133087 Report

Quoted By: >>14133282 >>14133908

There's nothing wrong with easy problems too, it is good practice for dumdums like myself
I've never liked how in a lot of math circles, there's this kind of ridiculous disdain for simple problems like they physically hurt. It's a very gross kind of self-indulgent theatrical thing, very disgusting to witness
I'm not saying that I see that here, just rambling and reminding people that it's ok to post dum-dum tier problems/solutions. Personally I still struggle with "number of a certain kind of poker hand" type problems. But I haven't put much effort in and I'm stronger in other areas, it doesn't bother me.

In fact, does anyone have recommendation for their very favorite intro level combinatorics text? If it's bundled in a discrete/graph theory text that's fine too if the combinatorics is handled particularly well by your opinion.
Personally, I prefer texts that have a bit of narrative meat to them, over texts that try to reach some maximum density of concise presentation.

Anonymous

View Same Google iqdb SauceNAO rosehipeulerformulabriish.png, 800KiB, 1540x1080

Anonymous Fri 21 Jan 2022 21:59:02 No.14133282 Report

Quoted By: >>14133888

>>14133014
Well, I honestly don't have anything too advanced. I haven't started my math classes yet so my level is pretty low and so far I have only looked at problems around my level.
But here's one I'd say is the hardest one, at least for me. It's about Euler's formula. I hope it's good enough.
>>14133087
Agreed, I like easy problems, though it's mostly because I'm bad. But the best problems are those that are hard but no so hard that I couldn't solve it. There should be balance.

Anonymous

Anonymous Fri 21 Jan 2022 22:28:24 No.14133406 Report

Quoted By: >>14133609

How large must a party be, to be assured that at least 5 people are either all pairwise strangers, or have all pairwise met before?

Anonymous

View Same Google iqdb SauceNAO apu_crying.jpg, 28KiB, 619x453

Anonymous Fri 21 Jan 2022 23:02:43 No.14133498 Report

Quoted By: >>14133619

>>14130332
but, i want eti puff

Anonymous

View Same Google iqdb SauceNAO sataniacombina.png, 598KiB, 807x807

Anonymous Fri 21 Jan 2022 23:47:43 No.14133609 Report

Quoted By: >>14134002

>>14133406
isn't this Ramsey number of 5,5?
If I recall correctly, it wasn't calculated yet because of how difficult it was for some reason. I might be wrong. Please explain.
>>14132351
Very devilish problem. A lot of 6s. Just going to bump it so I can attempt it tomorrow. But I have an idea about it.

Anonymous

View Same Google iqdb SauceNAO kayeatingbaklava.jpg, 111KiB, 800x794

Anonymous Fri 21 Jan 2022 23:49:57 No.14133619 Report

Quoted By:

>>14133498
I'm sorry, the store doesn't have puff...
are you turkish as well?
here, have a baklava. 100% turkish food.

Anonymous

Anonymous Fri 21 Jan 2022 23:52:55 No.14133629 Report

Quoted By:

>>14130151
>Can people smarter than me
everybody is equally smart, you can increase you're IQ by 100 points

Anonymous

Anonymous Sat 22 Jan 2022 00:46:24 No.14133738 Report

Quoted By: >>14134325

>>14132550
>I haven't studied linear algebra yet so honestly I didn't understand a word of it
It's really simple stuff.

For a given matrix A, there are some vectors nonzero v such that when you multiply A by v, you get a scalar multiple of v, meaning Av = ?v, where ? is a real (or complex) number. We call the vector v an "eigenvector of A", and we call ? an "eigenvalue of A associated to v".

This obviously isn't true for any general vector, and it's very obviously true for the zero vector.
Moreover, if v is an eigenvector and ? is its eigenvalue, any scalar multiple of v is also an eigenvector of A with the same eigenvalue ?. (Try verifying it: Take cv, and plug it into the equation)

You want to find the eigenvalues and eigenvectors because you can use them to diagonalize A; if you put all the eigenvectors of A into the columns of a matrix P (and it happens to be a square matrix), then you know each column of the product AP will be the same column of P, but multiplied by the corresponding eigenvalue. This can be written as PD, where D is a diagonal matrix with the diagonal entries being the corresponding eigenvalues of the columns of P. So you get AP = PD. You can rearrange the equation to get A = PDP' (where the apostrophe means inverse).

Now you can do fun stuff like A^n = (PDP')*(PDP')*...*(PDP') n times, remove the parentheses and cancel the P with P', and you get A^n = P(D^n)P'. And this is relevant for our original question, because once you replace in the matrix equation for our answer and multiply out, you get the formula for Mn.

To actually compute these eigenstuff, rewrite Av = ?v as Av = (?I)v (I being the identity matrix), then rearrange as (A-?I)v = 0, so the new equation says (A-?I) sends the nonzero vector v to the zero vector, meaning the determinant of (A-?I) is zero. Get the determinant, you get a polynomial (in our case a quadratic), set it to zero, solve for ?. Take these ?'s back into (A-?I)v = 0, solve for v.

Anonymous

View Same Google iqdb SauceNAO l1.jpg, 38KiB, 453x654

Anonymous Sat 22 Jan 2022 01:56:03 No.14133888 Report

Quoted By: >>14134325

>>14133282
Well I have seen euler's formula a couple of times. I never thought of proving it though. I'm not great at graph proofs so I might be missing something but here is my shot.
Suppose in a graph we denote the countries as $C$ . Then we want to prove that $|C|+|V| = |E| + 2$ in an arbitrary connected graph .

Lemma 1. A cycle of length bigger than 2 in a graph splits the plane in 2 countries. Also there is an edge in the cycle which if we remove will cause the 2 countries to 'join'.
Proof. Arranging vertices like pic rel should be enough to convince someone of the correctness of the statement.

Lemma 2. A tree does not split the infinite country, i.e $|C| = 1$ .
Proof. Given a tree with $n$ nodes we root it at an arbitrary vertex. Constantly constructing the tree from root to the leaves we can see that we won't split the country at any point.

Now we will prove euler's formula.
Suppose we have a graph $G=(V, E)$ .
If there is not a cycle then, since the graph is connected, we will have a tree. In a tree $|E|=|V|-1$ and by Lemma 2 $|C|=1$ so in fact $|C|+|V|=1+(|E|+1)=|E|+2$ , and so we are done.
If there is a cycle then by Lemma 1 there will be and edge $e$ which if we remove will join 2 countries. Removing it we will now have $E'=E-\{e\}$ ( $|E'|=|E|-1$ ) and $|F'|=|F|-1$ .
Considering the equation we want to prove, we remove 1 from both sides so if the formula holds for the new graph it will hold for the one we want.
Continuously removing such edges will decrease $|E|$ by 1 each time but we can't keep taking away from a positive integer so the algorithm should terminate.
In other words eventually we will eventually reach a tree. (Also notice that the graph will always continue to be connected so we don't break any rules).

Thanks for the problem btw. It is very well known but still I hadn't given it much thought.

Anonymous

Anonymous Sat 22 Jan 2022 02:02:36 No.14133908 Report

Quoted By:

>>14133087
Not sure if it is a good resource but honestly Combinatorics by Joy Morris was the read that made me feel like stuff were starting to seem obvious. That feeling of 'shit, of course that's true I'm so stupid!'. Hopefully you'll feel the same way.
As for practicing, the Art and Craft of Problem Solving by Paul Zeitz has some great combinatorics problems. Some of which are not as exercise but rather as a demonstration. It is generally a good book

Anonymous

View Same Google iqdb SauceNAO erdos laughing.jpg, 44KiB, 260x316

Anonymous Sat 22 Jan 2022 02:38:31 No.14134002 Report

Quoted By: >>14134325

>>14133609
>isn't this Ramsey number of 5,5?
Yes it was my attempt at a ruse, a bamboozle, some simple shenanigans

Anonymous

View Same Google iqdb SauceNAO erdosthebook.png, 956KiB, 683x905

Anonymous Sat 22 Jan 2022 05:27:08 No.14134325 Report

Quoted By: >>14134822

>>14133738
hmm hmm I see. Thank you very much for explaining. I will try to really understand this stuff and then try attempting the eti negro problem using this.
>>14133888
Great job! And nice trips.
As far as I can tell your proof is correct.
Would you be interested in being friends and such? If you have a discord or something I'd like to add you.
Also thank you as well, you gave these problems a lot of your time and I appreciate it.
>>14134002
we do a little trolling

Anonymous

Anonymous Sat 22 Jan 2022 07:08:03 No.14134507 Report

Quoted By: >>14134822

>>14131839
>>14132466
>>14132490
>>14132550
https://en.wikipedia.org/wiki/Derangement
Notice how, once you get the probability by dividing by n!, you're left with an expression that looks like the Taylor series for exp(x) evaluated at -1.
The probability is therefore roughly 1/e.

Anonymous

Anonymous Sat 22 Jan 2022 10:16:46 No.14134822 Report

Quoted By:

>>14134507
Oh yeah that's pretty cool. So that's why e pops up so much huh.

>>14134325
>If you have a discord or something I'd like to add you.
Yeah, feel free to do so: cowboy_ohm#0710

Anonymous

View Same Google iqdb SauceNAO CE1208CC-D978-454C-913B-C54D35CA (...).png, 846KiB, 1419x1665

Anonymous Sat 22 Jan 2022 16:40:57 No.14135594 Report

Quoted By:

Bump

Anonymous

View Same Google iqdb SauceNAO graphs.pdf, 75KiB, 1x1

Anonymous Sat 22 Jan 2022 21:04:58 No.14136490 Report

Quoted By: >>14136623 >>14137921

>>14131839
How did I do?

Anonymous

View Same Google iqdb SauceNAO 1634958306707.jpg, 16KiB, 465x488

Anonymous Sat 22 Jan 2022 21:41:20 No.14136623 Report

Quoted By:

>>14136490
jesus man!
Well done, though I'm not looking too carefully, just impressed on the efforts.
Combinatorists go the extra mile!

Anonymous

Anonymous Sat 22 Jan 2022 23:39:01 No.14136938 Report

Quoted By:

>>14130151
Guys, I'm not a math major. So I'm not very good at math but combinatorics interests me a lot. I bought a book from the library to study, but these books don't explain the subject. Now my main question is, can you guys suggest videos for studying combinatorics?

Anonymous

Anonymous Sat 22 Jan 2022 23:50:24 No.14136965 Report

Quoted By: >>14137005

Algebraic enumeration is useful as a tool for DNA and RNA analysis, which is a popular topic.

Anonymous

Anonymous Sun 23 Jan 2022 00:02:42 No.14137005 Report

Quoted By:

>>14136965
Could you elaborate?

Anonymous

View Same Google iqdb SauceNAO kemonographtheory.jpg, 1MiB, 2508x3541

Anonymous Sun 23 Jan 2022 06:17:11 No.14137921 Report

Quoted By:

>>14136490
Simply phenomenal mate. You did perfect.
God be my witness, if I could give some medal for all the solutions given to problems I posted , it would go to you. Thanks a lot. And thanks for the references at the end as well. Great job.

Anonymous

Anonymous Sun 23 Jan 2022 11:12:42 No.14138410 Report

Quoted By: >>14138607

Okay autists, how far into linear algebra do I need to go in order to understand all this stuff?

Anonymous

Anonymous Sun 23 Jan 2022 12:41:51 No.14138607 Report

Quoted By:

>>14138410
For the linear algebra stuff used here, just a basic course on it. It's not difficult.
But there's more stuff used here, like graphs (graph theory), principle of inclusion-exclusion, generating functions, combinatorics (discrete math course).

The things discussed here aren't high-level. This is 4chan, so you shouldn't expect anything complicated.

Anonymous

Anonymous Sun 23 Jan 2022 13:00:31 No.14138663 Report

Quoted By: >>14140658 >>14141004

How many different 3 x 5 x 7 rectangular prisms can you make out of only red or blue 1 x 1 x 1 cubes that have no rows in any direction whose cubes are all the same color? The answer for 2 x 3 x 5 is 6510.

Anonymous

Anonymous Sun 23 Jan 2022 23:31:45 No.14140658 Report

Quoted By: >>14140967

>>14138663
9114

Anonymous

Anonymous Mon 24 Jan 2022 01:11:27 No.14140967 Report

Quoted By:

>>14140658
the answer for 2 x 5 x 7 is 20218802310

Anonymous

Anonymous Mon 24 Jan 2022 01:28:13 No.14141004 Report

Quoted By: >>14141051 >>14141075 >>14141141

>>14138663
That's way too complicated man.
I suppose you have a program of some sorts.
I mean, my strategy would be to count the number of colorings which have a specific rotational symmetry (I would need to be careful of overcounting here) while they have some (perhaps 0) rows of the same color.
Do some PIE magic there and find the answer. I would be interested there are just too many symmetries. Maybe I'll try the 1d and 2d case sometime and see if there is an easy generalization or whatever.

Anonymous

Anonymous Mon 24 Jan 2022 01:45:37 No.14141051 Report

Quoted By: >>14141074 >>14141075

>>14141004
the 2pq case is identical to the pq case because a 2-colored pq matrix can only comply by fitting its own inverse onto itself. the 3pq case needs more than this.

Anonymous

Anonymous Mon 24 Jan 2022 01:55:01 No.14141074 Report

Quoted By: >>14141089

>>14141051
>pq
what is this?

Anonymous

Anonymous Mon 24 Jan 2022 01:55:10 No.14141075 Report

Quoted By:

>>14141004
>>14141051
for example the 3 x 3 x 3 case gives 151206 cubes with no tic tac toes

Anonymous

Anonymous Mon 24 Jan 2022 02:01:18 No.14141089 Report

Quoted By:

>>14141074
Sorry, I mean pq to be two primes and 2pq to be two primes times two.

Anonymous

Anonymous Mon 24 Jan 2022 02:04:04 No.14141102 Report

Quoted By:

>>14130332
Looks like another application of binomial coefficients, the MOST POWERFUL of all mathematical theorems.

Anonymous

Anonymous Mon 24 Jan 2022 02:14:45 No.14141141 Report

Quoted By:

>>14141004
don’t worry about C or D or E orbits just S

Capcode	All Only User Posts Only Moderator Posts Only Admin Posts Only Developer Posts
Show Posts	All Only With Images Only Without Images
Deleted Posts	All Only Deleted Posts Only Non-Deleted Posts
Ghost Posts	All Only Ghost Posts Only Non-Ghost Posts
Post Type	All Only Sticky Threads Only Opening Posts Only Reply Posts
Results	All Grouped By Threads
Order	Latest Posts First Oldest Posts First

Your latest searches