Tagged Questions
This tag is for basic questions about the study of finite or countable discrete structures — specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions. ...
0
votes
1answer
22 views
Inclusion-Exclusion Principle for basic combinatorics problem…
How many ways are there to pick five people for a committee if there are six
(different) men and eight (different) women and the selection must include at
least one man and one woman?
I know ...
1
vote
0answers
17 views
Number of queries required to find the function.
this is a slight variation to question $3$ of the Nordic mathematical olympiad of 2010.(in short that one deals with bijections and this one deals with any kind of function).
In this variation we ...
0
votes
3answers
40 views
SAT Math probability and repeats
A ball's area is divided into two sections. If each section is to be painted using one of 5 different colors, how many differently painted designs are possible?
I know that the first area has 5 ...
0
votes
0answers
23 views
Distance Transitive Graph Property
Asked this over in math overflow and have refined the question a bit.
I'm working on trying to show this, but can't seem to get a proof methodology worked out. No guarantees that it is true, but ...
-1
votes
0answers
41 views
2 player team knowing maximum moves
Given a list of N players who are to play a game. Each of them are either well versed in a move or they are not. Find out the maximum number of moves a 2-player team can know.
And also find out how ...
0
votes
1answer
21 views
Number of particular terms in a product
I hope this question is not too stupid, but I know very little about combinatorics and i can't find an answer..
So fix $r\in \mathbb{N}$. Let $x_1,\ldots, x_r$ be variables, let the product between ...
1
vote
1answer
34 views
52-card deck probability…
If 13 players are each dealt four cards from a 52-card deck, what is the probability
that each player gets one card of each suit?
So I chose to do the situation where we have no repetition (i.e ...
1
vote
0answers
27 views
Equivalent definitions for a coloop?
From wikipedia, in a matroid,
An element that belongs to no circuit is called a coloop. Equivalently, an element is a coloop if it belongs to every basis.
I wonder why the equivalence?
From ...
0
votes
1answer
12 views
Missing Numbers in Roulette, Dice, and Other Gambling Devices
Case 1: I roll a die N times. What is the probability that one of the 6 numbers never comes up? The probability that K of the 6 numbers never comes up?
Case 2: Same idea, but with a Las Vegas ...
0
votes
1answer
23 views
Counting of the elements in a set
I have an algorithm returning a set of groups from a time series. Be $X$ this time series, made of $n$ points $x_1$ to $x_n$.
My algorithm returns from the time series a set of groups G, containig ...
2
votes
2answers
114 views
Combinatorial optimization - Bijections between duplicated numbers
English is not my native language: sorry for my mistakes. Thank you in advance for your answers.
I have originally posted this problem on Stackoverflow. Thanks to some people, I have been able to see ...
0
votes
0answers
15 views
Finding integer vectors in the column space of a matrix
Consider a given set $S \subset Z$. $S$ is a finite set. Matrix $A \in S^{N \times M}$ is also given.
Does there exist an algorithm to find all the vectors belonging to the space Col$(A)\cap S^N$
...
0
votes
0answers
27 views
Are Hadamard matrices related with quick response codes (Qr Codes)? [on hold]
Reed Solomon Codes have any conections with hamard codes?
2
votes
0answers
35 views
number of Lattice paths from origin to diagonal after removing vertices
i am stuck with the following problem:
consider the quarter plane $\mathbb{N}_0^2$ with vertices $(i,j)\in\mathbb{N}_0^d$ and edges from each vertex $(i,j)$ to $(i+1,j)$ and $(i,j+1)$, i.e. one ...
0
votes
2answers
55 views
Advanced Counting Puzzle
Suppose we have a house in which every room has an even number of doors. Prove that the number of doors from the house to the outside world is also even.
0
votes
1answer
14 views
How do the dependent sets of a matroid characterize the matroid?
Wikipedia says:
The dependent sets of a matroid characterize the matroid completely. The collection of dependent sets has simple properties that may be taken as axioms for a matroid.
So I ...
1
vote
0answers
26 views
Name for variations of elements from several sets
Consider the set $S=\{1,2,3\}$. As is well known,
$(1,1), (1,2), (1,3), (2,1), (2,3), \ldots, (3,3)$
are the variations with repetition of elements of $S$ taken two at a time. We can similarly ...
1
vote
1answer
45 views
Divide and Conquer (recurrence relation problem)…
The problem:
(a) Use a divide-and-conquer approach to devise a procedure to find the largest
and next-to-largest numbers in a set of n distinct integers.
(b) Give a recurrence relation for ...
3
votes
0answers
50 views
A function on sets which is constant for all permutations
Let $U=\{1, 2,\ldots, 2014\}$. For positive integers $a$, $b$, $c$ we denote by $f(a, b, c)$ the number of ordered 6-tuples of sets $(X_1,X_2,X_3,Y_1,Y_2,Y_3)$ satisfying the following conditions:
...
0
votes
2answers
327 views
Finding Coprime triplets
Given a sequence a1, a2, ..., aN. Count the number of triples (i, j, k) such that 1 ≤ i < j < k ≤ N and GCD(ai, aj, ak) = 1. Here GCD stands for the Greatest Common Divisor.
Example : Let N=4 ...
3
votes
1answer
57 views
How many orientations are there for pawns (for a single player) on a chess board?
How many orientations are there for pawns on a chess board?
Pawns can only move forward or diagonally forward.
No two pawns may exist on the same square.
Pawns start on the second row, and ...
5
votes
1answer
70 views
Binomial Congruence
How can we show that $\dbinom{pm}{pn}\equiv\dbinom{m}{n}\pmod {p^3}$ for positive integers m and n and p a prime greater than 5? I can do it for mod p^2 but Im stuck here.
4
votes
1answer
51 views
Rearrange columns and rows of a matrix such that it can be split in half
I am not a mathematician, so please excuse me if this question turns out to be trivial. I need this at work, but I could not figure out how to solve this efficiently, though it looks like it might be ...
0
votes
1answer
37 views
Straight in 52cards+2Joker
I have 52card (ace to king) + 2Joker
I'm supposed to compute how much straights of 5 cards I can make, excluding the straight flushes (straights with all cards being the same color)
My reasoning is : ...
0
votes
1answer
25 views
Game of coins with two players
Two Players play a game as follow : Given total N coins where x coins are of red color and y coins of blue color.
Now Player1 selects a coin from the heap of coin and put it in a line on table. Then, ...
0
votes
1answer
31 views
Simple Combinations
Question: Class consists of $7$ men and $5$ women. Find number of committees of five that can be selected from the class if the committee is to consists of at least one man and at least one woman.
My ...
3
votes
1answer
34 views
A bijection defined on the set of configuration of lamps
Consider $n$ lamps clockwise numbered from $1$ to $n$ on a circle.
Let $\xi$ to be a configuration where $0 \le \ell \le n$ random lamps are turned on. A cool procedure consists in perform, ...
3
votes
1answer
45 views
Combinatorics: Mean and Variance of an indicator function of items arranged in a circle.
I have a problem from a homework which I've been struggling with.
I normally wouldn't post homework here, but I've spent several hours trying to understand the correct way to solve this , to no avail.
...
0
votes
1answer
23 views
Möbius function for posets and primes
Let the Möbius function $\mu_P : P \times P \rightarrow \mathbb{Z}$ for a poset $P$ be defined as $$\mu_P(x,y) = \begin{cases} 0 & x \not\leq y \\ 1 & x = y \\ - \sum\limits_{x \leq z < ...
0
votes
1answer
22 views
Distinguishing between two sets of tournament partition
A "tournament" is a complete graph such that each edge is directed one way or the other (but not both). Does there exist a tournament of size $2n$ such that we can partition it into two sets $A,B$, ...
0
votes
1answer
21 views
Simple Permutations/Combinations Question
A group of 5 men and 5 women stand in line to have their photo taken.
How many ways can they stand in line if no two men and no two women stand together?
My method: _M_M_M_M_M_
Male * Female = 5P5 ...
5
votes
6answers
168 views
The physical meaning of ${n \choose k} = {n \choose n-k}$.
They say that $${n \choose k}={n \choose n-k}.$$
Can someone explain its physical meaning?
Among many problems that use this proof, here is an example:
The english alphabet has $26$ letters ...
5
votes
1answer
128 views
Looking for different proofs of “Discrete Liouville's Theorem”.
Good day.
There is a question I have already encountered twice, in very different contexts, that is relatively simple looking, but both solutions I know involve some pretty advanced theorems from the ...
2
votes
2answers
58 views
Counting problem: selecting $n$ objects among $k$ infinite collections.
Here's a counting question that got me thinking. Unfortunately, I couldn't get around it. Need help.
You are given $k$ distinct coloured boxes. In each box, lies infinite balls of the same colour as ...
1
vote
1answer
23 views
What kind of set system is defined to have this property?
Let $E$ be a set, and $F \in \mathcal P(E)$ has the following property:
For every $x\in E$ and $Y,Z\in F$ with $x\notin Y\cup Z$, there exists $X\in F$ with $(Y\cap Z)\cup\{x\}\subseteq X$.
I wonder ...
1
vote
2answers
59 views
points with integer coordinates inside triangles in $\Bbb{R}^3$
I'm taking off from Number of lattice points inside a triangle and its area
Consider a triangle in $\Bbb{R}^3$ whose vertices have integer coordinates. What's the fastest way of counting how many ...
0
votes
0answers
49 views
How to establish this result using induction?
A point $(x,y)$ in the plane is called a lattice point if both coordinates $x$ and $y$ are integers.
Let $P$ be a polygon whose vertices are lattice points. Then the area of $P$ is $I + \frac{1}{2}B ...
0
votes
1answer
22 views
How to calculate the number of points in the interior and on the boundary of these figures with vertices as lattice points?
We define a point $(x,y)$ in the plane to be a lattice point if both $x$ and $y$ are integers.
Now let $$S\colon= \{ (x,y) \ | \ 0 \leq x \leq m, \ 0 \leq y \leq \frac{nx}{m} \}, $$ where $m$ and ...
8
votes
1answer
110 views
Tricky (extremal?) combinatorics problem
Apologies for being unsure the best way to express this problem.
I have 9 tables with 4 students at each table. I want to re-seat all students so no two students who have sat together ever sit ...
1
vote
1answer
71 views
Advanced Counting Problem [on hold]
1) How many positive integers are there whose digits strictly increase from left to right?
(For example, 28, 13589, and 4 are all such integers. "Strictly" means no two digits can be equal, so 15668 ...
0
votes
0answers
15 views
$k$ edge-disjoint $r$-arborescences in an acylic digraph
An $r$-arborescence of a digraph $D$ is a rooted spanning tree with root $r\in V(D)$ in which all the edges of $D$ are directed away from $r$.
I would like to prove the following:
I have thought ...
1
vote
0answers
23 views
Meaning of proper antichain
I saw this sequence on the Online Encyclopedia of Integer Sequences, which describe the number of 3-element proper antichains of an n-element set.
What does it mean to be a 3-element proper antichain ...
1
vote
4answers
46 views
Possible arrangements of marbles in bags?
I've come across a question on a math test asking, "How many different ways can you put a dozen identical marbles into six bags so that each bag has atleat one marble in it?". I would imagine that ...
0
votes
1answer
18 views
Permtutation and combination word problem
In the below solved problem, every thing is okay, but if we have $4$ consonants then why we are giving $5!$? and is this a combination problem? how to distinguish?
Question:
In how many different ...
7
votes
1answer
51 views
Is it possible to partition $\mathbb{N}_+$ into a *finite* family of sets completely not closed under $+$?
Let's say that $A \subseteq \mathbb{N}_+$ is completely not closed under $+$ if
$$
\forall_{a,b \in A}[{a+b \notin A}]
$$
Is it possible to partition $\mathbb{N}_+$ into a finite family of sets ...
2
votes
0answers
37 views
solving recurrence relations for functions with more than one variable
Is there a way to find formula for a function on more than one variable which is given by recurrence relation with some initial conditions?
e.g.if one knows the value of f(n,p,l) for all p,l where ...
0
votes
0answers
38 views
Combination Problem on Create Groups !!!
I'm getting stuck on this combination problem I ran into on a previous final exam:
How many ways can 3 different Scientific Groups be formed using 5 students such that
each student is at ...
6
votes
4answers
116 views
The number of permutations of $\{1,2,\ldots,n\}$ that have exactly one ascent (rise).
Sloane's OEIS A000295 counts the number of $n$-permutations with exactly one ascent. For example $a(3)=4$ because we have: $1\wedge32$, $21\wedge3$, $2\wedge31$, $31\wedge2$ where I have marked the ...
2
votes
2answers
1k views
A general form for a function of parameters which reduces to Harmonic number when all parameters are =
Looking for the general form $f_n$ a solution for an integral with $n$ strictly positive parameters $\beta_i$, $\beta_1,\beta_2,\ldots, \beta_n$ .
The integral is as follows $$ f_n=\int_0^\infty ...
5
votes
2answers
84 views
How to Count the number of words over an alphabet subject to restrictions on letter count?
For an alphabet $X$, is there a method of computing how many words over $X$ of length $n$ there are where the number of occurrences of each letter must satisfy a system of equations?
For example if ...
