For 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
0answers
14 views

Counting problem - verification please?

A question we did in class asks: "In how many ways can we put 4 girls and 4 boys on a row (so order matters) so that a certain girl and a certain boy are always seated next to each other, and no 2 ...
0
votes
0answers
17 views

In how many ways can five different keys be put in a flat leather key case?

In how many ways can five different keys be put in a flat leather key case?
-3
votes
1answer
28 views

In how many ways can two chocolate chip, three raisin, and one peanut butter cookie be distributed to six children?

A mother has six cookies, two chocolate chip, three raisin, and one peanut butter. In how many distinct ways can she pass them out to six children so that each gets one? Assume that those of the ...
0
votes
0answers
10 views

Does there exists a positive $t$ that satisfy this given condition?

I am curious about the validity of my claim concerning the equations: $(2k-1)t+1$ (1) $(2k^2-2k)t+(2k-1)$ (2) where $k=2,3,4,...$ My claim is for almost all $k$ or for infinitely many $k$, there ...
1
vote
0answers
19 views

Pattern Inventory - even and odd

Say we have the following Pattern Inventory: \begin{align*} \text{Inve}(a, b, c,d) = \end{align*} \begin{align*} \frac{1}{16}\bigg(\big(a + b + c + d\big)^{8} + \big(a^2 + b^2 + c^2 + d^2\big)^4 + ...
-1
votes
1answer
14 views

Questions regarding seating arrangements

Consider there are $9$ people and $3$ tables that sits the following way ($5$ chairs, $3$ chairs and $2$ chairs). How many combinations if order matters to the people being seated and no chair can be ...
3
votes
1answer
38 views

Why this solution of the birthday problem is wrong? [duplicate]

If we have $n$ people there are $n(n-1)/2$ possible pairs that we can find. The probability that any two people have the same birthday is $1/365$. So for $n$ people the probability of finding at least ...
4
votes
3answers
52 views

In every set of $14$ integers there are two that their difference is divisible by $13$

Prove that in every set of $14$ integers there are two that their difference is divisible by $13$ The proof goes like this, there are $13$ remainders by dividing by $13$, there are $14$ numbers ...
1
vote
0answers
28 views

Simple $\{-1,0,1\}$ equation set

I'm trying to find the shortest path, getting from $x=0$ to $x=k$ in a certain problem, where I can slowly accelerate and decelerate. It comes down to finding the smallest $n$ and set of values ...
0
votes
0answers
36 views

When will the game end? [on hold]

Two men are playing a game. They have a card deck consisting of exactly 10 cards, numbered from 1 to 10, and all values are different. On each turn a fight happens. Each of them picks one card from ...
1
vote
0answers
14 views

Lines and planes-recursive formula

A family of $n$ lines is drawn in the plane such that each pair of lines cross and no $3$ dinstinct lines have a point in common Let $r(n)$ denote the number of regions into ...
1
vote
4answers
38 views

How many ways can you choose $4$ teams of $2$ from $8$ people.

How many ways can you choose $4$ teams of $2$ from $8$ people. My thoughts were that you have $8$ slots to be filled so you have $8!$ ways to arrange them but this overcounts by a factor of $2$ since ...
0
votes
1answer
58 views

Tricky question about binomial expansions. [duplicate]

State the binomial expansion of $(1+x)^n$ So I can do this $$(1+x)^n=\sum_{i=0}^{n} {n\choose i}x^i$$ Then given $n=2k$ is even. Derive an expression for $$\sum_{i=0}^{2k} (-1)^i{2k\choose i}$$ ...
2
votes
1answer
67 views

Trirectangular tetrahedron

Looking at http://mathworld.wolfram.com/TrirectangularTetrahedron.html I wonder what the symmetry group of a trirectangular tetrahedron is?
1
vote
4answers
59 views

There exist a set $X$ such that the number of function $y: x\to \{1,2,3\}$ is $1000$.

There exist a set $X$ such that the number of function $y: x\to \{1,2,3\}$ is $1000.$ My attempt: False, Let set $z = \{1,2,3\}$ then $|z|^{|x|}$ is set of function $y:x\to z.$ $|x| = n$ and $|z| = ...
1
vote
0answers
16 views

How to find a set of integer vectors (of length L) such that all its subsets with size L are linearly independent?

Given a number $M\geq L$, how to find a set of $M$ vectors in $\mathbb{Z}_{\geq0}^{L}$, say $S=\{\mathbf{a}_1,\cdots,\mathbf{a}_L\}$, such that: 1-All subsets of $S$ with size $L$ are linearly ...
1
vote
2answers
57 views

Probability in a Restaurant

In a revolving restaurant, there are four round tables each with three seats. How many different ways can $12$ people sit in this restaurant? This is what I think the answer is: $$\binom{12}{4} ...
0
votes
1answer
30 views

How to find weight function using generating series?

How to find the weight function and corresponding set given the generating series? Is there a general method for this kind of problems, I am preparing for an olympiad. Consider the below example: ...
1
vote
1answer
40 views

covering subsets

Let $A=\left\{ {1, 2, \ldots, n}\right\}$. Let $B$ be the set of all size $m$ subsets of $A$. $B=\left\{{B_1,B_2, \ldots , B_{\binom{n}{m}} } \right\}$, $ |B_i|=m$ then we want to find $k$ subsets ...
1
vote
0answers
38 views

Lights out - foobar - optimise python implementation beyond binary matrix solver

I'm looking for further details on solving 'Lights out' puzzle, as asked in foobar challenge. Sorry I don't have enough credit to add/comment on existing threads, but I'm interested in a specific ...
3
votes
4answers
40 views

6 people are holding a show, one at a time, such that person $x$ has to go after person $y$ and person $z$. How many ways could the show be held?

Let's say the people are called $a$, $b$, $c$, $x$, $y$, $z$ My initial thinking was to go by fixing "$x$" in a certain position, so: $\underline {} \underline {} \underline {}\underline ...
1
vote
1answer
15 views

How do I get number of combination for pairs of football teams?

Suppose we have 8 football teams playing each other in 4 matches. How do I find the number of combinations that is possible? E.g. Teams A,B,C,D,E,F,G,H can be in the following matches: Match 1: A vs ...
0
votes
1answer
56 views

combinatorics contest problem

Question: Calvin has a bag containing $50$ red balls, $50$ blue balls, and $30$ yellow balls. Given that after pulling out 65 balls at random (without replacement), he has pulled out $5$ more red ...
1
vote
4answers
46 views

Combinatorics: Simplify the generating function $x^0+x^2+x^4+\cdots$

This is probably going to have a simple solution, and I'm going to kick myself when I see it, but I have a bit of mental block on this topic in general that I'm trying to clear before the next year of ...
2
votes
1answer
34 views

How to find the recurrence relation from a given polynomial?

Consider the formal power series: $A(x)=\sum a_nx^n$. and $A(x)= \frac{8+14x-50x^2}{1-7x^2+6x^3}$ I am trying to derive a recurrence relation, Is there a general method for doing it? Please help, ...
2
votes
2answers
33 views

How many possible orders are there?

A tapas bar serves 15 dishes, of which 7 are vegetarian, 4 are fish and 4 are meat. A table of customers decides to order 8 dishes, possibly including repetitions. a) Calculate the number of possible ...
0
votes
0answers
17 views

