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. ...

learn more… | top users | synonyms (4)

0
votes
1answer
32 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 ...
0
votes
0answers
57 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
23 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
52 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 ...
2
votes
2answers
55 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 ...
1
vote
3answers
47 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
30 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
3answers
221 views

Combinatorial optimization - Bijections between duplicated numbers

English is not my native language: sorry for my mistakes. Thank you in advance for your answers. Two Bijections and an Array... Here is a 2D array (in this particular example: rows: 1 to 4; ...
0
votes
0answers
20 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$ ...
3
votes
0answers
51 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
81 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
16 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
27 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
61 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
54 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
350 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
60 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
77 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
54 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
39 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
33 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
34 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
42 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, ...
4
votes
2answers
81 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
25 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
26 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
179 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 ...
6
votes
1answer
146 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
60 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
25 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
84 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
50 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
26 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
129 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 ...
0
votes
1answer
85 views

Advanced Counting Problem [closed]

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
18 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
27 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
47 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
54 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
38 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
42 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
122 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
88 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 ...
1
vote
1answer
54 views

Ratio of sum in black and white squares

For even positive integer $n$ we put all numbers $1,2,...,n^2$ into the squares of an $n\times n$ chessboard (each number appears once and only once). Let $S_1$ be the sum of the numbers put in the ...
5
votes
1answer
66 views

Drawing previously undrawn cards from a deck

Suppose you have a deck of $y$ cards. First, randomly select $y-x$ distinct cards and sign the face of each, then shuffle all the cards back in to the deck. Proceed as follows: Draw a card. If it is ...
6
votes
1answer
46 views

Sequences where each number is a divisor of one less than the next

Let $N,k$ be fixed. Call a sequence of positive integers $a_1,a_2,\dots,a_k$ good if for each $i$, $a_i$ is a divisor of $a_{i-1}-1$. Consider the set $$S = \{a_i : a_1,\dots,a_k \text{ is a good ...
2
votes
0answers
39 views

A symbolic formula for grid problem

I was reading the problem given in How many squares contains paint It looks like I don't understand how the hint given in an answer leads to the solution. Assume that corners of the board are $(0,0), ...