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)

1
vote
1answer
62 views

Odd town Even town explanation.

I am struggling to understand the solution to the following problem: If $\mathcal F\subset 2^{[n]}$ such that for each $F_1$ and $F_2$ in $\mathcal F$ we have $|F_1|,|F_2|\equiv 1 \bmod 2$ and ...
1
vote
2answers
58 views

number of combinations of selecting 1 element each from 3 sets..

Suppose we have 3 sets A=(a1,a2,...) B=(b1,b2,....) and C=(c1,c2,...) which may contain comman elements that is element present in set A may present in set B or in Set C,element in set B may be there ...
2
votes
1answer
52 views

Question regarding combinatorics of resistance network. [closed]

If you have $N$ $1$Ohm resistors, how many distinct equivalent resistances can you create? Assume that only parallel and series and mixture of them is allowed and no bridging between two parallel ...
2
votes
0answers
39 views

Partitions of $\mathbb{R}^+$ into subset closed by sum and product

Suppose we can partition $\mathbb{R}$ into two subset $A,B$, both non empty and closed by sum and product. Let $0\in A$, and suppose that exists $b\in B$. Then $b^2\in B$. Now, $-b\in B$, cause if ...
3
votes
6answers
128 views

How many $3$ digit numbers with digits $a$,$b$ and $c$ have $a=b+c$

My question is simple to state but (seemingly) hard to answer. How many $3$ digit numbers exist such that $1$ digit is the sum of the other $2$. I have no idea how to calculate this number, but I hope ...
0
votes
2answers
38 views

How many odd numbers are there with one or more even digits within a range?

Imagine you have a range [A,B], how could I know how many odd numbers with even digits are there in the range? Can't figure it out.
0
votes
0answers
62 views

Choosing distinct elements from 5 sets

Given $5$ sets of each of them having $n_1, n_2, n_3 \dots n_5$ number of elements (all elements are integers from $1$ to $k$). What are the number of ways of choosing one element from each set such ...
4
votes
4answers
69 views

Conjecture for product of binomial coefficient

Is it true that for any $n, k\in\mathbb N$ $$\frac{(kn)!}{k!(n!)^k} = \prod_{l=1}^k {{ln-1}\choose{n-1}} \quad?$$ I tested it for some small $k$ and $n$, but I don't know how to prove that it is true ...
0
votes
3answers
100 views

Given the sequence $3, 4, 11, 16, 42\ldots $ how can I derive a general formula for it?

Given a sequence $3, 4, 11, 16, 42\ldots $ how can I derive a general formula for this sequence? Is there any optimised approach? My approach: the given series is equal to summation of $\binom{n}{k}$ ...
3
votes
4answers
327 views

A consequence of Wilson's Theorem

By Wilson's Theorem we know that $$(p-1)! \equiv -1 \mod p.$$ A consequence of this is apparently $$(p-(k+1))!k! \equiv (-1)^{k+1} \mod p$$ where $0 \leq k \leq p-1$. I was told to think of it like ...
0
votes
4answers
30 views

In how many ways can we arrange $n$ A's and $n-1$ B's into $2n-1$ slots?

There are $2n-1$ slots/boxes in all and two objects say A and B; total number of A's are $n$ and total number of B's are $n-1$. (All A's are identical and all B's are identical.) In how many ways ...
0
votes
0answers
13 views

Slots Machine Matching feature 2

I'm designing a slot machine. I need to find the number of combinations that two matching icons will appear side-by-side in a 3X5 window (3 rows, 5 reels (columns)) A match gives the user some ...
1
vote
0answers
75 views

Simplex Notation

Let $\left(V,T\right)$ denote an affine space and let $v_0, \dots v_n$ denote some affine independent points of $V$. A $m$-simplex $s$ with vertices $v_0, \dots v_m$ can be represented by ...
-4
votes
2answers
59 views

Number of squares on a rectangular board that are neither in the 4th row nor in the 7th column

A rectangular game board is composed of identical squares arranged in a rectangular array of $r$ rows and $r+1$ columns. The $r$ rows are numbered from $1$ through $r$, and the $r+1$ columns are ...
-6
votes
0answers
107 views

Solve fibonacci equation

Given two numbers M and N we need to solve : ( ∑ ( 6 * x * y * z * Fibo[x] * Fibo[y] * Fibo[z] ) ) % M , where x + y + z = N. Here x, y, z ≥ 0 and are integers. ...
3
votes
1answer
81 views

How to prove a duality about partitions of numbers?

I found the following theorem, which I think should be correct but I do not know how to prove it: Consider the set containing sums $A=\lbrace\sum\limits_{i=-a}^a iX_i\rbrace$ where $X_i$ is a ...
0
votes
1answer
36 views

