Permutations, combinations, bijective proofs, generating functions
1
vote
0answers
21 views
Scaling a regenerated square pattern in $\mathbb{R}^2$
We have the first quadrant of $\mathbb{R}^2$, i.e. $\{(a,b):a>0\land b>0\}$ and we have a special arrangement of squares as shown. We scale everything by $\dfrac{1}{3}$ and obtain the ...
0
votes
0answers
22 views
Selecting items to satisfy multiple constraints
I have a problem that goes like this:
I need to pick X items from my list of available items. Each item has Y attributes, which are just integers. The distribution of the attributes between items is ...
2
votes
1answer
20 views
Is there a tree where the number of vertices with degree less than 3 is greater than the diameter?
Let $T$ be an undirected tree, let $d$ be the diameter of $T$, and let $s$ be the number of vertices in $T$ with degree less than 3. Recall the diameter of a graph is the length of the longest ...
2
votes
1answer
53 views
How to determine the no. of integral partitions into $k$ parts?
I wanted to know, if I was to partition $500$ into positive $k$ integers, not necessarily distinct under the following constraints
1.k is +ve.
2.all k parts need not be distinct.
3.the first ...
0
votes
1answer
47 views
Sum of N numbers whose sum is M
In how many ways can we sum N nonnegative numbers (that is, taking values 1, 2, 3...) such that their sum is M? I found this problem doing convolution of series and combinatorics has never been my ...
-3
votes
1answer
90 views
Prove that $\mathbb C\setminus \mathbb R$ is not countable [closed]
I managed to prove that $\mathbb C$ and $\mathbb R\setminus \mathbb N$ are not countable now I'm left with this last one.
In other words I'm willing to show that $\mathbb C\setminus \mathbb R \sim ...
2
votes
6answers
125 views
Probability problem
I have $3$ coins, $1$ coin has $2$ heads (HH), 1 coin has $2$ tails (TT), $1$ coin has $1$ head and $1$ tail (HT). I toss the coin, it fells on my hand, and the side i see is a tail. What's the chance ...
1
vote
1answer
37 views
Number of solutions for $\sum_{i=1}^{4} x_i < 22$ with condition.
I'm looking for the number of solutions to $\displaystyle\sum_{i=1}^{4} x_i < 22$ where $x_i > i$
Any help is appreciated.
I tried solving it using combinations to do $C(11,4)$ but that ...
0
votes
1answer
22 views
Anagrams with sequences inside
I need some help with this exercise:
Find the number of anagrams of the word “MONOCROMO” containing atleast one of the sequences “OMO”, “MON”, “CRO”.
Normally I know what to do, but in this one ...
2
votes
1answer
39 views
Find the natural number $n$ satisfy the condition
Find the natural number $n$ satisfy the condition
$$\dfrac{1}{2}C_{2n}^1 - \dfrac{2}{3} C_{2n}^2 + \dfrac{3}{4} C_{2n}^3 - \dfrac{4}{5} C_{2n}^4 + \cdots - \dfrac{2n}{2n+1} C_{2n}^{2n} ...
0
votes
1answer
18 views
After subdividing a painted cube, how many smaller cubes have paint on exactly 2 sides?
A solid cube of side 6 is first painted pink and then cut into smaller cubes of side 2. How many of the smaller cubes have paint on exactly 2 sides?
Answer with illustrations will be helpful for ...
11
votes
0answers
55 views
Minesweeper - Chance of one-click win
I'd like to know if it's possible to calculate the odds of winning a game of Minesweeper (on easy difficulty) in a single click. This page documents a bug that occurs if you do so, and they calculate ...
1
vote
1answer
30 views
Counting probability question-what is the sample space in this problem?
Hi folks this is a self learn probability (counting) question from DeGroot. The question is:
Suppose that a box contains r red balls and w white balls. Suppose also that the balls are drawn out ...
3
votes
3answers
18 views
Constrained ( Variable Length ) Permutation Calculation.
I am writing some tracking software, but I think this is pretty purely a math question. I don't need to know the math to accomplish this with my code, but I like math and I want to learn! Thus ...
0
votes
3answers
43 views
Probability, combinations with repetition
A store sells n different kinds of fruits. A boy buys k fruits. Find the probability that he buys all the kinds of fruits.
Give me a hint, please.
Thank you.
2
votes
1answer
41 views
Grouping items into groups with max size
If I have up to $n$ non distinct items to distribute among $b$ distinct buckets that can hold up to $c$ items each, how can I find how many different states there can be? The ordering of items doesn't ...
8
votes
2answers
204 views
Techniques for summing ratio of binomial coefficients
There are several identities that involve the sum of the product of binomial coefficients. However what I am searching for is an identity that involves the ratio of binomial coefficients. ...
21
votes
6answers
7k views
How many triangles
I saw this riddle today, it asks how many triangles are in this picture
.
I don't know how to solve this (without counting directly), though I guess it has something to do with some recurrence.
...
4
votes
1answer
383 views
Card Shuffling [SPOJ]
The original question is posted on SPOJ, and included below:
Here is an algorithm for shuffling N cards:
1) The cards are divided into K equal piles, where K is a factor of N.
2) The ...
5
votes
2answers
265 views
Elementary bound of binomial coefficient
I'm working my way through an Erdős paper from the sixties and some of the elementary bounds he claims seem to be just beyond my reach. The expression looks horrendous but maybe there is a clever ...
1
vote
0answers
27 views
Partition Proof
Let $\lambda$ be a partition of $N$ of rank $r$. How can I show that:
$$\sum_wx^\lambda(w)=f^\lambda(-1)^{t(\lambda)}\prod^r_{i=1}(\lambda_i-1)!(\lambda'_i-1)!$$
where $w$ ranges over all ...
5
votes
3answers
125 views
Compositions of $n$ with largest part at most $m$
This is a problem from Stanley's Enumerative Combinatorics that I'm failing at a bit (lot):
Let $\bar{c}(m,n)$ denote the number of compositions of $n$ with largest part at most $m$. Show that ...
-6
votes
1answer
118 views
How to explain that $\{(1,3),(2,4)\} = \{1,3,2,4\}$ [closed]
How to explain that $\{(1,3),(2,4)\} =\{1,3,2,4\}?$
Same goes to this question. How to explain that $\{(1,2),(3,4)\} = \{1,2,3,4\}?$
I did tried by using the product of transposition, but it didn't ...
1
vote
3answers
45 views
How many different numbers are composed by n repeated digits?
For example, there are 3 digits: 1, 1, 4 and they compose 3 different numbers: 114, 141, 411.
My questions is: given n repeated digits: 1 * n1, 2 * n2, 3 * n3, ..., 9 * n9, in which ni >= 0 and n1 + ...
4
votes
2answers
566 views
Factorial division using Pascal's triangle.
I want to get values of factorial divisions such as 100!/(2!5!60!)(the numbers in the denominator will all be smaller than the numerator, and the sum of the ...
1
vote
1answer
83 views
Given n girls and boys how many ways are there to arrange them such that any two boys have atleast 'k' girls between them.
Professor X wants to position $1 \leq N \leq 100,000$ girls and boys in a single row to present at the annual fair.
Professor has observed that the boys have been quite pugnacious lately; if two ...
0
votes
1answer
70 views
What is combinatorics? How is it related to Ramsey theory? What is the background needed to study it? [closed]
What is combinatorics? How is it related to Ramsey theory? What is the background needed to study it?
When I was reading about Ramsey theory in some reviews on some books, many people mentioned this ...
0
votes
2answers
39 views
From a deck of 52 cards, the face cards and four 10's are removed. From these 16 cards four are choosen.
From a deck of 52 cards, the face cards and four 10's are removed. From these 16 cards four are chosen. How many possible combinations are possible that have at least 2 red cards?
My solution I'm ...
-2
votes
1answer
46 views
Discrete Math Satisfying functions with sets [closed]
Let $A = \{1, 2, 3,\ldots, 10\},$ and $ B = \{1, 2, 3, \ldots , 7\}.$
How many functions $f : A\to B$ satisfy $|f(A)| = 4?$ How many have $|f (A)| \le 4$?
6
votes
2answers
655 views
Minimizing Appreciating Quantities vs. Maximizing Depreciating Quantities
Suppose you have a set $S = \{r_1, ..., r_n :\, r_k \in (1, \infty)\, \forall \,k \in \{1,...,n\}\}$. Find a bijective mapping $f: \{0,...,n-1\}\rightarrow \{1,...,n\}$ that minimizes
\begin{align*}
...
6
votes
2answers
195 views
What is the number of ways to choose x groups from y items? (partitions with x cells of a multiset)
Where a group can consist of 1 or more items, groups don't have to be equally sized and items can be duplicates. Example - Choose 3 groups:
Items: 1 2 2 3
Groups:
(1) (2 2) (3)
(1 2) (2) (3)
(3 ...
1
vote
2answers
41 views
How many divsors of $4725$ are there?
I need to solve the following problem:
How many divsors of $4725$ are there?
I found the number of divsors between $0-9$ that can divide $4725$ which are: $3,5,7,9$ but how do I find the ...
2
votes
1answer
50 views
In how many ways can you rearrange CANADA?
I'm trying to solve the following question which is in the permutations unit:
In how many ways can all the letters of the word CANADA be arranged if the consonants must always be in the order in ...
0
votes
2answers
27 views
Probability of selecting q red balls from m red balls and n blue balls
Suppose there are $m$ red balls and $n$ blue balls in an urn. We randomly choose $p:m<p<n$ balls uniformly from the urn. What is the probability that exactly $q$ red balls are chosen?
Note:- ...
0
votes
0answers
45 views
Combinations may be tough to compute [closed]
Kindly observe the known statement given below.
"The traveling salesman problem, or TSP for short, is this: given a finite number of 'cities' along with the cost of travel between each pair of them, ...
-1
votes
3answers
66 views
How many ways can $5$ rings be placed on $4$ fingers?
I've been trying to solve this problem and I am kind of struggling with it and with other combinatorics problems. Could you check and see if i did it right?
Given problem:
How many ways can 5 ...
13
votes
1answer
150 views
Closed form for $\sum_{n=1}^\infty\frac{\psi(n+\frac{5}{4})}{(1+2n)(1+4n)^2}$
This question came up in the process of finding solution to another problem. Eventually, the problem was solved avoiding calculation of this sum, but it looks quite interesting on its own. Is there a ...
4
votes
2answers
50 views
Products in a Set
Let:
$$S := \{1,2,3,\dots,1337\}$$
and let $n$ be the smallest positive integer such that the product of any $n$ distinct elements in $S$ is divisible by $1337$. What are the last three digits of ...
3
votes
1answer
33 views
Groupings for N items
For $n = 3$, there's 1 group of 3 or 3 groups of 1, or a group of 2 and a group of 1, for a total of 3 different "groupings".
for $n = 2$, there's 2 "groupings": 1 group of 2 or 2 groups of 1
I had ...
1
vote
1answer
42 views
Permutations without any cycle of length $k$
Let $k\in\mathbb{N}$ be a fixed natural number and $f_k(n)$ denotes the number of all permutations of $\left\{1,..,n\right\}$ that does not contain any cycle of length $k$. Find as simple as ...
2
votes
0answers
41 views
Facing mostly-faced decks
In my day job, I am often called upon to take a large stack of—let's call them cards—and make sure that a large majority of them are facing in a particular direction. In most cases, there ...
1
vote
0answers
38 views
Finding a generating function of a series
So say if you have a sequence defined as, for $a\in\mathbb{Z}$,
$$ c_n = \binom{a}{0} \binom{a}{n} - \binom{a}{1} \binom{a}{n-1} + \cdots+ (-1)^n \binom{a}{n} \binom{a}{0} = \sum_{i=0}^n (-1)^i ...
4
votes
0answers
28 views
Dimension of the space of algebraic Riemann curvature tensors
Given $n\in \mathbb N$, consider the vector space $\mathbb R^{n^4}$ whose elements I will denote by $(R_{abcd})$ with indices $a,b,c,d \in \{1, \dots, n\}$. This vector space is $n^4$-dimensional. The ...
1
vote
1answer
41 views
combinatorics - Distribution of Distinct Balls into Distinct Boxes
As we all know, the number of ways in which k balls can be distributed into n boxes
where each box can contain at most 1 ball is $^nP_k$.
The value is $\; ^nP_k \;$ only when $\;k\le n\;$ right?
The ...
4
votes
1answer
60 views
Evaluate complicated sum
Evaluate following sum:
$$\sum_{1\leqslant i< j \leqslant m}\sum_{\substack{1\leqslant k,l \leqslant n\\ k+l\leqslant n}} {n \choose k}{n-k \choose l}(j-i-1)^{n-k-l}.$$
Hint: use combinatorial ...
1
vote
0answers
57 views
counting more problem continue [duplicate]
i have asked but no one was able to help so i am re-posting, hoping someone can help me. i did the computation and i could be wrong but i have provided my answer.
Given problem:
How many ways can 5 ...
10
votes
3answers
159 views
Integer sequences which quickly become unimaginably large, then shrink down to “normal” size again?
There are a number of integer sequences which are known to have a few "ordinary" size values, and then to suddenly grow at unbelievably fast rates. The TREE sequence is one of these sequences, which ...
1
vote
2answers
38 views
Number of sequences with n digits, even number of 1's
ASKED:
Let $c_n$ be the number of sequences with $n$ digits from $\{1,2,3,4\} $ with an even number of $1's$.
Determine $c_n$ for $n \geq 0$.
GIVEN RESULT:
$c_{n+1} = 3 \cdot c_n + 1 \cdot ...
5
votes
0answers
39 views
Generating function with Stirling's numbers of the second kind
It's very easy to prove that:
$$\sum_k \left\{k\atop n\right\}z^k=\frac{z^n}{(1-z)(1-2z)...(1-nz)}$$
But this generating function looks very pretty, so my question is: does this identity have some ...
3
votes
1answer
34 views
choosing $5$ non consecutive books from a shelve of $12$
In how many ways can you pick five books from a shelve with twelve books, such that no two books you pick are consecutive?
This is a problem that I have encountered in several different forms ...
