Permutations, combinations, bijective proofs, generating functions
1
vote
3answers
38 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 + ...
-5
votes
1answer
100 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
0answers
17 views
Grouping items into groups with max size
If I have $n$ items to distribute among $b$ 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 matter, and obviously $cb ...
-1
votes
1answer
62 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 ...
-2
votes
1answer
44 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$?
1
vote
2answers
36 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
46 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
0answers
33 views
Number of anagrams of the word “MONOCROMO” containing atleast one of the sequences “OMO”, “MON”, “CRO”
I need some help to verify that my way of doing this is correct (and also that the result is correct). In some cases i'm stuck and unsure of what to do. Please give me a hand.
The idea is to use the ...
0
votes
0answers
44 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, ...
4
votes
2answers
45 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 ...
0
votes
2answers
35 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 ...
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:- ...
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 ...
2
votes
0answers
38 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
36 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 ...
3
votes
0answers
26 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
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 ...
1
vote
1answer
38 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 ...
-1
votes
3answers
62 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 ...
5
votes
0answers
36 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 ...
1
vote
2answers
36 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 ...
0
votes
0answers
23 views
Enumerating the number of subsets of size i that sum to a specific value
Suppose we are given an integer $n$ and an integer $i$ where $i \le n$. We want to find all the subsets of {1, 2, 3 ... n-1} of size $i$ that will sum to $kn$ where $k$ is a positive integer.
Edit: ...
0
votes
1answer
16 views
Ordered set partitions
Let $a_n$ be a number of ordered partitions of the set $\left\{1,..,n\right\}$, which means that order of elements in block is not relevant, but order of blocks does matter. (so $a_n = ...
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 ...
1
vote
3answers
30 views
Combinations question - why is my approach wrong?
I'm learning Permutations and Combinations and while trying to solve this simple question, I stuck on the solution:-
From a group of 7 men and 6 women, five persons are to be selected to form a ...
1
vote
1answer
22 views
Permutations with exactly $k$ inversions
Let $I_{n,k}$ denotes the number of permutations of $\left\{1,..,n\right\}$ that have exactly $k$ inversions. Prove that:
$$\sum_k I_{n,k}x^k = \frac{\prod_{i=1}^n (1-x^i)}{(1-x)^n}$$
The only ...
4
votes
1answer
57 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
3answers
42 views
How many of these four digit numbers are odd/even?
For the following question:
How many four-digit numbers can you form with the digits $1,2,3,4,5,6$ and $7$ if no digit is repeated?
So, I did $P(7,4) = 840$ which is correct but then the ...
0
votes
0answers
35 views
Counting Permutations [duplicate]
I have 1 Permutation of $N$ numbers i.e. $1,2,\ldots,N$. I have another integer $M$ which lies in range $(N,2N)$ . I want to find no. of permutations of $1\ldots N$ where sum of two adjacent numbers ...
2
votes
1answer
33 views
Identity with an alternating binomial sum: $\sum\limits_{i=1}^n(-1)^i{n-i \choose n-k} {k \choose i} = {n-k\choose k}$
I'm learning for the test and:
Prove identity:
$$\sum_{i=1}^n(-1)^i{n-i \choose n-k} {k \choose i} = {n-k\choose k}$$
for all $n,k\in \mathbb{N}$.
This problem is just awful. I was trying to ...
6
votes
2answers
603 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*}
...
1
vote
1answer
39 views
Counting problem poker
I have never played poker in my life and i have to solve this complicated problem.
How many five card poker hands contain at least $3$ jacks?
Here is what i know:
There are $52$ cards in a deck. ...
3
votes
3answers
40 views
dimension of space of polynomials
Let $\mathcal P_k^n$ be the space of all polynomials of degree $\leq k$ in $n$ variables. Prove $\dim\mathcal P_k^n = {n+k\choose k}$.
I tried showing this by taking $n\in\mathbb N$ an arbitrary ...
-2
votes
4answers
50 views
Prove simple graph with conditions on vertices and edges contains triangle
Let $G$ be a simple graph with $2n$ vertices and more than $n^2$ edges. Then
prove that $G$ must contain a triangle.
Can you find a 'good' condition on the number of edges of
a graph with $3m$ ...
5
votes
1answer
39 views
Evaluating $\sum^n_{k=0}{n\choose{k}}{m\choose{k}}$ for fixed $m,n$
For evaluating $\sum^n_{k=0}{n\choose{k}}{m\choose{k}}$ for fixed $m,n$, I got ${n+m\choose{n}}$, does it look right?
I rewrite it as $\sum^n_{k=0}{n\choose{n-k}}{m\choose{k}}$, that's what I did.
5
votes
2answers
58 views
${n\choose1}+3{n\choose3}+5{n\choose5}+…$ in closed form
How can I evaluate ${n\choose1}+3{n\choose3}+5{n\choose5}+...$ in closed form?
Binomial theorem? Is that what I'm suppose to use? I'm not really understanding this.
2
votes
2answers
50 views
How many even number in a sequence are there?
How many even numbers in the below numbers ?
$$\binom{k}{0},\binom{k}{1},\binom{k}{2},\ldots,\binom{k}{k}$$
Worng: Is it true that all of them are odd iff $k$ is odd, and if $k$ is even then ...
2
votes
2answers
38 views
Distributing two distinct objects to identical boxes
Hiii,
I've been struck with a problem which deals with the distribution of two distinct objects such that p of one type and q of other type into three identical boxes.
As if it were only one object ...
0
votes
1answer
49 views
Interpreting vaguely written questions [closed]
There are stalls for 10 animals. In how many ways can the shipload be made, if there cows,calves and horses to be transported, animals of each kind being not less than 10?
Does this question even ...
2
votes
0answers
36 views
Checking an inductive proof on a combinatorial product
Consider the following product, for $n, k, i \in \Bbb Z_+, k \geq 2$:
$$
{\prod_{\ell = 1}^i {n + k - \ell \choose k } \over \prod_{\ell = 1}^{i-1} { k + \ell \choose k}} \tag{$*$}
$$
It has been my ...
3
votes
1answer
52 views
Closed formula for number of $n$ distinct topologies
While studying some topoligies I asked myself how many distinct topologies exist on a set of $n$ points. It can be shown there is a relation to $T_0$ topologies and a formula for $n$ distinct ...
0
votes
1answer
42 views
Upper bound for the number of primes in a series of n consecutive odd positive integers (all greater than 3)
Apart from 3, 5, 7, there cannot be three consecutive odd numbers which are all primes, as is well known. I wonder how this fact* can be used to calculate the upper bound in the title for any n.
*: ...
-3
votes
1answer
77 views
Number of solution for $xy +yz + zx = N$
Is there a way to find number of "different" solutions to the equation $xy +yz + zx = N$, given the value of $N$.
Note: $x,y,z$ can have only non-negative values.
3
votes
1answer
41 views
Fun combinatorics: How many numbers with some restrictions
I came accross this fun problem today: How many 8-digit numbers are there where:
each digit appears only one
digits 1-4 appear sequentially (though not necessarily consecutively)
5 does not appear ...
1
vote
0answers
29 views
A family of $8$-regular Ramanujan Cayley Graphs
I'm looking for expander graphs with certain properties.
Is there a family of $8$-regular Ramanujan Cayley graphs $\{\text{Cay}(G_n,S_n)\}_n$ such that each of them has no cycles of odd length?
...
0
votes
1answer
35 views
Number of rules in my fuzzy logic
I have 6 variables with 4 membership functions such as "tiny,small,large,huge".
I tried to write the rules and came up with 200 rules but the combinations are killing me and it is still incomplete.
...
1
vote
2answers
53 views
What is the smallest alphanumeric string that has 10 million permutations?
I'm aiming to create UUIDs, for a project I'm working on.
The standard UUID generators create a very long strings. I'm only anticipating a maximum of 10 million uses and because I'm storing that many ...
6
votes
1answer
35 views
Probability of adjacent seating
A homework question states:
A room holds two rows of six seats each. Two friends are assigned
randomly to the 12 seats. What is the probability that the 2 friends
sit in adjacent seats?
...
2
votes
1answer
61 views
Recursive equation for palindromes
Can someone help me determine the recursive equation for all binary strings that are palindromes? A binary string is a palindrome if it reads the same forward and backward. Examples of palindromes are ...