What's the approximation of such a combination? [duplicate]

Given $k,m, k \leq m$. $N=\binom {m+k}{m}$ What's the approximation of N?
7
votes
0answers
52 views

In how many ways can the integers from $1$ to $n$ be divided into two groups with the same sum?

In how many ways can the integers $1,2,\ldots,n$ be divided into two groups with the same sum? I have tried calculating some of these values for small $n$, but cannot seem to find a pattern. Any ...
2
votes
0answers
22 views

Combinatorics: number of functions/predicates satisfying a sum on their entries

Given integers $n,m$, is there a closed form expression for the cardinality of the following set? $$\left\{ p : \{1,\dots,n\}^2 \rightarrow \{true,false\} \quad \Bigg| \sum_{i,j,k \in \{1,\dots,n\}} ...
0
votes
2answers
24 views

Counting problem: ways of opening stores in non-adjacent blocks?

A coffee company wants to set up stores along the main street of town, which has $n$ blocks. The company won’t open two stores in the same block, or in two adjacent blocks. Q: For this coffee shop, ...
2
votes
0answers
56 views

Combinatorial formula for the number of different words

Does there exist a closed formula for the following: Suppose we have $m$ distinct letters and we are allowed to use each letter at most $d$ times. What is the number of distinct words of length $k?$ ...
1
vote
1answer
33 views

How can I find how many unique strings there are with an equal numbers of elements, given a string length and number of elements to choose from?

The question is all in the title. Here's an example: Elements: A, B; Length: 4: AABB ABAB ABBA BABA BBAA BAAB There are 6 such unique strings for 2 elements and ...
0
votes
0answers
21 views

Maximizing the following function

I need to find values of $k_1$, $k_2$ and $k_3$ that maximize $C^{m_1}_{mm_1} \cdot C^{m_2}_{k_1-mm_1} \cdot C^{n_1}_{nn_1} \cdot C^{n_2}_{k_2-nn_1} \cdot C^{p_1}_{pp_1} \cdot C^{p_2}_{k_3-pp_1}$ ...
1
vote
1answer
21 views

The generating set of Cayley graphs over $Z_n$

Say we have a undirected and connected Cayley graph over $\mathbb{Z}_n$, with generating set $S=\{\pm x_0,\pm x_1,\ldots,\pm x_k\}$. Is it true that we can assume without the loss of generality that ...
6
votes
2answers
135 views

Proof of an identity of $n!$

I came up (numerically) with an identity concerning n! and I was wondering about a proof of it. Here it is: \begin{align} \ n! &= \sum_{r=0}^{n} { \binom{n}{r} (-1)^r(k-r)^n } \quad \forall n ...
1
vote
0answers
12 views

Number of ways to connect sets of k vertices in a perfect n-gon [duplicate]

This is a copy of my post at Mathexchange.com, as my question is still not fully answered and I really wanna find a solution to this. Feel free to refer to there for useful comments and partial ...
0
votes
4answers
45 views

How many three digit numbers with increasing digits can be formed from the set $\{1, 2, 3, 4, 5, 6, 7, 8\}$?

Suppose we pick 3 numbers $x,y,z \in \{1,2,3,4,5,6,7,8\}$ and form a 3 digit number $xyz$ how many possible combinations numbers can we create such that $x < y < z$. For example $357$ ...
0
votes
3answers
43 views

Probability of choosing two numbers so they differ by at least 2

A box has $10$ balls numbered $1,2, \dots, 10.$ A ball is picked at random and then a second ball is picked at random from the remaining nine balls. Find the probability that the numbers on the two ...
2
votes
4answers
74 views

Two dice thrown together.

Each face of a die is marked with a different number from 1 to 6. The number on the faces of the die are marked in such a way that the sum of the numbers on any pair of opposite faces is 7. Two such ...
0
votes
0answers
18 views

Number of subset problem [duplicate]

Question: A woman is preparing to go for a party .She need to colour her nails (all her nails considered 10 nails) She want to use either pink nail polish or red nail polish to colour each nails. ...
3
votes
2answers
61 views

Set and subsets link by prime numbers

I have a bit idea to solve this problem for small $n$ by programation but I think for $n>100$ I will need maths to help me. My problem is : Let S be the set of prime numbers less than n. Find ...
5
votes
1answer
60 views

How to prove the maximum possible number of elements of $S$ is $48$?

Let set $S\subseteq \{1,2,3,\cdots,100\}$,for any two different $a,b\in S$,there exist postive integer $k$ and $c,d\in S(c<d)$,($c,d$ can equal to $a$ or $b$),such $$a+b=c^k\cdot d$$ show that ...
-6
votes
2answers
53 views

Chances of this… [on hold]

9 people sat in a circle. They wrote their name on a piece of paper, folded it over and placed it in a hat. The hat was shuffled to mix up the pieces of paper. The first person picked out the name ...
1
vote
1answer
16 views

Number of solutions to equation $\sum_{i=1}^{n}x_i = R$ where $x_i>k$ where $k$ is a positive number

I know that the number of solutions to an equation of the form: $$\sum_{i=1}^{n}x_i = R$$ equals $\binom{n+R-1}{R}$. I am aware of the $x_i$ LESS THAN EQUAL TO case where, if say $x_6 \leq 3$, I ...
0
votes
2answers
48 views

In how many ways can we place $n$ indistinguishable balls in $n$ urns so that exactly one urn is empty?

How many ways can we place $n$ indistinguishable balls in $n$ urns so that exactly one urn is empty? So if I do this similar to stars and bars I am looking to put $n$ balls in actually $n-1$ urns, so ...
0
votes
1answer
35 views

Dividing $n$ identical things into $r$ groups

I was reading a course on Combinatorics where I came across following: The number of ways in which $n$ identical things can be divided into $r$ groups so that no group contains less than $m$ items ...
2
votes
3answers
38 views

Number of words which can be formed with INSTITUTION such that vowels and consonants are alternate

Question: How many words which can be formed with INSTITUTION such that vowels and consonants are alternate? My Attempt: There are total 11 letters in word INSTITUTION. The 6 consonants are ...
9
votes
4answers
243 views

Number of ways to connect sets of $k$ dots in a perfect $n$-gon

Let $Q(n,k)$ be the number of ways in which we can connect sets of $k$ vertices (dots), in a given perfect $n$-gon, such that no two lines intersect at the interior of the $n$-gon and no vertice ...
2
votes
1answer
61 views

Knight movement on chess field

I had this task in programming competition: There are two knights, which are $(p_1,q_1)$ and $(p_2, q_2)$. $(p,q)$ knight is figure, with p(q)-length first step, and q(p)-length second step in ...
5
votes
3answers
423 views

How many possible words of this type can be formed?

We are making $10$ letter words using the letters $A,C,G,T$. How many possible words are there of the form $A...AC...CG...GT...T$ This is where all of the $A's$ go before the all of the $C's$ and ...