2D boolean matrix number of unique combinations without mirrored/rotated ones

Given a $n \times n$ boolean matrix, it's well known that number of all possible combinations of 0s and 1s in that matrix would be $2^{n^2}$, as there are $n^2$ places which could take exactly 2 ...
-1
votes
0answers
50 views

Counting distinct nonempty sequences

Given N and an array of length N i need to count nonempty sequence (p[1], p[1]+1), (p[2], p[2]+1), ..., (p[s], p[s]+1), where p[k]+1 ≤ p[k+1] for k = 1, 2, ..., s − 1. Here p[i] is the point number i ...
0
votes
0answers
19 views

Number of Strongly Connected Components and Property Testing.

I am working on a problem about the strong connectivity of digraphs. Given graph $\vec G$ that is $k$-$\textit far$ away from being strongly connected (i.e, the minimum number of edges that need to be ...
1
vote
1answer
45 views

Permutations through different points

I'm watching Next (2007) and I'm trying to figure out a formula. The premise of the movie is that the protagonist can look into the future for two minutes and he is able to use this to alter his ...
4
votes
1answer
35 views

Is the number of associative $n$-ary algebraic operations on a finite set with 2 cardinality always 8?

We know that if $n = 2$ then the operation is called a binary operation. $ \circ $ on set $X$ is a function $\circ : X \times X \rightarrow X$. And the number of all associative binary operation on a ...
6
votes
4answers
181 views

Truncated alternating binomial sum

It is easily checked that $ \sum_{i = 0}^n (-1)^i \binom{n}{i} = 0$, for example by appealing to the binomial theorem. I'm trying to figure out what happens with the truncated sum $\sum_{i=0}^{D} ...
-1
votes
0answers
48 views

Combinatorics and product rule

Given arrays $A_1, A_2, A_3, ... A_n$. Each array has distinct integers. $A_1 \times A_2 \times .... \times A_n$ is the set of $n$-tuples. How many $n$-tuples have distinct entries? What is the ...
1
vote
0answers
21 views

“Spanning” the difference set of $S$

Suppose that $S$ is a finite set of natural numbers, and $\{(x_i, y_i)\}$ is a set of tuples of numbers in $S$ with $$ \{x_i - y_i\} = S - S := \{a - b \mid a, b \in S\} $$ that is, $\{(x_i, y_i)\}$ ...
4
votes
3answers
152 views

Biggest subset of $\{1, 2 … 1000\}$ such that difference between any pair of elements $\neq 4, 7$

The problem, as stated in the title, is to find the maximal size of a subset $V$ of $S = \{1, 2, ... 1000 \}$ such that no two elements of $V$ have a difference of 4 or 7 between them, i.e. $x \in V ...
0
votes
1answer
57 views

Number theoretical Application of the Pigeonhole Principle

I'm currently working through a paper related to my bachelors thesis and I'm stuck at a point where the author mentions the following result as "a standard application of the pigeonhole principle". ...
2
votes
0answers
33 views

How to load warehouse pallets efficiently?

Assume that we would wan't to develop a warehouse management system, which picks up plastick boxes and stacks them on a pallet. A pallet has a maximum of 5 vertical box stacks and the maximum height ...
3
votes
1answer
59 views

Extended Calendar Cube Question

The calendar cube puzzle is famous: using two six-sided cubes, label them such that any day of any month can be represented by positioning the cubes accordingly. The solution involves allowing the ...
2
votes
1answer
44 views

Behavior of Pascal's triangle in $n\mod m$ where $m>2$, any fractals?

If Sierpinski Triangles are found in Pascal's Triangle under modulo 2 what happens when we view Pascal's Triangle under modulo $m$ where $m>2$? Do fractals appear and if so for which numbers? ...
1
vote
4answers
45 views

Subsets of divisors

How many subsets of the set of divisors of $72$ (including the empty set) contain only composite numbers? For example, $\{8,9\}$ and $\{4,8,12\}$ are two such sets. I know $72$ is $2^3\cdot 3^2$, so ...
1
vote
1answer
51 views

How to compute the expected number of unwatched rooms?

Imagine that I have a number of rooms, r, that I want to have watched. So I install one video camera in each room and have televisions that can show what's going ...
2
votes
1answer
93 views

Combinatorics problem about listing numbers $1,2,…n$

In how many ways can the numbers $1,2,...,n$ be arranged as $a_1,a_2,...,a_n$ so that for each $i > 1$ there is a $j < i$ such that $a_j = a_i \pm 1$? For example, ...
0
votes
0answers
29 views

Slots Machine Matching feature

I'm designing a slot machine. I need to find the number of combinations that two matching icons will appear side-by-side in a $3\times 5$ window ($3$ rows, $5$ reels (columns)) A match gives the ...
3
votes
5answers
1k views

Probability of guessing a PIN-code

A friend and I recently talked about this problem: Say my friend feels a little adventurous and tells me that exactly three of four digits of his PIN-code are the same, what is the probability that I ...
1
vote
0answers
40 views

A variation of the menage problem

A combinatorics problem I am chewing on without success is: 3 couples and 40 others are to be arranged randomly in a row. What is the probability that no two couples sit together ? I have looked at ...
0
votes
1answer
67 views

Trying to find Generalization of Product rule when selections are dependent

Given these sets. $A = \{1, 2, 3, 4\}$, $B = \{3, 4, 5\}$, $C = \{1, 2, 3, 4\}$ I'm trying to apply a formula for the inclusion exclusion principle in finding the number of triplets with distinct ...
0
votes
1answer
29 views

Why is the number of binary Lyndon words of length n usually divisible by 3?

Binary Lyndon words are counted by the OEIS sequence A001037. Of the first 100 of terms in this sequence, about 80% are divisible by 3. There are hints of a pattern, but I see nothing solid. The ...
1
vote
3answers
91 views

Evaluate $\frac{\partial^2}{\partial t^2} \left[ \prod_{j=1}^k (1+t+\dots+t^{d_j -1}) \right]$ at $t=1$

I need to find a "nice" formula for the evaluation of $\frac{\partial^2}{\partial t^2} \left[ \prod_{j=1}^k (1+t+\dots+t^{d_j -1}) \right]$ at t=1, where $d_j \in \mathbb{N}$. I have already proved ...
7
votes
0answers
143 views

Prove that all light bulbs can't light off

Given a table of dimensions $2010\times2012$ where every cell has one light bulb. At the beginning the number of turned on light bulbs is bigger than $2009\times2011$.If in any part of table ...
0
votes
2answers
31 views

Ways to select a hand of 9 cards from a deck of 36

This is a very basic self learning question, the scenario is there are 36 cards of 4 suits from 1 to 9 of each suit. One can pick a hand of 9 cards. My question is how many ways can someone pick a ...
2
votes
1answer
48 views

Minimum number of out-shuffles required to get back to the start in a pack of $2n$ cards?

So I'm stuck on this problem. If you perform a faro out-shuffle (i.e. a perfect "riffle shuffle" where the top and bottom cards stays in place) on a pack of 52 cards ($n=26$), you can get back the ...
1
vote
1answer
48 views

Count of matched items in multiple sets

I do apologize if this is a duplication. I did find a question that appears close to describing something of what I'm looking for, but I'm just not "seeing" the complete picture (maybe): Counting ...
2
votes
1answer
54 views

Verify combinatoric argumentation.

I tried to find all the numbers between 100 and 999, that consist of (pairwise) different ciphers. So the first would be 102 and the last would be 987. I think there are 9*9*8 such numbers, here's ...
0
votes
1answer
56 views

Number of ways by which we can form a n digit number such that no two digit are same in the number?

Example : 2 digit number : so all two digit number except 11 22 33 44 55 66 77 88 99...this is simple but how to generalize for a number of n digit?(Also at each place any digit from 0 to 9 can come ...
1
vote
1answer
35 views

A question involving the throw of seven dice, which of my answers is correct?

Seven dice are thrown, what is the probability that all numbers show up on the dice? My first answer uses the logic that if all numbers show up and you throw seven dice, then one number is repeated ...
1
vote
0answers
69 views

Counting number of perfect matching in bipartite graph. [duplicate]

Graph G is bipartite graph, I want to just count number of perfect matching. Is there any algorithm exist using combinatorial+graph theory, by which i cant count this. I tried by traversing the graph, ...
0
votes
1answer
267 views

Select elements from N sets

N sets are given which can have any number of elements from 1-100 each.Now we need to count arrangements in which we select 1 element from each set under the condition that we can not choose same ...
-1
votes
0answers
43 views

No. of Combinations Possible

I have 'n'(<=10) arrays each containing some distinct numbers (from 1 to 100). I need to pick one no. from each array such that no 2 nos. are same. I need to find the total no. of such ...
0
votes
0answers
88 views

Selecting n different numbers from m sets of numbers?

we are given M sets of numbers.Each set has numbers ranging from 1 to 100.(there can be any number of elements in a set but all elements of one set are distinct (at max 100 elements)).we need to find ...
0
votes
0answers
35 views

Real sequence satisfies a combinatoric uniform property

Does there exist a sequence of real numbers $\{a_n\}_{n\in \mathbb{Z}_{>0}}$such that, for any fixed $k\in \mathbb{Z}_{>0}$, then $a_1, \cdots, a_k$ has a bijection to ...